Games and AI Group

Fanorona is a board game with its roots in Madagascar. It is derived from the game “Alquerque” which might be over 3000 years old. Below we explain the rules of Fanorona. The explanation is based on the rules given in (Bell, [1980]) and in (Chauvicourt and Chauvicourt [1980]). 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. We will call Fanoron-Tsivy from now on Fanorona, because it is the best-known board size and
the main subject of this article.

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 plays first.

 

Rules of the Games

We distinguish two kinds of moves, capturing and non-capturing moves. Capturing
moves are obliged and have to be played, if possible, above non-capturing moves.
Capturing implies removing one or more pieces of the opponent. It can be done in
two different ways, either (1) by approach or (2) by withdrawal. An approach is the
movement of the capturing piece to an intersection adjacent to an opponent piece
provided that the opponent piece is situated on the continuation of the capturing
piece’s movement line. A withdrawal works analogously as an approach but the difference is that the movement is away from the opponent piece. When an opponent piece is captured, all opponent pieces in line behind that piece (as long as there is no interruption by an empty point or an own piece) are captured as well.

As in checkers it is allowed to continue capturing with the same piece as long as
possible. We call this extended capturing. Although a player is obliged to play a capturing move above a non-capturing move, the player may stop capturing after any number of opponent pieces are captured. This rule is different from the checkers rule where stopping a capturing sequence is not permitted.

There are three more rules concerning capturing pieces. (1) It is not allowed
to capture by approach and withdrawal at the same time. (2) It is not allowed to make a capturing move in the same direction as the capturing move directly before. A player is allowed to play a capturing sequence two times into the same direction if a capturing movement in another direction is done in between. The last movement direction of the capturing in the previous turn (i.e., before the last opponent move) does not influence possible capturing directions in the current turn. (3) The current capturing piece is not allowed to arrive on the same intersection twice during a capturing sequence. If no capturing move can be played, a non-capturing move is allowed. This is called a paika move and consists of moving one piece along a line to an adjacent intersection.

The player who first captures all opponent pieces wins the game. The game is a
draw if no player is able to win against the opponent. In practice this is achieved
by repetition of the same position with the same player to move (Schadd [2006]).
There does not exist any documentation stating what the outcome of the game
would be if a player is not able to move. If this occurs during a game we define that
a player who is not able to move forfeits the game. However, this situation rarely
occurs and it is unlikely that the game-theoretical value would change if another
outcome would be defined in this situation. It has still to be determined whether
such situations can be reached legally.

 

Solving the game

Solving the game has be done in two stages. The first was constructing an endgame database (Strohlein[1970). During the analysis we saw that most moves are played with few pieces on the board. Thus endgame databases proofed to be very successful for Fanorona. During this research we managed to make a 7 piece endgame database. This means that we solved all positions with 7 or less 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 less 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” (Allis [1994] ) . 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 minimally need to be evaluated in order to prove the goal of the search. The goal of the search can be 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.

References

• L. V. Allis. Searching for Solutions in Games and Artificial Intelligence. PhD thesis, Rijksuniversiteit Limburg, Maastricht, The Netherlands, 1994.
   
• R. C. Bell. Board and Table Games from Many Civilizations. Dover Publications,
  1980.
   
• J. Chauvicourt and S. Chauvicourt. Le Fanorona - Jeu National Malgache. Nouvelle Imprimerie de Arts Graphiques, 1980. In French.
   
• M. P. D. Schadd. Solving Fanorona. Master’s thesis, Universiteit Maastricht, Maastricht, The Netherlands, 2006.
   
• T. Strohlein. Untersuchungen uber kombinatorische Spiele. PhD thesis, Fakultat fur Allgemeine Wissenschaften der Technischen Hochschule Munchen, Munchen, Germany, 1970.