五子棋 AI 設計：Minimax + Alpha-Beta 實戰

Chess Master 八合一棋類裡，五子棋的 AI 是寫起來最有趣的之一。15×15 棋盤、棋子無移動、沒有走法限制 — 看似簡單，但要做出讓玩家覺得「跟它下會輸」的程度，需要 minimax 搜尋 + 評估函式 + 剪枝 + ordering 四個元素配合。這篇拆給你看。

核心演算法：Minimax

Minimax 是回合制零和遊戲的經典演算法。基本概念：

• 輪到 AI（max 玩家）：選對自己最有利的招
• 輪到對手（min 玩家）：假設對手會選對 AI 最不利的招
• 遞迴向下搜尋 N 步深

function minimax(board, depth, isMax) {
  if (depth === 0 || isWin(board)) return evaluate(board);

  if (isMax) {
    let best = -Infinity;
    for (const move of legalMoves(board)) {
      board[move] = AI;
      const score = minimax(board, depth - 1, false);
      board[move] = EMPTY;
      best = Math.max(best, score);
    }
    return best;
  } else {
    let best = Infinity;
    for (const move of legalMoves(board)) {
      board[move] = HUMAN;
      const score = minimax(board, depth - 1, true);
      board[move] = EMPTY;
      best = Math.min(best, score);
    }
    return best;
  }
}

問題：15×15 = 225 個位置。深度 3 的搜尋空間 = 225³ ≈ 1100 萬節點。瀏覽器跑不動。

Alpha-Beta 剪枝

觀察：minimax 樹有很多分支可以「不搜也知道結果」。如果某個對手的選擇已經讓 AI 失敗，AI 就不會走那條路 → 整個子樹可以剪掉。

function minimax(board, depth, alpha, beta, isMax) {
  if (depth === 0 || isWin(board)) return evaluate(board);

  if (isMax) {
    let best = -Infinity;
    for (const move of legalMoves(board)) {
      board[move] = AI;
      best = Math.max(best, minimax(board, depth - 1, alpha, beta, false));
      board[move] = EMPTY;
      alpha = Math.max(alpha, best);
      if (beta <= alpha) break;  // 剪枝
    }
    return best;
  } else {
    let best = Infinity;
    for (const move of legalMoves(board)) {
      board[move] = HUMAN;
      best = Math.min(best, minimax(board, depth - 1, alpha, beta, true));
      board[move] = EMPTY;
      beta = Math.min(beta, best);
      if (beta <= alpha) break;  // 剪枝
    }
    return best;
  }
}

剪枝後實測搜尋節點少 80%。深度 4 的五子棋 AI 在現代瀏覽器跑 1–2 秒能算完。

評估函式（Evaluate）

這是 AI 強度的核心。我用「pattern matching」 — 掃所有方向找特定棋型：

對手的棋型分數取反：

const score = aiPatternScore - humanPatternScore * 1.1;
// 防守稍微比進攻重要 (×1.1)

Move Ordering

剪枝效率高度依賴「先搜好的招」。如果先搜爛招，剪不到很多。Move ordering 的策略：

1. 只考慮已有棋子周圍 2 格內的位置：15×15 = 225 個位置，但合理的選擇通常 < 30 個
2. 用淺層評估排序：對每個候選位置算單步 evaluate，分數高的先搜
3. 勝負招最優先：如果某位置直接勝利或防止失敗，永遠第一個搜

function orderedMoves(board, isMax) {
  const candidates = nearestEmpty(board, 2);
  return candidates.map(m => ({
    move: m,
    score: quickEval(board, m, isMax)
  })).sort((a, b) => b.score - a.score)
    .map(x => x.move);
}

有 ordering 後，深度 6 的 minimax 在瀏覽器跑 1.5 秒能搞定。沒有 ordering 是 30 秒以上。

Iterative Deepening

進階技巧：先搜深度 2 找最佳招，再搜深度 3，再深度 4...... 每層的最佳招做為下一層的 ordering 參考。

let best = null;
for (let d = 2; d <= MAX_DEPTH; d++) {
  if (Date.now() - start > THINK_LIMIT) break;
  best = searchAtDepth(board, d, best);  // 用上次結果做 ordering
}
return best;

好處：時間用完還有「best 到目前為止」的招可用，不會卡住。

難度分級

讓 AI 看起來「在思考」

困難 AI 在現代瀏覽器只要 0.3 秒。但 0.3 秒結束玩家會覺得「電腦作弊」。強制 thinkingTimeMs 讓對局有節奏：

const start = Date.now();
const move = searchBestMove();
const elapsed = Date.now() - start;
const minThink = 1500;
if (elapsed < minThink) {
  await sleep(minThink - elapsed);
}
applyMove(move);

Web Worker 化

minimax 重度計算會卡 UI。把 AI 搬到 Web Worker：

// 主執行緒
const worker = new Worker('ai-worker.js');
worker.postMessage({ board, depth: 6 });
worker.onmessage = (e) => applyMove(e.data.move);

// ai-worker.js
self.onmessage = (e) => {
  const { board, depth } = e.data;
  const move = minimax(board, depth, -Infinity, Infinity, true);
  self.postMessage({ move });
};

結語

五子棋 AI 是「演算法 × 領域知識 × 工程優化」的小型完整案例。這四元素任何一個不到位，AI 都會弱。完整實作（約 400 行）整合在 Chess Master 八合一架構裡，玩家在普通難度跟它下大概 30% 勝率，符合「能贏但不容易」的設計目標。

有想交流棋類 AI 的，歡迎寄信 lo246179268@gmail.com。