Wednesday, June 27, 2007

Chess computer: null move pruning

I've implemented a feature called "null move pruning" which helps the search algorithm to get rid of ('prune') more unnecessary variations. I'm down to an average branching factor of slightly above 8 (from about 11). That means it's now possible to (within reasonable time) go 6 half-moves deep. And that's reason to celebrate, like every new half-move. Not that long ago 4 half-moves was unplayable (took too long). Six is still not much, but it's better and it's something. More will come.

Now I'm starting to feel a need to be able to measure its performance in some more way than I'm currently doing. As long as I'm just speeding it up in terms of positions analyzed per second it's no problem since it can be measured directly and with little risk of error, but some other changes as not as easily measured (yet). Of course, counting half-moves (or branching factor), as I've done in the current case, is as good as any measure (or even better) as long as it's free of error, but I'm not sure I've implemented the null move pruning correctly and would like to have it verified by some other means. It seems stronger when I'm playing it, but it couldn't beat a chess program that it earlier (without the null move pruning) had a chance to beat (though it didn't). An accurate way to measure its rating would have been great. Maybe it's time to get it ready for FICS, or maybe download one of those packages with test-scenarios that I've read about. Or something.

No comments:

Locations of visitors to this page