Difference between revisions of "Incremental Updates"

From Chessprogramming wiki
Jump to: navigation, search
 
(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Chess]] * [[Chess Position|Position]] * Incremental Updates'''
 
'''[[Main Page|Home]] * [[Chess]] * [[Chess Position|Position]] * Incremental Updates'''
  
[[FILE:Kandinsky - Mouvement I.jpg|border|right|thumb| [[Arts#Kandinsky|Wassily Kandinsky]] - Mouvement I <ref>[https://commons.wikimedia.org/wiki/File:Kandinsky_-_Mouvement_I.jpg Wassily Kandinsky - Mouvement I], [https://en.wikipedia.org/wiki/Tretyakov_Gallery Tretyakov Gallery]</ref> ]]
+
[[FILE:Kandinsky - Mouvement I.jpg|border|right|thumb| [[:Category:Wassily Kandinsky|Wassily Kandinsky]] - Mouvement I <ref>[https://commons.wikimedia.org/wiki/File:Kandinsky_-_Mouvement_I.jpg Wassily Kandinsky - Mouvement I], [https://en.wikipedia.org/wiki/Tretyakov_Gallery Tretyakov Gallery]</ref> ]]
  
 
'''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.
 
'''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.
Line 31: Line 31:
 
* [[Make Move]]
 
* [[Make Move]]
 
* [[Material]]
 
* [[Material]]
 +
* [[NNUE]]
 
* [[Unmake Move]]
 
* [[Unmake Move]]
 
* [[Zobrist Hashing]]
 
* [[Zobrist Hashing]]
Line 36: Line 37:
 
=Publications=  
 
=Publications=  
 
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html Machine Intelligence Vol. 4]
 
* [[John J. Scott]] ('''1969'''). ''A chess-playing program''. [http://www.doc.ic.ac.uk/~shm/MI/mi4.html 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
 
* [[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
  
Line 51: Line 53:
 
==2015 ...==  
 
==2015 ...==  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=58628 Incremental update] by [[Matthew R. Brades]], [[CCC]], December 19, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=58628 Incremental update] by [[Matthew R. Brades]], [[CCC]], December 19, 2015
 +
* [http://www.talkchess.com/forum3/viewtopic.php?t=63356 The Inferno thread] by [[Harm Geert Muller]], [[CCC]], March 06, 2017 » [[Shogi#Tenjiku|Tenjiku Shogi]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=68995 How to incrementally update attack tables?] by [[Maksim Korzh]], [[CCC]], November 21, 2018 » [[Attack and Defend Maps]]
  
 
=External Links=  
 
=External Links=  

Latest revision as of 18:21, 25 February 2021

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 [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

Publications

Forum Posts

2005 ...

Re: undo move vs. Position Cloning by Don Dailey, CCC, September 16, 2009 » Doch

2010 ...

2015 ...

External Links

References

Up one Level