Author: Stuart Cracraft
Date: 09:36:03 08/07/04
Go up one level in this thread
Also, I should add that the other reason (besides
my attacker/defender-finding code being no master
than my makemv()) that SEE() may not work for me
is that my evaluation is purely pc/sq. I do no
other evaluation besides material and pc/sq.
I think SEE() works best with full evaluation due
to reduced evaluations and bitboards due to faster
attack/defense -- hopefully others see this also.
On August 07, 2004 at 12:32:27, Stuart Cracraft wrote:
>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.