| 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. More Informationhttp://tromp.github.io/go/legal.html Related ArticlesGoogle's AI Beats Human Professional Player At Go Microsoft Research takes on Go AI and Games Pioneer, A L Samuel 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, Facebook, Google+ or Linkedin.
Comments
or email your comment to: comments@i-programmer.info |
| Last Updated ( Wednesday, 03 February 2016 ) |
