Thursday, May 1, 2014
There are several techniques available to deal with that and iCE uses most of them. Last time I measured it did search the best move first in more than 90% of the positions.
For that I tried to use some knowledge in the function that orders moves, e.g. order moves with an attacked piece early and moves to squares attacked by opponents pawns late in the list so the function got a bit complex.
One technique I do not use (I tried once but it failed) is history heuristics. This is a simple statistics. Moves that were in other earlier searched positions good are tried before moves that have no or a bad history. I wondered whether I can maybe now replace a bit of my complex knowledge with such a statistics to simplify the engine a bit.
And it turned out I can.
I striped all my move ordering functions that handle quiet moves from knowledge and replaced it by history. The now simpler engine even seems to play a bit better, not by a huge margin but statically significant.
After a lot of failed attempts I'm happy I encountered now a change that works and even makes things simpler. However the idea is well known and widely applied. So nothing to get to excited about.