Changes

Jump to: navigation, search

Encoding Moves

3,803 bytes added, 18:21, 10 May 2020
A second method for encoding moves using move index of some sort.
<span id="MoveIndex"></span>
==Move Index==
===With a list of legal moves===
If the 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.
{|
| <span style="font-size: 80%;">3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1</span>
|}
 
===Encoding moves as if on an empty board===
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 board:
* pawn - 12 (4 promotion * 3 targets)
* knight - 8
* bishop - 13
* rook - 14
* queen - 27
* king - 8 (there are two additional castling moves, but they are only possible from the start position 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>2 + 12*8 + 8*2 + 13*2 + 14*2 + 27 + 8 == 203</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) = 2 + 8*2 + 13*2 + 14*(2+8-n) + 27*(1+n) + 8 == 219 + 13n</code>. <code>f(n=2)=245</code> is the highest <code>n</code> such that the upper bound is lower than <code>256==2^8</code>.
 
So for legal Chess960 positions with at most 2 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 <code>popcount</code> 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==
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.

Navigation menu