Generation of moves is a basic part of a chess engine with many variations concerning a generator or an iterator to loop over moves inside the search routine. The implementation heavily depends on the board representation, and it can be generalized into two types, pseudo-legal and legal move generation.
In Pseudo-legal move generation pieces obey their normal rules of movement, but they're not checked beforehand to see if they'll leave the king in check. It is left up to the move-making function to test the move, or it is even possible to let the king remain in check and only test for the capture of the king on the next move.
Legal
In Legal move generation, as the name implies, only legal moves are generated, which means extra time must be spent to make sure the king isn't going to be left or placed in check after each move. Pins are the main difficulty, particularly when en passant is involved.
Special Generators
Most programs use special move generators for the quiescence search, sometimes supplemented by one for getting out of 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 and promotions. They can use the fact that a knight or bishop must start off on the 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 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, only king moves are permitted.
Some programs do not generate all moves at once, but do it in several stages (i.e. hash move first, then captures, then 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 [2].
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 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 table of values to test its accuracy.
Carl Ebeling, Andrew James Palay (1984). The Design and Implementation of a VLSI Chess Move Generator. Proceedings of the 11th Annual International Symposium on Computer Architecture. IEEE and ACM.
Reijer Grimbergen, Hitoshi Matsubara (2001). Plausible Move Generation in Two-Player Complete Information Games Using Static Evaluation. Transactions of the Japanese Society for Artificial Intelligence, Vol.16, pp. 55-62. pdf
Table of Contents
Legality
Pseudo-legal
In Pseudo-legal move generation pieces obey their normal rules of movement, but they're not checked beforehand to see if they'll leave the king in check. It is left up to the move-making function to test the move, or it is even possible to let the king remain in check and only test for the capture of the king on the next move.Legal
In Legal move generation, as the name implies, only legal moves are generated, which means extra time must be spent to make sure the king isn't going to be left or placed in check after each move. Pins are the main difficulty, particularly when en passant is involved.Special Generators
Most programs use special move generators for the quiescence search, sometimes supplemented by one for getting out of 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 and promotions. They can use the fact that a knight or bishop must start off on the 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 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, only king moves are permitted.
Chunk move generation
With 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 lists (i.e. for tactical and quiet moves), which is convenient for book-keeping and assigning scores based on MVV-LVA, SEE, history, piece square table etc., to later perform a selection sort before actually making the move.Staged move generation
Some programs do not generate all moves at once, but do it in several stages (i.e. hash move first, then captures, then 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 [2].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 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 table of values to test its accuracy.See also
General
Board Array
0x88
Vector Attacks
Bitboards
Hardware
Chess Programs
Publications
1950 ...
1970 ...
1980 ...
1990 ...
2000 ...
2010 ...
Forum Posts
1990 ...
Re: move generators in computer chess, Tricky bit tricks by Marcel van Kervinck, rgcc, October 20, 1994 » Traversing Subsets of a Set
2000 ...
2005 ...
Re: Move generation: staged vs all-at-once by Lance Perkins, CCC, April 30, 2009
2010 ...
- Assembly move generation in Freccia by Stefano Gemma, CCC, July 26, 2011
2012- move generation speed by Folkert van Heusden, Winboard Forum, January 03, 2012
- Is there such a thing as branchless move generation? by John Hamlen, CCC, June 07, 2012 » DirGolem, GPU
- hyper threading and move generation by Gabor Buella, CCC, August 01, 2012
- What's the fastest move generator? by Marcel Fournier, CCC, August 29, 2012
- Re: Question About CPP-C#, Performance, and Square Representation by Erik Madsen, CCC, October 03, 2012 » MadChess [4] [5]
- Plausible move generator by Jorge Garcia, CCC, November 09, 2012
- Diepeveen's move generator by Hrvoje Horvatic, CCC, November 18, 2012 » Table-driven Move Generation
20142015 ...
- On bitboard legal move generation by Lasse Hansen, CCC, February 09, 2015
- Questions about chess programming from a newbie by Matt Palmer, CCC, April 18, 2015
- Caching generated moves list in recursive searches by Rein Halbersma, CCC, May 10, 2015
2016- speed up your engine part 4 by Laurie Tunnicliffe, CCC, August 03, 2016 » Staged move generation
- Performance diff between legal / illegal move generator by Mahmoud Uthman, CCC, October 22, 2016
2017External Links
generate.c by Scott Gasch
References
What links here?
Up one level