Finally (since 2016), we know exactly the number of legal positions in a Go board 19x19
And here a well deserved update to our forum, about this last post:
The same researcher, John Tromp, finally concluded the computation in 2016:
On Jan 20, 2016, the number of legal positions on a standard size Go board was determined to be:
L19 = 208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935
This number is approximate
~ 2.08 * 10^170, and that is huge!
How did they do it?
It is quite interesting to know how they tackled the problem. Even if you don’t know computer programming, the logic can be appreciated if put in simple words.
The first attempt, that worked well for boards less than 5x5, was the so called “brute force”. Imagine you start with an empty board and fill in with black and white pieces until you run out of intersections. Then you substitute the last stone from, say, Black to White or to Empty (the 3 possible states an intersection can be), then you come back 2 moves, and do it again, and again; then you retract 3 moves and do it again, again and again… And you keep counting… This is the brute force. You put all the permutations in the board, in an organized way so you don’t lose track of what you already counted, and that is it.
Not good enough to count even a 5x5 board with the computer power from 2006. At that time, the paper published by Tromp showed this table:
Being the first boards of the table (from 2 to 4) computed by brute force. Then dynamic programming enters the scene.
The idea behind the new algorithm that allowed the computation of all the successive boards from 5x5 to 19x19 is simple: think counting “per elimination”.
It is easy to understand that if a position can only be in three states (empty, black stone or white stone), then the total number of permutations (legal and illegal) is simple
3^(19 * 19) or
1.7 * 10^172
Now what they did was use a deconstruction algorithm similar to the Sieve approach to calculate large prime numbers, adapted it, and in the end, instead of trying to calculate the number now called
L19, they only needed to calculate the 361st power of a sparse matrix of a 363 billions rows and columns.
It is a sparse matrix because because it represents a graph where you don’t want the illegal positions, only the legal ones organized by “paths”. So instead of counting positions, you will count the number of paths to move from one position to another.
In his paper from 31/Jan/2016 he explains the process using a 2x2 board. Look how cool is it.
First we see all illegal positions on a 2x2 board:
Now we see a graph that shows the transitions (paths) of all legal boards, the ones we need to count:
Just follow the arrows and see how you can move from one position to another.
Isn’t that amazing? The total number is just
81-24=57 legal positions. Remember we are talking here about static positions, not dynamic positions. That is: we don’t really care who has the turn to play. Look this small part of the graph:
If we would consider who has the turn, then it would be 8 possibilities instead of this 4.
Also, pay attention on this arrow in red:
In this position, a black stone is added and this causes the whole group of 4 black stones to die, leading then to the empty-board position, as pointed by the red arrow.
They used a special rule to help creating the positions, “the suicide rule”. That is, after adding a stone of any color, proceed with:
- remove all groups of the opposite color without liberties (capture)
- remove all groups of the same color that ended up without liberties (suicide)
This generalization was shown in the article that it didn’t change the number of positions being counted, and helped to speed up the creation of all the paths.
How long did it take?
It used a Chinese technique to split the computation into 9 simultaneous part, each one contributing 64 bits to the final big number that needs 566 bits to store.
The 9 jobs started at 06/March/2015 and the last job ended at 26/Dec/2015, running in 3 different servers (two in Princeton, at the Natural Science Dept. and the Communication Center Dept., and one offered by HP Helion Cloud).
So, 9 months and 20 days in total, of pure computer power. But, as explained by Tromp, it took 10 years of research and computer evolution (hardware and software evolution).
The result was saved in 30 PetaBytes of disk (kilo, mega, tera, peta…, powers of 1024).
Amazing, isn’t it?
That is it for today! I hope you enjoyed this “news”, although this is from 2016.
- Tromp & Farneback. Combinatorics of Go. 2016.
- Computers and Games: 5th International Conference, CG 2006, Turin, Italy
- Computers and Games: 9th International Conference, CG 2016, Leiden, The Netherlands
- Number of legal Go positions, by Tromp at Github
- John Tromp Home Page
- Go Rules by Tromp
- SlashDot news