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.)
This is a count of legal[1] positions, or how many games you can end up with.
A "solved" game would be one with efficient real-time evaluation of the next "winning moves", which is entirely a different job.
[1] That should also depend on the regional rule variation. A legal move by the Chinese rule may not be one by the Korean rule.
Do you realise how big a number 10^(10^48) actually is?
The bit in brackets has 48 digits (say 47 zeroes after a number). Then the total is actually THAT NUMBER of digits.
10^48 = 100000000000000000000000000000000000000000000000
10^(10^48) has ^^^^^^ that many decimal digits in it's expression.
For reference, Giga is 10^9. Tera is 10^12. Exa is 10^18.
And THIS number, has 10^48 DIGITS when you say how big it is. It would take more than the storage of the world to write out how big that number was.
You capture opponents pieces and remove them from the board. There's a good introduction here (the site is a great resource overall): http://senseis.xmp.net/?RulesO... In addition to playing a stone, passing is always a legal move (if both players pass the game ends). Because of this, "infinite loop" positions occur frequently and there's a rule called ko to address that. If your move would repeat the previous board position, you must play somewhere else. (Again, a good explanation is http://senseis.xmp.net/?Ko ) At any rate, for any given board state, there are a huge (but finite) number of different sequences of moves that might have led to that board state.
The notion of legal position namely "every group of connected stones of the same color having an empty point adjacent to it" is NOT dependent on any particular choice of go rules.
Only legality of moves is...
Yes, I counted the number of possible board states, which I call positions.
You propose to instead use the word position to describe the complete game state including set of previously visited board positions.
I say that's really confusing.
2x2 is Go played on a 2x2 board.
where the 4 corners are the playable points.
A game can continue for dozens of moves.