Authors: van Horssen, Jan-Jaap
Article Type:
Research Article
Abstract:
In previous publications on the MTD ( f ) 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 1 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 MTD ( f ) 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 MTD ( f ) 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. 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 MTD ( f ) 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 MTD ( f ) 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.
Show more
DOI: 10.3233/ICG-190096
Citation: ICGA Journal,
vol. 41, no. 1, pp. 15-23, 2019
Price: EUR 27.50
