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.

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 [1] [2] .

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


Publications


Forum Posts

2005 ...

2010 ...

2015 ...


External Links


References

  1. ^ Search Techniques in REBEL (Lazy Eval) from How Rebel Plays Chess by Ed Schröder
  2. ^ Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008

What links here?


Up one Level