Evolution of a Go program

About the development of Moyo Go Studio, software to (help) play the Oriental game of Go. Go is a two-player zero-sum game of perfect information. It is considered much harder than Chess. Currently, in spite of enormous effort expended, no computer program plays it above the level of a beginner.

Friday, March 03, 2006

A Faster Search

Some folks didn't like the elliptical graph so the next update will have an ordinary bar graph.

Kombilo uses all kinds of tricks to speed up search, and MoyoGo doesn't yet, for its recent implementation of "free" pattern search. MoyoGo is about as fast or a little slower than Kombilo, but I am now working on a massive speedup that might make most searches near-instantaneously. Near-instant "Kombilo" searches would open up a whole new realm of possibilities, such as doing automatic searches for continuation patterns etc.

Kombilo uses hashes and end-position matching to greatly speed up search, an MoyoGo simply plays through all games and matches all possible patterns. That's more accurate as well, instead of using hashes. You can imagine that when it's now about as fast as Kombilo (with the same number of games and the same pattern), that the potential for speedup is enormous. I think I can speed things up with about a factor 100, in CPU terms. But the bottleneck remains the HD bandwidth, so a more realistic figure is ten times faster than Kombilo, which would still mean the same search times if you search through MoyoGo's entire game database.