[News] Number of legal 19X19 positions computed (2016)

General Go Discussion
1

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:

image

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 3^361 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:

image

Now we see a graph that shows the transitions (paths) of all legal boards, the ones we need to count:

image
image650Ă—610 31.1 KB

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:

image

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:

image

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.

Cheers,

Dr. Bèco

References:

12 Likes
2

Next step: total number of legal games!

3 Likes
3

The total number of legal games has also been explored by collaboration between Matthieu Walraet and John Tromp:

They constructively establish that there are at least 10^10^100 (a googolplex) legal games of go.

The googolplex is an absurdly large number, since it has a googol (10^100) digits. I believe the estimate for the number of atoms in the universe is around 10^80. The age of the universe in seconds is less than 10^18. Thus, it seems that there is not enough space nor time to even write down the exact number of go games, much less to precisely compute it.

Earlier draft:

6 Likes
4

(Your point still stands, I’d just like to remark that this would refer to the number of atoms in the observable universe. Always irks me when that word is omitted :slight_smile: )

5 Likes
5

Aren’t there four possible states on a go board? Empty, white stone, black stone and empty in ko?

Let’s observe following board position:

Jegyzet%202020-01-22%20101705
Jegyzet 2020-01-22 101705.jpg1138Ă—1140 136 KB

Whether C3 is a plain empty or empty in ko makes a huge difference.

  • If the marked field is plain empty, White takes and practically won the game.
  • If it’s empty in ko, she must pass and consequently lost the game.
4 Likes
6

In this case, player to play becomes part of the board state as well. And you have to add forbidden intersections in general, not only ko.

There are 3 possible colourations for each point on the board in tromp-taylor rules.

In most (all) rules, Kos are forbidden by forbidding repetitions, not by adding a marker to the board. I’m not aware of rules adding KO as 4th board colouring.

AGA, Chinese and Japanese rules are talking about (whole-)board position when discussing superko, but neither defines what a board position is. (I lost the interest to look the other rules up Rules of Go at Sensei's Library)

My interpretation of the rules is, if ko-forbidden is part of a board position, superko rules allow for an extra round of repetition, since the board position with ko-forbidden is not the same as the position without ko-forbidden (creating a paradox on the way).

So no, KO isn’t a possible state for a intersection.

Here the relevant parts of tromp-taylor rules:

  1. Go is played on a 19x19 square grid of points, by two players called Black and White.
    Each point on the grid may be colored black, white or empty.
  1. A turn is either a pass; or a move that doesn’t repeat an earlier grid coloring.
4 Likes
7

In short, no, “empty in ko” is not a fourth state for a point on the board.

Ko rules depend on more than just the current board state, which makes it neither necessary nor sufficient to think of “empty in ko” as a meaningful state for a point on the board.

Using a fourth state is not necessary, since all of the various ko rules (like all of the different flavors of superko rules) can be simply stated without defining this fourth state. Indeed, I think it is easier to state various types of ko rules without introducing a fourth state. As @flovo pointed out, adding an “empty in ko” state would require needless rewording the superko rules in order to avoid confusion/paradox.

Adding a fourth state is also not sufficient, since various forms of the superko rules depend not only on the current board position, but also the entire past history of board positions (since very long cycles are possible), whose turn it was before each position (if using situational superko), and whether the player passed or played a stone (for natural situational superko).

4 Likes
8

Thanks; I think I got it. I was under the impression that a board position is something that somehow also determines what continuations are possible. Clearly, I was mistaken. I learned something again :slight_smile:

3 Likes