A Gomoku AI With Minimax, Alpha-Beta Pruning, and Pattern-Based Evaluation

#javascript #ai #gamedev #algorithms

A Gomoku AI With Minimax, Alpha-Beta Pruning, and Pattern-Based Evaluation

The hard AI does a 4-ply minimax search with alpha-beta pruning. A 15×15 board has 225 cells, so naive minimax at depth 4 would visit 225^4 ≈ 2.5 billion positions. Pruning + restricting moves to cells within radius 2 of existing stones cuts this to a few thousand. Combined with a pattern-based evaluator that scores open-three, closed-four, etc., the result plays competent opening and blocks immediate threats.

Gomoku (five-in-a-row) is simpler than chess but deep enough to need actual search. The game tree is huge, the heuristics matter, and the difference between "easy" and "hard" AI is mostly about how deep you can afford to search.

🔗 Live demo: https://sen.ltd/portfolio/gomoku-ai/
📦 GitHub: https://github.com/sen-ltd/gomoku-ai

Features:

15×15 standard Gomoku board (Canvas rendering)
Minimax + alpha-beta pruning
3 difficulty levels (depth 1 / 2 / 4)
Pattern-based evaluator (open/closed, 2-4 in a row)
Move restriction to radius-2 of existing stones
Immediate-threat blocking
Undo, move history, last-move highlight
Japanese / English UI
Zero dependencies, 42 tests

The pattern evaluator

The eval function scans every line (rows, columns, both diagonals) and scores each run of consecutive same-color stones based on length and open-ended-ness:

export function scorePattern(count, openEnds) {
  if (count >= 5) return 1_000_000; // win
  if (count === 4 && openEnds === 2) return 50_000; // open four - forced win
  if (count === 4 && openEnds === 1) return 1_000;  // closed four
  if (count === 3 && openEnds === 2) return 1_000;  // open three - strong
  if (count === 3 && openEnds === 1) return 100;
  if (count === 2 && openEnds === 2) return 100;
  if (count === 2 && openEnds === 1) return 10;
  return 0;
}

"Open" means both ends of the run are empty cells (not blocked by opponent or edge). An open three is nearly as good as a closed four because you can make an open four next turn.

The overall board score is own_patterns - opponent_patterns * 1.1 — slightly defensive, which prevents the AI from going all-in on offense while the opponent builds a winning threat.

Alpha-beta pruning

Classic alpha-beta: track the best score the maximizing player is guaranteed (alpha) and the best the minimizing player is guaranteed (beta). Prune any branch where beta <= alpha because neither side would rationally pick it:

function minimax(board, depth, isMax, player, alpha, beta) {
  if (depth === 0 || isTerminal(board)) return evaluateBoard(board, player);
  const moves = getNearbyCells(board, 2);
  if (isMax) {
    let best = -Infinity;
    for (const [r, c] of moves) {
      const newBoard = placeStone(board, r, c, player);
      best = Math.max(best, minimax(newBoard, depth - 1, false, player, alpha, beta));
      alpha = Math.max(alpha, best);
      if (beta <= alpha) break; // α-β cutoff
    }
    return best;
  } else {
    // symmetric min branch
  }
}

Without pruning, depth-4 is infeasible. With pruning + good move ordering (evaluating promising moves first), entire subtrees get skipped and depth-4 finishes in well under a second for most board states.

Move restriction

The crucial optimization: don't consider every empty cell. At any point in the game, the only moves worth evaluating are cells within a few cells of existing stones:

export function getNearbyCells(board, radius = 2) {
  const nearby = new Set();
  for (let r = 0; r < BOARD_SIZE; r++) {
    for (let c = 0; c < BOARD_SIZE; c++) {
      if (board[r][c] !== EMPTY) continue;
      // Check if any stone exists within `radius`
      for (let dr = -radius; dr <= radius; dr++) {
        for (let dc = -radius; dc <= radius; dc++) {
          const nr = r + dr, nc = c + dc;
          if (nr >= 0 && nr < BOARD_SIZE && nc >= 0 && nc < BOARD_SIZE && board[nr][nc] !== EMPTY) {
            nearby.add(`${r},${c}`);
          }
        }
      }
    }
  }
  return [...nearby].map(s => s.split(',').map(Number));
}

After a few moves, a typical search considers ~20-40 candidates per ply instead of 200+. This is what makes depth-4 practical.

Win detection from the last move

Instead of scanning the whole board each turn, checkWin starts from the last placed stone and walks outward in 4 directions (horizontal, vertical, both diagonals):

export function checkWin(board, row, col, player) {
  const directions = [[0,1], [1,0], [1,1], [1,-1]];
  for (const [dr, dc] of directions) {
    let count = 1;
    // Walk positive direction
    let r = row + dr, c = col + dc;
    while (inBounds(r, c) && board[r][c] === player) { count++; r += dr; c += dc; }
    // Walk negative direction
    r = row - dr; c = col - dc;
    while (inBounds(r, c) && board[r][c] === player) { count++; r -= dr; c -= dc; }
    if (count >= 5) return true;
  }
  return false;
}