Difference between revisions of "Move Generation"

From Chessprogramming wiki
Jump to: navigation, search
 
(20 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Board Representation]] * Move Generation'''
 
'''[[Main Page|Home]] * [[Board Representation]] * Move Generation'''
  
[[FILE:GenratorZecheZollern.JPG|border|right|thumb|link=https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Kompressormotor.jpg?uselang=en| Blast Generation <ref>[https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Kompressormotor.jpg?uselang=en electric driven air compressor] in the [https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Dortmund_-_Maschinenhalle.jpg?uselang=en machine hall] of [[:Category:Zollern|Zollern II/IV Colliery]], [https://en.wikipedia.org/wiki/Dortmund Dortmund] [https://de.wikipedia.org/wiki/B%C3%B6vinghausen_(Dortmund) Bövinghausen], Germany - part of [[:Category:Industrial Heritag Trail|The Industrial Heritage Trail]], Photo by [[Gerd Isenberg]], September 18, 2016</ref>  ]]  
+
[[FILE:GenratorZecheZollern.JPG|border|right|thumb|link=https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Kompressormotor.jpg?uselang=en| Blast Generation <ref>[https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Kompressormotor.jpg?uselang=en electric driven air compressor] in the [https://commons.wikimedia.org/wiki/File:Zeche_Zollern_Dortmund_-_Maschinenhalle.jpg?uselang=en machine hall] of [[:Category:Zollern|Zollern II/IV Colliery]], [https://en.wikipedia.org/wiki/Dortmund Dortmund] [https://de.wikipedia.org/wiki/B%C3%B6vinghausen_(Dortmund) Bövinghausen], Germany - part of [[:Category:Industrial Heritage Trail|The Industrial Heritage Trail]], Photo by [[Gerd Isenberg]], September 18, 2016</ref>  ]]  
  
 
'''Generation''' of [[Moves|moves]] is a basic part of a chess engine with many variations concerning a [https://en.wikipedia.org/wiki/Generator_%28computer_programming%29 generator] or an [https://en.wikipedia.org/wiki/Iterator_pattern iterator] to loop over moves inside the [[Search|search]] routine. The implementation heavily depends on the [[Board Representation|board representation]], and it can be generalized into two types, pseudo-legal and legal move generation.  
 
'''Generation''' of [[Moves|moves]] is a basic part of a chess engine with many variations concerning a [https://en.wikipedia.org/wiki/Generator_%28computer_programming%29 generator] or an [https://en.wikipedia.org/wiki/Iterator_pattern iterator] to loop over moves inside the [[Search|search]] routine. The implementation heavily depends on the [[Board Representation|board representation]], and it can be generalized into two types, pseudo-legal and legal move generation.  
Line 13: Line 13:
  
 
=Special Generators=  
 
=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.  
+
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.
 
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 generation=
+
=Chunk Move 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]].
 
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>
 
<span id="Staged"></span>
=Staged move generation=  
+
=Staged Move 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>.
 
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=  
 
=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.
 
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>
 +
=Un-Move Generation=
 +
'''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 possible legal predecessor or parent positions for [[Retrograde Analysis|retrograde analysis]] tasks.
  
 
=See also=
 
=See also=
Line 77: Line 80:
 
==1980 ...==
 
==1980 ...==
 
* [[Joe Condon]], [[Ken Thompson]] ('''1982'''). ''Belle Chess Hardware'', [[Advances in Computer Chess 3]], Reprinted ('''1988''') in [[Computer Chess Compendium]]
 
* [[Joe Condon]], [[Ken Thompson]] ('''1982'''). ''Belle Chess Hardware'', [[Advances in Computer Chess 3]], Reprinted ('''1988''') in [[Computer Chess Compendium]]
* <span id="Waterloo1982"></span>[[Greg Bakker]], [[Jim Jonkman]], [[Jonathan Schaeffer]], [[Tom Schultz]] ('''1982'''). ''VLSI Implementation of a Chess Legal Move Generator''. EE755S-1, [[University of Waterloo]] <ref>[https://uwaterloo.ca/water-under-the-bridge/1983 1983 | Waking up to change] in [https://uwaterloo.ca/water-under-the-bridge/about-authors Chris Redmond and Simon the Troll] ('''1998'''). ''[https://uwaterloo.ca/water-under-the-bridge/ Water Under the Bridge]''. [[University of Waterloo]] » [[Move Generation#Waterloo1982|VLSI Move Generation]]</ref>
+
* <span id="Waterloo1982"></span>[[Greg Bakker]], [[Jim Jonkman]], [[Jonathan Schaeffer]], [[Tom Schultz]] ('''1982'''). ''VLSI Implementation of a Chess Legal Move Generator''. EE755S-1, [[University of Waterloo]] <ref>[https://uwaterloo.ca/water-under-the-bridge/1983 1983 | Waking up to change] in [https://uwaterloo.ca/water-under-the-bridge/about-authors Chris Redmond and Simon the Troll] ('''1998'''). ''[https://uwaterloo.ca/water-under-the-bridge/ Water Under the Bridge]''. [[University of Waterloo]] » [[#Waterloo1982|VLSI Move Generation]]</ref>
* [[Jonathan Schaeffer]], [[Patrick A.D. Powell]], [[Jim Jonkman]] ('''1983'''). ''[https://link.springer.com/chapter/10.1007/978-3-642-95432-0_19 A VLSI legal move generator for the game of chess]''. in [https://en.wikipedia.org/wiki/Randal_Bryant Randal Bryant] (eds.) [https://link.springer.com/book/10.1007%2F978-3-642-95432-0 Third Caltech Conference on Very Large Scale Integration]  
+
* [[Jonathan Schaeffer]], [[Patrick A.D. Powell]], [[Jim Jonkman]] ('''1983'''). ''[https://link.springer.com/chapter/10.1007/978-3-642-95432-0_19 A VLSI legal move generator for the game of chess]''. in [[Mathematician#REBryant|Randal E. Bryant]] (eds.) [https://link.springer.com/book/10.1007%2F978-3-642-95432-0 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]].
 
* [[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''. [[ICGA Journal#7_3|ICCA Journal, Vol. 7, No. 3]]
 
* [[Stuart Cracraft]] ('''1984'''). ''Bitmap move generation in Chess''. [[ICGA Journal#7_3|ICCA Journal, Vol. 7, No. 3]]
Line 126: Line 129:
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=331 Move Generation Speed] by [[Dan Honeycutt]], [[Computer Chess Forums|Winboard Forum]], October 21, 2004
 
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=331 Move Generation Speed] by [[Dan Honeycutt]], [[Computer Chess Forums|Winboard Forum]], October 21, 2004
 
==2005 ...==
 
==2005 ...==
 +
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623 Yet another new bitboard move generation method] by [[Zach Wegner]], [[Computer Chess Forums|Winboard Forum]], September 22, 2006 » [[Titboards]]
 +
: [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=5623&start=6 Re: Yet another new bitboard move generation method] by [[Harm Geert Muller]], [[Computer Chess Forums|Winboard Forum]], October 01, 2006 <ref>[http://www.talkchess.com/forum3/viewtopic.php?f=7&t=52861&start=8 Re: multi-dimensional piece/square tables] by Tony P., [[CCC]], January 28, 2020</ref>
 
* [http://www.talkchess.com/forum/viewtopic.php?t=17790 Is it time for another new move generator?] by [[Michael Sherwin]], [[CCC]], November 11, 2007  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=17790 Is it time for another new move generator?] by [[Michael Sherwin]], [[CCC]], November 11, 2007  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=17820 Did someone mention the GNUChess move Generator?] by [[Michael Sherwin]], [[CCC]], November 12, 2007 » [[GNU Chess]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=17820 Did someone mention the GNUChess move Generator?] by [[Michael Sherwin]], [[CCC]], November 12, 2007 » [[GNU Chess]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=19837 compact bitboard move generator] by [[Robert Hyatt]], [[CCC]], February 25, 2008 » [[Bitboard Serialization]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=20630 Move generator] by [[Chua Kong Sian|kongsian]], [[CCC]], April 12, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=20630 Move generator] by [[Chua Kong Sian|kongsian]], [[CCC]], April 12, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=25917 Bitboards / move generation on larger boards] by [[Gregory Strong]], [[CCC]], January 09, 2009  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=25917 Bitboards / move generation on larger boards] by [[Gregory Strong]], [[CCC]], January 09, 2009  
Line 147: Line 153:
 
* [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=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=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, December 30, 2014 » [[Retrograde Analysis]]
+
* [http://www.talkchess.com/forum/viewtopic.php?t=54796 Reverse move generation] by Kostas Oreopoulos, [[CCC]], December 30, 2014 » [[Move Generation#Reverse|Un-Move Generation]], [[Retrograde Analysis]]
 
==2015 ...==
 
==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/forum/viewtopic.php?t=55275 On bitboard legal move generation] by [[Lasse Hansen]], [[CCC]], February 09, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=56049 Questions about chess programming from a newbie] by Matt Palmer, [[CCC]], April 18, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=56049 Questions about chess programming from a newbie] by Matt Palmer, [[CCC]], April 18, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=56299 Caching generated moves list in recursive searches] by [[Rein Halbersma]], [[CCC]], May 10, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=56299 Caching generated moves list in recursive searches] by [[Rein Halbersma]], [[CCC]], May 10, 2015
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=58433 An approach to precomputed move generation bitboards] by [[Michael Sherwin]], [[CCC]], December 01, 2015
 
'''2016'''
 
'''2016'''
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61020 speed up your engine part 4] by [[Laurie Tunnicliffe]], [[CCC]], August 03, 2016 » [[Move Generation#Staged|Staged move generation]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=61020 speed up your engine part 4] by [[Laurie Tunnicliffe]], [[CCC]], August 03, 2016 » [[Move Generation#Staged|Staged move generation]]
Line 161: Line 168:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64619 History heuristic and quiet move generation] by [[Daniel José Queraltó]], [[CCC]], July 16, 2017 » [[History Heuristic]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64619 History heuristic and quiet move generation] by [[Daniel José Queraltó]], [[CCC]], July 16, 2017 » [[History Heuristic]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65900 Skipping duplicat moves] by [[Harm Geert Muller]], [[CCC]], December 03, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65900 Skipping duplicat moves] by [[Harm Geert Muller]], [[CCC]], December 03, 2017
 +
'''2019'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70082 Opinions requested for new move gen idea]  by [[Michael Sherwin]], [[CCC]], March 03, 2019 » [[Table-driven Move Generation]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70508 My newest almost bb move generator is wonderful] by [[Michael Sherwin]], [[CCC]], April 17, 2019
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70515 Efficient capture generation in the game of Thud] by koedem, [[CCC]], April 18, 2019
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=74917 Comparing 4 move generators: 0x88 vs 10x12 vs 10x12 + bitboards HYBRID vs Pure MAGIC BITBOARDS] by [[Maksim Korzh]], [[CCC]], August 28, 2020
 +
'''2021'''
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76835 Staged move generation?] by [[Niels Abildskov]], [[CCC]], March 10, 2021 » [[Move Generation#Staged|Staged Move Generation]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77350 Being silly with perft and legal move generation] by [[Jakob Progsch]], [[CCC]], May 19, 2021 » [[Perft]], [[#Legal|Legal Move Generation]], [[En passant]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77465 Advice on optimizing my move generation] by Christian Dean, [[CCC]], June 11, 2021
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77671 Efficiently Generated Legal moves question] by Pedro Duran, [[CCC]], July 08, 2021 » [[Legal Move]]
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77906 Move generator advice] by Ellie Moore, [[CCC]], August 08, 2021
 +
* [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|Un-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]]
 +
'''2022'''
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79365 Move generation for bitboards] by [[Elias Nilsson]], [[CCC]], February 16, 2022
  
 
=External Links=  
 
=External Links=  
 
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm Chapter 3: Board Games - 3.1 CHESS] from [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. Allen & Unwin, ISBN-13: 978-0080212227
 
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm Chapter 3: Board Games - 3.1 CHESS] from [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. Allen & Unwin, ISBN-13: 978-0080212227
* [http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm Description of 0x88 method] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
+
* [http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm Description of 0x88 method] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
* [http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
+
* [http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
 
* [http://john.stanback.net/zarkov/zarkov_methods.html How Zarkov Plays Chess] by [[John Stanback]]
 
* [http://john.stanback.net/zarkov/zarkov_methods.html How Zarkov Plays Chess] by [[John Stanback]]
 
* [http://perl.guru.org/scott/hobbies/chess/ Monsoon/Typhoon Homepage] by [[Scott Gasch]], covers [[0x88]] move generation
 
* [http://perl.guru.org/scott/hobbies/chess/ Monsoon/Typhoon Homepage] by [[Scott Gasch]], covers [[0x88]] move generation
: [http://wannabe.guru.org/svn/typhoon/trunk/generate.c generate.c] by [[Scott Gasch]]
 
* [http://www.cis.uab.edu/hyatt/bitmaps.html Description of Rotated Bitboards] by [[Robert Hyatt]]
 
 
* [http://www.pradu.us/old/Nov27_2008/Buzz/ Buzz - A Winboard Chess Playing Program] by [[Pradu Kannan]] - Source of [[Magic Bitboards|magic]] Move Generator
 
* [http://www.pradu.us/old/Nov27_2008/Buzz/ Buzz - A Winboard Chess Playing Program] by [[Pradu Kannan]] - Source of [[Magic Bitboards|magic]] Move Generator
* [http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/chess-programming-part-iii-move-generation-r1126 Chess Programming Part III: Move Generation] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], July 2000
+
* [https://www.gamedev.net/tutorials/_/technical/artificial-intelligence/chess-programming-part-iii-move-generation-r1126/ Chess Programming Part III: Move Generation] by [[François-Dominic Laramée]], [https://en.wikipedia.org/wiki/GameDev.net gamedev.net], July 2000
* [http://labraj.uni-mb.si/en/Chess_Move_Generator Chess Move Generator - Computer Architecture and Languages Laboratory], [[University of Maribor]]
+
* [https://labraj.feri.um.si/en/Chess_Move_Generator Chess Move Generator - Computer Architecture and Languages Laboratory], [[University of Maribor]]
 
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The move generator] by [[Pedro Castro]]
 
* [https://sites.google.com/site/hispanicchessengines/programs--interface---engines/engine Engine - Hispanic Chess Engines | The move generator] by [[Pedro Castro]]
* [https://en.wikipedia.org/wiki/Generator_%28computer_programming%29 Generator (computer programming) from Wikipedia]
+
* [https://peterellisjones.com/posts/generating-legal-chess-moves-efficiently/ Generating Legal Chess Moves Efficiently] by [[Peter Ellis Jones]], February 09, 2017
  
 
=References=
 
=References=
 
<references />
 
<references />
 
 
'''[[Board Representation|Up one level]]'''
 
'''[[Board Representation|Up one level]]'''
 
[[Category:Zollern]]
 
[[Category:Zollern]]
[[Category:Industrial Heritag Trail]]
+
[[Category:Industrial Heritage Trail]]

Latest revision as of 17:39, 12 March 2022

Home * Board Representation * Move Generation

Blast Generation [1]

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.

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.

Un-Move Generation

Un-Move Generation produces a list of all possible moves (including captures and promotions) which could be un-made from a target position to reach all possible legal predecessor or parent positions for retrograde analysis tasks.

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: Yet another new bitboard move generation method by Harm Geert Muller, Winboard Forum, October 01, 2006 [4]
Re: Move generation: staged vs all-at-once by Lance Perkins, CCC, April 30, 2009

2010 ...

2012

2014

2015 ...

2016

2017

2019

2020 ...

2021

Re: Fast reverse move generation by Peter Österlund, CCC, December 18, 2021 » Texel

2022

External Links

References

Up one level