PRE-SEARCHING

Article type: Research Article

Authors: Hlynka, Markian¹ | Schaeffer, Jonathan¹

Affiliations: Edmonton, Canada

Note: [1] Department of Computing Science, University of Alberta, Edmonton, Alberta, Canada T6G 2E8. Email: (markian,jonathan}@cs.ualberta.ca

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.

DOI: 10.3233/ICG-2004-27402

Journal: ICGA Journal, vol. 27, no. 4, pp. 203-208, 2004