No history yet

Bitboard State Representation

The 64-Bit Board

To build an AI that can master a game like 2048, you need to simulate millions of games. Standard 2D arrays are too slow and memory-intensive for this scale. The performance bottleneck isn't just computation; it's memory access. Every cache miss is a costly delay when you're running deep search algorithms like Monte Carlo Tree Search.

The solution is to pack the entire 4x4 board into a single 64-bit unsigned integer (uint64_t). This might seem restrictive, but it's a perfect fit. Since a 4x4 grid has 16 tiles, we can dedicate 4 bits, or one nibble, to each tile. This gives us 16 tiles × 4 bits/tile = 64 bits in total.

A nibble can represent integers from 0 to 15. We don't store the tile's face value directly. Instead, we store its base-2 logarithm. An empty tile is 0, a '2' tile is 1, a '4' tile is 2, an '8' tile is 3, and so on. This scheme allows us to represent tiles up to 32768 (which is $2^{15}$). The rare 65536 tile would require a 5th bit, but for most high-performance training, a 4-bit representation is a highly effective trade-off.

This compact structure means the entire game state is a single value. It can be passed to functions by value, stored in a single CPU register, and copied with a single instruction. This is a massive win for performance.

Accessing and modifying tiles involves bitwise operations. To get a tile at a specific row and column, you shift the board's 64-bit integer to the right and apply a mask.

#include <cstdint>

// Use a type alias for clarity
using board_t = uint64_t;

// Get the log2 value of a tile at (row, col)
// (0,0) is the top-left tile
int get_tile(board_t board, int row, int col) {
    // Each tile is 4 bits. Find the correct shift amount.
    int shift = (row * 4 + col) * 4;
    // Shift the bits into the least significant position and mask
    return (board >> shift) & 0xF;
}

// Set the log2 value of a tile at (row, col)
board_t set_tile(board_t board, int row, int col, int value) {
    int shift = (row * 4 + col) * 4;
    // First, create a mask to clear the 4 bits at the target position.
    // Then, OR the board with the new value shifted into place.
    return (board & ~(0xFULL << shift)) | (static_cast<board_t>(value) << shift);
}

Bitwise Move Generation

The real power of bitboards emerges when generating moves. Instead of iterating through a 2D array, we can manipulate entire rows or columns at once. A row is simply a 16-bit value that can be extracted with a single shift and mask. A column is trickier, as its bits are non-contiguous. However, we can use precomputed lookup tables or specialized bit-twiddling hacks to transpose the board or pack columns into 16-bit integers efficiently.

Once a row is extracted into a 16-bit integer, we can perform a move (left or right slide) using a lookup table. A 16-bit integer has $2^{16}$ (65,536) possible values. We can precompute the result of a slide-and-merge operation for every single one of these values. The table would store both the new state of the row and the score generated by the merges.

During a simulation, a 'move left' operation becomes four table lookups, one for each row. This is orders of magnitude faster than a loop-based approach.

Performance Implications

This bitboard representation is fundamental to achieving the performance needed for deep searches. The benefits are multifaceted:

  1. Cache Locality: The entire board state is contained within a single 8-byte word. This fits perfectly within a single cache line (typically 64 bytes), drastically reducing cache misses. When a search algorithm traverses millions of nodes in a game tree, keeping the state representation compact ensures the CPU's cache is used effectively.

  2. State Hashing: In many search algorithms, we need to store visited states in a transposition table to avoid re-computing results. With a uint64_t representation, the board is its own hash key. There's no need to compute a hash function; we can use the board's 64-bit value directly. This eliminates hash collisions (unless you are using a smaller table and need to modulo) and speeds up lookups significantly.

  3. Parallelism: Bitwise operations map directly to CPU instructions that can operate on 64 bits simultaneously. This is a form of that is impossible to achieve with array-based representations, where you are limited to processing one element at a time.

By moving state representation from a high-level abstraction like a 2D array to a low-level bitboard, you unlock the full potential of the underlying hardware. It's a critical optimization for any agent that relies on exploring a vast number of future possibilities.

Quiz Questions 1/5

Why is a single 64-bit unsigned integer (uint64_t) an ideal choice for representing a 4x4 game board in a high-performance 2048 AI?

Quiz Questions 2/5

In the described bitboard implementation for 2048, how is the value of a tile actually stored within its 4-bit segment?