Fanorona
Topic Editor: Maarten Schadd
Contributions are welcome and the ICGA will, with permission, list contributor's
History of Fanorona
Fanorona is the national game of Madagascar and was derived from the game Alquerque which might be over 3000 years old. Fanorona has three standard versions: Fanoron-Telo, Fanoron-Dimyand, and Fanoron-Tsivy. The difference between these variants is the size of board played on. 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 since the Fanoron-Tsivy variant is the widest-known variant.
There exist some legendary stories about Fanorona and one of them involves a King called Ralombo. Due to this story the program used for solving Fanorona was called “KING RALOMBO“. King Ralomba became sick and decided that it was time for one of his sons to inherit his kingdom. The king did not want to split up his kingdom so he decided that the first son which arrived at the castle was the most devoted one and therefore should become the next king. So the king sent out messengers calling for his sons. The elder son was playing Fanorona by the time the messenger arrived. He did arrive at a very difficult situation called telo noho dimy which is a 3 pieces against 5 pieces situation. He was so concentrated on how he could win this situation that he did send the messenger away so that he could concentrate on the game. By the time he arrived at the castle of the King the younger son had inherited the throne.
Rules of Fanorona
Board
FanoRona is played on a 5×9 board and it is played along the lines and on its intersections just as Go. A line represents the way along which a stone can move during the game. There are strong and weak points (intersections). On a weak point it is only possible to move a stone horizontally and vertically, while on a strong point it also is possible to move stones diagonally. A stone can only move from one point to another at a time. Each player has 22 stones at the start position as shown in Figure 2.1. The player to start is White, as may be expected from a western game.
Figure 2.1: The start position of a Fanorona game.
Capturing
Players are allowed to play a move alternatively. Even if a move consists of multiple movements of one single stone we will still denote it as a single move. Capturing stones of the opponent can be done in two different ways, either by approach or by withdrawal. An approach is the movement of the capturing stone to an adjacent point of an opponent stone if the opponent’s stone is placed on the extension of the movement line of the capturing stone. A withdrawal is the movement away from the opponent’s stone if the capturing stone is placed on an adjacent point of the opponent’s stone and if the opponent’s stone is placed on the extension of the movement line of the capturing stone. When an opponent’s stone is captured by approach or by withdrawal, all opponent stones in line behind that stone (as long as there is no interruption by an empty point or an own stone) are captured too.
Figure 2.2 shows how the capturing mechanism works. In the situation shown in Figure 2.2 White can capture Black’s stone on d2 by moving his white stone from b2 to c2. With this move also Black’s on e2 will be captured. g2 will not be captured since there is no black stone on f2. This was a capturing by approach since White moved his stone towards Black’s stone on d2. White can also capture by withdrawal if he moves his white stone from f4 to e4 since he is moving away from Black’s stone on g4. i4 will not be captured since there is a white stone disrupting the line at h4.
White cannot capture c4 with f4 since for a capturing move the own stone has to be next to the one captured after this move and f4 is too far away to capture c4. In order to allow a capturing the capturing stone has to be moved to an adjacent point next to the captured stone if it is approached. If a capturing is done by withdrawal then the capturing stone has to start at an adjacent point next to the captured stone and move away from it.
>Figure 2.2: An example position during a Fanorona game
White also cannot capture c4 with b2 since c4 is not on the extension of a movement line from b2. Only stones can be captured which are located in the extension of the movement line of the capturing stone. Thus capturing “around a corner” is not allowed.
For describing a move we will define the following notation: a1-b2A means that the stone on a1 will move to b2 and approaches (A) the stone on c3. For a withdrawal the letter “W” is used. If a stone is moved without capturing opponent stones then no letter “A” or “W” will be used. Like Checkers it is allowed to keep capturing with the same stone as long as possible. Figure 2.2 shows that White can capture c4 with the move: b2-c2A-c3A. A player must choose a capturing move above a non-capturing move but a player is free to stop with capturing after any number of opponent stones are captured. In Figure 2.2 White is allowed to stop early and only play b2-c2A. A move where no stones are captured is called a paika move. Thus White is not allowed to play the paika move b2-b1 here since capturing is possible.
There are three more rules concerning capturing stones. The first is that it is not allowed to capture by approach and withdrawal at the same time. This is the case at the start position shown in Figure 2.1 where White could play d3-e3 as an approach or a withdrawal. In such a situation the player has to choose if the current move is an approach or a withdrawal. The second rule is that it is not allowed to make a capturing move in the same direction as the capturing move directly before. We illustrate this rule by referring to Figure 2.2. White is not allowed to play: f4-e4W-d4A since his stone would move two times in a row in the same direction. A player is allowed to play a capturing sequence with two times the same direction if a capturing with another direction is done in between them.
The last movement direction of the capturing in the turn before (i.e., before the previous opponent move) does not influence allowed capturing directions in the current turn. The last rule is that the current capturing stone is not allowed to arrive at the same point twice during a capturing sequence. If in Figure 2.2 a black stone would be on g5 then White is not allowed to play f4-e4W-e3A-f4A because of this rule.
End of the game
The player who first captures all opponent stones wins the game. There exist draw situations in FanoRona and both players can call it a draw if both do not see an opportunity to win. Such a draw situation is
detectable in Figure 2.3 with White to move. White cannot move his stone in the middle or he will lose the game. The tactic for the black player is to stay always on the other side of White’s moving stone in
order to achieve a draw.
Figure 2.3: This position is a draw with White to move.
To illustrate why the position in Figure 2.3 is a draw we can analyse all possible moves for White excluding symmetry.
1. b2-a3 - Black answers with b3-b2A-c1W and White loses the game.
2. b2-a2 - Black answers with b3-b2A-c2W and White loses the game.
3. b2-a1 - Black answers with b3-b2A-c3W and White loses the game.
4. b1-a1 - The answer of Black could be
b3-a3 - White wins the game by playing a1-a2A.
b3-c3 - White has four moves because of symmetry.
b2-a2 - Black wins by playing c3-b2A-c2W.
b2-a3 - Black wins by playing c3-b2A-c1W.
b2-b3 - Black wins by playing c3-b2A-b1W.
a1-b1 - Now Black has only two moves.
c3-c2 - White wins by playing b2-a2W.
c3-b3 - With this move the game arrived at the same position again which
means that this will be repeated forever and this game is a draw.
So the draw strategy for Black is to circle around the middle and always stay on the exact opposite side of the White’s outer stone. The tradition of FanoRona allows the losing player to play a “VELO” game with different rules to regain his honor. These rules do not allow the player who won the first game to capture enemy stones until the winner only has 5 stones left in the Velo game. If he now still can win against the loser of the first game then the loser did also lose his honor. We will not focus on this Velo game.
Research on Fanorona
This section contains information about my research on Fanorona.
Analysis of the game
In order to compare the complexity of Fanorona with other board games the game-tree complexity and the state-space complexity of Fanorona were computed. The state-space complexity is an indication of how many different positions are possible. The game-tree complexity is an indication on how large the game tree of the game is. Using a lot of randomly played games these numbers are computed. Table 3.1 shows the estimated state-space and game-tree complexities compared to other board games.
3.1: State-space and game-tree complexity of games.
Although this numbers seem to be discouraging, Fanorona is not as hard as it seems. The main reason for that are the unique properties of the game. Due to the fact that capturing moves are obligated, most moves at the start of the game will be capturing moves which usually capture multiple stones at once. Thus an endgame state is achieved fast. Figure 3.3 shows the average branching factor as a function of the number of pieces on the board. There are two maxima visible. The maximum to the right indicates situations where the board has opened up after the first couple of moves are played. At around 34 pieces on the board there are the most possibilities for capturing. The second maxima to the left indicates situations in the endgame where the branching factor increases again because paika moves are played. The minimum at 15 pieces on the board indicates that state of the game where the last capturing moves before the endgame are played. In those situation players only have very little possible capturing moves where they can choose from.
Figure 3.3: The average branching factor as function of the number of pieces on the board.
Although it might seem that the maximum to the right contributes the most to the complexity, it actually is the maximum to the left which gives Fanorona the high game-tree complexity. During the start of the game capturing moves are played almost exclusively. This means that the maximum to the right is traversed very fast. At the maximum to the left however, mostly paika moves are played. Thus multiple moves are needed to traverse one step to the left in this graph.
Solving the game
In order to solve the game of Fanorona multiple methods have been tested on their usefulness. More information on that can be found in my Master Thesis. Solving the game has be done in two stages. The first was constructing an endgame database. 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”. 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”. In my Master Thesis I describe a variation on this search which uses greedy PN numbers. This counts the pieces on the board and creates proof- and disproof number based on the number of pieces for each player. The result of this is a smaller search tree if the goal, that White can win the game is true.
Other methods tested proofed to be less useful.
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 a couple of hours computing time. It turns out that the Fanorona is a draw. This means that if both players are playing optimally a draw is the result of the game. Apparently there are a lot of draws in the game tree. This claim still has to be confirmed but there are multiple reasons for this claim. First of all, it does not matter which of the five starting moves white plays. They all end in a draw with optimal play from both players. Furthermore a lot of draws have been found during the creation of the endgame databases. There still exist a large amount of 4vs3 situations which are a draw without capturing any stones. Such a draw situation on the 3x3 board has been shown during the introduction of Fanorona.
Table 5.7 shows an overview of the result with optimal play on smaller board sizes. What is very interesting in this Figure is that we see that White can win the game on a board which either has horizontal or vertical size equal to 3. But as soon the board gets bigger with both sides at least 5 then White looses his advantage in the majority of cases.
Table 5.7: Overview on the results with optimal play.
Further research
I will investigate optimal played games to investigate how the draws are achieved. Furthermore it might be possible to solve all possible telon oho situations. Also I plan to make a program capable of playing Fanorona very well. This program should be able to show the interested reader how to play the game and also compete with the human masters of this game. It can of course not play optimally from the start since it should play within a reasonable amount of thinking time (1 minute).
More information
For more information on the game and applied methods I refer to:
M. P. D. Schadd, M. H. M. Winands, J. W. H. M. Uiterwijk, H.J. van den Herik, and M. H. J. Bergsma.
Best Play in Fanorona leads to Draw. New Mathematics and Natural Computation 4 (3): 369-387, 2008.
About the author
Maarten Schadd is a member of the Games
and AI research group at Maastricht University.
This group has a reputation in solving board games. In the past the following
games were solved: Four-in-a-row, Qubic, Go-Moku, Domineering, Kalah, 5x5 Go,
and 6x6 Atari Go.
Links
David Eppsteins Fanorona applet