共享会话

🤖 Minimax搜尋分析

分享于 2026年8月18日 23:30

提问者

分析當前的minimax搜尋：是否為廣度搜尋？整個流程是怎樣的？你認為有什麼可以改進的地方？

trigolden_game2652.htmltext/plain · 223.1 KB预览下载

QuanAI

結論：它不是廣度優先搜尋（BFS）

目前的 runStateMinimax() 是：

迭代加深（iterative deepening） + 深度優先（DFS）Minimax + Alpha–Beta 剪枝

它在「逐層增加搜尋深度」這一點上，外觀有點像廣度搜尋；但每次實際評估某個分支時，會一路遞迴走到底（或走到截斷深度）才回溯，因此核心走訪方式是 DFS，不是把同一層所有節點都放進 queue 後再往下一層展開的 BFS。

此外，遊戲並非全程都用 minimax：

殘局：剩餘回合數 turnsLeft <= ENDGAME_MINIMAX_TURNS 時，使用 minimax。
非殘局：使用 runStateMCTS()。
第一手：placeAIFirstMove() 是隨機選棋型、翻面與角度，完全不搜尋。

現有 minimax 的流程

正在绘制流程图…

`runStateMinimax()` 內部的細節

1. 以目前行動方作為根節點的最大化方

const rootPlayer = rootState.mover;

評估值始終從 rootPlayer 的角度看：

目前分差 - 搜尋開始前分差

也就是：

V(s) = \bigl(S_{\text{root}}(s) - S_{\text{opp}}(s)\bigr) - \bigl(S_{\text{root}}(s_0) - S_{\text{opp}}(s_0)\bigr)

這讓本次搜尋的數值表示「這手棋之後，根玩家淨賺／淨失多少分」。

2. 迭代加深

外層做的是：

js
for (let depth = 1; depth <= maxDepth; depth++)

依序完成：

深度 1：只看自己本回合；
深度 2：看自己、對手；
深度 3：再看自己；
…
最多看至 maxDepth = turnsLeft，理論上可搜尋到對局正常結束。

這個設計對限時 AI 很實用：

深度 $d$ 必須「整層完整跑完」才會採用結果；
若時間到，會放棄尚未完成的深度；
但仍能使用深度 $d-1$ 已完成的可靠最佳走法。

這是目前實作中很好的地方。

3. 每一層從全部根走法中選最佳走法

對每個 rootMoves：

js
const child = applySearchTurnToState(rootState, move, { validate: false }).state;
const value = alphaBetaState(child, depth - 1, -Infinity, Infinity);

然後取最大值：

if (value > iterationBestValue) {
  iterationBestValue = value;
  iterationBestMove = move;
}

因此根節點的決策是：

\operatorname*{argmax}_{m \in \text{LegalMoves}(s_0)} V(\operatorname{result}(s_0,m))

4. `alphaBetaState()` 是深度優先遞迴

在任一局面：

先增加節點計數；
檢查取消或逾時；
檢查正常終局；
檢查仲裁終局；
若深度已用完，回傳靜態評估；
產生合法走法並排序；
若輪到根玩家，取子節點最大值；
若輪到對手，取子節點最小值；
以 alpha–beta 條件剪枝。

最大化節點：

js
best = Math.max(best, alphaBetaState(child, depth - 1, alpha, beta));
alpha = Math.max(alpha, best);
if (beta <= alpha) break;

最小化節點：

js
best = Math.min(best, alphaBetaState(child, depth - 1, alpha, beta));
beta = Math.min(beta, best);
if (beta <= alpha) break;

因此它不會像 BFS 那樣先展開所有深度 1，再展開所有深度 2；而是像：

根
 ├─ 走法 A
 │   ├─ 對手走法 A1
 │   │   ├─ 我方走法 A1a
 │   │   └─ 我方走法 A1b
 │   └─ 對手走法 A2
 ├─ 走法 B
 │   └─ ...
 └─ 走法 C

一路深入、回傳、再換下一分支。

仲裁規則在搜尋中的處理

這部分是目前實作的重點，也做得相當正確。

在深度截斷前，程式會先判斷：

js
if (!hasArbitrationDefence(state)) {
  return evaluateArbitrationTerminal(...);
}

換言之，只要輪到某方時，上一方沒有留下至少一組「共活」的仲裁防禦回合，該方可以仲裁直接獲勝。

它使用：

SEARCH_TERMINAL_VALUE = 1000000

表示此類終局：

根玩家能仲裁成功：+1000000
對手能仲裁成功：-1000000

這非常重要，因為它確保 AI 不會在淺層評估中，把「目前多拿幾分、但下一回合必被仲裁判負」誤認為好棋。

合法走法與排序

走法產生

generateLegalTurns(state) 會包含：

一般情形：同一個對方棋子上的兩子共活組合；
最後僅剩一子時：單子合法落點；
計分例外：
- 單接可形成可計分頂鑫；
- 兩子互相構成雙接；
- 不同目標上的跨目標組合，但必須真的形成尚未計分且距離大於 0 的頂鑫。

因此，minimax 並不是只搜尋某些啟發式候選；在殘局模式下，設計目標是搜尋完整合法回合集合。

排序

orderMovesForSearch() 主要依：

moverGain * 100

也就是「這一步立刻造成的己方淨得分」排序；同分時再以棋型優先順序及隨機值打破平手。

這種排序不改變 minimax 理論上的正確性，但會大幅影響 alpha–beta 剪枝效果與限時下的實際棋力。

可以改進的地方

1. 根節點沒有共享 alpha：最直接、最值得先修的效能問題

目前每個根候選都這樣搜尋：

js
alphaBetaState(child, depth - 1, -Infinity, Infinity)

也就是說：即使前面已經找到值為 10 的根走法，下一個根走法仍然以完整窗 [-∞, +∞] 搜尋。

這不影響正確性，但浪費了大量剪枝機會。

改法

在根節點維護 rootAlpha：

js
let rootAlpha = -Infinity;

for (const move of rootMoves) {
  const child = applySearchTurnToState(rootState, move, { validate: false }).state;
  const value = alphaBetaState(child, depth - 1, rootAlpha, Infinity);

  if (value > iterationBestValue) {
    iterationBestValue = value;
    iterationBestMove = move;
  }

  rootAlpha = Math.max(rootAlpha, iterationBestValue);
}

效果是：後面的候選只需證明「能否超過目前最佳值」，通常可讓對手節點更早 beta <= alpha 而被截斷。

2. 應使用上一輪的最佳走法作為 Principal Variation 優先走法

目前根走法排序主要依「當前立即得分」，並帶有隨機打破平手：

js
randomTie: Math.random()

但迭代加深最有價值的資訊之一，就是深度 $d-1$ 的最佳走法通常也是深度 $d$ 最值得先搜的走法。

建議

每完成一層後：

將 committedBestMove 放到下一層 rootMoves 最前；
在每個非根節點，可儲存該局面的最佳走法，下一次優先嘗試；
再搭配 root alpha，剪枝效益會明顯提高。

概念上：

rootMoves = moveBestToFront(rootMoves, committedBestMove);

這通常比單純依當回合得分排序更適合 minimax。

3. 加入置換表（Transposition Table）

目前同一個實質局面若透過不同落子順序抵達，仍可能被重新搜尋。

此遊戲每回合有兩子，且部分棋子組合在幾何與庫存狀態上可能重合；加上跨目標例外，搜尋樹中產生等價狀態並不意外。

置換表應記錄

至少要用以下資訊組成 state key：

棋盤上所有棋子的規範化位置／形態集合；
雙方剩餘棋子庫存；
當前行動方；
雙方分數；
scoredVictims；
任何會影響合法性、計分或仲裁的狀態。

表項則存：

{
  depth,
  value,
  boundType, // EXACT / LOWER / UPPER
  bestMove
}

其中 boundType 很重要，因為 alpha–beta 中被截斷的值不一定是精確 minimax 值。

效益：

大幅減少重複展開；
可提供 hash move，改善走法排序；
尤其在殘局深搜時很有價值。

4. 深度截斷評估函式太單薄

現有評估函式只看分數差：

return currentDiff - rootBaseDiff;

即：

\text{eval} = \Delta \text{score}_{root} - \Delta \text{score}_{opponent}

若搜尋已經完整走到終局，這完全合理；但在「時間不夠、只能提交較淺完整深度」時，它對局面品質的辨識不足。

例如兩個同樣暫時 $+2$ 的局面：

A：對方下回合有大量立即得分與安全共活；
B：對方幾乎沒有可下的共活，甚至接近仲裁風險；
C：己方下一手有高價值頂鑫威脅。

目前在深度截斷時，三者可能全被當成同一價值。

可加的啟發式特徵

在不破壞終局精確性的前提下，只在 depth <= 0 使用：

\text{eval} = w_s \cdot \Delta\text{score} + w_m \cdot \Delta\text{mobility} + w_t \cdot \Delta\text{tacticalPotential} + w_a \cdot \text{arbitrationSafety} + w_i \cdot \Delta\text{inventoryFlexibility}

可考慮：

己方／對方可用合法回合數；
共活回合數，尤其是仲裁防禦用的共活數；
立即可形成的單接、雙接、跨目標計分機會；
對手下一回合可拿到的最大即時得分；
棋型庫存稀缺性與配對彈性；
能否讓對手缺乏仲裁防禦，而己方仍保持防禦。

注意：仲裁必勝／必敗仍應維持 ±SEARCH_TERMINAL_VALUE，不應只以一般啟發式處理。

5. 合法走法生成與完整排序可能比遞迴本身更昂貴

每個節點都可能執行：

generateLegalTurns(state)
orderMovesForSearch(state, legalMoves)

而排序時對每個走法又做：

analyseSearchMove(state, move)

其中會模擬落子與計分。若合法回合數很多，時間可能大量花在：

列舉所有共活；
產生跨目標配對；
幾何相容檢查；
模擬計分；
對每個走法都做完整排序分析。

現有增量索引、SAT 快取與延遲建立子節點索引，已經是很好的優化；但還能再進一步。

建議

快取某局面的合法走法與排序結果
同一局面被重訪時不必重新列舉與排序。
分階段走法排序
優先順序可為：
- TT/hash move；
- 上一深度 PV move；
- 仲裁相關／強制防禦走法；
- 立即得分高的走法；
- 其他普通走法。
延遲產生走法（lazy move generation）
不一定要先完整建出所有走法、完整算完所有排序分數，才開始搜尋。
保留完整性與啟發式候選剪枝的區別
若 minimax 要作為「精確殘局求解器」，不能直接丟掉未被看好的合法走法；可以改變搜尋順序，但不能任意減少候選集合。
若目標是更快但允許近似，才可用 beam search、候選上限等方法。

6. 時限檢查應深入到昂貴迴圈

目前 alphaBetaState() 一進入節點會檢查：

js
if (cancelAi || performance.now() >= deadline) {
  throw new SearchTimeout();
}

這是必要的；但如果某次 generateLegalTurns() 或 orderMovesForSearch() 內部非常昂貴，瀏覽器仍可能在那段時間內卡住，直到回到遞迴節點入口才發現逾時。

建議

將 deadline / cancel token 傳入：

共活組合列舉；
跨目標組合列舉；
大型排序迴圈；
幾何驗證批次迴圈。

每處固定間隔檢查一次，必要時立即丟出 SearchTimeout。
這不只會讓 AI 更準時，也會改善取消按鈕與 UI 回應性。

7. 隨機排序不利於可重現測試與除錯

目前在：

shuffledCopy()；
tilePriority；
randomTie: Math.random()；

都引入隨機性。

這能避免 AI 永遠走同一種同分棋，但也會造成：

同一盤面、同一秒數，結果可能不同；
難以做回歸測試；
難以比較某次優化是否真的提升；
TT / PV move 的效果較不穩定。

建議

把「搜尋排序」與「最終同分選擇」分開：

搜尋期間固定排序：使用穩定 deterministic key；
最終僅在價值相同的最佳根走法中隨機挑選；
或以固定 seed 的 PRNG，讓棋譜可重現。

8. MCTS 與 minimax 的評估邏輯可再統一

這不是 minimax 本身的錯誤，但和整體 AI 有關：

minimax 的葉節點：直接用分數差；
MCTS 的葉節點：也直接靜態評估，再經 tanh(rawValue / 6) 正規化；
MCTS 沒有真正的隨機 rollout，而比較接近「UCB 選擇 + 靜態葉節點評估」。

這是可行的設計，但代表中局棋力高度依賴靜態評估；而目前靜態評估又只看得分差，對「可用共活」「仲裁壓力」「下回合頂鑫威脅」的敏感度不夠。

若先改善第 4 點的評估函式，minimax 截斷品質與 MCTS 中局品質都會一起提升。

建議的優先級

優先做：低風險、高報酬

根節點共享 alpha
上一迭代最佳走法優先（PV ordering）
搜尋排序改為 deterministic；最終同分才隨機
在走法生成／排序的內層迴圈加入 deadline 檢查

第二階段：明顯提升殘局速度與棋力

置換表 + hash move
快取合法走法與排序結果
加強深度截斷的局面評估

第三階段：較複雜的強化

PVS / Negamax 重構；
killer move、history heuristic；
aspiration window；
若接受近似結果，再考慮 beam search 或 selective extension。

總評

目前實作的架構其實已具備不錯的基礎：

正確區分一般終局與仲裁終局；
仲裁判定置於深度截斷之前；
有迭代加深，且只提交完整深度；
有 alpha–beta；
有走法排序；
有 SAT 快取、增量索引、延遲建立子節點索引；
殘局 minimax、中局 MCTS 的切換邏輯清楚。

最關鍵的不足不在於「它是不是 BFS」——它明確不是，而是 DFS 型 alpha–beta minimax——而在於：

根節點未共享 alpha、缺乏 PV/TT 導向的排序、截斷評估只看分差，以及合法走法產生／排序仍可能是主要時間瓶頸。

若只做一項修改，我會先做「根 alpha 共用 + PV move 優先」；這通常是最小改動且能立即提高實際搜尋深度的改善。