Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

References

Buro, M. (1999). Toward opening book learning. ICCA Journal, 22(2), 98–102. doi:10.3233/icg-1999-22204.

Campbell, M. (1999). Knowledge discovery in Deep Blue. CACM, 42(11), 65–67. doi:10.1145/319382.319396.

Chen, J.C., Wu, I.C., Tseng, W.J., Lin, B.H. & Chang, C.H. (2015). Job-level alpha-beta search. IEEE Transactions on Computational Intelligence and AI in Games, 7(1), 28–38. doi:10.1109/TCIAIG.2014.2316314.

Fishburn, J.P. (2017). Match29.pgn. Available at: drive.google.com/open?id=0B2pvWWlf39g-SkVIX1RsTEdSWDQ.

Hyatt, R.M. (1999). Book learning – A methodology to tune an opening book automatically. ICCA Journal, 22(1), 3–12. doi:10.3233/icg-1999-22102.

Lincke, T.R. (2001). Strategies for the automatic construction of opening books. In

Marsland and

Frank (Eds.), Computers and Games. LNCS: Vol. 2063 (pp. 74–86). Springer.

Lincke, T.R. (2002). Exploring the computational limits of large exhaustive search problems. Doctoral dissertation, Swiss Federal Institute of Technology, Zurich.

Linscott, G. (2017). ELO ratings. Available at: http://forwardcoding.com/projects/ajaxchess/rating.html.

ChessBase (2017). Live database. ChessBase. Available at: http://database.chessbase.com/.

10.

CPW (2017). Opening book. Chess Programming Wiki. Available at: http://chessprogramming.wikispaces.com/Opening+Book.

11.

Wu, I.C., Lin, H.H., Sun, D.J., Kao, K.Y., Lin, P.H., Chan, Y.C. & Chen, P.T. (2013). Job-level proof number search. IEEE Transactions on Computational Intelligence and AI in Games, 5(1), 44–56. doi:10.1109/TCIAIG.2012.2224659.

Search-based opening book construction

Abstract

Keywords

Get full access to this article

References