The idea applies to nodes where we have searched a significant fraction of the moves already, so there is high probability the node will fail low. At this point, we simply abort the search and return alpha rather than continue trying the rest of the moves.
This seems quite drastic, and I expected it to be one of the many ideas that fail miserably, but I was pleasantly surprised that it seemed to be worth about +20 to +30 elo....
Code: Select all
Rank Name Elo + - games score oppo. draws
1 GNU Chess 6.0.1 100 10 10 3000 61% 19 18%
2 Arasan 14.0 (1 cpu) 57 10 10 3000 55% 19 21%
3 Crafty-21.6 56 10 10 3000 55% 19 22%
4 EXchess v2012_04_29 31 8 8 5000 50% 33 23%
5 EXchess v2012_04_28 24 8 8 5000 49% 33 24%
6 DoubleCheck 2.7 20 10 10 3000 50% 19 18%
7 EXchess vref 0 8 8 5000 46% 33 24%
8 EXchess v6.10 -66 10 10 3000 37% 19 40%
EXchess vref is the current best version of my engine without this idea implemented. v2012_04_28 and v2012_04_29 have less and more agressive implementations of the idea respectively. The other engines are my current test opponents. The test games here are very fast (6s + 0.1s per move per side). The error bars here are 2 sigma (95% confidence).
The implementation is absolutely straight forward... essentially we wait until we get to the part of the movelist where we would normally be testing for LMR and pruning (after all good captures and killer moves), and we simply check what fraction of the moves have been played... if that fraction is larger than a certain amount, abort the search.
v2012_04_28 applies this with the equivalent of the following pseudo-code...
Code: Select all
// Search Abort Test
if(depth < 5
&& !first_move_searched
&& !pos.check // we are not in check
&& !next->pos.check // current move doesn't cause check
&& move.score < 2000000 // move scored below good captures & killers
&& alpha == beta - 1 // zero-window node
&& alpha > -MATE/2 // not during a MATE resolution
&& 100*mcount > (100-10*(5-depth))*total_moves))
{
clean-up and abort search by returning alpha
}
Code: Select all
if(100*mcount > (100-10*(7-depth))*total_moves))
It is surprising to me that this works as well as it seems to... especially the more agressive version. Other than the two versions above, I've made no serious attempt to tune this up or try variations on the conditions, so it is possible there is more gain here to be had. Does anyone have experience with this type of idea? My best guesses for its apparent success are...
(1) Something about my implementation of LMR or pruning is not optimal, so this idea exploits some of the potential gain there.
(2) It somehow is covering up a bug in my engine
(3) It is actually an enhancement.
- Dan