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.'"

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

FPGAs?

[g-san]

Yes FPGAs are easy to program, but there is a tradeoff: speed. And since this is a brute force application, you probably don't want to use FPGAs.

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.

Re:why check everything

[Llywelyn]

Go is not NPC. The Japanese Rules are EXPTIME-complete. Go Endgames are PSPACE-hard, and ladders are PSPACE-complete. Under the Chinese rules it is thought that the game might be EXPSPACE-complete, but this has not yet been proven.

We also have yet to develop heuristics that even evaluate one position very well, especially during the opening or middle game. Machine learning is not a cure-all here: there's a combinatoric explosion that happens very quickly with this game which makes most of the techniques difficult to train even under the best of circumstances.

Not to say that such won't eventually be possible, but it's handwaving.

Re:why check everything

[Llywelyn]

Technically speaking, solving go for the standard 19x19 board, or any fixed board size, is a constant-time operation, hence far short of NP-complete.

Not any more than solving 128-bit cipher is a constant-time problem.

Using the Japanese rules Go has been proven to be EXPTIME-complete [wikipedia.org].

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 [www.lri.fr].

Re:FPGAs?

[Shalth]

Actually, if you are going for speed you do want to use an FPGA. Even though there is an inherant iteration problem associated with determining the best move for Go, you can create a very parrallel algorithm that would search many different paths at the same time. Now if you are refering to the clock speed of FPGA's, then that is not an issue either. Even though most modern dual core and quad core processors can run at 2.4+ Ghz, they are most times limited to several levels of pipelining. This limits each processor to maybe 10 billion opperations per second.

Now with FPGA's, an average clock cycle that it would be run at would be around 200 Mhz. This may seem slow at first but once you realize that at this 200 Mhz clock speed you are calculating several thousand computations you will see that you can easily crush the 10 billion opperations per second of a normal processor and reach several trillion opperations per second with a single FPGA.

It's 10^170, not 10^60

[PacoSuarez]

The article says *chess* has about 10^60 positions. Go actually has 10^170. Now all the people that have made silly arguments about how 10^60 means the game is untreatable should apologize, I suppose. Oh, and go will fall too. My bet is 20 years before a computer beats the best human players. We know more about how to write a go program than most people think.