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."
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."
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."
hey man, don't be a prick
go is super interesting from a formalistic perspective given that it has an extremely large amount of emergent behavior.
that is, the rules are so simple, that it should really be as easy to analyze as connect 4
but its likely the most complicated full-information game created by man
so, no, the exactly number isn't particularly interestingbut give the guy a break. 'mathematical go' by berlekamp is pretty
boring and trite and focusses on some really uninteresting endgame positions. but he tried to get a handle on things.
john tromp, one of the contributing authors, has made some very cool contributions on the solvability of go, the exact nature
of the rulesets, various automated processes for studying go positions, library software for keep track of the best human move
in a given position, etc etc.
so stfu
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
Yeah, $200k seems a bit steep. I mean, if it was for national defense, pushing data against the stock market, or even running a moderately sized corporation's ERP stack it would be a totally acceptable expenditure
It is an interesting problem to posit how it would be possible to get the same gear for a fraction of the cost, say 10%, or $20k
This may seem wildly optimistic, but in the dot-com meltdown I remember seeing gear with million dollar price tags going for $10k on ebay
The chassis, processors, and potentially even disk arrays may be easily obtained. I have worked at companies where they were shoved out the loading dock door on a monthly basis, because newer gear had smaller footprints and we could stuff ten times as many processors or terabytes into the same constrained space that we were stuck with
RAM may be a problem since they are asking for 512GB per machine. This would probably be in 32GB sticks, which are as easily traded as gold, and even if a company was shit-canning them, the more enterprising techs should be expected to be grabbing them at every opportunity
The common nexus for this gear would be the computer salvage companies that get paid to haul it away and make a secondary profit off of reselling what they can. How would these go-crackers find a salvage company with similar leanings? If that connection could be made, they may get away with it for the discounted cost of re-sold RAM
Which leads us to the next issue, supplying 15KW of juice to run these on, the additional power to pull that heat out of the space and enough battery supply to handle a power outage without losing your entire data set. In the corporate world, this is another $50k of Liebert gear and a diesel generator. And your gonna have somebody on-call to monitor, tune and otherwise tend to their wants and needs...
in cheapo-town... this could be a garage and a stack of deep-cell batteries with the over-worked go-crackers reheating pizza on the top of a server
I think that it is an interesting exercise to figure out how to deliver a half-million dollar hardware solution for next to nothing, anybody else have their 2-bits to throw at it?
Wherever You Go, There You Are
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).