7
edits
Changes
→Move Index
| <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==
