PRE-SEARCHING

Abstract

This paper introduces the idea of pre-searching a position – searching it before αβ determines that it needs to be searched. Consider the case where an iteration of αβ search comes across a position p that needs to be searched to depth d1, and the transposition table reveals that p will likely need to be searched later in that iteration to depth d2 greater than d1. Pre-searching involves speculatively searching p to depth d2, even though it has not been demonstrated that search to this depth is needed. If the gamble is successful, then additional accuracy is introduced to the search (using a result with extra search depth d2 – d1). While any search extension scheme is not without some risk, empirical results indicate that the impact on the αβ search-tree size is small, but the additional accuracy that is introduced improves program performance.