25,161
edits
Changes
no edit summary
=Special Generators=
Most programs use special move generators for the [[Quiescence Search|quiescence search]], sometimes supplemented by one for getting out of [[Check|check]]. These special cases can be made more efficient than generating and testing each possible move to fit specific criteria. For example, if the king is in check, the only possible legal moves are to capture the attacking piece, block the attacker if it is a "ray" piece, or move the king to safety. Special generators for the quiescence search might want to generate checks in addition to [[Captures|captures]] and [[Promotions|promotions]]. They can use the fact that a knight or bishop must start off on the [[Color of a Square#SameColor|same color square]] as the opponent king if they are to attack it. And rooks can only generate at most 2 checking moves...to the [[Intersection Squares|squares]] with the rook's column and the king's row or the king's column and the rooks row.
Similar tricks can be used for generating possible moves out of check, which must be by the king, capturing the opponent's checking piece, or blocking its attack if it is a ray piece. When in [[Double Check|double check]], only king moves are permitted.
=Chunk move generationMove Generation=
With [[Move Ordering|move ordering]] in mind, chess programs, while traversing pieces and their move-target sets once, store and buffer generated moves inside one or two [[Move List|move lists]] (i.e. for [[Tactical Moves|tactical]] and [[Quiet Moves|quiet moves]]), which is convenient for book-keeping and assigning scores based on [[MVV-LVA]], [[Static Exchange Evaluation|SEE]], [[History Heuristic|history]], [[Piece-Square Tables|piece square table]] etc., to later perform a [https://en.wikipedia.org/wiki/Selection_sort selection sort] before actually [[Make Move|making the move]].
<span id="Staged"></span>
=Staged move generationMove Generation=
Some programs do not generate all moves at once, but do it in several stages (i.e. [[Hash Move|hash move]] first, then [[Captures|captures]], then [[Killer Move|killer moves]], then all the rest in a chunk) on the premise that if one of the early moves causes a cutoff, then we may save on the effort of generating the rest of the moves <ref>[http://www.talkchess.com/forum/viewtopic.php?t=27657 Move generation: staged vs all-at-once] by [[Steven Edwards]], [[CCC]], April 30, 2009</ref>.
=Debugging=
It is important to ensure that the move generator works properly. Although this could be tested by playing many games, a better approach is to write a [[Perft]] function. This function [[Recursion|recursively]] generates moves for the current position and all children up to a certain depth, and by counting all the leaf nodes, it can be compared to a [[Perft Results|table of values]] to test its accuracy.
<span id="Reverse"></span>
=Reverse Move Generation=
'''Reverse Move Generation''', also called '''Un-Move Generation''' produces a list of all possible moves (including [[Captures|captures]] and [[Promotions|promotions]]) which could be [[Unmake Move|un-made]] from a target position to reach all legal predecessor or parent positions for [[Retrograde Analysis|retrograde analysis]] tasks.
=See also=
* [http://www.talkchess.com/forum/viewtopic.php?t=54465 Black/White symmetry in move generation] by Jeffery A Esposito, [[CCC]], November 25, 2014 » [[Color Flipping]]
* [http://www.talkchess.com/forum/viewtopic.php?t=54704 Symmetric move generation using bitboards] by [[Lasse Hansen]], [[CCC]], December 20, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54796 Reverse move generation] by Kostas Oreopoulos, [[CCC]], December 30, 2014 » [[Move Generation#Reverse|Reverse Move Generation]], [[Retrograde Analysis]]
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=55275 On bitboard legal move generation] by [[Lasse Hansen]], [[CCC]], February 09, 2015
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78084 Legal or pseudolegal move generator?] by Pier Carlo, [[CCC]], September 03, 2021
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=78164 Distinguish rook and bishop move efficiently] by [[Guido Flohr]], [[CCC]], September 14, 2021
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78913 Fast reverse move generation] by koedem, [[CCC]], December 18, 2021 » [[Move Generation#Reverse|Reverse Move Generation]], [[Retrograde Analysis]]
: [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78913&start=1 Re: Fast reverse move generation] by [[Peter Österlund]], [[CCC]], December 18, 2021 » [[Texel]]
=External Links=
