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.

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.