Author: José Carlos
Date: 04:05:28 08/07/04
Go up one level in this thread
On August 07, 2004 at 06:46:15, Alessandro Damiani wrote:
>
>>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);
> };
I'm not sure I understand here. Don't you apply promoted piece in SEE()? If
so, you shouldn't prune at all captures with SEE() < 0, but you need to apply
this "if" also.
I simply add the score of the promoted piece (- 1 pawn) when I calculate SEE,
just in case it's not recaptured.
José C.
> 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.