I wondered whether the reason that I did not improve was the fact that the remaining room left for improvement was so small. So I started to measure the quality of the move order in my engine (should have done that earlier, I know).
I ran a 10 second search over 250 random test positions to get an idea at which position in the list a move causes a cutoff. The earlier the better. Here are my results from those 250 positions.
Total recorded cut offs: 251,607,401
CutOff with 1st move: 95.368%
CutOff with 2nd move: 2.519%Avg. move no that causes cut off: 1.174
CutOff in remaining moves*: 8,643,777 (3.43%)
CutOff move no in remaining moves: 3.022
Cutoff with a losing capture: 1,558,615 (0.62%)
*after hash, captures and killers
This analyses shows that in more than 95% the cutoff happens with the first move that is searched, which is an excellent number. Killer moves and captures also lead to early cutoffs, so in only a bit more 3% of all nodes where a cutoff is possible the quiet moves have to be generated and searched at all.
And here without doing history heuristics or piece square stuff in average the 3rd move in the list gets us a cutoff. I do however look at the killer moves from 2 plys above and 2 plys below the current node and order those moves first in the list if they are legal in thsi position. This seems to help a little bit to improve the order and I have this data anyway available.
After seeing those numbers I don't think I will put more efforts in this area in the near future because the order quality seems quite good already and the slow down in execution to get a better ordering in 3% of cut nodes will probably not pay off.
No comments:
Post a Comment