Author: William Bryant
Date: 17:10:09 05/14/99
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.