So I am looking for a simple implementation of easy move. So far I found this:
Code: Select all
int easy;
int Search(int alpha, int beta, int depth)
{
for(iterDepth=1; iterDepth<depth; iterDepth++) { //(I)ID
alpha = originalAlpha, bestScore = -INFINITY; firstMove = TRUE;
for(ALL_MOVES) {
Make(move);
score = -Search(-beta, -alpha, iterDepth-1); // recursion
UnMake(move);
if(score > bestScore) { // normal alpha-beta score propagation
bestScore = score;
if(score > alpha) {
alpha = score;
if(score >= beta) break; // beta cutoff;
}
}
if(NodeIsRoot()) {
// ********* HERE COMES THE EASY-MOVE CODE: ************
if(iterDepth > 3 && easy) {
if(!firstMove && score > alpha - easy) easy = 0;
alpha = alpha - easy; // lower alpha for next move
}
// *************** END OF EASY-MOVE CODE ***************
if(TimeUsed() > TimeLimit(easy) && !DisastrousFailLow()) break; // be happy with what we have
}
firstMove = FALSE;
} // next move
if(NodeIsRoot()) {
PrintPV();
if(TimeUsed() > SafeToStartNewIter(easy)) break; // no time for new iteration
}
} // next depth
return bestScore;
}
The idea behind the implementation is that in the first few iterations a unique best move should have floated to the beginning of the move list, and will be searched first. The variable firstMove already kept track of that for the benefit of PVS. Now if a later move at iteration 4 or higher has a score that is within a margin 'easy' from the current best move, as recorded in this iteration's alpha, (which will certainly the case if it actually improved alpha, as then score = alpha > alpha - easy after increasing alpha), we clear 'easy', to indicate that life is not easy, but a real choice is to be made.
Of course normally you would not know how close the later moves score to alpha, because if they are below alpha they fail low, and the score is just an upper limit. So we have to lower alpha to alpha - easy, which is done for the next move if the current one did not already spoil the easiness. This opens the window with which the next move will be searched. (I guess I could also lower beta, but PVS uses window {alpha, alpha+1} on the later moves anyway, so as long as they keep failing low beta is never used. And the first one that doesn't fail low compared to the artificially lowered alpha will spoil the easiness once and for all, hopefully at quite low depth, so I did not bother.)
So as long as 'easy' has some non-zero value, all later moves will be searched with the artificially lowered alpha, enabling us to reliably check if the easiness criterion remains fulfilled. The global varianble 'easy' can be initialized before the search to whatever threshold we want to use for a move to qualify as easy.
Does this make any sense?
The easy-move code is put before the tests it there is time to continue, so that these tests can make use of the value of 'easy' to greatly reduce the time quota if 'easy' is still non-zero.
