SOLVING KALAH

Article type: Research Article

Authors: Irving, Geoffrey^{a; 1} | Donkers, Jeroen^{b; 2} | Uiterwijk, Jos^{b; 2}

Affiliations: [a] Pasadena, California | [b] Maastricht, The Netherlands

Note: [1] Student at Computer Science Dept., California Institute of Technology, Pasadena, CA 91125, USA. E-mail: irving@caltech.edu.

Note: [2] Dept. of Computer Science, Universiteit Maastricht, Maastricht, The Netherlands. E-mail:{uiterwijk,donkers}@cs.unimaas.nl.

Abstract: Using full-game databases and optimized tree-search algorithms, the game of Kalah is solved for several starting configurations up to 6 holes and 5 counters per hole. The main search algorithm used was iterative-deepening MTD(f). Major search enhancements were move ordering, transposition tables, futility pruning, enhanced transposition cut-off, and endgame databases.

DOI: 10.3233/ICG-2000-23303

Journal: ICGA Journal, vol. 23, no. 3, pp. 139-147, 2000