Gomoku

1. Minimax with Alpha-Beta Pruning

The AI evaluates future board positions up to depth 3. Alpha-Beta Pruning skips branches that cannot improve the result, dramatically reducing the search space.

function minimax(
  board: Stone[][],
  depth: number,
  alpha: number,
  beta: number,
  isMax: boolean,
  startTime: number,
): number {
  if (Date.now() - startTime > 2000) {
    return evaluateBoard(board);
  }
  const win = checkWinner(board);
  if (win?.winner === 2) return SCORE_TABLE.FIVE;
  if (win?.winner === 1) return -SCORE_TABLE.FIVE;
  if (depth === 0) return evaluateBoard(board);

  const candidates = getCandidates(board);
  if (!candidates.length) return 0;

  if (isMax) {
    let best = -Infinity;
    for (const [r, c] of candidates) {
      board[r][c] = 2;
      const val = minimax(board, depth - 1, alpha, beta, false, startTime);
      board[r][c] = 0;
      best = Math.max(best, val);
      alpha = Math.max(alpha, best);
      if (beta <= alpha) break;
    }
    return best;
  } else {
    let best = Infinity;
    for (const [r, c] of candidates) {
      board[r][c] = 1;
      const val = minimax(board, depth - 1, alpha, beta, true, startTime);
      board[r][c] = 0;
      best = Math.min(best, val);
      beta = Math.min(beta, best);
      if (beta <= alpha) break;
    }
    return best;
  }
}

2. Heuristic Evaluation

Since the AI cannot search to the end of the game, it scores positions using pattern recognition. Open fours and open threes are weighted higher than half-fours and half-threes, and defense is weighted slightly higher than offense.

const SCORE_TABLE = {
  FIVE: 1_000_000,
  OPEN_FOUR: 100_000,
  HALF_FOUR: 10_000,
  OPEN_THREE: 5_000,
  HALF_THREE: 500,
  OPEN_TWO: 100,
  HALF_TWO: 10,
};

function evaluateBoard(board: Stone[][]): number {
  const dirs = [[0,1], [1,0], [1,1], [1,-1]];
  let score = 0;
  for (const [dr, dc] of dirs) {
    score += scanDirection(board, dr, dc, 2) * 1.0;  // AI attack
    score -= scanDirection(board, dr, dc, 1) * 1.1;  // Player defense
  }
  return score;
}

3. Candidate Move Restriction

To keep the branching factor manageable, the AI only considers moves within two cells of existing stones. On an empty board it always plays the center (7, 7).

function getCandidates(board: Stone[][]): [number, number][] {
  const RANGE = 2;
  const candidates = new Set<string>();
  let hasStone = false;
  for (let r = 0; r < 15; r++) {
    for (let c = 0; c < 15; c++) {
      if (board[r][c] === 0) continue;
      hasStone = true;
      for (let dr = -RANGE; dr <= RANGE; dr++) {
        for (let dc = -RANGE; dc <= RANGE; dc++) {
          const nr = r + dr, nc = c + dc;
          if (nr >= 0 && nr < 15 && nc >= 0 && nc < 15 && board[nr][nc] === 0) {
            candidates.add(`${nr},${nc}`);
          }
        }
      }
    }
  }
  if (!hasStone) return [[7, 7]];
  return Array.from(candidates).map(key => key.split(',').map(Number) as [number, number]);
}

4. Overline Rule (장목)

Unlike standard five-in-a-row, Gomoku uses the overline rule: exactly 5 consecutive stones win, but 6 or more do not. The winner check scans all directions and rejects any sequence that can be extended to 6.