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.
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.
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.
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.