Estimates for the complexity of checkers and draughts on different board sizes are calculated and experimentally determined. The estimates found for international draughts are a correction of previous estimates in the literature. The estimates found for the other board sizes are first estimates, with the exception of 8 × 8 checkers, which is used as a reference. The small games of 6 × 6 checkers and 6 × 6 draughts are also weakly solved. Both games are a draw with perfect play by both sides.
Allis, L.V. (1994). Searching for Solutions in Games and Artificial Intelligence. Maastricht, The Netherlands: Rijksuniversiteit Limburg.
2.
Fraenkel, A.S., Garey, M.R., Johnson, D.S., Schaefer, T. & Yesha, Y. (1978). The complexity of checkers on an n × n board. In 19th Annual Symposium on Foundations of Computer Science (pp. 55–64). IEEE. doi:10.1109/SFCS.1978.36.
3.
Lanctot, M., Winands, M.H., Pepels, T. & Sturtevant, N.R. (2014). Monte Carlo tree search with heuristic evaluations using implicit minimax backups. Proceedings of the 2014 IEEE Conference on Computational Intelligence in Games (CIG) (pp. 1–8). IEEE.
4.
Marsland, T.A. & Campbell, M. (1982). Parallel search of strongly ordered game trees. ACM Computing Surveys (CSUR), 14(4), 533–551. doi:10.1145/356893.356895.
5.
Robson, J.M. (1984). N by N checkers is Exptime complete. SIAM Journal on Computing, 13(2), 252–267. doi:10.1137/0213018.
6.
Schaeffer, J. (1983). The history heuristic. ICGA Journal, 6(3), 16–19. doi:10.3233/ICG-1983-6305.
7.
Schaeffer, J. (2007). Game over: Black to play and draw in checkers. ICGA Journal, 30(4), 187–197. doi:10.3233/ICG-2007-30402.
8.
Schaeffer, J. & Lake, R. (1996). Solving the game of checkers. Games of No Chance, 29, 119–133.
9.
Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A. & Lillicrap, T. (2017). Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm. Arxiv preprint. Available at arXiv:1712.01815.
10.
Slate, D.J. & Atkin, L.R. (1977). Chess 4.5 – The Northwestern University Chess Program. In P.W.Frey (Ed.), Chess Skill in Man and Machine (pp. 82–118). Springer.
11.
Van Horssen, J.J. (2012). Schwarzman vs. MAXIMUS: A man-machine match in international draughts. ICGA Journal, 35(2), 106–119. doi:10.3233/ICG-2012-35209.
12.
Van Rijn, J.N. (2011). PSPACE-Hardness of Checkers and Draughts. Leiden, The Netherlands: Leiden Institute of Advanced Computer Science, Universiteit Leiden.
13.
Bik, A. (Online). Perft for 8 × 8 checkers. TalkChess.http://talkchess.com/forum3/viewtopic.php?topic_view=threads&p=680216&t=27814.
14.
Bor, K. (Online). Turbo Dambase. http://www.turbodambase.nl/tdamhome.php.
15.
Gilbert, E. (Online). Perft. World Draughts Forum. http://laatste.info/bb3/viewtopic.php?f=53&t=2308.
16.
Halbersma, R. (Online a). Perft for arbitrary board sizes. World Draughts Forum. http://laatste.info/bb3/viewtopic.php?f=53&t=2666.
17.
Halbersma, R. (Online b). Perft on large boards. World Draughts Forum. http://laatste.info/bb3/viewtopic.php?f=53&t=4563.
18.
Halbersma, R. (Online c). Search Algorithm. World Draughts Forum. http://www.laatste.info/bb3/viewtopic.php?f=53&t=4013&start=698.
19.
Van Horssen, J.J. (Online). Complexity of Checkers and Draughts on board sizes 6 × 6/8 × 8/10 × 10/12 × 12/14 × 14. World Draughts Forum. http://laatste.info/bb3/viewtopic.php?f=53&t=7817.
20.
Wikipedia (Online a). English draughts (or checkers), https://en.wikipedia.org/wiki/English_draughts.
21.
Wikipedia (Online b). International draughts, https://en.wikipedia.org/wiki/International_draughts.
22.
Wikipedia (Online c). Game complexity, https://en.wikipedia.org/wiki/Game_complexity.
