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."
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
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. :)
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
Fair enough, then what is the 'benefit' of solving this?
Guessing they needed to heat their apartment and having the server run flat-out for 9 months helped - a lot.
It must have been something you assimilated. . . .
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!
Agreed, there is "one color go" as you describe it.
The point I was trying to make is that while this version of go is not very popular, any chess player starting at about National Master level (and certainly for those at IM level) is capable of playing blindfolded.
This ability is simply a by-product of their training, not something they specifically aim for.
For Go players, the ability to play with the same color stones is not something that follows naturally from their training.
Go and Chess expand different abilities of the human brain.
How do you justify the cost of a book, movie tickets, money spent on vacation travel or, going further, a degree that's not an engineering degree? Because if you run your numbers, there's no financial reason for any of those things.
Yes, there is absolutely no financial reason to be a doctor, lawyer, accountant, architect, dentist, vet, banker, real estate agent, marketer, economist, fashion designer, Army General, rock star, Hollywood actor, actuary, quantity surveyor...they're all just hobbies rather than jobs where you can earn any money.
To have a right to do a thing is not at all the same as to be right in doing it
Instead of going to Dell, why not use Amazon EC2? Probably do it way cheaper and you could set it up in a couple hours.
Slashdot still doesnâ(TM)t support Unicode after it was added to the HTML standard in 1997.
Just knowing the total number of positions doesn't really do much. It's just a huge combinatorics problem. Knowing the number of positions doesn't tell you much about which positions are good or bad, or even which ones are likely to happen in an actual game. I guess it gives you some idea of the problem space for solving the game, but that doesn't get you very far. We already knew the problem space is extremely huge. I don't think that standard methods or computing all the possible moves like we did with checkers or chess are the right way to go about it. On a 19x19 board, there are 361 choices for the first move. and for the second move there are 360 options. That's 129000 possible combinations for the first 2 moves. Mind you, many of those are symmetrical, but it's still a large number of positions. Compare that to checkers where the are 16 possible 2 move openings, and chess, where there are 100 possible 2 move openings, many of which we know are almost never used in competition play. Attacking go using the same strategies as chess seems like it would just lead nowhere.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.