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?

 

Goplayicon

 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. 

 goicon

More Information

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 

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

 

Banner


Firefox 1.0 Released 20 Years Ago
10/11/2024

A news item with the headline "Firefox browser takes on Microsoft" from 20 years ago has attracted renewed attention. It was originally published on the BBC News website on November 9th, 2004 rec [ ... ]



Ursina - A Game Engine Powered by Python
08/11/2024

Ursina is a new open source game engine in which you can code any type of game in Python, be it 2-D, 3-D, an application, a visualization, you name it.


More News

 

espbook

 

Comments




or email your comment to: comments@i-programmer.info

 

Last Updated ( Wednesday, 03 February 2016 )