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:


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. 


More Information

Related Articles

Google's AI Beats Human Professional Player At Go 

Microsoft Research takes on Go 

AI and Games Pioneer, A L Samuel 

Poker Sorted - Meet Cepheus 

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


To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, FacebookGoogle+ or Linkedin



BusyBeaver(5) Is 47,176,870

The thing about the BusyBeaver function is that it is very easy to understand, but very difficult to compute. We now know its value up to 5, which isn't much progress for more than 50 years work.

Andrew Tanenbaum Gains ACM Award

Andrew Tanenbaum has been awarded the 2023 ACM System Software Award for MINIX the operating system he created for teaching purposes and which was an important influence on Linux.

More News


kotlin book



or email your comment to:


Last Updated ( Wednesday, 03 February 2016 )