25,161
edits
Changes
no edit summary
<span id="MoveIndex"></span>
==Move Index==
If the [[Move Generation|generated moves ]] inside a [[Move List|move list]] are [https://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>[https://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>
| <span style="font-size: 80%;">3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1</span>
|}
This method can be refined if variable-length encoding is allowed. This is especially useful for long sequences of moves. If the number of legal moves from the position is equal to <code>n</code> then only <code>ceil(log2(n))</code> bits need to be used to encode the move (note: positions without a move available require special handling; position with one move available need 0 bits, so they may need some more information to encode whether a move was made or the game terminated prior to it, depending on use-case). Empirical data based on a sample of human games shows that each move when encoded with this scheme takes approximately 5.11 bits, that is about 63.8% of the original size (1 byte per move).
A simple variation of this is to use a list of pseudo-legal moves, which may speed up the encoding/decoding process at a cost of a slightly larger size. On the same dataset as above it amounts to approximately 5.41 bits per move, or about 67.7% of the original size. Other methods of indexing into the movelist (for example using 2 indirections - piece and square) and other criteria for the moves included in the movelist can be devised for different tradeoffs between speed and compression ratio.
==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 from one [[Squares|square]] - for [[Sliding Pieces|sliding pieces]] assuming no obstacles:
{| class="wikitable"
! Piece
! # of Moves
! Remarks
|-
| [[Pawn]]
| style="text-align:right;" | 12
| 7th rank, 4 [[Promotions|promotions]] * 3 [[Target Square|target squares]]
|-
| [[Knight]]
| style="text-align:right;" | 8
| from the 16 [[Center#ExtendedCenter|extended center]] squares
|-
| [[Bishop]]
| style="text-align:right;" | 13
| from the 4 [[Center|center]] squares
|-
| [[Rook]]
| style="text-align:right;" | 14
| from any square
|-
| [[Queen]]
| style="text-align:right;" | 27
| 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>
offset = 0
for each square in our_pieces_bb:
if square == move.from:
break
offset += upper_bound(pos.piece_on(square).type)
move_index = offset + piece_move_index(moved_piece, move)</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 [[Population Count|popcount]] instruction is available:
<pre>
offset = 0
for each piece_type lower than moved_piece.type:
offset +=
popcount(pos.pieces_bb(piece_type, side_to_move))
* upper_bound(piece_type)
offset +=
popcount(
pos.pieces_bb(moved_piece.type, side_to_move)
& squares_before_bb(move.from))
* upper_bound(piece_type)
move_index = offset + piece_move_index(moved_piece, move)
</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).
This method is used in one of the move encodings available in the [[BCGN]] chess game storage format <ref>[https://github.com/Sopel97/chess_pos_db/blob/master/docs/bcgn/move_index.md A detailed walkthrough of an implementation of BCGN's move index based move encoding scheme · GitHub]</ref>.
<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
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=20092 Two doubts] by [[Fermin Serrano]], [[CCC]], March 10, 2008
==2010 ...==
* [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]]
==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=
