25,161
edits
Changes
Created page with "'''Home * Board Representation * Move Generation''' FILE:GenratorZecheZollern.JPG|border|right|thumb|link=https://commons.wikimedia.org/wiki/File:Zeche_Zo..."
'''[[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 [[Arts#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 [[Arts#IndustrialHeritageTrail|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.
=Legality=
==Pseudo-legal<span id="PseudoLegal"></span>==
In Pseudo-legal move generation [[Pieces|pieces]] obey their normal rules of movement, but they're not checked beforehand to see if they'll leave the [[King|king]] in [[Check|check]]. It is left up to the [[Make Move|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.
<span id="Legal"></span>
==Legal==
In Legal move generation, as the name implies, only [[Legal Move|legal moves]] are generated, which means extra time must be spent to make sure the [[King|king]] isn't going to be left or placed [[Check|in check]] after each move. [[Pin|Pins]] are the main difficulty, particularly when [[En passant|en passant]] is involved.
=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 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 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.
=See also=
==General==
* [[Encoding Moves]]
* [[Mate-in-two]]
* [[Color Flipping#Monochrome|Monochrome Move Generation]]
* [[Move List]]
* [[Move Ordering]]
* [[Perft]]
==Board Array==
* [[Mailbox]]
: [[0x88]]
: [[Vector Attacks]]
* [[Sensor Chess#MoveGeneration|Move Generation with 256 bytes RAM or less?]]
* [[Table-driven Move Generation]]
==Bitboards==
* [[Bitboard Serialization]]
* [[DirGolem]]
* [[Pieces versus Directions]]
* [[Sliding Piece Attacks]]
<span id="Hardware"></span>
==Hardware==
* [[Belle#Hardware|Belle]]
* [[Berkeley Chess Microprocessor]]
* [[Brutus#MoveGeneration|Brutus]]
* [[CHEOPS]]
* [[ChipTest#MoveGeneration|ChipTest]]
==Chess Programs==
* [[Atlas#MoveGeneration|Move Generation in Atlas]]
* [[CPW-Engine_movegen(0x88)|Move Generation in CPW-Engine]]
* [[MadChess#MoveGeneration|Move Generation in MadChess]]
* [[Rajah#0x88|Move Generation in Rajah]]
* [[Thor's Hammer#MoveGeneration|Move Generation in Thor's Hammer]]
* [[Tinker#MoveGeneration|Move Generation in Tinker]]
* [[10x12 Board#OffsetMG|Move Generation in TSCP]]
* [[Vanilla Chess#MoveGeneration|Move Generation in Vanilla Chess]]
* [[Table-driven Move Generation#Ferret|Table-driven Move Generation in Ferret]]
* [[Table-driven Move Generation#GNUChess|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'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
* [[Gerard Zieliński]] ('''1976'''). ''[http://www.emeraldinsight.com/doi/abs/10.1108/eb005412 Arrays for Programming Chess]''. [http://www.emeraldinsight.com/loi/k 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]]
* <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>
* [[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]
* [[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]]
* [[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the [http://www.cisl.ucar.edu/computers/gallery/cray/xmp.jsp X-MP/48].'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]
* [[Carl Ebeling]] ('''1986'''). ''[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7692 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'''). ''[http://repository.cmu.edu/compsci/1566/ 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'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=124744&contentType=Conference+Publications&searchWithin%3Dp_Authors%3A.QT.Testa%2C+J..QT. 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]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1996'''). ''Parallel Move Generation System for Computer Chess''. [http://search.ieice.org/bin/index.php?category=D&lang=E&curr=1 IEICE Transactions on Information and Systems], April, 1996, pp. 290-296
* [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal#20_3|ICCA Journal, Vol. 20, No. 3]]
* [[Robert Hyatt]] ('''1999'''). ''[http://www.cis.uab.edu/hyatt/bitmaps.html Rotated Bitmaps, a New Twist on an Old Idea]''. [[ICGA Journal#24_4|ICCA Journal, Vol. 22, No. 4]]
* [[Feng-hsiung Hsu]] ('''1999'''). ''IBM’s Deep Blue Chess Grandmaster Chips''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.5392&rep=rep1&type=pdf 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. [http://www.teu.ac.jp/gamelab/RESEARCH/jsai2001.pdf pdf]
* [[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], (Supervisor: [[Zeljko Zilic]], Co-Supervisor: [[Monroe Newborn|Monty Newborn]]), [http://www.iml.ece.mcgill.ca/%7Emboule/files/mbthesis02.pdf pdf]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[McGill University]], [http://www.iml.ece.mcgill.ca/%7Emboule/files/cicc02.pdf pdf] » [[FPGA]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[ICGA Journal#25_2|ICGA Journal, Vol. 25, No. 2]], [http://iml.ece.mcgill.ca/~mboule/files/icga02.pdf pdf]
* [[Reijer Grimbergen]] ('''2007'''). ''Using Bitboards for Move Generation in Shogi''. [[ICGA Journal#30_1|ICGA Journal, Vol. 30, No. 1]], [http://www2.teu.ac.jp/gamelab/RESEARCH/ICGAJournal2007.pdf pdf], was topic of the [[Conferences#GPW|11th Game Programming Workshop]]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess'', Ph.D. Thesis, [http://www.personeel.unimaas.nl/uiterwijk/Theses/PhD/Reul_thesis.pdf pdf]
==2010 ...==
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien], [https://en.wikipedia.org/wiki/Taiwan Taiwan], December 2012 » [[Learning]], [[UCT]]
=Forum Posts=
==1990 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/2a726f0678600ca5 move generators in computer chess] by [[Deniz Yuret]], [[Computer Chess Forums|rgcc]], October 11, 1994
: [http://groups.google.com/group/rec.games.chess/msg/f4f0751cc8b928c8 Re: move generators in computer chess, Tricky bit tricks] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgcc]], October 20, 1994 » [[Traversing Subsets of a Set]]
* [https://groups.google.com/d/msg/rec.games.chess/vvl1nLv1MD8/oHVKdLXuiaUJ bitboard move generation] by [[Robert Hyatt]], [[Computer Chess Forums|rgc]], October 25, 1994
* [https://groups.google.com/d/msg/rec.games.chess/Kl1MCF9tmpA/7tY-FfFSJDMJ move generators in computer chess] by [[Joël Rivat]], [[Computer Chess Forums|rgc]], October 26, 1994
* [https://groups.google.com/d/msg/rec.games.chess/106wKFeI8BA/zNuzu-2aMowJ bitboard move generator] by [[Joël Rivat]], [[Computer Chess Forums|rgc]], November 13, 1994
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/33c57503391f3a89 Speed of Move Generator] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], August 15, 1995
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/4b0a4302870bf6ac Move generator design choices] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], April 26, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/3601d68c3678dc7f Sane numbers] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], June 26, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7292bfb78152b40b GNU move generation] by [[Jan Willem de Kort]], [[Computer Chess Forums|rgcc]], March 18, 1998 » [[GNU Chess]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=109588 Fast BB move generation] by [[Bas Hamstra]], [[CCC]], May 08, 2000
* [https://www.stmintz.com/ccc/index.php?id=112809 move_generation + hash] by [[Georg von Zimmermann]], [[CCC]], May 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=116593 Pre-calculated move generation] by Ujecrh, [[CCC]], June 26, 2000
* [https://www.stmintz.com/ccc/index.php?id=188901 Move generation question for the big boys] by [[Sune Fischer]], [[CCC]], September 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=238333 Precomputed move information] by [[Sune Fischer]], [[CCC]], July 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=266381 Natural move generation with bitboards (was Re:significant math)] by [[Alessandro Damiani]], [[CCC]], November 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=275167 Strength question] by [[Bruce Moreland]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=294549 Which open source chess program has the fastest move generator?] by [[Dennis Breuker]], [[CCC]], April 25, 2003
* [https://www.stmintz.com/ccc/index.php?id=303316 Improvements in BF makes my MoveGen suck =(] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 » [[Branching Factor]]
* [https://www.stmintz.com/ccc/index.php?id=311601 Speed improvement in split move generation] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 16, 2003
* [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 ...==
* [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=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=27657 Move generation: staged vs all-at-once] by [[Steven Edwards]], [[CCC]], April 30, 2009
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=264380 Re: Move generation: staged vs all-at-once] by [[Lance Perkins]], [[CCC]], April 30, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=39873 Assembly move generation in Freccia] by [[Stefano Gemma]], [[CCC]], July 26, 2011
'''2012'''
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52125&sid=d3919159e42267a64891e4e0e3bfbaf0 move generation speed] by [[Folkert van Heusden]], [[Computer Chess Forums|Winboard Forum]], January 03, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43971 Is there such a thing as branchless move generation?] by [[John Hamlen]], [[CCC]], June 07, 2012 » [[DirGolem]], [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44658 hyper threading and move generation] by [[Gabor Buella]], [[CCC]], August 01, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44939 What's the fastest move generator?] by Marcel Fournier, [[CCC]], August 29, 2012
* [http://talkchess.com/forum/viewtopic.php?p=485936#485936 Re: Question About CPP-C#, Performance, and Square Representation] by [[Erik Madsen]], [[CCC]], October 03, 2012 » [[MadChess]] <ref>[http://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx yield - MSDN C# Reference]</ref> <ref>[http://startbigthinksmall.wordpress.com/2008/06/09/behind-the-scenes-of-the-c-yield-keyword/ Behind the scenes of the C# yield keyword | Struggles] by [http://startbigthinksmall.wordpress.com/ Lars Corneliussen], June 9, 2008</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=45926 Plausible move generator] by Jorge Garcia, [[CCC]], November 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46056 Diepeveen's move generator] by Hrvoje Horvatic, [[CCC]], November 18, 2012 » [[Table-driven Move Generation]]
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=54337 Just another movegen] by [[Syed Fahad]], [[CCC]], November 14, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54368 How to call the Satana move generation] by [[Stefano Gemma]], [[CCC]], November 17, 2014 » [[Satana]]
* [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, December 30, 2014 » [[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/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
'''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=61797 Performance diff between legal / illegal move generator] by [[Mahmoud Uthman]], [[CCC]], October 22, 2016
'''2017'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=3081 Most efficient way to generate legal king moves?] by notachessplayer, [[Computer Chess Forums|OpenChess Forum]], February 04, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63346 Back to the basics, generating moves on gpu in parallel...] by [[Srdja Matovic]], [[CCC]], March 05, 2017 » [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64242 Fastest pawn quiet move generation I was able to come with] by [[Daniel José Queraltó]], [[CCC]], June 10, 2017 » [[C#Duff|Duff's Device]]
* [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
=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://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/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://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://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.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
* [http://labraj.uni-mb.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://en.wikipedia.org/wiki/Generator_%28computer_programming%29 Generator (computer programming) from Wikipedia]
=References=
<references />
'''[[Board Representation|Up one level]]'''
[[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 [[Arts#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 [[Arts#IndustrialHeritageTrail|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.
=Legality=
==Pseudo-legal<span id="PseudoLegal"></span>==
In Pseudo-legal move generation [[Pieces|pieces]] obey their normal rules of movement, but they're not checked beforehand to see if they'll leave the [[King|king]] in [[Check|check]]. It is left up to the [[Make Move|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.
<span id="Legal"></span>
==Legal==
In Legal move generation, as the name implies, only [[Legal Move|legal moves]] are generated, which means extra time must be spent to make sure the [[King|king]] isn't going to be left or placed [[Check|in check]] after each move. [[Pin|Pins]] are the main difficulty, particularly when [[En passant|en passant]] is involved.
=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 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 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.
=See also=
==General==
* [[Encoding Moves]]
* [[Mate-in-two]]
* [[Color Flipping#Monochrome|Monochrome Move Generation]]
* [[Move List]]
* [[Move Ordering]]
* [[Perft]]
==Board Array==
* [[Mailbox]]
: [[0x88]]
: [[Vector Attacks]]
* [[Sensor Chess#MoveGeneration|Move Generation with 256 bytes RAM or less?]]
* [[Table-driven Move Generation]]
==Bitboards==
* [[Bitboard Serialization]]
* [[DirGolem]]
* [[Pieces versus Directions]]
* [[Sliding Piece Attacks]]
<span id="Hardware"></span>
==Hardware==
* [[Belle#Hardware|Belle]]
* [[Berkeley Chess Microprocessor]]
* [[Brutus#MoveGeneration|Brutus]]
* [[CHEOPS]]
* [[ChipTest#MoveGeneration|ChipTest]]
==Chess Programs==
* [[Atlas#MoveGeneration|Move Generation in Atlas]]
* [[CPW-Engine_movegen(0x88)|Move Generation in CPW-Engine]]
* [[MadChess#MoveGeneration|Move Generation in MadChess]]
* [[Rajah#0x88|Move Generation in Rajah]]
* [[Thor's Hammer#MoveGeneration|Move Generation in Thor's Hammer]]
* [[Tinker#MoveGeneration|Move Generation in Tinker]]
* [[10x12 Board#OffsetMG|Move Generation in TSCP]]
* [[Vanilla Chess#MoveGeneration|Move Generation in Vanilla Chess]]
* [[Table-driven Move Generation#Ferret|Table-driven Move Generation in Ferret]]
* [[Table-driven Move Generation#GNUChess|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'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
* [[Gerard Zieliński]] ('''1976'''). ''[http://www.emeraldinsight.com/doi/abs/10.1108/eb005412 Arrays for Programming Chess]''. [http://www.emeraldinsight.com/loi/k 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]]
* <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>
* [[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]
* [[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]]
* [[Burton Wendroff]] ('''1985'''). ''Attack Detection and Move Generation on the [http://www.cisl.ucar.edu/computers/gallery/cray/xmp.jsp X-MP/48].'' [[ICGA Journal#8_2|ICCA Journal, Vol. 8, No. 2]]
* [[Carl Ebeling]] ('''1986'''). ''[http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=7692 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'''). ''[http://repository.cmu.edu/compsci/1566/ 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'''). ''[http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=124744&contentType=Conference+Publications&searchWithin%3Dp_Authors%3A.QT.Testa%2C+J..QT. 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]], [https://era.library.ualberta.ca/public/datastream/get/uuid:e4fbf48d-7603-490f-85cc-5497bbecf5a8/DS1 pdf]
* [[Yi-Fan Ke]], [[Tai-Ming Parng]] ('''1996'''). ''Parallel Move Generation System for Computer Chess''. [http://search.ieice.org/bin/index.php?category=D&lang=E&curr=1 IEICE Transactions on Information and Systems], April, 1996, pp. 290-296
* [[Ernst A. Heinz]] ('''1997'''). ''[http://people.csail.mit.edu/heinz/dt/node2.html How DarkThought Plays Chess].'' [[ICGA Journal#20_3|ICCA Journal, Vol. 20, No. 3]]
* [[Robert Hyatt]] ('''1999'''). ''[http://www.cis.uab.edu/hyatt/bitmaps.html Rotated Bitmaps, a New Twist on an Old Idea]''. [[ICGA Journal#24_4|ICCA Journal, Vol. 22, No. 4]]
* [[Feng-hsiung Hsu]] ('''1999'''). ''IBM’s Deep Blue Chess Grandmaster Chips''. [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.126.5392&rep=rep1&type=pdf 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. [http://www.teu.ac.jp/gamelab/RESEARCH/jsai2001.pdf pdf]
* [[Marc Boulé]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. Masters thesis, [[McGill University]], (Supervisor: [[Zeljko Zilic]], Co-Supervisor: [[Monroe Newborn|Monty Newborn]]), [http://www.iml.ece.mcgill.ca/%7Emboule/files/mbthesis02.pdf pdf]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[McGill University]], [http://www.iml.ece.mcgill.ca/%7Emboule/files/cicc02.pdf pdf] » [[FPGA]]
* [[Marc Boulé]], [[Zeljko Zilic]] ('''2002'''). ''An FPGA Move Generator for the Game of Chess''. [[ICGA Journal#25_2|ICGA Journal, Vol. 25, No. 2]], [http://iml.ece.mcgill.ca/~mboule/files/icga02.pdf pdf]
* [[Reijer Grimbergen]] ('''2007'''). ''Using Bitboards for Move Generation in Shogi''. [[ICGA Journal#30_1|ICGA Journal, Vol. 30, No. 1]], [http://www2.teu.ac.jp/gamelab/RESEARCH/ICGAJournal2007.pdf pdf], was topic of the [[Conferences#GPW|11th Game Programming Workshop]]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess'', Ph.D. Thesis, [http://www.personeel.unimaas.nl/uiterwijk/Theses/PhD/Reul_thesis.pdf pdf]
==2010 ...==
* [[Adrien Couetoux]], [[Olivier Teytaud]], [[Hassen Doghmen]] ('''2012'''). ''Learning a Move-Generator for Upper Confidence Trees''. [http://ics2012.ndhu.edu.tw/ ICS 2012], [https://en.wikipedia.org/wiki/Hualien_City Hualien], [https://en.wikipedia.org/wiki/Taiwan Taiwan], December 2012 » [[Learning]], [[UCT]]
=Forum Posts=
==1990 ...==
* [http://groups.google.com/group/rec.games.chess/browse_frm/thread/2a726f0678600ca5 move generators in computer chess] by [[Deniz Yuret]], [[Computer Chess Forums|rgcc]], October 11, 1994
: [http://groups.google.com/group/rec.games.chess/msg/f4f0751cc8b928c8 Re: move generators in computer chess, Tricky bit tricks] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgcc]], October 20, 1994 » [[Traversing Subsets of a Set]]
* [https://groups.google.com/d/msg/rec.games.chess/vvl1nLv1MD8/oHVKdLXuiaUJ bitboard move generation] by [[Robert Hyatt]], [[Computer Chess Forums|rgc]], October 25, 1994
* [https://groups.google.com/d/msg/rec.games.chess/Kl1MCF9tmpA/7tY-FfFSJDMJ move generators in computer chess] by [[Joël Rivat]], [[Computer Chess Forums|rgc]], October 26, 1994
* [https://groups.google.com/d/msg/rec.games.chess/106wKFeI8BA/zNuzu-2aMowJ bitboard move generator] by [[Joël Rivat]], [[Computer Chess Forums|rgc]], November 13, 1994
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/33c57503391f3a89 Speed of Move Generator] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], August 15, 1995
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/4b0a4302870bf6ac Move generator design choices] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], April 26, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/3601d68c3678dc7f Sane numbers] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], June 26, 1996
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7292bfb78152b40b GNU move generation] by [[Jan Willem de Kort]], [[Computer Chess Forums|rgcc]], March 18, 1998 » [[GNU Chess]]
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=109588 Fast BB move generation] by [[Bas Hamstra]], [[CCC]], May 08, 2000
* [https://www.stmintz.com/ccc/index.php?id=112809 move_generation + hash] by [[Georg von Zimmermann]], [[CCC]], May 28, 2000
* [https://www.stmintz.com/ccc/index.php?id=116593 Pre-calculated move generation] by Ujecrh, [[CCC]], June 26, 2000
* [https://www.stmintz.com/ccc/index.php?id=188901 Move generation question for the big boys] by [[Sune Fischer]], [[CCC]], September 15, 2001
* [https://www.stmintz.com/ccc/index.php?id=238333 Precomputed move information] by [[Sune Fischer]], [[CCC]], July 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=266381 Natural move generation with bitboards (was Re:significant math)] by [[Alessandro Damiani]], [[CCC]], November 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=275167 Strength question] by [[Bruce Moreland]], [[CCC]], January 05, 2003
* [https://www.stmintz.com/ccc/index.php?id=294549 Which open source chess program has the fastest move generator?] by [[Dennis Breuker]], [[CCC]], April 25, 2003
* [https://www.stmintz.com/ccc/index.php?id=303316 Improvements in BF makes my MoveGen suck =(] by [[Albert Bertilsson]], [[CCC]], June 26, 2003 » [[Branching Factor]]
* [https://www.stmintz.com/ccc/index.php?id=311601 Speed improvement in split move generation] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], August 16, 2003
* [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 ...==
* [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=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=27657 Move generation: staged vs all-at-once] by [[Steven Edwards]], [[CCC]], April 30, 2009
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=264380 Re: Move generation: staged vs all-at-once] by [[Lance Perkins]], [[CCC]], April 30, 2009
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=39873 Assembly move generation in Freccia] by [[Stefano Gemma]], [[CCC]], July 26, 2011
'''2012'''
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=52125&sid=d3919159e42267a64891e4e0e3bfbaf0 move generation speed] by [[Folkert van Heusden]], [[Computer Chess Forums|Winboard Forum]], January 03, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=43971 Is there such a thing as branchless move generation?] by [[John Hamlen]], [[CCC]], June 07, 2012 » [[DirGolem]], [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44658 hyper threading and move generation] by [[Gabor Buella]], [[CCC]], August 01, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=44939 What's the fastest move generator?] by Marcel Fournier, [[CCC]], August 29, 2012
* [http://talkchess.com/forum/viewtopic.php?p=485936#485936 Re: Question About CPP-C#, Performance, and Square Representation] by [[Erik Madsen]], [[CCC]], October 03, 2012 » [[MadChess]] <ref>[http://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx yield - MSDN C# Reference]</ref> <ref>[http://startbigthinksmall.wordpress.com/2008/06/09/behind-the-scenes-of-the-c-yield-keyword/ Behind the scenes of the C# yield keyword | Struggles] by [http://startbigthinksmall.wordpress.com/ Lars Corneliussen], June 9, 2008</ref>
* [http://www.talkchess.com/forum/viewtopic.php?t=45926 Plausible move generator] by Jorge Garcia, [[CCC]], November 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46056 Diepeveen's move generator] by Hrvoje Horvatic, [[CCC]], November 18, 2012 » [[Table-driven Move Generation]]
'''2014'''
* [http://www.talkchess.com/forum/viewtopic.php?t=54337 Just another movegen] by [[Syed Fahad]], [[CCC]], November 14, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=54368 How to call the Satana move generation] by [[Stefano Gemma]], [[CCC]], November 17, 2014 » [[Satana]]
* [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, December 30, 2014 » [[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/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
'''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=61797 Performance diff between legal / illegal move generator] by [[Mahmoud Uthman]], [[CCC]], October 22, 2016
'''2017'''
* [http://www.open-chess.org/viewtopic.php?f=5&t=3081 Most efficient way to generate legal king moves?] by notachessplayer, [[Computer Chess Forums|OpenChess Forum]], February 04, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63346 Back to the basics, generating moves on gpu in parallel...] by [[Srdja Matovic]], [[CCC]], March 05, 2017 » [[GPU]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64242 Fastest pawn quiet move generation I was able to come with] by [[Daniel José Queraltó]], [[CCC]], June 10, 2017 » [[C#Duff|Duff's Device]]
* [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
=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://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/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://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://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.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
* [http://labraj.uni-mb.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://en.wikipedia.org/wiki/Generator_%28computer_programming%29 Generator (computer programming) from Wikipedia]
=References=
<references />
'''[[Board Representation|Up one level]]'''
