Tuesday, February 21, 2006

It works!

Absolute worst-case search time on my machine is 22 seconds to search through 43,000 games. This is for unrealisticly large, complex, edge-less patterns. A more typical search time for edgeless patterns is between 7 and 17 sec. Large edge patterns and Joseki patterns take half a second only! Smaller edge patterns take up to six seconds.

This test case takes 11.6 sec. (301 matches).

I'll make it multithreaded, so that on near-future mainstream machines, most searches will take less than a second.

It looks like I succeeded in being 10 times faster than Kombilo, but I'll do a benchmark later. Kombilo, as its main optimization, looks at the final positions whether a match could have happened in the game, and examins only those games further. This algorithm doesn't do that yet, neither has it been optimized for 64-bits, so there is ample room for optimization.