Number Of Legal Go Positions Finally Worked Out

### New Book Reviews!

 Number Of Legal Go Positions Finally Worked Out
Written by Mike James
Wednesday, 03 February 2016

Go is an important game for AI in that, until very recently, humans were much better at it than computers. It is a complex and subtle game that has only just yielded one of the most fundamental parameters of any game - how many legal positions are there.

Only last week we reported the news that Google's DeepMind has a program that plays really well, well enough to beat a professional player of the game. At the same time we have another breakthrough - an answer to the question, How many Go moves are there?

Picture Credit: Goban1

A Go board is 19x19 and you can place a black or white stone on any location, thus each location can be in one of three states - empty, black or white. This means that if all combinations were legal positions the game would have 3361 possible states. Stones may be placed anywhere on the board but to be legal every group of stones of the same color has to have at least one empty position adjacent to one of its stones. If this condition is not met then the group is captured by the other player and the stones are removed from the board. Hence the only positions that can occur in Go are exactly the legal positions.

So how many legal positions are there?

An approximation to this number, called L19, has been known since 2006.

L19 is approximately 2.081681994 * 10170

After another ten years of work by John Tromp, we finally have:

```2081681993819799846
9947863334486277028
6522453884530548425
6394568209274196127
3801537852564845169
8519643907259916015
6281285460898883144
2712971531931755773
6620397247064840935```

How was it done?

It turns out that the problem reduces to the task of raising a sparse matrix with 363 billion rows and columns to the 361 power. Yes, that was a 363 billion row square matrix.

This formulation was known in the early 2000s but the computing power has only just been available. After Tromp worked out the number of legal moves for the 18-position board you might have thought that he would get lots of offers of help, but only HP with its Helion Cloud offered to provide computational resources. The computation started on March 6, 2015 and ran till December 26, 2015 and after some post-processing the number was announced on January 20, 2016. An estimated 30 petabytes of disk I/O was generated.

If you like the idea of checking the computation by running the program again you will need something like a server with 15TB of fast scratch diskspace, 8 to 16 cores, and 192GB of RAM and expect to wait a few months.

Now we have the number of legal moves on all Go board sizes from one to 19. What next?

Although AI has found Go harder than chess to play, we still don't know the number of possible games of chess - we don't even know the order of magnitude.

http://tromp.github.io/go/legal.html

#### Related Articles

Google's AI Beats Human Professional Player At Go

Microsoft Research takes on Go

AI and Games Pioneer, A L Samuel

Deep Learning Chess

Komodo Is Computer Chess Champion Again

Marry Or Move On - There's An Algorithm For That

17x17x17 Rubik Cube Solved In 7.5 Hours

 Java 10 Improves Garbage Collection19/04/2018Java 10 has improved its garbage collection and compilation, and has also extended the Class-Data Sharing feature to improve startup and footprint. Java 10 is a feature release of Java SE. + Full Story JDK 10 Released22/03/2018The latest version of Java, JDK 10, has been released, just six months after Java 9 hit the shelves. This version adds local variable type inference among other improvements. + Full Story More News