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.)
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
A 2x2 board has more than 3^4 possible games, not legal positions. The same legal position may occur in multiple games.
That number probably refers to legal games (=sequences of moves). The result on the 19x19 board enumerates the legal positions, instead. Confusing abstract.
My first program:
Hell Segmentation fault
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 summary is crap from beginning to end. It confuses counting positions with enumerating them. It confuses the number of possible games with the number of possible positions. All in all, a typical timothy post.
https://youtu.be/umDCQNTkSCk
Is it just my observation, or are there way too many stupid people in the world?
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.
I don't know if backtracking is used but if it is, that's 1.21 gigawatts.
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...
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.
Has anyone checked the sky? I hope that overhead the stars aren't, without any fuss, going out.
Confucius say, "Find worm in apple - bad. Find half a worm - worse."
That's a pointless measurement, though. A game of checkers has infinite possible games because you can repeat positions. For a player, or an AI trying to win a game, all that matters is the current game state and the possible game states, not how you arrived to that state.
2x2 is Go played on a 2x2 board.
where the 4 corners are the playable points.
A game can continue for dozens of moves.
And the number of legal chess positions is in between the number of legal 9x9 Go positions and the number of legal 10x10 Go positions...
Looking into the paper, we see that with L(2,2)=81-16-8=57 various positions that are symmetric transforms of each other are considered distinct. For example, on sees this in the upper right and lower left corners of Figure 1. Now, it's true that superko will break some of that symmetry, but not all of it. How much complexity disappears with more accounting for symmetry?
This 8 move game disproves your claim:
. .
. .
A2
X .
. .
B1
X .
. O
A1
X .
X O
B2
. O
. O
A1
. O
X O
A2
O O
. O
A1
. .
X .
B2
. O
X .
A2
X O
X .
pass
pass
Btw, we're counting all games, not just games without mistakes.