Move Generation
Home * Board Representation * Move Generation
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.
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
Bitboards
Hardware
Chess Programs
- Move Generation in Atlas
- Move Generation in CPW-Engine
- Move Generation in MadChess
- Move Generation in Rajah
- Move Generation in Thor's Hammer
- Move Generation in Tinker
- Move Generation in TSCP
- Move Generation in Vanilla Chess
- Table-driven Move Generation in Ferret
- Table-driven Move Generation in GNU Chess
Publications
1950 ...
- Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium
1970 ...
- Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
- Gerard Zieliński (1976). Arrays for Programming Chess. Kybernetes, Vol. 5, No. 2
- Ozalp Babaoglu (1977). Hardware implementation of the legal move generation and relative ordering functions for the game of chess. Master's thesis, University of California, Berkeley
- Peter W. Frey (1977). An Introduction to Computer Chess. Chess Skill in Man and Machine pp. 54-81
1980 ...
- Joe Condon, Ken Thompson (1982). Belle Chess Hardware, Advances in Computer Chess 3, Reprinted (1988) in Computer Chess Compendium
- Greg Bakker, Jim Jonkman, Jonathan Schaeffer, Tom Schultz (1982). VLSI Implementation of a Chess Legal Move Generator. EE755S-1, University of Waterloo [3]
- Jonathan Schaeffer, Patrick A.D. Powell, Jim Jonkman (1983). A VLSI legal move generator for the game of chess. in Randal Bryant (eds.) Third Caltech Conference on Very Large Scale Integration
- 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.
- Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3
- Burton Wendroff (1985). Attack Detection and Move Generation on the X-MP/48. ICCA Journal, Vol. 8, No. 2
- Carl Ebeling (1986). All the Right Moves: A VLSI Architecture for Chess. Ph.D. thesis, Carnegie Mellon University, MIT Press, Cambridge, MA. ISBN 0-262-05035-8.
- Feng-hsiung Hsu (1986). Two designs of functional units for VLSI based chess machines. Carnegie Mellon University, Computer Science Department. Paper 1566.
- Feng-hsiung Hsu (1987). A Two-Million Moves/Sec CMOS Single-Chip Chess Move Generator. IEEE J. of Solid-state Circuits, Vol. 22, No. 5, pp. 841-846.
1990 ...
- James Testa, Alvin M. Despain (1990). A CMOS VLSI chess microprocessor. University of California, Berkeley, IEEE Custom Integrated Circuit Conference
- Chun Ye (1992). Experiments in Selective Search Extensions. MSc. thesis, Department of Computing Science, University of Alberta, pdf
- Yi-Fan Ke, Tai-Ming Parng (1996). Parallel Move Generation System for Computer Chess. IEICE Transactions on Information and Systems, April, 1996, pp. 290-296
- Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
- Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
- Feng-hsiung Hsu (1999). IBM’s Deep Blue Chess Grandmaster Chips. pdf
2000 ...
- 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
- Marc Boulé (2002). An FPGA Move Generator for the Game of Chess. Masters thesis, McGill University, (Supervisor: Zeljko Zilic, Co-Supervisor: Monty Newborn), pdf
- Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. McGill University, pdf » FPGA
- Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. ICGA Journal, Vol. 25, No. 2, pdf
- Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf, was topic of the 11th Game Programming Workshop
- Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, pdf
2010 ...
- Adrien Couetoux, Olivier Teytaud, Hassen Doghmen (2012). Learning a Move-Generator for Upper Confidence Trees. ICS 2012, Hualien, Taiwan, December 2012 » Learning, UCT
Forum Posts
1990 ...
- move generators in computer chess by Deniz Yuret, rgcc, October 11, 1994
- Re: move generators in computer chess, Tricky bit tricks by Marcel van Kervinck, rgcc, October 20, 1994 » Traversing Subsets of a Set
- bitboard move generation by Robert Hyatt, rgc, October 25, 1994
- move generators in computer chess by Joël Rivat, rgc, October 26, 1994
- bitboard move generator by Joël Rivat, rgc, November 13, 1994
- Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995
- Move generator design choices by Martin Borriss, rgcc, April 26, 1996
- Sane numbers by Martin Borriss, rgcc, June 26, 1996
- GNU move generation by Jan Willem de Kort, rgcc, March 18, 1998 » GNU Chess
2000 ...
- Fast BB move generation by Bas Hamstra, CCC, May 08, 2000
- move_generation + hash by Georg von Zimmermann, CCC, May 28, 2000
- Pre-calculated move generation by Ujecrh, CCC, June 26, 2000
- Move generation question for the big boys by Sune Fischer, CCC, September 15, 2001
- Precomputed move information by Sune Fischer, CCC, July 02, 2002
- Natural move generation with bitboards (was Re:significant math) by Alessandro Damiani, CCC, November 20, 2002
- Strength question by Bruce Moreland, CCC, January 05, 2003
- Which open source chess program has the fastest move generator? by Dennis Breuker, CCC, April 25, 2003
- Improvements in BF makes my MoveGen suck =( by Albert Bertilsson, CCC, June 26, 2003 » Branching Factor
- Speed improvement in split move generation by Federico Corigliano, CCC, August 16, 2003
- Move Generation Speed by Dan Honeycutt, Winboard Forum, October 21, 2004
2005 ...
- Is it time for another new move generator? by Michael Sherwin, CCC, November 11, 2007
- Did someone mention the GNUChess move Generator? by Michael Sherwin, CCC, November 12, 2007 » GNU Chess
- Move generator by kongsian, CCC, April 12, 2008
- Bitboards / move generation on larger boards by Gregory Strong, CCC, January 09, 2009
- Move generation: staged vs all-at-once by Steven Edwards, CCC, April 30, 2009
- 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
2014
- Just another movegen by Syed Fahad, CCC, November 14, 2014
- How to call the Satana move generation by Stefano Gemma, CCC, November 17, 2014 » Satana
- Black/White symmetry in move generation by Jeffery A Esposito, CCC, November 25, 2014 » Color Flipping
- Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
- Reverse move generation by Kostas Oreopoulos, December 30, 2014 » Retrograde Analysis
2015 ...
- 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
- An approach to precomputed move generation bitboards by Michael Sherwin, CCC, December 01, 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
2017
- Most efficient way to generate legal king moves? by notachessplayer, OpenChess Forum, February 04, 2017
- Back to the basics, generating moves on gpu in parallel... by Srdja Matovic, CCC, March 05, 2017 » GPU
- Fastest pawn quiet move generation I was able to come with by Daniel José Queraltó, CCC, June 10, 2017 » Duff's Device
- History heuristic and quiet move generation by Daniel José Queraltó, CCC, July 16, 2017 » History Heuristic
- Skipping duplicat moves by Harm Geert Muller, CCC, December 03, 2017
2019
- Opinions requested for new move gen idea by Michael Sherwin, CCC, March 03, 2019 » Table-driven Move Generation
- My newest almost bb move generator is wonderful by Michael Sherwin, CCC, April 17, 2019
- Efficient capture generation in the game of Thud by koedem, CCC, April 18, 2019
External Links
- Chapter 3: Board Games - 3.1 CHESS from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
- Description of 0x88 method from Bruce Moreland's Programming Topics
- Move Table move generation from Bruce Moreland's Programming Topics
- How Zarkov Plays Chess by John Stanback
- Monsoon/Typhoon Homepage by Scott Gasch, covers 0x88 move generation
- Description of Rotated Bitboards by Robert Hyatt
- Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of magic Move Generator
- Chess Programming Part III: Move Generation by François-Dominic Laramée, gamedev.net, July 2000
- Chess Move Generator - Computer Architecture and Languages Laboratory, University of Maribor
- Engine - Hispanic Chess Engines | The move generator by Pedro Castro
- Generator (computer programming) from Wikipedia
References
- ↑ electric driven air compressor in the machine hall of Zollern II/IV Colliery, Dortmund Bövinghausen, Germany - part of The Industrial Heritage Trail, Photo by Gerd Isenberg, September 18, 2016
- ↑ Move generation: staged vs all-at-once by Steven Edwards, CCC, April 30, 2009
- ↑ 1983 | Waking up to change in Chris Redmond and Simon the Troll (1998). Water Under the Bridge. University of Waterloo » VLSI Move Generation
- ↑ yield - MSDN C# Reference
- ↑ Behind the scenes of the C# yield keyword | Struggles by Lars Corneliussen, June 9, 2008