Introduction: Motivation and Board Representation

What is Minimax Search

Minimax is the classical algorithm for two-player zero-sum games. The idea is simple: one player maximizes the score, the other minimizes it, and both play optimally. At every game state, the algorithm considers all possible moves, alternating between max and min layers to compute the minimax value:

v(s)= \begin{cases} \max_{a\in A(s)} v(s_a) & \text{(MAX)} \\ \min_{a\in A(s)} v(s_a) & \text{(MIN)} \end{cases}

Gomoku is a natural fit for minimax: it's a game of perfect information, zero-sum, and deterministic. But the 19x19 board creates a branching factor of roughly 200+ legal moves per position — making naive minimax computationally intractable at any meaningful depth. Everything in this engine is about taming that branching factor.

Why C++

The engine was first implemented in Python to iterate quickly on rules and heuristics, but 19x19 benchmarks exposed a hard performance ceiling. In internal tests, recursive double-three validation alone was over 10x slower than the C++ version, and full-board search could not realistically meet the project requirement of ~500ms average response time. The production engine was therefore moved to C++98 (a familiar toolchain from previous 42 projects) to achieve predictable latency in search.

The key architectural decision was to represent the board as bitboards: two arrays of uint64_t[19], one per player. This makes move generation, pattern matching, and evaluation a matter of bitwise operations instead of array iteration. The bitboard layout improved more than evaluation alone: occupancy checks became simple OR/AND operations, move generation used shift-based neighbor masks to prune the candidate set, and fixed-size bit extraction with precomputed lookup tables kept evaluation effectively $O(1)$ per axis.

- Minimax request-handling pipeline diagram -

Bitboard Design

The board is stored as two separate uint64_t arrays — one for each player:

Source: minimax/inc/gomoku/Board.hpp:53-54

      // minimax/inc/gomoku/Board.hpp:53-54
uint64_t last_player_board[BOARD_SIZE];
uint64_t next_player_board[BOARD_SIZE];

cpp

Each uint64_t represents one row of the 19x19 board. Bits 0–18 correspond to columns; bits 19–63 are unused. Keeping separate bitboards per player (rather than a single tri-state board) made the implementation easier to maintain while enabling fast OR for occupancy checks and fast AND/SHIFT for pattern extraction in the evaluation function.

      Example row — stones at columns 0, 3, 7, 12, 18

 col:   0    1    2    3    4    5    6    7    8    9   10   11   12   13   14   15   16   17   18
       [●]  [ ]  [ ]  [●]  [ ]  [ ]  [ ]  [●]  [ ]  [ ]  [ ]  [ ]  [●]  [ ]  [ ]  [ ]  [ ]  [ ]  [●]
        │              │                   │                        │                             │
        ▼              ▼                   ▼                        ▼                             ▼
 bit:   1    0    0    1    0    0    0    1    0    0    0    0    1    0    0    0    0    0    1

 uint64_t row_mask:
 ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬──────────────┐
 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0  0  ………  0 │
 └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴──────────────┘
   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18   19 ──────── 63
   ├──────────────── bits 0–18  (used, 1 bit per column) ─────────────────┤  bits 19–63 (always 0)

 (row_mask >> k) & 1  ==  1   →  stone at column k
 (row_mask >> k) & 1  ==  0   →  empty at column k

text

Move generation uses neighbor masks to restrict candidates to positions adjacent to existing stones. Rather than iterating all 361 positions, the engine computes a bitmask of cells neighboring occupied positions using horizontal, vertical, and diagonal bit shifts:

Source: minimax/src/gomoku/search/Minimax.cpp:27-45

      // minimax/src/gomoku/search/Minimax.cpp:27-45
void computeNeighborMask(const uint64_t occupancy[BOARD_SIZE],
                         uint64_t neighbor[BOARD_SIZE]) {
  for (int i = 0; i < BOARD_SIZE; i++) {
    uint64_t row = occupancy[i];
    uint64_t horz = shiftRowLeft(row) | shiftRowRight(row) | row;
    uint64_t vert = 0;
    if (i > 0) vert |= occupancy[i - 1];
    if (i < BOARD_SIZE - 1) vert |= occupancy[i + 1];
    uint64_t diag = 0;
    if (i > 0) {
      diag |= shiftRowLeft(occupancy[i - 1]);
      diag |= shiftRowRight(occupancy[i - 1]);
    }
    if (i < BOARD_SIZE - 1) {
      diag |= shiftRowLeft(occupancy[i + 1]);
      diag |= shiftRowRight(occupancy[i + 1]);
    }
    neighbor[i] = horz | vert | diag;
  }
}

cpp

Neighbor masking applies a bitwise AND between the neighbor mask and inverse occupancy to keep only empty cells near existing stones, typically reducing candidates from 361 to around 20–40. This replaces a full-board cell scan with a few bitwise operations per row.

Zobrist hashing provides incremental board hashing for the transposition table. A table of random 64-bit keys (piece_keys[19][19][3]) is generated at startup using Boost's MT19937 RNG. Placing or removing a stone XORs the corresponding key into the hash — no full-board recomputation ever needed.

Undo/Redo during search uses an UndoInfo struct that records the move and any captured stones. The board is mutated in-place and restored after each recursive call, avoiding expensive board copies at every search node.

Difficulty Modes

The engine exposes three difficulty levels, each selecting a different search algorithm and evaluation function:

Difficulty	Search Algorithm	Max Depth	Time Limit	Eval Function
Easy	Alpha-Beta	5	None	Simple
Medium	Iterative Deepening	Up to 10	0.4s	Simple
Hard	PVS	10	None	Hard (pattern-counted)

On the opening move the engine always plays center — a standard Gomoku heuristic. The simple evaluation uses raw lookup table scores (fast, sufficient for lower difficulties); the hard evaluation counts specific pattern types and applies nuanced capture vulnerability analysis — details in Evaluation.

References

Prev Next