Author: James Swafford
Date: 21:00:28 05/14/99
Go up one level in this thread
This is really good, thanks for posting it.
I've learned a couple things.
I was using a window of (-beta, -alpha) vice (-beta, -beta+1).
I don't do the mate extension, either, but I'll be sure
to try it.
As for 'widening the window in the downward direction to
see if the null search fails low (indicating an undetected
threat)', how much?
--
James
On May 14, 1999 at 20:10:09, William Bryant wrote:
>I'm ready to ruin a perfectly good search by adding more code. If done right,
>the Null move should make it much stronger. My copy of C. Donningers paper has
>been ordered by inter library loan so I have not yet read the paper. Below is a
>summary or digest of information available from this forum over the last year
>concerning null moves.
>
>I think this is a pretty up to date summary of the heuristic, but would
>appreaciate any comments.
>
>Note: I have assembled this from many posts, maybe even yours. I claim no
>copyright on the material. For those, like me, ready to expand their programs
>with Null move search, I hope this summary helps. Please feel free to correct
>any errors I might have made.
>
>William
>wbryant@ix.netcom.com
>
>Null Move Summary
>
>Description
> Null moves are a forward pruning mechanism to generate a beta cutoff without
>doing a full search
>
>Situations to Avoid Null Moves
>1. When the side on move is in check. Then a null move simply allows the other
>side to capture the King.
>2. Having just done a null move.
>3. Endgame positions. Null move fails terrible when in Zugzwag, when in a
>position where not moving is an advantage and all moves result in a worse
>position. Then, the null move gives a beta cutoff when the regular move would
>not. This is usually based upon material score for the original side on move.
>4. Some have advocated only doing null moves outside the principle variation.
>Others have argued that a majority of the search with PVS is done on the PV, so
>this eliminates some of the savings of null moves.
>5. Some have advocated only doing one null move per node (none in the subnodes),
>rather than multiple nulls in the evaluation of a node. Also, consider starting
>with a single null move (non in subnodes) until bugs are worked out.
>
>Making the Null move
>
>1. Save the current board state in regards to ep square and other information
>needed to unmake the null move.
>2. Update the hash table signature to reflect the change in ep status (if any),
>the change in side on move status, etc. There is no ep square for the new side
>to move during a null move. These changes will be restored in unmaking the null
>move
>
>Calling the Null move search
>
>The search is called with a window of -beta, -beta+1. The idea is to see if a
>beta cuttoff is generated with the reduced depth and narrow window. This should
>be a very fast search and may prevent a much slower full width search.
>
>The search is called at a reduced depth. Popular is a depth reduction of 2.
>(YMMV). This is sometimes called the ‘R’ value.
>
>Mating Extension
>
>If the value returned from the null search is below the threshold for a mate
>score, the depth is extended one ply before searching normally. IE the side on
>move (before the null move) gets mated with the null move, this is a dangerous
>position and should be searched deeper.
>
>
>Other Options
>
>Widening the null move window in the downward direction to see if the null move
>search fails low (ie undetected threat) and extending the full width search on
>this circumstance as well.
>
>To use the Null search value to reset alpha. In general, most have suggested
>not to do this.
>
>Pseudocode for null moves
>
>if (NotInCheck and NullOK and DepthSufficient and MaterialSufficient) {
> MakeNullMove(); // similar to do move but reset the data //
>structures, save the ep square, ect for new // side on move
> if (depth - NULL_MOVE_DEPTH_REDUCTION)
> // if there is remaining depth
> Score = -Search(-beta, -beta+1, depth - NULL_MOVE_DEPTH_REDUCTION,
> false);
> // for the null move alpha = -beta;
> // beta = -beta+1;
> //else call the Qsearch with the null move window
> else if (depth - NULL_MOVE_DEPTH_REDUCTION == 0)
> Score = -QSearch(-beta, -beta+1);
>
> TakeBackNullMove();
> if (Score >= beta) { // Null move cutoff
> NullMoveCuttoff++; // counter for successful null moves
> return beta; // alternatively, return Score
> }
> else if (Score < -MateScore)
> depth++; // may wish to handle null move scores that //suggest a
>mate by
> // increasing depth and researching
>}
>
>
>Reference
>
>C. Donninger
>ICCA Journal, Vol 16, no. 3, 1993
>pp 137 - 143
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.