Evaluation: Pattern Lookup Tables

The Evaluation Problem

At every leaf node, the search needs a static score estimating which player is winning. On a 19x19 board searching to depth 10, the evaluation function is called millions of times per move. It must be fast.

What needs scoring: continuous stone lines (open threes, open fours, gomoku), blocking threats, capture opportunities, capture vulnerability, and positional advantage. Iterating the board and counting patterns at each call would be far too slow.

Window-Based Pattern Extraction

For each position, the engine extracts a 9-cell window along each of the 4 axes (horizontal, vertical, two diagonals): 4 cells backward from the center + the center stone + 4 cells forward. Each cell is encoded in 2 bits:

• 00 = empty
• 01 = player 1
• 10 = player 2
• 11 = out-of-bounds

The full 9-cell window becomes an 18-bit integer. The center 2 bits are fixed to WINDOW_CENTER_VALUE = 0 (encoded as empty) — this works because separate lookup tables exist for each player (patternScoreTablePlayerOne / patternScoreTablePlayerTwo), so the center cell does not need to encode player identity. The remaining 16 bits from the 8 side cells are the variable part that distinguishes patterns. This encoding uses the bitboard directly — pattern extraction is a series of bit shifts and masks, not array lookups.

- 9-Cell diagonal Window and 18-bit Encoding -

Pre-Computed Lookup Table

At server startup, all $2^{18} = 262{,}144$ possible 18-bit patterns are evaluated once and stored in score arrays:

Source: minimax/src/gomoku/eval/Evaluation.cpp:280-304

      // minimax/src/gomoku/eval/Evaluation.cpp:280-304
void initCombinedPatternScoreTables() {
  std::fill(patternScoreTablePlayerOne,
            patternScoreTablePlayerOne + LOOKUP_TABLE_SIZE, INVALID_PATTERN);
  std::fill(patternScoreTablePlayerTwo,
            patternScoreTablePlayerTwo + LOOKUP_TABLE_SIZE, INVALID_PATTERN);

  const unsigned int sideCount = 1 << (2 * SIDE_WINDOW_SIZE);

  for (unsigned int backward = 0; backward < sideCount; ++backward) {
    if (!isValidBackwardPattern(backward)) continue;
    for (unsigned int forward = 0; forward < sideCount; ++forward) {
      if (!isValidForwardPattern(forward)) continue;

      unsigned int pattern = (backward << (2 * (SIDE_WINDOW_SIZE + 1))) |
                             (WINDOW_CENTER_VALUE << (2 * SIDE_WINDOW_SIZE)) |
                             forward;
      patternScoreTablePlayerOne[pattern] =
          evaluateContinuousPattern(backward, forward, PLAYER_1);
      patternScoreTablePlayerTwo[pattern] =
          evaluateContinuousPattern(backward, forward, PLAYER_2);
    }
  }
}

    

At search time, evaluation reduces to: extract 18-bit pattern per axis, index the table, sum. Four lookups total per position:

This is the payoff of the bitboard representation: the evaluation that dominates runtime is reduced to $O(1)$ per axis.

Source: minimax/src/gomoku/eval/Evaluation.cpp:324-369

      // minimax/src/gomoku/eval/Evaluation.cpp:324-369
int evaluateCombinedAxis(Board *board, int player, int x, int y,
                         int dx, int dy) {
  int score = 0;
  unsigned int forward =
      board->extractLineAsBits(x, y, dx, dy, SIDE_WINDOW_SIZE);
  unsigned int backward =
      board->extractLineAsBits(x, y, -dx, -dy, SIDE_WINDOW_SIZE);
  unsigned int revBackward = reversePattern(backward, SIDE_WINDOW_SIZE);

  unsigned int combined = (revBackward << (2 * (SIDE_WINDOW_SIZE + 1))) |
                          (WINDOW_CENTER_VALUE << (2 * SIDE_WINDOW_SIZE)) |
                          forward;
  if (player == PLAYER_1) {
    score = patternScoreTablePlayerOne[combined];
  } else if (player == PLAYER_2) {
    score = patternScoreTablePlayerTwo[combined];
  }
  // ... capture scoring adjustments ...
  return score;
}

    

Simple vs Hard Evaluation

Simple eval (easy/medium difficulty) uses raw lookup table scores. The pattern table already encodes whether a pattern is an open three, closed four, gomoku, etc. — the score is a single table lookup per axis. This is fast and sufficient for lower difficulties.

Hard eval (hard difficulty) goes further. Beyond raw scores, it counts specific pattern types using the PatternCounts struct and applies weighted scoring with nuanced logic:

Source: minimax/inc/gomoku/Evaluation.hpp:9-25

      // minimax/inc/gomoku/Evaluation.hpp:9-25
#define MINIMAX_TERMINATION 1000000

#define CAPTURE_WIN 22000000
#define GOMOKU 21000000
#define BLOCK_GOMOKU 2000000
#define PERFECT_CRITICAL_LINE 1900000
#define BLOCK_CRITICAL_LINE 1800000
#define CAPTURE_BLOCK_CRITICAL 1700000
#define CAPTURE_CRITICAL 1600000

#define CONTINUOUS_OPEN_4 9000
#define CONTINUOUS_CLOSED_4 5000
#define CONTINUOUS_OPEN_3 4500
#define CONTINUOUS_CLOSED_3 4000
#define CONTINUOUS_OPEN_2 -3000
#define PERFECT_LINE 10000

    

The hard evaluation adds several layers over the simple eval:

• Capture vulnerability penalty — penalizes stones that can be sandwiched
• Perfect critical line detection — gomoku on lines that can't be captured
• Capture-on-critical-line bonuses — breaking an opponent's 4-in-a-row by capturing
• Center bonus with distance falloff — slight positional advantage for central play

The score hierarchy reflects priority decisions: CAPTURE_WIN (22M) beats GOMOKU (21M) because a 5-pair capture can override a would-be gomoku that contains capturable stones. These values were hand-tuned through playtesting — getting the relative priorities right (should blocking a 4-in-a-row score higher than making your own open 3?) is what makes the hard evaluation strong.