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

Not Any Time Soon

[eklitzke]

I'm not an active Go player anymore, but I used to me. And the current state of artificial Go intelligence is pretty sad. The best junior players in the world (10-13 or so, IIRC) can beat the very strongest computer Go programs, and they're literally orders of magnitude worse than the best human players.

Playing Go is more than just searching a lot of positions. The game is _very_ subtle. To even understand how a professional 9 dan player (i.e. the very highest ranked players) plays every move in a game, you really need to be at least a 7 dan or so -- anything less than that and the moves just won't make a lot of sense. I have the feeling that it will be at least a decade (but probably much longer) before computer opponents can beat professional players, and even longer than that until they can beat the very best human player.s

Re:I don't care how good it is

[Chris Mattern]

A computer will never beat a kid possessed by the ghost of an Edo period Spirit!

Er, actually, Fujiwara no Sai is Heian era, not Edo.

Chris Mattern

Re:Exhaustive?

[smallfries]

Oddly enough this very question forms the basis of the article that you haven't read... :)

The basic asnwer is that we can optimise doing something simple and replicate lots, far, far better than optimisiing something complex and replicating it a few times. Which if you think about it is the approach that the brain / evolution of the brain opts for.

The "brute-force" approach described is actually mid-way between a pure brute-force (exhaustive) search and a "smart" search using quite sophisticated techniques to prune the tree. The author talks about alpha-beta pruning, null-move generation and hypothesis testing. These techniques are still pure-search (brute force) techniques - ie you could apply them to any game tree, but their effects are similar to how a smart (tailored to the specific game) approach would work.

Progress in Computer Go

[igomaniac]

I'm a reasonably strong Go player myself (4. dan) and I've studied computational complexity - my gut feeling is that computers will not beat humans at Go in my lifetime even if Moore's law continues to apply. The only possibility is that someone comes up with a completely new approach, a bit like when alpha-beta search was invented for Chess. At the moment the most interesting approach is Monte Carlo methods applied to Go which has so far lead to a gain of at least two stones strength for the current programs. The strongest Monte Carlo based program is currently MoGo by Sylvain Gelly et al. which you can find more information about at http://www.lri.fr/~gelly/MoGo.htm.