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

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.