Complexity of checkers and draughts on different board sizes

Article type: Research Article

Authors: van Horssen, Jan-Jaap^{; *; **}

Affiliations: Prinses Marijkelaan 127, 3708 DB Zeist, The Netherlands

Correspondence: [**] Corresponding author. E-mail: janjaapvanhorssen@gmail.com.

Note: [*] E-mail: janjaapvanhorssen@gmail.com.

Abstract: 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.

Keywords: Complexity class, state-space complexity, game-tree complexity, checkers, draughts, international, Brazilian, Canadian, South-African, Dumm, 6 × 6, weakly solved

DOI: 10.3233/ICG-190077

Journal: ICGA Journal, vol. 40, no. 4, pp. 341-352, 2018