Author: Stuart Cracraft
Date: 09:32:27 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);
> };
>
> 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
Thanks much for the above -- I tried many variants of the above and
also exactly as above. My program did not speed up. It slowed down.
It is not a bitboard routine and I fear that SEE() may not help it
due to the cost of determining attacks to a square (not much
more expensive than making a move with makemv) so from its point
of view, the capture search is faster without SEE() than with,
even though it looks like more nudes get pruned, because of the
cost of SEE() relative to my MAKEMV().
I hope that makes sense.
I tried your variant 1 and your variant 2 and also with various levels
of positional margin from 0 pawns to 3 pawns. My fastest search with
the most nodes in a fixed time interval across 30 problems was without
SEE.
Stuart
P.S. I did get the SEE() code itself working great and tried it
in a variety of positions and it correctly returned 0 for no
advantage, and above or below zero by the relevant amounts
based on how much would be won or lost -- I used Andreas's code
with very minor modifications.
So it is a big disappointment to me that SEE didn't help for
a non-bitboard and non-0x88 program like this.
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.