In previous publications on the algorithm, the intricacies of the mechanisms to select (1) the best move (the move to play), (2) the move to store in the transposition table (TT), (3) the principal variation (PV), if any, and (4) the move to ponder on (the move the opponent is expected to play) are left to the reader. This note1
An earlier version of this note was published on the World Draughts Forum (see Van Horssen, Online a). This triggered reactions by Ed Gilbert (Kingsrow) and Gérard Taille (Damy). They independently solved the problem of move selection in in the presence of search inconsistencies, resulting in equivalent solutions (however, not published). During the work on this note I became aware of a number of insightful posts on the Computer Chess Club forum, by various contributors and scattered around many different discussion threads (see CCC, Online and CCCA, Online). The Chess Programming Wiki (Isenberg, Online) served as a welcome entry point. The most important post, concerning the (semi-)PV and thus the best move, is referenced explicitly (see Letouzey, Online b). In addition, a number of implementations found on the GitHub repository were also studied. Regarding the behavior when search inconsistencies are present, we may state that some implementations are safe (although all different) and some are unsafe, that is, capable of blundering.
fills a theoretic void on these four topics, showing that in the presence of search inconsistencies there is a safe mechanism to select the best move. Selecting a ponder move is also investigated. Experimental results in 10 × 10 draughts are summarized and provided online.
Get full access to this article
View all access options for this article.
References
1.
Breuker, D., Uiterwijk, J.W.H.M. & Van Den Herik, H.J. (1997). Information in transposition tables. Advances in Computer Chess, 8, 199–211.
2.
Hyatt, R.M. (2014). A solution to short PVS caused by exact hash matches. ICGA Journal, 37(3), 178–181. doi:10.3233/ICG-2014-37307.
3.
Marsland, T.A. (1986). A review of game-tree pruning. ICCA journal, 9(1), 3–19.
4.
Plaat, A. (1996) Research re: Search & re-search (Doctoral dissertation, Thesis Publishers).
5.
Plaat, A., Schaeffer, J., Pijls, W. & De Bruin, A. (1994). A new paradigm for minimax search. Technical Report TR-CS-94-18, Department of Computing Science, University of Alberta, Edmonton, AB, Canada. 1994.
6.
Schaeffer, J. & Plaat, A. (1996). New advances in alpha-beta searching. In Proceedings of the 1996 ACM 24th Annual Conference on Computer Science (pp. 124–130). ACM.
7.
Stock, E. & King, D.J. (2010). A new enhancement to MTD(f). In 15th International Computer Games Conference, 28–31 July, 2010. Kentucky, USA.
8.
Ahle, T. (Online). Sunfish: A Python Chess Engine in 111 lines of code. https://github.com/thomasahle/sunfish.
