Fanorona is a board game with its roots in Madagascar. It is derived from the game “Alquerque”, which might be over 3000 years old. The goal of the game is to capture all opponent pieces. The game is a draw if neither player succeeds.

Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimyand, and Fanoron-Tsivy. The difference between these versions is the board size. Fanoron-Telo is played on a 3×3 board and the difficulty of this game can be compared to the game of Tic-Tac-Toe. Fanoron-Dimyand is played on a 5×5 board and Fanoron-Tsivy is played on a 5×9 board. Fanoron-Tsivy is usually called Fanorona, because it is the best-known board size. The Fanorona board consists of lines and intersections. A line represents the path along which a piece can move during the game. There are weak and strong intersections.

On a weak intersection it is only possible to move a piece horizontally and vertically, while on a strong intersection it is also possible to move a piece diagonally. A piece can only move from one intersection to an adjacent intersection. In the initial position each player has 22 pieces. Players move alternately; White move first.

Solving the game

Solving the game was done in two stages. The first stage was constructing an endgame database. When analysizing the game we saw that most moves are played with few pieces on the board. Thus endgame databases proved to be quite successful for Fanorona. During the research we managed to make a 7 piece endgame database. This means that we solved all positions with 7 or fewer pieces on the board and stored that information in a file. It turned out that there exist a total of 6,261,651,660 different positions with 7 or fewer pieces on the board and the database used 3.6 GB of hard disk space. The construction of the 4vs3 database alone took more then three weeks. In total more then 2 months were used to compute all endgame databases.

The second step was to implement a search technique called “Proof-number search”. This technique stores the search tree in memory and chooses the most promising node for evaluation. Thus PN search (Proof-number search) is a best first search. PN search uses for each node a proof number and a disproof number to indicate how many nodes at least have to be evaluated in order to prove the goal of the search. The goal of the search can be to prove that “White wins the game when playing optimally”.

The combination of the endgame database and the customized PN form the core of the program KINGRALOMBO. This program was able to solve the start position of Fanorona in more than a week of computing time. It turns out that the Fanorona is a draw. 130,820,097,938 nodes were created during the search to prove that Fanorona is a draw. This means that if both players are playing optimally a draw is the result of the game. So far the moves d3-e3A and f2-e3A have been proven to be optimal to achieve the draw in the initial position.

Key Publication

  • Schadd, M.P.D., Winands, M.H.M., Uiterwijk, J.W.H.M., Herik, H.J. van den, and Bergsma M.H.J. (2008). Best Play in Fanorona Leads to Draw. New Mathematics and Natural Computation, Vol. 4, No. 3, pp. 369-387.