25,161
edits
Changes
Created page with "'''Home * Chess * Position * Incremental Updates''' '''Incremental updates''' keep global or shared structures up to date after Make Mo..."
'''[[Main Page|Home]] * [[Chess]] * [[Chess Position|Position]] * Incremental Updates'''
'''Incremental updates''' keep global or shared structures up to date after [[Make Move|making]] and [[Unmake Move|unmaking]] [[Moves|moves]] on the [[Board Representation|internal board]], likely inside a [[Depth-First|depth-first]], [[Alpha-Beta|alpha-beta]] like [[Search|search-algorithm]]. Incremental update on the same global or shared data ever and ever, will likely keep it in fast cache memory, and saves [https://en.wikipedia.org/wiki/Memory_bandwidth 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|ply-index]] or fetching a pointer.
=Chess Position=
Incremental updates by make/unmake are obligatory for square centric board [[Array|arrays]] like [[Mailbox|mailbox]] and [[0x88]] along with their [[Piece-Lists#IncrementalUpdate|piece-lists]], as well for the classical [[Bitboard Board-Definition|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|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|array]] indexed by [[Ply|ply]] or on a [[Stack|stack]] ([https://en.wikipedia.org/wiki/LIFO_(computing) LIFO]), most notably [[En passant|ep state]], [[Castling rights|castling rights]] and the [[Halfmove Clock|halfmove clock]] enforcing the [[Fifty-move Rule|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|material]] signature, only affected by [[Captures|captures]] or [[Promotions|promotions]], or for instance [[Zobrist Hashing|zobrist keys]] for a [[Pawn Hash Table|pawn hash table]], only affected by moving/capturing pawns. Standard zobrist keys for [[Transposition Table|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|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 [[Debugging|debug]] purposes.
=Evaluation=
Other global structures or variables as candidates of an incremental update are related to [[Evaluation]], beside the mentioned [[Material|material]] (balance), [[Lazy Evaluation|lazy evaluation]] terms, like the sum of all [[Piece-Square Tables|piece-square values]] <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#LAZY%20EVAL Search Techniques in REBEL (Lazy Eval)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008</ref> .
=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]]
* [[General Setwise Operations#UpdateByMove|Bitboard Update By Move]]
* [[Color Flipping]]
* [[Copy-Make]]
* [[Encoding Moves]]
* [[Lazy Evaluation]]
* [[Make Move]]
* [[Material]]
* [[Unmake Move]]
* [[Zobrist Hashing]]
=Publications=
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence Vol. 4]
* [[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 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=28523 Incremental Zobrist - slow?] by [[Vlad Stamate]], [[CCC]], June 20, 2009 » [[Zobrist Hashing]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29770 undo move vs. Position Cloning] by BoldReceiver, [[CCC]], September 16, 2009
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=291570&t=29770 Re: undo move vs. Position Cloning] by [[Don Dailey]], [[CCC]], September 16, 2009 » [[Doch]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=42167 Incremental or non-incremental PST evaluation calcs] by [[Mark Pearce]], [[CCC]], January 26, 2012 » [[Piece-Square Tables]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50805 copy/make vs make/unmake] by [[Robert Hyatt]], [[CCC]], January 07, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=52085 Incrementally-updated attack map] by [[Harm Geert Muller]], April 21, 2014 » [[Attack and Defend Maps]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53502 Memory usage in make/unmake vs logic complexity] by [[Matthew Lai]], [[CCC]], August 30, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=58628 Incremental update] by [[Matthew R. Brades]], [[CCC]], December 19, 2015
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#LAZY%20EVAL Search Techniques in REBEL (Lazy Eval)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]] » [[Lazy Evaluation]], [[Rebel]]
* [https://en.wikipedia.org/wiki/Frumpy Frumpy] - Life Without Pain, [https://www.discogs.com/Frumpy-All-Will-Be-Changed/master/209708 All Will Be Changed] (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=NAlJ0llUDVc|alignment=left|valignment=top}}
=References=
<references />
'''[[Chess Position|Up one Level]]'''
'''Incremental updates''' keep global or shared structures up to date after [[Make Move|making]] and [[Unmake Move|unmaking]] [[Moves|moves]] on the [[Board Representation|internal board]], likely inside a [[Depth-First|depth-first]], [[Alpha-Beta|alpha-beta]] like [[Search|search-algorithm]]. Incremental update on the same global or shared data ever and ever, will likely keep it in fast cache memory, and saves [https://en.wikipedia.org/wiki/Memory_bandwidth 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|ply-index]] or fetching a pointer.
=Chess Position=
Incremental updates by make/unmake are obligatory for square centric board [[Array|arrays]] like [[Mailbox|mailbox]] and [[0x88]] along with their [[Piece-Lists#IncrementalUpdate|piece-lists]], as well for the classical [[Bitboard Board-Definition|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|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|array]] indexed by [[Ply|ply]] or on a [[Stack|stack]] ([https://en.wikipedia.org/wiki/LIFO_(computing) LIFO]), most notably [[En passant|ep state]], [[Castling rights|castling rights]] and the [[Halfmove Clock|halfmove clock]] enforcing the [[Fifty-move Rule|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|material]] signature, only affected by [[Captures|captures]] or [[Promotions|promotions]], or for instance [[Zobrist Hashing|zobrist keys]] for a [[Pawn Hash Table|pawn hash table]], only affected by moving/capturing pawns. Standard zobrist keys for [[Transposition Table|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|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 [[Debugging|debug]] purposes.
=Evaluation=
Other global structures or variables as candidates of an incremental update are related to [[Evaluation]], beside the mentioned [[Material|material]] (balance), [[Lazy Evaluation|lazy evaluation]] terms, like the sum of all [[Piece-Square Tables|piece-square values]] <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#LAZY%20EVAL Search Techniques in REBEL (Lazy Eval)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]]</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008</ref> .
=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]]
* [[General Setwise Operations#UpdateByMove|Bitboard Update By Move]]
* [[Color Flipping]]
* [[Copy-Make]]
* [[Encoding Moves]]
* [[Lazy Evaluation]]
* [[Make Move]]
* [[Material]]
* [[Unmake Move]]
* [[Zobrist Hashing]]
=Publications=
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence Vol. 4]
* [[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 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=28523 Incremental Zobrist - slow?] by [[Vlad Stamate]], [[CCC]], June 20, 2009 » [[Zobrist Hashing]]
* [http://www.talkchess.com/forum/viewtopic.php?t=29770 undo move vs. Position Cloning] by BoldReceiver, [[CCC]], September 16, 2009
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=291570&t=29770 Re: undo move vs. Position Cloning] by [[Don Dailey]], [[CCC]], September 16, 2009 » [[Doch]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=42167 Incremental or non-incremental PST evaluation calcs] by [[Mark Pearce]], [[CCC]], January 26, 2012 » [[Piece-Square Tables]]
* [http://www.talkchess.com/forum/viewtopic.php?t=50805 copy/make vs make/unmake] by [[Robert Hyatt]], [[CCC]], January 07, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=52085 Incrementally-updated attack map] by [[Harm Geert Muller]], April 21, 2014 » [[Attack and Defend Maps]]
* [http://www.talkchess.com/forum/viewtopic.php?t=53502 Memory usage in make/unmake vs logic complexity] by [[Matthew Lai]], [[CCC]], August 30, 2014
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=58628 Incremental update] by [[Matthew R. Brades]], [[CCC]], December 19, 2015
=External Links=
* [http://www.top-5000.nl/authors/rebel/chess840.htm#LAZY%20EVAL Search Techniques in REBEL (Lazy Eval)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]] » [[Lazy Evaluation]], [[Rebel]]
* [https://en.wikipedia.org/wiki/Frumpy Frumpy] - Life Without Pain, [https://www.discogs.com/Frumpy-All-Will-Be-Changed/master/209708 All Will Be Changed] (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=NAlJ0llUDVc|alignment=left|valignment=top}}
=References=
<references />
'''[[Chess Position|Up one Level]]'''
