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.