Slashdot Mirror
Finally Calculated: All the Legal Positions In a 19x19 Game of Go (github.io)
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.)
No- they computed what all the possible boards are. "Solving" Go would involve finding an optimal move for each of those possible boards, which is much harder.
It's like asking for the Answer to the Ultimate Question of Life, the Universe, and Everything, getting an answer of "42", then realizing you didn't actually know what the question was.
#naabhaprzrag, #sverubfr-000, #agi-fcbafberq, negvpyr[pynff*=' negvpyr-ary-'] { qvfcynl: abar !vzcbegnag; }
A solution for Go would involve creating a directed graph, with cycles allowed. The result found in this article is the number of nodes in this graph. The edges in the graph would be legal moves, moving from one legal board configuration to another.
You would have to additionally label each node in the graph with the scoring value of that position for each player, if the players agreed to end the game at that position. (The game of go does not have an explicit winning goal like "checkmate" in chess, rather the players agree that any more moves are pointless, and then count their territory.) It would probably also be a good idea to have a label for a position not being a reasonable place to end a game.
Each edge (move) would also have to be labelled with the number of captured stones.
Counting the number of legal games (with no handicap) would be counting all possible non-cyclic paths through the graph, starting from the blank board node, going to every position where it would be reasonable to end the game in. For each path, count the number of captures for each player, and add those + handicap/komi to the territory values of the position. Then you can determine who the winner is for that game.
The number of edges required in that game graph is likely many times larger than the number of nodes. I would rather not think about the number of paths.
This does not solve Go. It does make it possible to estimate how feasible solving Go is: Roughly how many universe-lifetimes will it take for your computer to calculate the next move?
The 386356909593 games do account for superko.
That is exactly the number of simple (meaning not visiting the same point twice) paths starting
from the empty node in the graph in Figure 4 on page 5 of our paper http://tromp.github.io/go/gost...
Without superko, the number of 2x2 games would simply be infinite...