The strictest criteria for searching moves that still seemed to make sense are:
* Don't try Higher x Lower if the victim is protected
* Don't try equal captures if the victim is protected
* Don't try to capture something if the opponent can capture something more or equally valuable with his reply
There is no obvious gain from moves that fit any of these descriptions. They could be winning captures, but without thinking ahead more than 2 ply you cannot know that. So they are more like 'wild goose chases'. One way to prevent search explosion is to limit the number of such goose chases.
This gives you a handle for iteratively deepening QS, turning it from an aggressive depth-first search (which is especially prone to search explosion) to a much more stable breadth-first search (which offers a much better guarantee of finding quick and cheap refutations if they exist). What you can do is in the horizon node iterate over capture searches that allow at most 0, 1, 2, 3, ... goose chases in any branch. Presumably this would converge to a stable QS tree at some point. (And if not, you can abort the deepening, which is more than you could do if you would just have 'plunged in', allowing any goose chase in a single depth-first search.)
A basic need for this algorithm is a way to check if a piece is protected or not. A poor man's implementation for this could be to just make the move, and then run the move generator to check if a recapture is possible, and legal. But of course much more advanced methods for this are in common use.
In all cases you would pass the value of the last victim with a QS call. If a moves that is not LxH or has an unprotected victim would capture something more valuable, the previous move would be counted as a goose chase as well. (Despite the fact that it might have been LxH or captured something unprotected.)
Example: you have PxB, but the opponent can retaliate with RxR. At first glance the PxB seems an OK move, but as soon as you discover RxR in the daughter (which will be pretty early, if you use MVV ordering), you will determine if the Rook was protected. Should it turn out that it was not, the PxB is now counted as a goose chase, and reduces your remaining budget for those (possibly aborting the curent branch immediately, if you had none). Though shalt not capture a Bishop if thy Rook is hanging! If the Rook was protected, however, the possibility that a Rook trade could follow would not deter you in any way from making the PxB capture.
After having screened all captures of B and higher this way, (as retaliation against a hanging B also makes the PxB not an obvious gain), you can establish if PxB was a goose chase, and if so, decrement the budget for those, and abort with +INF score if it was already exhausted. If it wasn't, you continue searching captures that provide obvious gain (LxH or unprotected victim) passing the remaining budget, and, when the budget is positive, the other captures with a decremented budget.
If, for example the RxR reply to PxB would be on a protected Rook, it would still be searched if the original goose-chase budget for PxB had been 1 (as PxB would have been 'clean' then), but now with butget 0, because R x protected R is non-obvious. This could lead to a second RxR (if the protector was a Rook, and we did not have a second attacker, so that our Rook would now be hanging, so capturing it would be searched despite the remaining zero-budget). If we would have a second attacker on the Rook (say Q), however, it would stop after PxB, RxR, as the subsequent RxR would find its victim protected (by QxR), and thus considered a goose chase, while there was no budget left for those. (And indeed, it would be just an additional Rook trade, which would not alter the score.
Code: Select all
int Attacked(square)
{
GenerateCaptures();
for(ALL_MOVES) {
if(move.toSquare == square) return 1;
}
return 0;
}
int Protected(square)
{
GenerateCaptures();
for(ALL_MOVES) {
if(move.toSquare == square) {
MakeMove();
legal = !Attacked(kingSqr);
UnMake();
if(legal) return 1;
}
}
return 0;
}
int QS(alfa, beta, budget, threshold)
{
int currentEval = Evaluate();
if(currentEval >= alpha) alpha = currentEval;
if(alpha >= beta) return beta;
GenerateCaptures();
SortMoves();
for(ALL_MOVES) {
if(value[victim] < threshold) break; // assumes MVV sorting
if(value[victim] > value[piece] || !Protected(move.toSqr)) { // pre-screening
budget--; // previous move was goose chase
if(budget < 0) return +INF; // reject it
break;
}
}
for(ALL_MOVES) {
int cost = 0;
if(value[victim] <= value[piece] && Protected(move.toSqr)) cost = 1;
if(cost > budget) continue; // move is goose chase, and out of budget
MakeMove();
score = -QS(-beta, -alpha, budget - cost, value[victim]);
UnMake();
if(score > alpha) { // alpha-beta stuff
...
}
}
}
