Search-based opening book construction

Article type: Research Article

Authors: Fishburn, John P.^{; *}

Affiliations: 5010 Gardner Drive, Alexandria, VA 22304, USA

Note: [*] Tel.: +1 908 578 1760; E-mail: [email protected].

Abstract: An algorithm is described for constructing a chess opening book, to be used in play against an opponent using another book that is given. The book under construction is represented as a Directed Acyclic Graph, with chess positions as nodes and moves as directed arcs between nodes. Each position is given an absolute position probability that a game played between the given and being-constructed book will eventually reach that position. Books for White and Black are constructed separately. Assuming a book is being constructed for White, a position priority queue repeatedly chooses the highest-probability unexpanded position for expansion. If it is Black’s turn to move, moves with move probabilities for the position are copied from the given book. If it is White’s turn to move, a search determines the best move, which is added with move probability one. More-probable positions are searched to a greater depth. Several books for White, representing a range of build CPU time, were constructed to be used in play against the book that comes with Crafty version 25.0.1, CB25.0.1. The strongest, B29, took 12 CPU-days to build. In 1000-game matches against Black/CB25.0.1 (Black using CB25.0.1 book), White/B29 scored 64 ELO points higher than did White/CB25.0.1.

Keywords: Opening book, chess, game tree search

DOI: 10.3233/ICG-180039

Journal: ICGA Journal, vol. 40, no. 1, pp. 2-14, 2018