Slashdot Mirror

← Back to Stories (view on slashdot.org)

Finally Calculated: All the Legal Positions In a 19x19 Game of Go (github.io)

Posted by timothy on from the tromp-campaign dept.

Reader John Tromp points to an explanation posted at GitHub of a computational challenge Tromp coordinated that makes a nice companion to the recent discovery of a 22 million-digit Mersenne prime. A distributed effort using pooled computers from two centers at Princeton, and more contributed from the HP Helion cloud, after "many hiccups and a few catastrophes" calculated the number of legal positions in a 19x19 game of Go. Simple as Go board layout is, the permutations allowed by the rules are anything but simple to calculate: "For running an L19 job, a beefy server with 15TB of fast scratch diskspace, 8 to 16 cores, and 192GB of RAM, is recommended. Expect a few months of running time." More: Large numbers have a way of popping up in the game of Go. Few people believe that a tiny 2x2 Go board allows for more than a few hundred games. Yet 2x2 games number not in the hundreds, nor in the thousands, nor even in the millions. They number in the hundreds of billions! 386356909593 to be precise. Things only get crazier as you go up in boardsize. A lower bound of 10^{10^48} on the number of 19x19 games, as proved in our paper, was recently improved to a googolplex. (For anyone who wants to double check his work, Tromp has posted as open source the software used.)

4 of 117 comments (clear)

  1. Is it solved then? by menkhaura · · Score: 4, Interesting

    Can we consider the traditional game of Go solved, then? And how about chess, what about calculating 32-piece EGTBs?

    --
    Stupidity is an equal opportunity striker.
    Fellow slashdotter Bill Dog
    1. Re: Is it solved then? by Anonymous Coward · · Score: 2, Interesting

      If you could envision the complete Graham's number your head would literally turn into a black hole (Numberphile).

  2. Re: 2x2 board by Teppy · · Score: 4, Interesting

    A 2x2 board has more than 3^4 possible games, not legal positions. The same legal position may occur in multiple games.

  3. Re:2x2 board by johntromp · · Score: 5, Interesting

    Author here.

    A single 2x2 game can visit as many as 48 of the 57 legal 2x2 positions, with many dozens of passes in between moves, and obviously many captures.

    This page

    http://tromp.github.io/java/go...

    on solving 2x2 go with various search methods may be helpful. I've lost track of my original 2x2 game counting code but suspect it was a close relative of this code.