Slashdot Mirror
Number of Legal 18x18 Go Positions Computed; 19x19 On the Horizon
johntromp writes It took about 50,000 CPU hours and 4PB of disk IO, but now we know the exact number of legal 18x18 Go positions. Seeking computing power for the ultimate 19x19 count. And it's not a heat-death-of-the-universe kind of question, either, they say: "Thanks to the Chinese Remainder Theorem, the work of computing L(19,19) can be split up into 9 jobs that each compute 64 bits of the 566-bit result. Allowing for some redundancy, we need from 10 to 13 servers, each with at least 8 cores, 512GB RAM, and ample disk space (10-15TB), running for about 5-9 months."
How many cryptocoins could be mined for that amount of computing power?
However, I think I'd like to learn to play this game. I played chess at an amateur level and did rather well at it during and even after college. I don't know if any of the skills transfer but I've been told that the mentality transfers. Being able to look a half dozen or more moves ahead and being able to picture all the moves my opponent can make are, as I have been told, something that does transfer.
"So long and thanks for all the fish."
we need from 10 to 13 servers, each with at least 8 cores, 512GB RAM, and ample disk space (10-15TB), running for about 5-9 months
sounds pretty slow to me
Being able to have 'rainbow table' level cheating at go? What's the application here?
I also took chess quite seriously for a few years, reaching approximately 1800. The pervasiveness of rote openings discouraged me a bit, but I always loved the game and still do. However, I abandoned it for Go, where I hold a shameful but enjoyable rating of 6-7kyu. I have never found any aspect of Go, other than scarcity of oponents , worth complaining about. It is, perhaps, the world's only perfect game. Just remember to lose your first 50 games as quickly as possible. Afterwards, expect a lifelong companion.
Here is the number of legal positions:
6697231142888292128927 401888417065435099377 8064017873281031833769694562442854721810521 43260127743713971848488909701 11836283470468812827907149926502 347633
Why they chose to present it like that, instead of scientific notation, I'll never know but there it is. It's so long Slash-filter won't let me post it without adding spaces.
"First they came for the slanderers and i said nothing."
Sure we can brute-force it, we'll just spit out a whole bunch of random machine code, and check each set to see if it solves the boolean satisfiability problem, and then see if it solves it in polynomial time. This approach just depends on P == NP being true in order to work. :)
Funny, unlike some engineering and physical science fields, math has no shortage of papers that are dozens, if not over hundred pages long. I've done physics work where I get told I should at least publish short updates if working on something big, while with math, I can wait until I have a large, complete picture.
I like to imagine you alt-tabbed from World of Warcraft sipping on a latte while typing that.
A game for adults http://www.sharedwisdom.com/ar...
http://www.amazon.com/The-Mast...
That is about $75k of computing resources from Amazon Web Services.
Spoiler Alert: It's 669,723,114,288,829,212,892,740,188,841,706,543,509,937,780,640,178,732,810,318,337,696,945,624,428,547,218,105,214,326,012,774,371,397,184,848,890,970,111,836,283,470,468,812,827,907,149,926,502,347,633
My Computer:
"For no reason at all, would you like to play a game of Go today?" *casual indifference*
Me:
"Sure, 20x20 board?" *smiles*
Computer:
"Never mind" *sulks*
"There is more worth loving than we have strength to love." - Brian Jay Stanley
Although a lot of knowledge is assumed on here, Go is one of the most well-known and popular board games worldwide. Probably more popular than chess, even.
Othello/Reversi, however is, not only a poor comparison but relatively unheard of. (I'm a massive fan of Othello, it has to be said).
Go is NOT like Othello at all. You have to put coloured stones on a grid-like board, 19x19 for standard Go, in such a way to "enclose" a block of your opponent's pieces. The complexity of Go is RIDICULOUSLY high, so much so that just to hold work out how many board positions there are takes months of computing time. Imagine how good the AI players are in such a circumstance!
When I was at university, 15 years ago, one of my professors (Professor Wilfred Hodges) was working on Go. It was his introductory lecture to describe the complexity of the game. It's astounding. At the time, the most powerful computer player in the world couldn't come close to beating even a seasoned amateur. They're a little closer now but nowhere near the way that Chess can be dominated by a single machine.
Go is one demonstration of how a human's pattern-matching and simultaneous processing can far outweigh anything that a computer can do at the moment. No doubt, with breakthroughs of thought and ever-increasing speed of computers, we'll eventually get there, but a human brain has been able to be there for, well, probably thousands of years already. And on a "puzzle" that's entirely logic-based and effectively ternary (white, black or no stone at all on each space).
Now let's give each position an IPv6 address. Ooops!
I can tell from my experience, having played Go decently, but being a calamity at Chess.
To give an example, I wrote a chess-playing program (a simple alpha-beta minimax with a value function pilfered from SunFish ...). When I set it to just 4 plies (that is two moves ahead) it absolutely destroys me. Basically, to be a decent chess player, you must have the ability to picture the board in your head and be able to do so for a few moves ahead. It is absolutely necessary when calculating exchanges and piece sacrifices. So a bit of ability to play blindfold chess is needed. Not a whole game, but to follow a line in your head.
https://github.com/thomasahle/...
No iterative deepening, no transposition table, no null-move search, no
Contrast this with Go, where blindfold play is almost unheard of. One of the well-known difficulties is to "play under the stones"
http://senseis.xmp.net/?IshiNo...
where part of a group is captured and you have to play new stones on the vacated intersections. This is a place where blindfold-chess type of skill is required, and most Go players avoid that. Here is a great article on that:
http://senseis.xmp.net/?Herman...
Also, the opening in chess follows very precise sequences, while in Go, the two players can almost ignore each other for the first few moves.
In the opening you have to think of the large-scale pattern of the territory you want to grab, not of the exact position of one piece/stone.
Besides curiousity, why was computing power (read: energy) spent on this?
"Consensus" in science is _always_ a political construct.
There's no way to bruteforce P = NP isn'it ?
We just need a genius to work on it for 10 years.
I've been working on it for 10 minutes, and it's patently obvious that P=NP when N=1, since 1 x anything is anything.
Not quite sure what all the fuss is about.
To have a right to do a thing is not at all the same as to be right in doing it
The only position not having a color-swapped sibling is the empty position...
What I enjoy the most is when the game is over and you spend a few hours discussing who won.
compute the number of nodes and CPU-hours required, hence the system cost, of a 20x20 system.
That's before you even start calculating the actual positions.
Political debates have me rolling my eyes so much I think I got optical whiplash. I should sue. - Foamy The Squirrel
It's interesting to see the exact number, but we obviously can't grok it. We want to know how many digits that number has.
Democracy Now! - your daily, uncensored, corporate-free