Finally Calculated: All the Legal Positions In a 19x19 Game of Go (github.io) 117
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.)
Is it solved then? (Score:5, Interesting)
Can we consider the traditional game of Go solved, then? And how about chess, what about calculating 32-piece EGTBs?
Re:Is it solved then? (Score:4, Informative)
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.
Re:Is it solved then? (Score:5, Insightful)
Re: (Score:3)
Re:Is it solved then? (Score:4, Informative)
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...
Re: (Score:2, Insightful)
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.
Re: (Score:1)
TFS makes it sound like they didn't even do that much - they merely calculated how MANY there are, which to be clear, is an impressive accomplishment, but there's no amount of storage in the world that can actually hold them all.
Re:Is it solved then? (Score:5, Informative)
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.
This sounds like a job for Siri (Score:5, Funny)
https://youtu.be/umDCQNTkSCk [youtu.be]
you made Matt Ahrens cry (Score:1)
wow. 10^48 huh?
that finally filled up my zpool.
what am I going to do with the other 999 quattuordecillion 999 tredecillion 999 duodecillion 659 undecillion 717 decillion 633 nonillion 79 octillion 61 septillion 536 sextillion 536 quintillion 625 quadrillion 392 trillion 568 billion 231 million 788 thousand and 544 bits now?
thanks alot, Tromp.
you big jerk.
Re: Is it solved then? (Score:2, Interesting)
If you could envision the complete Graham's number your head would literally turn into a black hole (Numberphile).
Re: (Score:2)
Think before you type... 10^1=10 has TWO digits, and ONE zero _after_ the 1. 10^2 =100 has THREE digits, and TWO zeros _after_ the 1. So 10^48 has 49 digits, and in base 10 has a 1 followed by 48 digits. But yes, so big we don't have a sensible 'giga' or 'mega' adjective even for the base10 logarithm...
Re: (Score:2)
Now we can quantify how much worse a "Go board error" is than a fencepost error. Quite a lot worse.
I like the idea of writing a sparse ternary array of 361x361x361, and then having to take the 363rd power of that. TFA's suggestion that Go counting could make a decent server benchmark: * The task is well defined, easily understood, and non-artificial. * The program code is small and self-contained. * The generated data sets are huge. * The p
Re: (Score:2)
I shall break the knuckles of the next web developer I meet. Pass the encouragement on to anyone you know at Slashcode and/ or WordPress.
Re: (Score:2)
One of my major gripes about slashdot is that it doesn't allow editing of one's comments.
PLEASE LET US EDIT!
Re: (Score:2)
; 10^(10^48)
Raising to very large power
Re: (Score:2, Insightful)
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 t
Re: (Score:2)
You know i've always thought about the beauty that i the simplicity of Go which creates a complexity for formulaic solving.
But i just thought of a new level, everything you said is dead one, but when you mentioned "without handicaps".. just made me stop and realize that once you figure out how to solve the base, you will need to go back and re do everything for each handicap possibility winch is 1-9 stones, and while they are traditionally placed on star points, that isn't a requirement.
yea wow, i'ts amazi
Re: (Score:2)
One of the rules of Go is that you can't repeat an earlier board position, meaning cycles are not allowed.
Re: (Score:2)
I can't remember any particular stories, but I would suspect that people have died - disembowelled and/ or beheaded - over some of these rule disputes. Which is why the rules have be
Re: (Score:2)
The board can be in one of 81 states (well, less, cos some are illegal.) The number of paths for the initial board to all ending boards is in the hundreds of billions.
Re: (Score:2)
The board can be in (19*19)^3 states.
Re: (Score:2)
You mean 3^(19*19), a MUCH bigger number.
Re: (Score:2)
Right, my bad ;)
Re: (Score:2)
Re: (Score:2)
By adding 17 grid positions both directions.
If you want to talk about 2x2 boards, say so, the topic/subject line e.g. would be a good place to mention it.
Re: (Score:3)
Re: (Score:2)
The first player has 4 choices (all equivalent), the second player has 3, but only one of those choices leads to the deadlock you described. Actually, a case could perhaps be made that the final state is not a deadlock because it removes all of the other player's liberties; but the same case could be made that this violates the suicide rule. I'm just going to call two parallel solid blocks a deadlock rather than look up a ruling.
The other two choices leave the third player with the choice to either immedi
Re: (Score:2)
I don't know GO, but one thing I have found out is that as play progresses, pieces are removed from the board. That throws my 4! analysis out the window.
Re: (Score:2)
When you play a stone onto the final remaining liberty of a stone or group of stones, then that group is removed from the board. Then the move is ended and you have to consider whether the board position is legal.
The atom of the game is "play stone and remove any prisoners captured, then consider if the board is legal", not "play stone, consider legality, then remove prisoners".
Re: (Score:2)
Re: (Score:2)
Re:Is it solved then? (Score:5, Insightful)
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?
Re: (Score:2)
A long time ago, I read that a universe jammed with subatomic particle-sized computing components, about 10^^120 (for solid neutrons), running for the age of the universe at the speed of light, couldn't come close to playing a perfect game of chess, which has many powers fewer moves to consider.
2x2 board (Score:1)
It would help to have more explanation of why a 2x2 board has more than 3^4 possible permutations.
Re: 2x2 board (Score:5, Interesting)
Re: 2x2 board (Score:4, Informative)
Re: (Score:2)
Re: 2x2 board (Score:4, Insightful)
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... [github.io]
Without superko, the number of 2x2 games would simply be infinite...
Re: (Score:2)
Re: (Score:1)
If your move would repeat the previous board position, you must play somewhere else.
Then I highly doubt they calculated all legal positions in the game. They probably calculated all legal positions of the board, but that's a different thing.
The number of possible positions of the board is upper-bounded by 3^(19^2), with 19^2 positions that each can hold a black stone, a white stone, or no stone at all. This exact number was probably computed by this research.
But the possible positions of the game include not just the current board position, but also the set of all previous board positi
Re: 2x2 board (Score:5, Informative)
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.
Re: (Score:1)
Re: (Score:2)
That's NOT how it's used in chess.
Even though the notion of chess position might include some game state information
like side to move, castling rights, and en-passent capturability,
I've NEVER seen it include the set of all previous board states, as would be necessary
for applying the 3-fold repetition rule in the game's future.
Re: (Score:2)
While you're not wrong, this might be a good moment to reflect that Go has a recorded history considerably longer than the history of the language you're writing in. (That's if you take your English back to Beowulf. "Hwat!" ; if you're talking about Shakespeare then the difference is greater.)
The mapping of chess game concepts thought English, into Japanese (or Chinese, or Korean) and onto Go game concept
Re: (Score:2)
You capture opponents pieces and remove them from the board.
And that would explain my confusion. I was unaware that squares could ever revert to blank.
Re: (Score:2)
... which is why you count the board state in ternary.
Re: (Score:3)
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...
Re: (Score:3)
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.
Re: (Score:2)
Re: (Score:2)
Re: (Score:3)
Re: (Score:3)
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.
Re:2x2 board (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... [github.io]
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.
Re: (Score:1)
What do you mean with 2x2 go?
A square with the 4 corners as legal positions?
The game is over after a few moves ... so the number of legal positions is rather small and far from billions.
Re:2x2 board (Score:4, Informative)
2x2 is Go played on a 2x2 board.
where the 4 corners are the playable points.
A game can continue for dozens of moves.
Re: (Score:2)
It can't continue over dozen of moves.
The maximum is six moves. Depending on the move of the second party it wins after six moves or loses after two.
Re: (Score:2)
That was meant to read "loses after three".
If you count symmetries as different variations, you get of course a few more positions but not moves. You also could let the beginner make a mistake after the second had made a mistake, and instead of winning after move 3 he would then lose after move six. There is no way the game can continue in the first case beyond move three and in the other cases beyond move six.
Re: (Score:3)
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
Re: (Score:2)
You might want to learn how to play Go:-)
Re: (Score:2)
No, the summary is confusing "games" and "board states". It explicitly states positions, not games.
Re: (Score:2)
You have failed to understand Go.
Board positions flip back and forth all the time as you capture territory, and then your opponent recaptures a portion, and so on.
Think more of Othello/Reversi - although there are only 8x8 board with each square either empty, black or white, the number of positions that flip back to earlier or similar positions is high throughout the game.
Re: (Score:1)
In Othello/Reversi, since the number of pieces on the board increases after each move, positions can't repeat.
Re: (Score:2)
It is extremely rare that territory gets recaptured.
Usually there is simply no places left to place stones in a meaningful way!
Re: (Score:2)
You were aware that you can pass in a game of Go? It's not the end of the game. So the number of initial plays on a 2x2 board is 5, not 4.
Re: (Score:2)
I play go.
And you can not pass in a game of go. Unless you have weird self made up rules.
Re: (Score:2)
I stand corrected, according to the english wiki you can pass. ... to tired right now to count the logical max amount of moves if both parties can arbitrarily pass.
Strange that I never experienced that, all games I played ended when one player suggested 'let's count' and the other agreed.
So we have a few more options
Re: (Score:2)
IF the prisoner isn't handed over, and you pass but the opponent does not, then either s/he has added a stone to a dead group which remains dead - this will go into your pr
Re: (Score:2)
I probably did a bit less then 1000 games ;D ... or about to acquire that level. Meanwhile I think I dropped down to 20 or something ;D
That might explain my missing of passing. I only was about 11th kyu or something
Re: (Score:2)
It took me about 8 months simultaneously learning and running a teaching club to get to 14 kyu. Then it took another year to make 11 kyu
Error on line 12 (Score:1)
Spotted a mistake in the code on line 12... sorry, you have to start over, fellas.
Re: (Score:2)
How about Tic Tac Toe?
No...let's play Global Thermonuclear War
Re: (Score:2)
error in title (Score:1)
Re: (Score:2)
They calculated what they are, they just didn't save them.
Re: (Score:1)
Re: (Score:2)
Counting sheep is good for going to sleep,
No its not [xkcd.com]
Bad description (Score:2)
They haven't calculated all the legal positions. They've counted all the legal positions.
A 2x2 board has an infinite amount of games... (Score:2)
... But only 85 legal positions, with many being mirroring positions.
Placing two stones of the same color over the diagonal of this board leads to an absorbing state.
Any other state can be reset by either black or white to a single stone.
This is assuming the players are not playing with the rule of no repetition (but with the rule of no suicide).
For clarity, see the rulebook.
Re: (Score:2)
Where does 85 come from? There are 4 positions, each with 3 legal states (back, white, empty). I get 3^4=81. Is there some rule I'm missing that creates 4 more legal states?
Re: (Score:2)
But each player has 3 possible moves, for every position on the board : play on this point ; play on any other legal point ; pass.
Re: (Score:2)
Power Costs (Score:2)
I wonder how many megawatts such a calculation takes?
Re: (Score:3)
I don't know if backtracking is used but if it is, that's 1.21 gigawatts.
Re: (Score:2)
Actually, I should have asked megawatt-hours.
Has anyone checked (Score:4, Funny)
Has anyone checked the sky? I hope that overhead the stars aren't, without any fuss, going out.
Re: (Score:2)
Re: (Score:2)
IF God existed, he'd play 3-d Go on 19x19x19, which would be on the order of L19^5^L19^L19, I think ( this result being "L19")
Are symmetries left our because of superko? (Score:3)
Error: Go is 20 by 20, not 19 x 19 (Score:1)
Re: (Score:2)