Solving Fanorona
This site contains an introduction to the game of Fanorona
and the latest news concerning my research on this board game.
Overvieuw
History of Fanorona
Fanorona is the national game of
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 8 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 9×5 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 his1 white stone from b2 to c2. With this move also Black’s
stone 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.
Table 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 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.
Table 5.7 shows an overview of the result with optimal play on different 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 gats bigger with a side equal to 5 then the result of optimal play turns into a draw most of the times.
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 telo noho dimy 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 my Master Thesis: Solving FanoRona This thesis has been written at a time when
the game was not yet solved so it does not contain information about the
solution of the Fanorona board. But it does contain
information about the smaller board sizes.
About the author
Maarten
Schadd is a member of the Games and AI research group at the Universiteit Maastricht. 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