BEST PLAY IN FANORONA LEADS TO DRAW
Maarten P. D. Schadd, Mark H. M. Winands, JOS W. H. M. UITERWIJK, H.J. van den Herik, MAURICE H. J. BERGSMA · New Mathematics and Natural Computation · 2008
Fanorona is the national board game of Madagascar. The game's complexity is approximately the same as that of checkers. In this article, we present a search-based approach for weakly solving this game. It is a well-chosen combination of Proof-Number search and endgame databases. Retrograde analysis is used to generate the endgame databases in which every position with 7 or fewer pieces on the board has been solved. Then, a Proof-Number search variant, PN2, exploits the databases to prove that the game-theoretical value of the initial position is a draw. Future research should develop techniques for strongly solving the game.