1. Solving Cram using Combinatorial Game Theory
- Author
-
Uiterwijk, JWHM, Cazenave, Tristan, van den Herik, Jaap, Saffidine, Abdallah, Wu, I-Chen, DKE Scientific staff, and RS: FSE DACS NSO
- Subjects
050101 languages & linguistics ,Theoretical computer science ,Process (engineering) ,Computer science ,BETA (programming language) ,05 social sciences ,ComputingMilieux_PERSONALCOMPUTING ,Combinatorial game theory ,02 engineering and technology ,Solver ,Alpha (programming language) ,0202 electrical engineering, electronic engineering, information engineering ,Domain knowledge ,020201 artificial intelligence & image processing ,0501 psychology and cognitive sciences ,computer ,computer.programming_language - Abstract
In this paper we investigate the board game Cram, which isan impartial combinatorial game, using an alpha-beta solver. Since Cram is anotoriously hard game in the sense that it is difficult to obtain reliableand useful domain knowledge to use in the search process, we decided torely on knowledge obtained from Combinatorial Game Theory (CGT).The first and most effective addition to our solver is to incorporateendgame databases prefilled with CGT values (nimbers) for all positionsfitting on boards with at most 30 squares. This together with twoefficient move-ordering heuristics aiming at early splitting positions intofragments fitting in the available databases gives a large improvement ofsolving power. Next we define five more heuristics based on CGT thatcan be used to further reduce the sizes of the search trees considerably.In the final version of our program we were able to solve all odd x oddCram boards for which results were available from the literature (evenx even and odd x even boards are trivially solved). Investigating newboards led to solving two boards not solved before, namely the 3 x 21board, a first-player win, and the 5 x 11 board, a second-player win.
- Published
- 2020