A Better Way to Represent Chess Moves

In the previous post Piece Movement Part 3: Pseudo-Legal Move Generation we used a normal C# struct to represent the move with some int and bool variables inside. This is a readable way to do things and can work well for a beginner chess engine. However, this is not the most memory efficient way to do this.

When a chess engine starts evaluating all of the positions, it evaluates millions per second, memory usage becomes a critical thing to manage. A competitive chess engine will need to find a better way to take up less space.

How can we Improve This?

You're likely already using bitboards, so the answer here will be unsurprising, binary. We can use a 16-bit binary number to store all of the necessary data for a chess move. A single int in C# is 32-bits, so this is a huge memory saving.

• Bits 0-5: From square (0-63)

• Bits 6-11: From square (0-63)

• Bits 12-15: Flags (capture, promotion types, en passant, castling)

Defining Move Flags

Using just 4 bits, we can represent 16 different move types. Here is an example struct I have used that defines the flags.

public struct MoveFlag
{
	public const int None = 0;                  //quiet Move
	public const int PawnDoublePush = 1;
	public const int CastleKingSide = 2;
	public const int CastleQueenSide = 3;
	public const int Capture = 4;
	public const int EnPassantCapture = 5;

	//promotion
	public const int PromoteKnight = 8;
	public const int PromoteBishop = 9;
	public const int PromoteRook = 10;
	public const int PromoteQueen = 11;

	//promotion with capture
	public const int PromoteKnightCapture = 12;
	public const int PromoteBishopCapture = 13;
	public const int PromoteRookCapture = 14;
	public const int PromoteQueenCapture = 15;

	//masks for faster checking
	public const int PromotionMask = 8; // 1000 binary
	public const int CaptureMask = 4;   // 0100 binary
}

Here is a table of why these specific numbers were chosen in that order. It basically comes down to each bit in the 4 bits representing something, for example if the first bit is 1 then it is a promotion. Using this, rather than checking manually if the flag is 8, or 9, or 10 and so on for a promotion, we can just check the move for the PromotionMask to get this information easily.

public bool isPromotion = (Flag & MoveFlag.PromotionMask) != 0;

The Move Struct

Now that we can represent the move flags in 4 bits, here is how the full move struct is created. It is a good idea to also have some helper variables inside of here. I use lambdas here as they dont take up memory, the variables just calculate the result when the variable is called and do not store any data.

public struct Move
{
	// raw data
  	private ushort Value;

	public Move(int from, int to, int flag)
    {
        	// to: bits 0-5
	    	// from: bits 6-11, 
		// flag: bits 12-15
        Value  =  (ushort)((to & 0x3F) | 
			  	((from & 0x3F) << 6) | 
		    		((flag & 0xF) << 12));
   	}
	
	//----helper variables----

	//decoding
	public int EndingPos => Value & 0x3F;
   	public int StartingPos => (Value >> 6) & 0x3F;
   	public int Flag => (Value >> 12) & 0xF;
	
	//flag checks
	public bool IsCapture => (Flag & MoveFlag.CaptureMask) != 0;
   	public bool IsPromotion => (Flag & MoveFlag.PromotionMask) != 0;

	public Piece PromotionPieceType
    {
        get
        {
            switch (Flag)
            {
                	case MoveFlag.PromoteQueen: 
				case MoveFlag.PromoteQueenCapture: 
					return Piece.WhiteQueen;

                	case MoveFlag.PromoteRook: 
				case MoveFlag.PromoteRookCapture: 
					return Piece.WhiteRook;

                	case MoveFlag.PromoteBishop: 
				case MoveFlag.PromoteBishopCapture: 
					return Piece.WhiteBishop;

                	case MoveFlag.PromoteKnight: 
				case MoveFlag.PromoteKnightCapture: 
					return Piece.WhiteKnight;

                	default: return Piece.None;
            }
        }
    }
}

Useful Bitwise Operations

If you're new to bitwise operations and bti manipulation, it might be a bit confusing to look at that move struct, here is some of the code explained in a bit more detail.

Masking

Before anything is moved, we use the bitwise AND (&) to make sure the data fits where it is meant to be.

• 0x3F is 63 in decimal, 00111111 in binary. Masking the square index with this makes sure that we only ever use the first 6 bits.

• 0XF is 15 in decimal, 1111 in binary. This makes sure that the flag never is more than 4 bits. It's done for safety to prevent a value from being more than its meant to and corrupting the whole move data.

Shifting

Left Shifts (<<) are used to push data into the correct parts.

• Target Square stays at the bottom (bits 0-5)

• From Square is shifted 6 bits to fit into bits 6-11

• Flag is shifted 12 bit left to make it fit at the end (bits 12-15)

Combining

To combine these seperate pieces into a single 16 bit value, the OR ( | ) operator is used.