Devlog 0x8 - Chess Move Encoding
Devlog 0x8. Today, we will talk about encoding and decoding chess moves. We need this so that we can store possible moves as 32 bit integers.
Encoding Chess Moves
In my chess engine, Kirin, we are going to use 32 bit integers to encode moves that are made in the game.
Here's what that looks like. First, let's establish what given bits within this 32 bit integer represent:
Binary Move Bits Representation Constants in Hex
0000 0000 0000 0000 0011 1111 Source Square 0x3f
0000 0000 0000 1111 1100 0000 Target Square 0xfc0
0000 0000 1111 0000 0000 0000 Piece 0xf000
0000 1111 0000 0000 0000 0000 Promoted Piece 0xf0000
0001 0000 0000 0000 0000 0000 Capture Flag 0x100000
0010 0000 0000 0000 0000 0000 Double Pawn Push 0x200000
0100 0000 0000 0000 0000 0000 Enpassant Flag 0x400000
1000 0000 0000 0000 0000 0000 Castling Flag 0x800000
As you can see, we only actually need the 24 least significant bits of the integer for my implementation of move encoding.
Encoding Implemented
To implement this encoding, you simply need a function that takes in information about a chess move, LHS each piece of information by the given number of bits already used, and then bitwise OR them together:
pub fn encodeMove(source: u32, target: u32, piece: u32, promoted: u32, capture: u32, double: u32, enpassant: u32, castling: u32) u32 {
return source | (target << 6) | (piece << 12) | (promoted << 16) | (capture << 20) | (double << 21) | (enpassant << 22) | (castling << 23);
}
Decoding Implemented
To implement decoding, we simply need to do the inverse of what's been done above. In the table above, the constants in hex are hexadecimal representations of the binary move bits.
This means that all we need to do to decode is bitwise AND the move with the given constant to "mask" the desired bits, and then RHS the result by the number of bits we used to encode that piece of information. Here's a few examples:
fn decodeMoveSource(move: u32) u32 {
return move & 0x3f;
}
fn decodeMoveTarget(move: u32) u32 {
return (move & 0xfc0) >> 6;
}
fn decodeMovePiece(move: u32) u32 {
return (move & 0xf000) >> 12;
}
fn decodeMovePromoted(move: u32) u32 {
return (move & 0xf0000) >> 16;
}
Thank you to Maksim Korzh, his implementation was incredibly useful when creating my own.
Thanks for reading and I'll see you tomorrow :)