Can the Game of Go Be Cracked by Brute Force?
Feng-hsiung Hsu, one of the key contributors to Deep Blue (Wikipedia ) and now at Microsoft Research Asia, has published a manifesto proposing that go can be cracked by chess-like brute force techniques. Really?
Hsu sets up as his strawman the “old AI” approach of mimicking human thought. But although the current crop of programs can be loosely lumped into this category, few believe that that is how go will be solved. The most promising direction is obviously UCT /Monte Carlo .
Hsu’s article would be best titled “Back to the Future”. He wants to trot out the old Deep Blue search+eval model with some tweaks to add another few orders of magnitude of analysis horsepower. He correctly identifies the two basic problems also discussed in my overview of computer go : the size of the tree and the difficulty of evaluation. However, his understanding of the latter problem is shallow at best. He says:
The second problem is the evaluation of the end positions. In Go you can’t just count up stones, because you have to know which stones are worth counting…before you can count a stone as live, you have to calculate several moves ahead just to satisfy yourself that it is really there in the first place.
This is completely wrong. You don’t have to just “calculate several moves ahead”. You have to essentially solve a problem which is as difficult as the original one.
The tweaks to the Deep Blue brute force model that Feng proposes as a way to solve the problem whose scale he is so egregiously underestimating include “null-move pruning” and caching the result of previous computations. And then custom hardware, combined with the inexorable advances in computing power that Moore’s Law gives us, could provide another four orders of magnitude, Feng suggests.
But is this anywhere near enough? The total of ten orders of magnitude probably is not enough in and of itself to deal with the greater branching factor in go, even with better pruning techniques, and that’s before we have addressed the problem of the hugely more complex evaluation function. Yes, it’s possible that caching could help there, but Feng underestimates the intricate interrelationships between local positions and the surrounding positions, which would require complex, time-consuming management of which cached solutions remain valid in what circumstances.
The bottom line is that the dynamic nature of go which makes it impossible to write a static evaluation function, even one million times slower than those used by chess programs, makes the entire Deep Blue model irrelevant. That is why the Monte Carlo model is so interesting.
Of course, if Microsoft is going to invest in this problem I’m sure they’ll figure these things out over time and their contributions will surely advance the cause of computer go. While they’re at it, why don’t they offer a $1M prize to stimulate external research as well?