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
It would help to have more explanation of why a 2x2 board has more than 3^4 possible permutations.
Spotted a mistake in the code on line 12... sorry, you have to start over, fellas.
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.
Error in the title. They most certainly did not calculate all legal positions, only the exact *number* of legal positions. Which is a *very* different thing.
In Othello/Reversi, since the number of pieces on the board increases after each move, positions can't repeat.
They haven't calculated all the legal positions. They've counted all the legal positions.
https://youtu.be/umDCQNTkSCk
Is it just my observation, or are there way too many stupid people in the world?
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.
Counting sheep is good for going to sleep,
No its not
Have gnu, will travel.
... 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.
systemd is not an init system. It's a GNU replacement.
I wonder how many megawatts such a calculation takes?
No, the summary is confusing "games" and "board states". It explicitly states positions, not games.
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."
It is extremely rare that territory gets recaptured.
Usually there is simply no places left to place stones in a meaningful way!
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
How about Tic Tac Toe?
No...let's play Global Thermonuclear War
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?
Go is a game played on a board with 20 x 20 = 400 intersections. That's where the pieces are placed, not in the center of the 361squares. I suppose I now know why most of my software is so crappy - nobody checks their assumptions. (There were 90 comments already when I wrote this!) Even when the evidence is staring them in the face, visible in every photo of a Go game, ever. What's gonna happen next, Republicans exhibiting climate denial or something crazy like that?
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.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
It's about 30,000 possible games, IIRC.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
I play go.
And you can not pass in a game of go. Unless you have weird self made up rules.
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
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
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
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 prisoner pile at end-game ; OR the opponent has played an unnecessary stone into their own territory and lost themselves a point of empty territory ; OR there was undecided territory on the board where YOU ought to have played instead of passing!
Go is a considerably more complex game than novices (people in the first couple of thousand games of their career) generally realise.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
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
Cost free eBook I read (by iBook/Kobo/Amazon/ObookO/Gutenberg etc.): "The Green Odyssey" by Philip Jose Farmer.
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. And there I've stagnated for nearly 30 years, because I only get about 2 or 3 games a year. (I've tried playing online. I hate it.)
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"