🔍 MCTS 效能與卡頓分析

以下僅依附件中的程式碼分析，不涉及修改。

一、MCTS 搜尋時為何顯示「—s」

直接原因在 runStateMCTS() 的進度更新區塊：

if (searchCount % 10 === 0) {
  showMessage(
    t('ai-mcts-progress', {
      time: '—',
      count: searchCount
    }),
    0,
    true
  );
  await new Promise(resolve => setTimeout(resolve, 0));
}

而 ai-mcts-progress 的文字模板是：

'蒙地卡羅樹搜尋 | 用時: {time}s | 搜尋次數: {count}'

所以 {time} 被硬編碼為 —，結果自然就是「—s」。這不是計時器失效，也不是 performance.now() 不能用；同一份程式中：

• runStateMinimax() 已經用
  js

  ((performance.now() - minimaxStartTime) / 1000).toFixed(1)

  顯示實際耗時；
• startAI() 的完成訊息也已用
  js

  ((performance.now() - startTime) / 1000).toFixed(1)

  顯示總耗時。

因此，MCTS 缺少的只是把開始時間保存並在進度訊息中計算差值；現有架構本身已具備所需計時來源。

二、generateArbitrationDefenceTurns() 與 generateLegalTurns() 的區別

兩者都先呼叫：

generateLegalSinglePlacements(state, state.mover)

產生「每一顆棋子單獨落下」的全部幾何合法落點；差別在於如何把兩個單子組成一個完整回合。

generateLegalTurns()：完整合法回合

它保留所有正常可走的回合：

1. 同一目標棋子

   • 兩顆新棋落在同一顆對方棋子；
   • 但不能貼同一條目標邊；
   • 兩顆新棋彼此不能衝突；
   • 庫存要足夠。

2. 不同目標棋子

   • 只有符合「頂鑫結構例外」時才合法；
   • 預篩條件是：
     js

     singleScoring[i] || singleScoring[j] || formsTriGolden(first, second)

     即其中一顆單獨形成可計分頂鑫，或兩顆新棋彼此形成頂鑫；
   • 最後仍會以 validateTurnOnState() 做完整驗證，包括：
     js

     adjudicateSearchTurn(state, move)

     確認確實形成尚未計分、距離大於 0 的計分結構。

所以它是「這一回合實際可以下甚麼」的完整集合。

generateArbitrationDefenceTurns()：仲裁專用的「共活」集合

它刻意忽略：

• 單接；
• 雙接；
• 跨目標頂鑫例外；
• 任何雖然合法、但不是「兩子同貼一個對方棋子的不同邊」的走法。

其核心分組是：

const targetMap = new Map();

for (const ghost of singles) {
  if (!targetMap.has(ghost.targetId)) {
    targetMap.set(ghost.targetId, []);
  }
  targetMap.get(ghost.targetId).push(ghost);
}

之後只在同一個 targetId 的候選內兩兩配對，並要求：

if (firstTargetEdge === secondTargetEdge) {
  continue;
}

也就是「同一對方棋子、不同邊」的共活。

程式註解與實際邏輯是一致的：即使一方還有單接、雙接或跨目標頂鑫的合法走法，只要沒有留下至少一組共活，下一方仍可仲裁成功。

最後一子時兩者幾乎一致

若某方只剩最後一顆棋子，getRequiredPiecesForState(state) 會回傳 1。此時兩個函式都改為：

generateLegalSinglePlacements(state, state.mover).map(ghost => [ghost])

因為末手只要求存在任意一個合法單子。

三、目前 MCTS 是否符合「每層列出所有活法、隨機挑一個、更多搜尋高分者」的設想？

部分符合，但不是完全相同的演算法。

1. 每一層的活法：會生成完整集合，但不是一開始全展開

MCTS 節點首次被訪問時，ensureNodeMoves() 會做：

let moves = isRoot ? rootMoves.slice() : generateLegalTurns(node.state);
node.orderedMoves = orderMovesForSearch(node.state, moves, ...);

也就是：

• 每個被實際走到的節點，都會用 generateLegalTurns() 取得完整合法回合集；
• 再用 orderMovesForSearch() 排序；
• 沒有只保留「最高分的幾個」作為唯一合法選項。

這點符合「每層要知道所有活法」的要求。

但是，程式用了 Progressive Widening（漸進擴展）：

const allowedChildren = Math.min(
  node.orderedMoves.length,
  Math.max(1, Math.ceil(MCTS_PW_K * Math.pow(node.visits + 1, MCTS_PW_ALPHA)))
);

含義是：

• 完整候選會先算出並排序；
• 但節點初期只會展開排序最前面的少數候選；
• 隨節點訪問次數增加，才逐步開放更多候選。

因此它不是「每次模擬都從該層全部活法隨機抽一個」，而是「先算全體、按評分排序、再逐漸擴展較靠前的候選」。

2. 它不是隨機 rollout MCTS

典型 MCTS 常見流程是：

1. Selection；
2. Expansion；
3. 隨機 rollout 至終局；
4. Backpropagation。

本程式沒有進行「隨機一路下到終局」的 rollout。展開到指定深度或遇到終局後，直接使用：

evaluateSearchState(node.state, rootPlayer, rootBaseDiff)

作為葉節點分數；其內容基本上是雙方當前分差。

而子節點選擇用的是 UCB：

const explore = cValue * Math.sqrt(
  Math.log(Math.max(1, node.visits)) / child.visits
);
const ucb = exploit + explore;

也就是根據：

• 已累積的平均值 valueSum / visits；
• 訪問次數；
• 探索項 explore；

決定繼續走哪一個分支，不是純隨機。

3. 「更多跑分數高的一個」：目前是「高分優先＋UCB 探索」

orderMovesForSearch() 的排序依據包括：

• 本回合直接淨得分 moverGain；
• 單接數 singleJieCount；
• 雙接 isDoubleJie；
• 戰術預搜尋 tacticalScores。

排序靠前的候選會先被 progressive widening 開放；之後 MCTS 又以 UCB 決定分支投入量。因此可以說它是：

先優先嘗試戰術／直接得分較好的走法，再透過 UCB 在高價值與未充分探索的走法之間分配搜尋量。

它不是隨機抽一個後單純給高分者更多次數，但效果上確實是偏向較高評價的候選。

四、是否使用了增量運算？

有使用的增量／快取：非常有限

目前明確存在的是每顆棋子的 SAT 邊界快取：

function preparePieceSAT(piece) {
  if (!piece || !piece.vertices) return piece;
  if (!piece.satBounds) piece.satBounds = calculateSAT(piece.vertices);
  return piece;
}

這避免同一個棋子每次碰撞檢查都重新計算五軸投影邊界。applySearchTurnToState() 也會保留既有棋子的物件參照，只對新棋準備 SAT：

boardPieces: state.boardPieces.slice()

以及：

preparePieceSAT(piece);

所以，「單一棋子的 SAT 投影」有快取。

沒有使用的關鍵增量運算

對於使用者所說的「只對本回合新增兩顆棋子做局部更新」，在最耗時的部分，程式沒有完成這種增量化。

1. 每個搜尋節點重新生成所有單子

每次 generateLegalTurns(state) 都重新呼叫：

generateLegalSinglePlacements(state, state.mover)

而它會：

• 掃過盤上所有對方棋子；
• 掃過尚可用的棋種；
• 正反面各一次；
• 目標邊 4 種；
• 自己貼合邊 4 種；
• 對每個候選呼叫 validatePlacementGeometry()；
• 再用 isValidGhost() 對整個盤面逐一做幾何衝突檢查。

沒有「父節點候選集 + 新增兩子影響範圍」的更新機制，也沒有按照盤面狀態保存生成結果的 transposition cache。

2. 兩子組合是重新兩兩枚舉

generateLegalTurns() 對所有單子做：

for (let i = 0; i < singles.length; i++) {
  for (let j = i + 1; j < singles.length; j++) {

這是平方級配對。每一對還可能進行：

• twoGhostsCompatible(first, second)；
• formsTriGolden(first, second)；
• validateTurnOnState(state, move)；
• adjudicateSearchTurn(state, move)。

這不是局部增量。

3. 計分是全盤重新掃描

adjudicateSearchTurn(state, placedPieces) 裡有：

const allPieces = state.boardPieces.concat(placedPieces);

for (const dinger of allPieces) {
  for (const victim of allPieces) {

即使本回合只新增一或兩顆棋，它仍對所有棋子對做接觸、頂點、邊與樹距離判斷，而不是只檢查「新棋與舊棋」及「新棋彼此」。

此外，每個可能的頂鑫關係還會呼叫：

getTreeDistance(dinger, victim, allPieces, idMap)

這也不是沿父狀態保存的可增量圖／距離結果。

4. 死活／共活判斷同樣重算

hasArbitrationDefence(state) 會直接：

return generateArbitrationDefenceTurns(state).length > 0;

而 generateArbitrationDefenceTurns() 不是「找到第一組共活便停止」，而是收集全部共活回合後才回傳陣列。對 MCTS 而言，實際只需要知道是否存在至少一組，卻仍付出了生成所有組合、去重、完整驗證的成本。

結論

目前的情況是：

• 有 SAT 快取；
• 沒有候選走法的真正增量更新；
• 沒有計分／連接圖／樹距離的真正增量更新；
• 沒有局面轉置快取；
• 沒有把「是否有至少一組共活」做早停。

所以答案是：目前並非使用者設想的那種「只根據新增兩子局部更新活法」的增量運算。

五、即使採用增量運算，仍會不會慢？

仍可能慢，但應該會比目前明顯改善。

原因是搜尋本身仍有分支爆炸：

• 每層有多個單子落點；
• 兩子回合需要配對；
• 盤面後期接觸、頂鑫與跨目標例外更多；
• MCTS 會在多個搜尋節點重複生成候選；
• Minimax／戰術預搜尋會遞迴展開多層。

不過，目前的瓶頸不是單純「活邊數量」。更主要是同一批資料被高成本地反覆全盤運算：

真正的增量化若能做到：

• 新落兩子只檢查與其可能接觸的既有棋；
• 局部更新邊接圖；
• 局部更新頂鑫關係與得分；
• 只更新受影響目標棋的單子候選；
• 以局面簽名共用已生成的候選與評估；
• 仲裁防守只需找到第一組時立即停止；

則後期速度預期會有相當大的改善。即使如此，深度過大、時間限制過高、分支數過多時仍然可能慢，但不應像現況一樣在很少的「表面活邊」下出現長時間主執行緒佔滿。

六、手機端卡死的直接原因分析

你提供的訊息是：

AI思考中：候選建構/完整單接/雙接預掃描（96/120）

這非常重要：它表示卡住時尚未進入 MCTS 主循環，而是在 runTacticalPresearch() 的第一段「完整預掃描」：

for (let i = 0; i < rootMoves.length; i++) {
  const move = rootMoves[i];
  const analysis = analyseSearchMove(rootState, move);

  if (analysis.isTactical) {
    tacticalRoots.push({ move, analysis });
    fallbackScores.set(
      turnSignature(move),
      evaluateSearchState(analysis.childState, rootPlayer, rootBaseDiff)
    );
  }

  await aiMaybeYield(
    t('ai-thinking-candidates', {
      phase: `完整單接／雙接預掃描 (${i + 1}/${rootMoves.length})`
    })
  );
}

因此，96/120 的意思不是「正在測 96 條活邊」，而是：

在根局面已生成的 120 個完整兩子回合候選 中，正逐一對第 96 個回合做戰術分析。

analyseSearchMove() 的成本很高

它對每一個候選呼叫：

const applied = applySearchTurnToState(state, move, {
  validate: false
});

而 applySearchTurnToState() 不驗證回合合法性，不代表它很輕。它仍然呼叫：

const adjudication = adjudicateSearchTurn(state, placedPieces);

然後 analyseSearchMove() 又對回合中的每顆棋再做一次：

adjudicateSearchTurn(state, [piece]).hasScoringStructure

一般兩子回合即至少包含：

1. 整個兩子回合一次全盤計分；
2. 第一顆單子一次全盤計分；
3. 第二顆單子一次全盤計分；
4. 如有雙接，還會檢查 formsTriGolden()。

也就是每掃描一個候選，至少三次全盤性計分分析；120 個根候選至少約 360 次這類分析，尚未計入生成 rootMoves 本身的成本。

全盤計分不是輕量操作

如前所述，adjudicateSearchTurn() 對盤面每一對棋子掃描：

for (const dinger of allPieces) {
  for (const victim of allPieces) {

並在可能接觸時進一步檢查頂點對邊、getTreeDistance() 等。

當雙方尚剩 16 與 17 顆時，按初始每方 18 顆推算，盤面大約已有：

• 玩家一已落 2 顆；
• 玩家二已落 1 顆；
• 加上初始局面進度，盤上棋子數大約已達 33 顆左右。

因此，即使可用活邊看起來不多，每次計分仍在掃描約 33–35 顆棋子的全盤關係。這是「活法不多卻仍很慢」的主要解釋。

候選數量不是由「活邊數」單獨決定

一條可用邊可能派生多種候選：

• 3 種棋形；
• 正反面 2 種；
• 每個棋形可能有不同可貼合邊；
• 兩顆棋再彼此配對；
• 同目標不同邊、跨目標頂鑫例外都會產生組合；
• 不同生成順序或幾何位置還要去重與驗證。

所以訊息中的 120 是「完整回合組合數」，不等於活邊數。即使盤面上可見活邊不多，兩子組合仍可達數十或上百。

七、為何會呈現「卡死」，而不只是慢？

1. 所有重運算都在瀏覽器主執行緒

這份程式沒有使用 Web Worker。幾何枚舉、全盤計分、戰術預搜尋、Minimax、MCTS 都在 UI 主執行緒執行。

雖然有：

await new Promise(r => setTimeout(r, 0));

用於讓出事件循環，但那只能發生在一個完整分析步驟完成後。若單一步驟本身很久，瀏覽器仍無法及時：

• 重繪畫面；
• 處理觸控；
• 回應點擊取消；
• 保持系統順暢。

手機 CPU 較弱時，這種主執行緒長任務很容易被感知為頁面卡死。

2. 進度「96/120」代表迴圈有走動，但單項分析已過重

既然 UI 曾顯示到 96/120，表示它此前至少曾讓出主執行緒並刷新訊息；因此比較像是：

• 不一定是無限迴圈；
• 而是第 96 個或後續候選的 analyseSearchMove()／全盤計分特別慢；
• 或手機在這些大量運算、物件建立與垃圾回收壓力下嚴重降速。

3. 戰術預掃描沒有在根候選掃描階段檢查截止時間

runTacticalPresearch() 的前半段掃描：

for (let i = 0; i < rootMoves.length; i++) {
  ...
  const analysis = analyseSearchMove(rootState, move);
  ...
  await aiMaybeYield(...);
}

這段有 cancelAi 的間接讓出機會嗎？沒有直接檢查；更關鍵的是也沒有：

if (performance.now() >= deadline) ...

截止時間檢查只出現在後面的戰術遞迴部分：

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

因此，即使 AI 的設定時間已耗盡，前面的「完整單接／雙接預掃描」仍可能繼續把全部 rootMoves 掃完。這會造成兩個現象：

1. 限時不是硬上限；
2. 在弱手機上，尚未進入真正 MCTS 前就已經用盡甚至超過大量時間。

這是此次 96/120 現象最直接的程式流程原因。

4. 仲裁檢查與每個搜尋節點也有同類問題

在 AI 開始時先做：

const arbitrationDefences = generateArbitrationDefenceTurns(rootState);

MCTS 每個首次訪問節點又會先做：

if (!hasArbitrationDefence(node.state)) {
  ...
}

而 hasArbitrationDefence() 會生成全部仲裁防守走法，不是找到第一組就停。這讓 MCTS 的每個新節點也可能花很多時間做完整枚舉。

八、綜合判定

關於時間顯示

「—s」是明確的硬編碼結果：

time: '—'

不是計時邏輯故障。

關於兩個生成函式

• generateLegalTurns()：AI 真正可走的完整合法回合集，包含頂鑫例外的跨目標走法。
• generateArbitrationDefenceTurns()：只用來判斷有沒有「共活」以阻止仲裁，刻意排除單接、雙接及跨目標例外。

關於增量運算

目前僅有 SAT 邊界快取；核心候選生成、兩子組合、得分判定、樹距離與仲裁防守，基本仍是重複全盤計算，不是以新增兩子進行局部增量更新。

關於手機卡死

依進度訊息可定位到：

runTacticalPresearch()

的根候選「完整單接／雙接預掃描」，尚未進入 MCTS 主迴圈。原因是：

1. 根回合候選有 120 個；
2. 每個候選至少觸發多次全盤 adjudicateSearchTurn()；
3. 每次計分會掃描整盤棋子關係並可能計算樹距離；
4. 預掃描階段沒有以 deadline 中止；
5. 所有工作都在手機瀏覽器的 UI 主執行緒；
6. 雖有 setTimeout(0) 讓出控制權，但不能切斷一個已開始的重型候選分析。

因此，這比較像是演算法重複全盤運算與主執行緒阻塞造成的極慢／假死，而非從訊息可直接判定的無限迴圈。