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.

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?"

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: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.