25,161
edits
Changes
no edit summary
| <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 moves a Piece piece of a given type can make from one [[Squares|Squaresquare]] - for [[Sliding Pieces|sliding pieces]] assuming no obstacles:
{| class="wikitable"
! Piece
<span id="Enumeration"></span>
===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.
=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=
