25,161
edits
Changes
no edit summary
<span id="MoveIndex"></span>
==Move Index==
{|
! 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>
|}
==Move Enumeration== ===Per Piece and Square=== For the subset of common chess positions a faster encoding scheme is possible that doesn't require move generation of any kind. Let's enumerate the upper bound on the number of unique moves a piece of a given type can make on an empty boardfrom one [[Squares|square]] - for [[Sliding Pieces|sliding pieces]] assuming no obstacles:* pawn {| class="wikitable"! Piece! # of Moves! Remarks|-| [[Pawn]]| style="text- align:right;" | 12 (| 7th rank, 4 promotion [[Promotions|promotions]] * 3 targets)[[Target Square|target squares]]|-| [[Knight]]* knight | style="text- align:right;" | 8* bishop | from the 16 [[Center#ExtendedCenter|extended center]] squares|-| [[Bishop]]| style="text- align:right;" | 13* rook | from the 4 [[Center|center]] squares|-| [[Rook]]| style="text- align:right;" | 14* queen | from any square|-| [[Queen]]| style="text- align:right;" | 27* king | from the 4 [[Center|center]] squares|-| [[King]]| style="text- align:right;" | 8 (| there are two additional [[Castling|castling moves]], <br/>but they are only possible from the start position <br/>where the king has 5 normal moves available.)|}
NOTE: We will always use this upper bound instead of the actual number of possible legal moves because this way we don't have to compute any attacks.
So for the standard chess piece set we have an upper bound of <code>12*8 + 8*2 + 13*2 + 14*2 + 27 + 8 == 201</code> possible moves before considering promotions. Each knight promotion reduces it by 12-8=4. Each bishop promotion increases it by 1; rook promotion by 2; queen promotion by 15. In the parametrized worst case (all pawns promoted to either rooks or queens) we have <code>n</code> queen and <code>8-n</code> rook promotions, so the upper bound is <code>f(n) = 8*2 + 13*2 + 14*(2+8-n) + 27*(1+n) + 8 == 217 + 13n</code>. <code>f(n=3)=256 <= 2^8</code>.
So for legal [[Chess960 ]] positions with at most 3 queens on the board one can encode any legal move in just one byte. Note that whether the result can always fit in one byte is determined based solely one the position, so no additional information needs to be stored for disambiguation. This way it's easy to implement a fallback for the positions not supported by this encoding (this could be either to use 2 bytes for the move index or use legal move generation to ensure all values take one byte).One way to encode a position using this information is in the following way:
<pre>
The <code>piece_move_index(moved_piece, move)</code> function can be implemented for example using lookup tables - the board state doesn't matter, only the move does.
Alternatively we can go through each piece type in some order (instead of going through individual squares), which allows faster computation of the offset if <code>[[Population Count|popcount</code> ]] instruction is available:
<pre>
offset = 0
</pre>
To decode the move we step through different offsets in the same way as we did when encoding, but now we have to look for the range of values that contains the encoded move index - once we find the range we can just decode the move index of that specific piece type (using an inverse of <code>piece_move_index</code>). While this method allows much faster encoding/decoding then the one involving a list of legal moves, it requires additional work if one needs to verify the correctness of the decoded moves (in the former one just needs to check if the index is within bounds).
<span id="Enumeration"></span>
==Move Enumeration=Over All Pieces and Squares===
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.
{| class="wikitable"
|-
|}
Reversible and Captures, [[Influence Quantity of Pieces]] times six target combinations for empty and five possible capture targets.
{| class="wikitable"
|}
Sheet of all moves, considering [[Castling]] (but no null move):
{| class="wikitable"
=Forum Posts=
==1993 ...==
* [https://groups.google.com/d/msg/rec.games.chess/RspnvkCEY7s/W4kUZ0uH7jMJ recording chess games in very few bits per move] by Toby Robison, [[Computer Chess Forums|rgc]], March 05, 1993
* [https://groups.google.com/d/msg/rec.games.chess/yL_tzhBpVsw/PBb6dSWl9FgJ Chess move binary encoding] by [[Jeff Mallett]] via [[Steven Edwards]], [[Computer Chess Forums|rgc]], July 04, 1994
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=424966 Subject: Maximum Number of Legal Moves] by [[Andrew Shapira]], [[CCC]], May 08, 2005
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73867 Generating all the moves on a board] by [[Marc-Philippe Huget]], [[CCC]], May 07, 2020
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78466 Move structure and hash tables] by gaard, [[CCC]], October 20, 2021
=External Links=