Author: Alessandro Damiani
Date: 03:46:15 08/07/04
Go up one level in this thread
>The use of SEE was in the quiescence search only and
>involved rejecting any search of a capture whose SEE
>value to the to square of the capture was <0, otherwise
>the move would be made, legality tested, and if legal,
>then the recursive capture search performed (with the
>same see test.)
>
After having corrected your SEE you can speed up your qsearch the following
ways:
Variant 1:
Only moves that improve the score are searched.
int quiescence(int alpha, int beta)
{
int posValue;
int value;
int best;
int i, n;
posValue= evaluatePosition();
if (posValue >= beta) return posValue;
best= posValue
if (best > alpha) alpha= best;
n= genQuiescenceMoves();
for (i = 0; i < n; i++) {
// we assume move[i] is the move to be searched
// determine the win limit:
value= winLimit(posValue, move[i]);
if (value > alpha) {
make(move[i]);
value= -quiescence(-beta, -alpha);
unmake(move[i]);
// beta cut-off?
if (value >= beta) return value;
}
else {
// it applies: value is the win limit and the win limit is not
enough
// skip search
};
if (value > best) {
best= value;
if (best > alpha) {
// new PV
alpha= best;
}
}
};
return best
}
Variant 2:
In addition to searching only moves that improve the score, this variant also
uses its knowledge to make the (alpha, beta) window of the subsequent search
smaller. This is more aggressive. The differences between this variant and the
previous one are highlighted with arrows ("-->" and "^^^^").
int quiescence(int alpha, int beta)
{
int posValue;
int value;
int best;
int i, n;
posValue= evaluatePosition();
if (posValue >= beta) return posValue;
best= posValue
if (best > alpha) alpha= best;
n= genQuiescenceMoves();
for (i = 0; i < n; i++) {
// we assume move[i] is the move to be searched
// determine the win limit:
value= winLimit(posValue, move[i]);
if (value > alpha) {
--> // limit the search's beta to winlimit if possible:
--> if (value > beta) value= beta;
make(move[i]);
--> value= -quiescence(-value, -alpha);
^^^^^^^
unmake(move[i]);
// beta cut-off?
if (value >= beta) return value;
}
else {
// it applies: value is the win limit and the win limit is not
enough
// skip search
};
if (value > best) {
best= value;
if (best > alpha) {
// new PV
alpha= best;
}
}
};
return best
}
A possible implementation of the function winLimit() looks as follows
int winLimit(int posValue, Move m)
{
int winLimit;
winLimit= posValue + SEE(m) + POSITIONAL_MARGIN;
if (isPromotion(m) {
winLimit+= val(promotionPiece(m)) - val(PAWN);
};
return winLimit;
}
The constant POSITIONAL_MARGIN can be used to avoid not playing good captures.
For instance, SEE(m) = 0, but the capture increases the positional score a lot.
Such a capture would not be searched in the case of POSITIONAL_MARGIN = 0. This
constant can also be made depend on the distance from the current ply to the
root of the quiescence tree: the farer away from the root of the quiescence
tree, the less the positional margin, hence being more selective.
All this stuff is basics. Take it as a good starting point. There are a lot of
degrees of freedom here, as usual in computer chess. Enjoy!
Alessandro
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.