DEV Community

Payam ghaderkourehpaz
Payam ghaderkourehpaz

Posted on

High-Performance Turn-Based Game AI: Integrating Bitboard Representation with Alpha-Beta Pruning in Rust and Go

#algorithms #go #performance #rust

Building game engines for classical board games (such as American Checkers, Draughts, Chess, and Backgammon) presents a classic computer science challenge: maximizing search depth within tight interactive latency budgets (sub-100ms per move).

While naive implementations frequently model the board as a multidimensional array or slice of objects, this approach suffers from severe cache misses and branching penalties in deep game trees. In this post, we explore how bitboard representation combined with Zobrist hashing and optimized Alpha-Beta pruning unlocks an order-of-magnitude performance improvement.

1. The Memory Bottleneck: Struct Arrays vs. Bitboards

Consider a standard 8x8 draughts board utilizing 32 playable dark squares. A naive representation in Go or Rust might look like this:

#[derive(Clone, Copy, PartialEq)]
enum Piece {
    Empty,
    WhiteMan,
    WhiteKing,
    BlackMan,
    BlackKing,
}

struct Board {
    squares: [Piece; 32],
    turn: Player,
}
Enter fullscreen mode Exit fullscreen mode

While clean and expressive, traversing a tree to ply 12 requires millions of state clones. Each state clone incurs memory allocations or array copies, causing L1/L2 cache evictions.

The Bitboard Solution

A Bitboard represents the presence or absence of pieces across the board as bit flags within standard CPU registers (u32 for 32 dark squares in checkers, or u64 for full 64-square chess boards):

struct Bitboard {
    white_men: u32,
    white_kings: u32,
    black_men: u32,
    black_kings: u32,
}
Enter fullscreen mode Exit fullscreen mode

The entire board state fits into four 32-bit registers (16 bytes total). Checking board properties becomes a series of single-cycle bitwise operations (AND, OR, XOR, NOT).

2. High-Speed Move Generation with Bit Shifts

In 8x8 draughts, diagonal steps map to fixed bit shifts. If squares are numbered 0 to 31, a forward-right step corresponds to a shift of +4 or +5 depending on the row's parity.

To compute all unoccupied landing squares for White men stepping forward-right:

// Compute all empty squares
let occupied = b.white_men | b.white_kings | b.black_men | b.black_kings;
let empty = !occupied;

// Forward-right moves for row with +4 shift
let right_moves = (b.white_men << 4) & empty & RIGHT_MASK;
Enter fullscreen mode Exit fullscreen mode

Population Count (popcount)

Counting material or evaluating piece count previously required iterating through an array. With bitboards, evaluating material balance compiles down to the native hardware instruction POPCNT:

#[inline(always)]
fn material_evaluation(b: &Bitboard) -> i32 {
    let white_score = (b.white_men.count_ones() as i32 * 100) 
                    + (b.white_kings.count_ones() as i32 * 175);
    let black_score = (b.black_men.count_ones() as i32 * 100) 
                    + (b.black_kings.count_ones() as i32 * 175);
    white_score - black_score
}
Enter fullscreen mode Exit fullscreen mode

A modern x86-64 or ARM64 processor executes count_ones() in a single clock cycle with zero memory access.

3. State Deduplication: Zobrist Hashing & Transposition Tables

In game trees, multiple move permutations frequently reach the exact same state (transposition). Without memoization, an Alpha-Beta search will evaluate duplicate subtrees repeatedly.

Zobrist Hashing computes a unique 64-bit fingerprint for any board state using pseudo-random XOR operations:

  1. Initialize a 3D table of random 64-bit integers: ZOBRIST_TABLE[piece_type][square].
  2. When a piece moves from from_sq to to_sq: Hash' = Hash XOR ZOBRIST[p][from_sq] XOR ZOBRIST[p][to_sq]

Because XOR is reversible, updating the hash takes O(1) without recomputing the board from scratch.

Transposition Table Entry 

struct TTEntry {
    hash: u64,
    depth: u8,
    score: i32,
    flag: NodeFlag, // Exact, LowerBound, UpperBound
    best_move: u16,
}
Enter fullscreen mode Exit fullscreen mode

During tree traversal, before expanding a node to depth d, if the transposition table already stores a search at depth >= d, the engine returns the cached evaluation immediately, cutting branching factors in half.

4. Move Ordering: The Secret to Alpha-Beta Efficiency

The theoretical optimum for Alpha-Beta pruning evaluates O(sqrt(b^d)) nodes instead of O(b^d)—effectively doubling search depth. However, this theoretical optimum is achieved only if the best move is searched first.

We order candidate moves using a three-tier heuristic:

  1. Hash Move: The best move stored in the Transposition Table from earlier shallow iterations (Iterative Deepening).
  2. Forced Jumps & Tactical Captures: In draughts, captures are mandatory. In other games, captures are prioritized via MVV-LVA (Most Valuable Victim - Least Valuable Attacker).
  3. Killer Heuristic: Non-capture moves that caused beta cutoffs in sibling nodes at the same search depth.

5. Benchmark Results

Comparing a naive struct-array engine against an optimized Bitboard + Transposition Table engine in a 10-ply search from standard starting positions:

Metric Naive Struct Array Bitboard + TT + Move Ordering
Nodes Evaluated / sec ~280,000 ~4,200,000
Speedup Factor 1.0x (Baseline) 15.0x
Max Search Depth (500ms budget) 6 plies 11 plies
Memory Allocations / Move ~14,000 allocs 0 allocs

Summary

By transitioning from heap-allocated objects to register-aligned bitboards and integrating hardware-level instructions like POPCNT and CTZ, turn-based game engines achieve deterministic sub-millisecond evaluation, unlocking superhuman tactical play on modest mobile and server hardware.

Top comments (0)