Older Version
Newer Version
ecabiac
Mar 27, 2016
[[toc]]
**[[Home]] * [[Chess]] * [[Moves]] * Encoding Moves**
**Encoding Moves** inside a chess program refers to both [[Chess Game#GameRecord|game records]] or [[Game Notation|game notation]], and [[Search|search]] related [[Move Generation|generation]], [[Make Move|make]] and [[Unmake Move|unmake move]] to [[Incremental Updates|incremental update]] the [[Chessboard|board]]. During generation, moves are stored inside [[Move List|move lists]], and [[Best Move|best moves]] or [[Refutation Move|refutation moves]] [[Fail-High|failing high]] inside the [[Search|search]] are stored inside the [[Transposition Table|transposition table]], [[Killer Heuristic|Killer slots]], [[Triangular PV-Table|PV-]] or [[Refutation Table|refutation table]], and moves, or certain aspects of a move, such as [[Origin Square|origin square]] and the [[Target Square|target square]] are used to index [[Butterfly Boards|butterfly boards]] for [[History Heuristic|history]]- or [[Countermove Heuristic|countermove heuristic]].
Move encoding in game records and game databases is usually designed to minimize size, while in search efficiency in generating is the main concern, considering [[Board Representation|board representation]] and other data structures like [[Attack and Defend Maps|attack and defend maps]]. In general, move encoding either comprehend full information, that is contains involved [[Pieces|pieces]] and square coordinates, or more common, omits the redundant piece information and relies on a adequate board representation to lookup the pieces by square. In [[Alpha-Beta]] like search, an important consideration is lazy move generation, to delay acquisition of certain information until it is really needed, which might be never in case of [[Node Types#CUT|Cut-nodes]].
=Information Required=
==From-To Based==
The information required to uniquely describe a move is the [[Origin Square|initial square]], also called from-, origin- or departure square, and the [[Target Square|target square]], also called to- or destination square, and in case of [[Promotions|promotions]] the promoted piece code. While this from-to information is also sufficient for [[Castling|castling]] in standard chess, due to the otherwise impossible double king step, it might not in [[Chess960]]. Therefore and also for <span style="line-height: 1.5;">efficiency reasons, castles are tagged as "special" moves. Such a move encoding conveniently fits inside a 16-bit [[Word|word]], 6 bits for from-to square each to index a [[Butterfly Boards|butterfly board]], still leaves a [[Nibble|nibble]] for flags for move kind and promoted piece code, for instance this arbitrary flags:</span>
||~ code ||~ promotion ||~ capture ||~ special 1 ||~ special 0 ||~ kind of move ||
||~ 0 ||= 0 ||= 0 ||= 0 ||= 0 ||= [[Quiet Moves|quiet moves]] ||
||~ 1 ||= 0 ||= 0 ||= 0 ||= 1 ||= [[Pawn Push#DoublePush|double pawn push]] ||
||~ 2 ||= 0 ||= 0 ||= 1 ||= 0 ||= [[Castling|king castle]] ||
||~ 3 ||= 0 ||= 0 ||= 1 ||= 1 ||= [[Castling|queen castle]] ||
||~ 4 ||= 0 ||= 1 ||= 0 ||= 0 ||= [[Captures|captures]] ||
||~ 5 ||= 0 ||= 1 ||= 0 ||= 1 ||= [[En passant|ep-capture]] ||
||~ 8 ||= 1 ||= 0 ||= 0 ||= 0 ||= [[Promotions|knight-promotion]] ||
||~ 9 ||= 1 ||= 0 ||= 0 ||= 1 ||= [[Promotions|bishop-promotion]] ||
||~ 10 ||= 1 ||= 0 ||= 1 ||= 0 ||= [[Promotions|rook-promotion]] ||
||~ 11 ||= 1 ||= 0 ||= 1 ||= 1 ||= [[Promotions|queen-promotion]] ||
||~ 12 ||= 1 ||= 1 ||= 0 ||= 0 ||= knight-promo capture ||
||~ 13 ||= 1 ||= 1 ||= 0 ||= 1 ||= bishop-promo capture ||
||~ 14 ||= 1 ||= 1 ||= 1 ||= 0 ||= rook-promo capture ||
||~ 15 ||= 1 ||= 1 ||= 1 ||= 1 ||= queen-promo capture ||
==Extended Move Structure==
The information which piece performs the move and which piece is captured (if any) is implicit given by the from-to squares, with the requirement to lookup the current board before making the move, but in case of [[Captures|captures]] not after making or before unmaking the move. Some programs use a 32-bit [[Double Word|double word]] as extended move structure at generation time as well for making/unmaking moves, with the upper bits used for a move score scaled by various [[Move Ordering|move ordering]] techniques for instance dedicated [[Piece-Square Tables|piece-square tables]] and/or [[History Heuristic|history heuristic]], and perhaps two three bit codes for the moving and captured piece (if any) which also implies a kind of [[MVV-LVA]] coding. Also the extended move may apply composite indices for [[Incremental Updates|incremental update]] of [[Zobrist Hashing|Zobrist]]- or [[BCH Hashing|BCH keys]].
Having the piece codes inside the move structure safes the board lookups during make, and makes storing captured pieces on a ply stack for unmake needless. Of course for space considerations to store moves inside [[Transposition Table|transposition table]], [[Killer Heuristic|Killer slots]], [[Triangular PV-Table|PV-]] or [[Refutation Table|refutation table]], the compact 16-bit move structure is still adequate for coordinate and move kind comparison with the lower 16 bits of the extended move structure.
==C++ Sample==
Rather than using [[C#Bitfield|bitfield]] move structures or classes in [[C]] and [[Cpp|C++]], most programmers rely on scalar integers, such as //short// and //int// for 16- or 32-bit words, but implement the composition and extraction while writing and reading various structure elements by explicit shifts and masks, likely encapsulated thought an interface with most likely inlined functions (or macros) to hide the internal representation. Further extended move structures might either embed or inherit this most compact base structure or class, which might already rely the native 32-bit integer type to avoid [[x86]] 16-bit optimization issues.
[[code format="cpp"]]
class CMove {
CMove(unsigned int from, unsigned int to, unsigned int flags) {
m_Move = ((flags & 0xf)<<12) | ((from & 0x3f)<<6) | (to & 0x3f);
}
void operator=(CMove a} {m_Move = a.m_Move;}
unsigned int getTo() const {return m_Move & 0x3f;}
unsigned int getFrom() const {return (m_Move >> 6) & 0x3f;}
unsigned int getFlags() const {return (m_Move >> 12) & 0x0f;}
void setTo(unsigned int to) {m_Move &= ~0x3f; m_Move |= to & 0x3f;}
void setFrom(unsigned int from) {m_Move &= ~0xfc0; m_Move |= (from & 0x3f) << 6;}
...
bool isCapture() const {return (m_Move & CAPTURE_FLAG) != 0;}
...
unsigned int getButterflyIndex() const {return m_Move & 0x0fff;}
bool operator==(CMove a) const {return (m_Move & 0xffff) == (a.m_Move & 0xffff);}
bool operator!=(CMove a) const {return (m_Move & 0xffff) != (a.m_Move & 0xffff);}
unsigned short asShort() const {return (unsigned short) m_Move;}
protected:
unsigned int m_Move; // or short or template type
};
[[code]]
=Various Encodings and Decorations=
==Algebraic Notation==
Based on [[http://en.wikipedia.org/wiki/Philipp_Stamma|Philipp Stamma's]] short [[Algebraic chess notation]], a move can be described by the moving piece code and destination square. In case of disambiguating moves if two (or more) identical pieces can move to the same square, the file of departure, or if files are identical as well, the rank or both file and rank are given. A capture move, denoted by the symbol 'x' (takes) does not explicitly specify the captured piece and requires a look to the board as well.
Chess programs usually use algebraic notations concerning the [[GUI|user interface]] and [[Portable Game Notation]] - for appropriate conversion they have to deal with disambiguating source squares, that is need to be aware of all other moves of this piece-kind to the destination square to determine whether the from square needs additional file and/or rank information despite the moving piece.
==Direction-Target==
Another move encoding alternative motivated by [[Pieces versus Directions#DirectionWise|direction wise]] target square serialization in [[Bitboards|bitboards]] is not to use the from-square but target square and [[Direction|direction]]. While the information is non-ambiguous it needs some effort with ray-lookup and [[BitScan|bitscan]] to determine the from-square.
==Check Flag==
It might be interesting to determine whether a move gives [[Check|check]] in advance during generation time, to possibly score them higher for move ordering, i. e. to don't [[Late Move Reductions|reduce]] or even [[Check Extensions|extend]] them, and also to safe in check detection after make move. However, as mentioned, lazy move generation is required, to delay acquisition of information until it is really needed, which might be never in case of [[Node Types#CUT|Cut-nodes]]. Additionally an early determined checking move, even if [[Fail-High|failing high]], usually implies a huge sub-tree due to [[Check Extensions|check extensions]], while an early non checking moves likely makes a cheaper [[Beta-Cutoff|cutoff]] for most futile Cut-nodes. Therefor, determining checking moves in advance is not that recommended for most board-representations.
[[#MoveIndex]]
==Move Index==
If the generated moves inside a [[Move List|move list]] are [[http://en.wikipedia.org/wiki/Determinism|deterministic]], one may encode moves as relative list index. Since the maximum number of moves per positions seems 218 <ref>[[http://www.stmintz.com/ccc/index.php?id=424966|Subject: Maximum Number of Legal Moves]] by [[Andrew Shapira]], [[CCC]], May 08, 2005</ref> <ref>[[http://www.talkchess.com/forum/viewtopic.php?t=39332|max amount of moves from a position?]] by [[Srdja Matovic]], [[CCC]], June 10, 2011</ref> , one [[Byte|byte]] is enough to index the move. This encoding was used in early game databases.
||||~ Two Positions with 218 Moves each ||~ [[http://commons.wikimedia.org/wiki/File:DickinsAnthony.jpg|A. Dickins]] (1968) <ref>[[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=410026&t=39332|Re: max amount of moves from a position?]] by [[Árpád Rusz]], [[CCC]], June 11, 2011</ref> ||
|| [[image:http://webchess.freehostia.com/diag/chessdiag.php?fen=R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1%20w%20-%20-&size=medium&coord=no&cap=no&stm=yes&fb=no&theme=classic&color1=E3CEAA&color2=635147&color3=000000]] ||~ || [[image:http://webchess.freehostia.com/diag/chessdiag.php?fen=3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk%20w%20-%20-&size=medium&coord=no&cap=no&stm=yes&fb=no&theme=classic&color1=E3CEAA&color2=635147&color3=000000]] ||
|| <span style="font-size: 80%;">R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1</span> ||~ || <span style="font-size: 80%;">3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1</span> ||
[[#Enumeration]]
==Move Enumeration==
Based on [[Influence Quantity of Pieces]] one may enumerate all moves, to specify a unique determined move number with respect to moving piece, from- and to squares, captured piece (if any) and promoted piece inside a 16-bit range.
===Pawn Moves===
||~ Move Kind ||~ Ranks ||~ Files ||~ Directions ||~ Target Combinations ||~ Cardinality ||
|| Pushs ||= 5 ||> 8 ||= 1 ||> 1 ||> 40 ||
|| Promotions ||= 1 ||> 8 ||= 1 ||> 4 ||> 32 ||
|| Double Pushs ||= 1 ||> 8 ||= 1 ||> 1 ||> 8 ||
|| **Total Pushs** ||= 6 ||> 8 ||= 1 ||> <span style="color: #c0c0c0;">1+2/3</span> ||> **80** ||
|| Captures ||= 5 ||> 7 ||= 2 ||> 5 ||> 350 ||
|| Captures & Promotions ||= 1 ||> 7 ||= 2 ||> 4*4 <ref>PxP not possible during promotion, therefore only four capture targets</ref> ||> 224 ||
|| En passant ||= 1 ||> 7 ||= 2 ||> 1 ||> 14 ||
|| **Total Captures** ||= 6 ||> 7 ||= 2 ||> ||> **588** ||
|| **Total Pawns** ||= 6 ||> ||= 3 ||> ||> **668** ||
===Piece Moves===
Reversible and Captures, [[Influence Quantity of Pieces]] times six target combinations for empty and five possible capture targets.
||~ Piece ||~ Influence Quantity ||~ Cardinality ||
|| Knight ||> 336 ||> 2016 ||
|| King ||> 420 ||> 2520 ||
|| Bishop ||> 560 ||> 3360 ||
|| Rook ||> 896 ||> 5376 ||
|| Queen ||> 1456 ||> 8736 ||
|| **Total** ||> 3668 ||> **22008** ||
===All Moves===
Sheet of all moves, considering [[Castling]] (but no null move):
||~ Piece ||~ Move Kind ||~ From-To ||~ None ||~ Captures ||~ per Side ||~ Total ||
|| Pawn ||= Promotions ||> 8 ||> 32 ||> - ||> 32 ||> 64 ||
|| ||= Captures & Promotions ||> 14 ||> - ||> 224 ||> 224 ||> 448 ||
|| ||= Double Pushs ||> 8 ||> 8 ||> - ||> 8 ||> 16 ||
|| ||= Pushs ||> 40 ||> 40 ||> - ||> 40 ||> 80 ||
|| ||= Captures ||> 70 ||> - ||> 350 ||> 350 ||> 700 ||
|| ||= En passant ||> 14 ||> - ||> 14 ||> 14 ||> 28 ||
|| ||= **Total** ||> ||> **80** ||> **588** ||> **668** ||> **1336** ||
|| King ||= Castles ||> 2 ||> 2 ||> - ||> 2 ||> 4 ||
|| ||= ||> 420 ||> 420 ||> 2100 ||> 2520 ||> 5040 ||
|| ||= **Total** ||> ||> **422** ||> **2100** ||> **2522** ||> **5044** ||
|| Knight ||= ||> 336 ||> 336 ||> 1680 ||> 2016 ||> 4032 ||
|| Bishop ||= ||> 560 ||> 560 ||> 2800 ||> 3360 ||> 6720 ||
|| Rook ||= ||> 896 ||> 896 ||> 4480 ||> 5376 ||> 10752 ||
|| Queen ||= ||> 1456 ||> 1456 ||> 7280 ||> 8736 ||> 17472 ||
||> ||= **Total** ||> ||> **3248** ||> **16240** ||> **19488** ||> **38976** ||
|| __**Total**__ |||| ||> __**3750**__ ||> __**18928**__ ||> __**22678**__ ||> __**45356**__ ||
=See also=
* [[Influence Quantity of Pieces]]
* [[Move Generation]]
* [[Move Ordering]]
=Forum Posts=
* [[http://www.stmintz.com/ccc/index.php?id=424966|Subject: Maximum Number of Legal Moves]] by [[Andrew Shapira]], [[CCC]], May 08, 2005
* [[http://www.talkchess.com/forum/viewtopic.php?t=39332|max amount of moves from a position?]] by [[Srdja Matovic]], [[CCC]], June 10, 2011 » [[Chess#Maxima|Chess Maxima]]
* [[http://www.talkchess.com/forum/viewtopic.php?t=41388|Contest: Find Position with the most moves]] by [[Charles Roberson]], [[CCC]], December 09, 2011
* [[http://www.talkchess.com/forum/viewtopic.php?t=52083|Move encoding]] by [[Russell Reagan]], [[CCC]], April 21, 2014
* [[http://www.talkchess.com/forum/viewtopic.php?t=53289|Killer and move encoding]] by [[Fabio Gobbato]], [[CCC]], August 14, 2014 » [[Killer Heuristic]]
=External Links=
* [[http://labraj.uni-mb.si/en/Move_Representation|Move Representation - Computer Architecture and Languages Laboratory]], [[University of Maribor]]
=References=
<references />
=What links here?=
[[include page="Encoding Moves" component="backlinks" limit="40"]]
**[[Moves|Up one Level]]**