Cracking Go

prostoalex writes "IEEE Spectrum looks at current trends in artificial technology to crack the ancient Chinese game of Go, which theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible? 'My gut feeling is that with some optimization a machine that can search a trillion positions per second would be enough to play Go at the very highest level. It would then be cheaper to build the machine out of FPGAs (field-programmable gate arrays) instead of the much more expensive and highly unwieldy full-custom chips. That way, university students could easily take on the challenge.'"

Comments

Exhaustive?

[SavedLinuXgeeK]

Using an exhaustive method is silly in a realm of 10^60 possibilities. Obviously human players, with much more finite resources (computationally that is) can do a much better job. Why not spend more time and being able to analyze the board better, and mimic the decision making patterns of the masters. I realize this has already been tried, and is still being worked on, but exhaustive search just seems like a waste of time and effort. My .02

Re:Exhaustive?

[eniac42]

but exhaustive search just seems like a waste of time and effort

Not so. The exhastive search approach provides a testable benchmark for true AI to exceed before it can prove it is productive AI. The famous Chess 4.6 program demonstrated that a simple "technical" tree search program could perform better than selective "intelligent" algorithms that tried to prune the search tree aggresively. With Go, this strategy fails - but the "intelligent" pruning mechanism is still eluding everyone..

There is still a golden prize in game-search algorithms - solve this, and other problems in AI can be solved too..

Re:Exhaustive?

[CodeBuster]

but the "intelligent" pruning mechanism is still eluding everyone.

It is not the pruning mechanism itself which is still eluding everyone, but rather the difficulty in formulating a sound evaluation function for use in the alpha-beta pruning optimization of the brute force search. The game of Go is interesting because it is often the case that a particular board configuration does not give much concrete information about its future potential. In other words, a seemingly disadvantageous board in the short run might actually lead to a better endgame than a seemingly more valuable board in the present. A small situation in one part of the board might effect the larger game in unexpected and interesting ways dozens of moves into the future. It is precisely this complexity which makes Go intriguing for players and difficult for computers.

Re:Exhaustive?

[fractoid]

Go for it. The article isn't about beating "UbuntuDupe's hypothetical game", it's about beating Go. There are lots of things that humans are better than computers at. None of that has any relevance to the article. Correct me if I'm wrong, UbuntuDupe, but - I don't think he was saying "let's solve a different game". He was just pointing out that the whole point Go is so hot in AI programming is that its state space is big enough that it *can't* be brute forced, and so whatever-it-is that you need to play it well with a human-sized intellect might just be 'intelligence'. Simply waiting until your hardware is swanky enough to brute force it is missing the point. Of course it may be that brute force state-space searches ARE the best approach to AI. Then again, it may not, and it's worth trying to find other approaches.

Chess playing became a much less interesting proposition when hardware became chunky enough that you could cache the first few moves from archives of known openings, brute-force search the next 12-15 moves, and store all endgames for the last 8 or so moves in a lookup table.

Re:Exhaustive?

[phantomfive]

My gosh that is the worst joke I've ever heard in my life. haha. You should be shot or something. :)

yay!

[apodyopsis]

My favorite game.

First time I played online I had my ass handed to me by a precocious 12 year old. Ah well, the memories.

*Alot* more complex and tactical then Chess, believe it.

See the rules at: http://www.britgo.org/intro/booklet.pdf

Play online here: http://www.pandanet.co.jp/English/

I recommend installing glGo and having a go vs. computer (on the easiest setting there is).

Enjoy, I do.

Re:yay!

[zippthorne]

Pure number of game states does not equate to richness of experience.

Would you say that "Diplomacy" is more or less tactical than "Axis and Allies?"

Re:Not Any Time Soon

[ajs]

Playing Go is more than just searching a lot of positions. The game is _very_ subtle. This is provably incorrect. Searching a lot of positions gets you a solution to the game. The problem is that "a lot" is defined as 10^60, which though it looks like a nice, friendly number isn't even remotely manageable. To give you a sense, the current U.S. national debt is around 9 trillion dollars. That's on the order of 10^12. That's a huge number, but the number of go positions is 1,000,000, 000,000,000, 000,000,000, 000,000,000, 000,000,000, 000,000 times larger than that!

This is an incomprehensibly large number, and the evaluation of each position alone is not trivial.

Not artificial intelligence

[Reality Master 101]

The fact that we're talking about trillion move/second machines rather than even attempting to do it the way humans do it ought to tell us what the current trend in artificial intelligence is.

Basically, the current trend is the same as it was 20/30/50 years ago. This IS NO science of artificial intelligence. We don't have a freaking clue how intelligence works. I think we will someday, but it's going to take a fundamental breakthrough in theory. A "Principia Intelligentsia" (I'm probably mutilating the Latin) by some genius that throws out all the fumbling and finally Explains It All.

Re:Not artificial intelligence

[Reality Master 101]

I would be really interested in knowing how you think we know that. We know they aren't consciously considering a trillion moves per second. But how do we know what kind of work the cognitive engine is doing underneath the consciousness? What if your brain evaluates quadrillions of moves per second, leaving you aware of only the best few it can find?

Because the brain only has 100 billion neurons and, at best, can fire only a couple thousand times a second. If 1% of an entire brain was dedicated to being little Go Position Computers, it would be hard to imagine how you could get a million moves a second, considering communication and infrastructure overhead. Much less a billion, or a trillion, and certainly much less than a quadrillion.

Of course, I could also make the argument just because we suck at rote computational things, and are wonderful at pattern matching things. If we really had exhaustive search capability like that, it would probably show up in some sort of everyday task.

Exhaustive Search is not realistic

[jmdc]

...theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible?

No.

A typical star is made up of ~10^57 hyrdogen atoms. If you could store an all the information you needed about a single ending position in a single atom, you'd need storage that had the mass of thousands of stars.

Not brute force, Monte-Carlo !!!

[Anonymous Coward]

This is one of the worst articles about computer-Go I've ever read. The author seems to completely overlook the recent advances in the field which made possible huge gains by replacing n-ply reading and evaluation by monte-carlo sampling of possible end positions. This is indeed some sort of brute-force but allows to avoid the proble of evaluating a partial position, which is very hard.

Still far from the best human players, but at least improving :)

Read an article to this effect....

[FooAtWFU]

I read an article to this effect in an AI class. Apparently the Latest Thing in solving things like Go is to take a good random sampling of just a few thousand (or tens of thousands of) possibilities in the future, and try to see what sort of move looks better, rather than trying to be exhaustive about the entire thing. I thought this was Quite Interesting. Meanwhile, the exhaustive search is really the least interesting way you could possibly do it, and won't likely provide you with much insight on Go, or related matters. *yawn*

Very true.

[Mahjub Sa'aden]

The game is _very_ subtle.

Absolutely. Last weekend -- Thanksgiving here in Canada -- my family vacationed in Northern Ontario. We didn't bring a television, but somebody did bring a Go set. I set about teaching most of my family how to play it. But what's amazing to me is how long it takes to get an adequate grasp of the basic concepts. Life, death, influence, strength, weakness, playing in the corners and sides, even scoring is hard. I don't even have a good handle on the game, and I've been playing extensively for some five years now.

In that context, I don't wonder that it's hard for computers to handle Go. The game has facets that are hard to quantify. It's hard for intelligent humans, too. Much like life.

Sort of makes you wonder; if a computer can figure out Go, how far from that point is real AI? Or does that question even mean anything?

Re:why check everything

[jpfed]

By that logic any problem can be called "constant time" as long as you've chosen an actual problem to solve. It's like that, although what I call a problem, you would likely call a class of problems, and what you would call a problem, I would call an instance of a problem. Using your terminology, it's useful to speak of the asymptotic complexity of a class of problems, but not of a single problem.

Just because you've fixed n to some value doesn't change the problem's complexity. If I say that such-and-such a problem can be solved in O(n^2) time, then what I mean by that is that the number of computations required to solve this problem is less than some function of the form an^2 + bn + c for some a, b, and c. A simpler way to say this is that the number of computations required to solve this problem is less than dn^2 (with the right choice of d, this can be greater than an^2 + bn + c for any particular choices of a, b, and c). So, to summarize, O(n^2) time means the number of computations is strictly less than dn^2 for some d (where d does NOT change as problem size changes).

Let's say I am going to bubble-sort a list that is n items long. The most aggressive (lowest) upper bound I can put on this operation is that it will take n(n+1)/2 swaps, so it will take O(n^2) time. Now, let's say that I know that the list is 10 items long. At this point, I can estimate the number of swaps will be at most 10*11/2 = 55.

Now, 55 is O(1), because there is d*1 for some d that is larger than 55 everywhere. Therefore, a bubble-sort run specifically on a list that is 10 items long is constant time.

There is an algorithm to find the median of a list that operates with a surprisingly low time-complexity (Iirc, it's O(n), but I might be wrong) that relies on the fact that a sorting problem of fixed size runs in constant time.

Re:Sure it is possible to search 10^60

[Workaphobia]

The greatest shortcoming of the human race is our apparent inability to understand the exponential function. You, the parent, the grandparent, and the summary seem to all not understand the nature of an intractable problem. "Trillions" of operations a second means nothing when the search space is that big, and no advance in computing (assuming we remain limited by Moore's law and level off in the foreseeable future) will help.

So while you, the parent, and the grandparent were trying to be funny, you were all grossly understating the difficulty. Although I like that Self->Grandchildren->Species is possibly an exponential progression - I would have been annoyed if it had been Self->Grandchildren->GreatGreatGrandchildren.

Re:Sure it is possible to search 10^60

[TapeCutter]

WOPR can solve it one digit at a time, 60 digits is no problem.