Incremental Updates
Home * Chess * Position * Incremental Updates
Incremental updates keep global or shared structures up to date after making and unmaking moves on the internal board, likely inside a depth-first, alpha-beta like search-algorithm. Incremental update on the same global or shared data ever and ever, will likely keep it in fast cache memory, and saves memory bandwidth compared to a Copy-Make approach, which needs a make-update on the copy as well, but no unmake-update rather than decrementing a ply-index or fetching a pointer.
Contents
Chess Position
Incremental updates by make/unmake are obligatory for square centric board arrays like mailbox and 0x88 along with their piece-lists, as well for the classical bitboard board-definition. A move only affects a small fraction of the complete board structure and the update cost is small compared to a copy of the whole board. Also one usually doesn't need an array of boards for random access, but only the current one.
However, there are aspects of a chess position, which can not generally restored from a child-position by unmaking a move, and which therefor need to be restored by either re-playing the whole game record from the root position, or to be memorized inside an array indexed by ply or on a stack (LIFO), most notably ep state, castling rights and the halfmove clock enforcing the fify-move rule. Also, if one doesn't keep a captured piece (if any) inside the move object, one has to memorize those pieces elsewhere as well, to restore the target square of the move about to unmake.
Material and Hash keys
Subject of incremental updates are further data which only change conditionally on certain move types, like material signature, only affected by captures or promotions, or for instance zobrist keys for a pawn hash table, only affected by moving/capturing pawns. Standard zobrist keys for TT purpose and dependent on ep state and castling rights, are slightly more complicated to restore. If stored inside a record anyway to detect repetitions, one has the option to restore the key after unmake from that record.
It is a good idea to compare incremental updated stuff like zobrist keys with its from scratch generated counterparts for debug purposes.
Evaluation
Other global structures or variables as candidates of an incremental update are related to Evaluation, beside the mentioned material (balance), lazy evaluation terms, like the sum of all piece-square values [2] [3] .
Attack table
Some programs keep Attack and Defend Maps up to date incrementally, which is runtime dependent on the number of squares whose attacks-to are influenced by the move. Due to its size and utilization, copy-make is no issue, but on the fly generation if actually needed.
See also
- Attack and Defend Maps
- BCH Hashing
- Bitboard Update By Move
- Color Flipping
- Copy-Make
- Encoding Moves
- Lazy Evaluation
- Make Move
- Material
- NNUE
- Unmake Move
- Zobrist Hashing
Publications
- John J. Scott (1969). A chess-playing program. Machine Intelligence Vol. 4
- David Slate, Larry Atkin (1977). Chess 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
- Peter W. Frey (1983). The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning. Computer Game-Playing (ed. Max Bramer), pp. 285-289. Ellis Horwood Limited
Forum Posts
2005 ...
- Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008
- Incremental Zobrist - slow? by Vlad Stamate, CCC, June 20, 2009 » Zobrist Hashing
- undo move vs. Position Cloning by BoldReceiver, CCC, September 16, 2009
- Re: undo move vs. Position Cloning by Don Dailey, CCC, September 16, 2009 » Doch
2010 ...
- Incremental or non-incremental PST evaluation calcs by Mark Pearce, CCC, January 26, 2012 » Piece-Square Tables
- copy/make vs make/unmake by Robert Hyatt, CCC, January 07, 2014
- Incrementally-updated attack map by Harm Geert Muller, April 21, 2014 » Attack and Defend Maps
- Memory usage in make/unmake vs logic complexity by Matthew Lai, CCC, August 30, 2014
2015 ...
- Incremental update by Matthew R. Brades, CCC, December 19, 2015
- The Inferno thread by Harm Geert Muller, CCC, March 06, 2017 » Tenjiku Shogi
- How to incrementally update attack tables? by Maksim Korzh, CCC, November 21, 2018 » Attack and Defend Maps
External Links
- Search Techniques in REBEL (Lazy Eval) from How Rebel Plays Chess by Ed Schröder » Lazy Evaluation, Rebel
