共享会话

🔧 MCTS搜尋修復改進

分享于 2026年8月17日 05:52

提问者

修復和改進當MCTS搜尋時，未能實時顯示時間和搜尋量。

為什麼在改成增量運算之後，運算量反而不如之前？

檢查代碼，看是否存在錯誤以及有哪些可以修復和改進的地方。

回答要求：

不要影響當前正確的流程，明確給出所要修改的地方和所要替換的代碼。

trigolden_game264.htmltext/plain · 237.6 KB预览下载

QuanAI

以下是對附件中 MCTS、增量索引、計時及 UI 更新流程的檢查結果。重點是：目前確實存在顯示錯誤，增量運算也存在「形式上增量、實際上每個搜尋節點大量複製」的效能問題。

一、問題結論

1. MCTS 沒有即時顯示時間，是明確的程式錯誤

目前 runStateMCTS() 中寫死：

time: '—'

所以不論運算多久，都不可能顯示實際時間。

而且目前只有：

js
if (searchCount % 10 === 0)

才更新一次畫面。假如每次模擬很慢，在時限內只完成 1～9 次搜尋，就會完全看不到任何 MCTS 進度更新。

2. 即使使用定時器，也無法在同步重運算期間重繪

目前 MCTS、候選生成、索引推導全部在瀏覽器主執行緒執行。

以下程式：

js
await new Promise(resolve => setTimeout(resolve, 0));

只有在程式執行到這一行時，瀏覽器才有機會更新畫面。如果單次：

generateLegalTurns()
orderMovesForSearch()
deriveIncrementalIndex()
analyseSearchMove()

耗時很長，畫面在這段時間仍然會暫停。

因此第一階段修復應改成「按時間節流，且每完成一次模擬便檢查是否應重繪」，而不能按每 10 次更新。

3. 增量運算後搜尋量降低的主要原因

目前每次搜尋套用一個假想回合時：

js
const parentIndex = ensureStateIncrementalSync(state);

next.incremental = deriveIncrementalIndex(
  parentIndex,
  next,
  placedPieces,
  adjudication.newScoredKeys
);

會立即建立完整子節點索引。

而 deriveIncrementalIndex() 一開始又會執行：

const index = cloneIncrementalIndex(parentIndex);

cloneIncrementalIndex() 會複製：

完整 idMap
完整 methods
雙方全部 byPlayer
完整 byTarget
完整 byEdge
全部 coLivePairs
全部 mutualPairs
全部 singleScoring

之後還會：

js
for (const [methodKey, method] of index.methods)

掃描所有現存活法，判斷新棋是否干涉。

所以目前真正的成本接近：

每建立一個搜尋子節點，就複製一次完整活法資料庫，再掃描一次全部活法。

這不是純粹的 O(新增棋子) 增量更新。當活法與配對數量很多時，完整複製 Map/Set 的成本、記憶體配置以及垃圾回收，可能比以前直接重算更慢。

4. `analyseSearchMove()` 造成大量不必要索引建立

目前：

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

analyseSearchMove() 的主要目的是計算：

當回合得分
單接數量
是否雙接
排序分數

但舊流程會在這裡立即為 applied.state 建立完整子索引。

而 analyseSearchMove() 被以下流程反覆呼叫：

runTacticalPresearch()
根候選排序
MCTS 根節點再次排序
Minimax 節點排序

很多被分析的子節點根本沒有繼續展開，卻仍提前支付完整索引建立成本。

最安全的改進方法是：

搜尋子節點先保存「父索引＋本回合新增棋子」，只有真正需要生成下一層合法回合時，才建立子索引。

這是延遲增量索引，不改變合法性、計分或搜尋結果。

5. MCTS 根候選被重複排序、重複分析

startAI() 已經執行：

rootMoves = orderMovesForSearch(rootState, rootMoves, tacticalScores);

但進入 runStateMCTS() 後又執行：

root.orderedMoves = orderMovesForSearch(rootState, rootMoves, tacticalScores);

同一批根候選被重新 analyseSearchMove() 一次。

這部分可以直接移除，不影響候選次序和搜尋流程。

6. 顯示的「搜尋次數」不包含前置運算

目前 searchCount 只在 MCTS 完成一次模擬後增加：

searchCount++;

但 AI 時限從這裡開始：

js
const startTime = performance.now();
const overallDeadline = startTime + timeLimit;

之後還要執行：

等待正式局面的增量索引
仲裁防禦生成
全部合法根候選生成
全單接／全雙接戰術預搜索
根候選排序
最後才進入 MCTS

因此「搜尋次數降低」不一定代表全部運算量降低，而是大量時間消耗在 MCTS 前置處理和增量索引複製中，這些工作沒有計入 searchCount。

二、必須修改 1：修復 MCTS 時間與搜尋量即時顯示

找到：

js
async function runStateMCTS(rootState, rootMoves, maxDepth, deadline, tacticalScores, cValue) {

在以下內容：

let searchCount = 0;

後面加入：

js
const mctsStartTime = performance.now();
let lastMCTSProgressTime = mctsStartTime;
const MCTS_PROGRESS_INTERVAL = 100;

修改後為：

js
async function runStateMCTS(rootState, rootMoves, maxDepth, deadline, tacticalScores, cValue) {
  const rootPlayer = rootState.mover;
  const opponent = rootPlayer === 1 ? 2 : 1;
  const rootBaseDiff = rootState.scores[rootPlayer] - rootState.scores[opponent];

  let searchCount = 0;

  // MCTS 本身的開始時間，不包含前面的候選建構及戰術預搜索。
  const mctsStartTime = performance.now();

  // 按經過時間更新畫面，不再依賴「每 10 次」。
  let lastMCTSProgressTime = mctsStartTime;
  const MCTS_PROGRESS_INTERVAL = 100;

然後在 MCTS 迴圈末端找到：

js
searchCount++;

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

  await new Promise(resolve => setTimeout(resolve, 0));
}

把以上整段替換成：

js
searchCount++;

const progressNow = performance.now();

/*
 * 每完成一次模擬都檢查是否需要更新。
 *
 * 不能再使用 searchCount % 10：
 * 如果單次模擬很慢，整個時限只完成不到 10 次，
 * 原本就永遠不會顯示 MCTS 進度。
 */
if (
  searchCount === 1 ||
  progressNow - lastMCTSProgressTime >= MCTS_PROGRESS_INTERVAL
) {
  showMessage(
    t('ai-mcts-progress', {
      time: ((progressNow - mctsStartTime) / 1000).toFixed(1),
      count: searchCount
    }),
    0,
    true
  );

  /*
   * 讓出主執行緒，讓瀏覽器實際重繪訊息框，
   * 同時讓取消 AI 的點擊事件有機會被處理。
   */
  await new Promise(resolve => setTimeout(resolve, 0));

  lastMCTSProgressTime = performance.now();
}

這項修改會修復：

MCTS 時間永遠顯示 —
少於 10 次搜尋時完全沒有進度
搜尋很慢時長時間不更新
取消 AI 操作反應過慢

不會改變：

UCB 選擇
Progressive widening
節點評估
搜尋結果
計分流程

三、必須修改 2：避免 MCTS 根候選重複排序

在 runStateMCTS() 中找到：

js
const root = makeNode(rootState);
root.orderedMoves = orderMovesForSearch(rootState, rootMoves, tacticalScores);

替換為：

js
const root = makeNode(rootState);

/*
 * startAI() 在呼叫 runStateMCTS() 之前已經用 tacticalScores
 * 完成根候選排序，這裡直接沿用，避免所有根候選被再次
 * analyseSearchMove()。
 */
root.orderedMoves = rootMoves.slice();

原因是 startAI() 已經有：

rootMoves = orderMovesForSearch(rootState, rootMoves, tacticalScores);

原本等於對全部根候選進行兩次相同的：

analyseSearchMove()
applySearchTurnToState()
計分分析
增量索引推導

這項替換不會改變排序結果，因為傳入 runStateMCTS() 的 rootMoves 已經完成排序。

四、必須修改 3：把搜尋節點索引改成延遲建立

這是改善搜尋量最重要的一項。

3.1 替換 `cloneSearchState()`

找到完整的：

js
function cloneSearchState(state) {

替換成：

js
function cloneSearchState(state) {
  return {
    boardPieces: state.boardPieces.slice(),
    counts: { ...state.counts },
    scores: { ...state.scores },
    scoredVictims: new Set(state.scoredVictims),
    mover: state.mover,
    turnNumber: state.turnNumber,
    scoringMode: state.scoringMode,
    startingPlayer: state.startingPlayer,
    gameNumber: state.gameNumber,
    lastTurnPieces: state.lastTurnPieces.slice(),
    nextHypId: state.nextHypId,

    version: state.version,
    incremental: state.incremental,
    incrementalPromise: state.incrementalPromise,

    /*
     * 搜尋子節點的延遲增量資料。
     *
     * applySearchTurnToState() 建立子局面時不立即複製整份索引；
     * 只有真正需要生成下一層合法回合時，才由
     * ensureStateIncremental()/ensureStateIncrementalSync()
     * 建立。
     */
    incrementalParent: state.incrementalParent || null,
    incrementalPlacedPieces: state.incrementalPlacedPieces
      ? state.incrementalPlacedPieces.slice()
      : null,
    incrementalNewScoredKeys: state.incrementalNewScoredKeys
      ? state.incrementalNewScoredKeys.slice()
      : null
  };
}

3.2 替換 `ensureStateIncremental()`

找到完整的：

js
async function ensureStateIncremental(state) {

替換為：

js
async function ensureStateIncremental(state) {
  if (state.incremental) {
    return state.incremental;
  }

  if (state.incrementalPromise) {
    const index = await state.incrementalPromise;

    if (!state.incremental) {
      state.incremental = index;
    }

    return state.incremental;
  }

  /*
   * 搜尋子節點的延遲增量建立。
   *
   * 只有在這個局面真的需要生成合法回合、仲裁防禦、
   * 共活或單接資料時，才從父索引推導。
   */
  if (state.incrementalParent) {
    state.incrementalPromise = (async () => {
      const parentIndex = await ensureStateIncremental(
        state.incrementalParent
      );

      const index = deriveIncrementalIndex(
        parentIndex,
        state,
        state.incrementalPlacedPieces || [],
        state.incrementalNewScoredKeys || []
      );

      if (!state.incremental) {
        state.incremental = index;
      }

      // 建立完成後釋放父鏈參照，降低 MCTS 記憶體占用。
      state.incrementalParent = null;
      state.incrementalPlacedPieces = null;
      state.incrementalNewScoredKeys = null;

      return state.incremental;
    })();

    return state.incrementalPromise;
  }

  /*
   * 沒有父增量資訊時，才使用完整重建作為相容備援。
   */
  state.incremental = buildIncrementalIndexFromBoard(state);
  state.incrementalPromise = Promise.resolve(state.incremental);

  return state.incremental;
}

3.3 替換 `ensureStateIncrementalSync()`

找到完整的：

js
function ensureStateIncrementalSync(state) {

替換為：

js
function ensureStateIncrementalSync(state) {
  if (state.incremental) {
    return state.incremental;
  }

  /*
   * 搜尋中的同步呼叫者不能 await，因此在真正需要索引時，
   * 才同步從父索引增量推導。
   */
  if (state.incrementalParent) {
    const parentIndex = ensureStateIncrementalSync(
      state.incrementalParent
    );

    state.incremental = deriveIncrementalIndex(
      parentIndex,
      state,
      state.incrementalPlacedPieces || [],
      state.incrementalNewScoredKeys || []
    );

    state.incrementalPromise = Promise.resolve(state.incremental);

    // 建立完成後釋放父鏈參照。
    state.incrementalParent = null;
    state.incrementalPlacedPieces = null;
    state.incrementalNewScoredKeys = null;

    return state.incremental;
  }

  /*
   * 只有不是正常增量子節點、也沒有可用父索引時，
   * 才完整重建。
   */
  state.incremental = buildIncrementalIndexFromBoard(state);
  state.incrementalPromise = Promise.resolve(state.incremental);

  return state.incremental;
}

3.4 修改 `applySearchTurnToState()` 的搜尋分支

在 applySearchTurnToState() 末端找到：

js
if (backgroundIndex) {
  /*
   * 正式人類／AI 落子：
   * 先完成遊戲流程和畫面切換，再在背景更新持久索引。
   */
  scheduleIncrementalIndex(state, next, placedPieces, adjudication.newScoredKeys);
} else {
  /*
   * MCTS/minimax 子節點：
   * 必須立即得到子節點索引，但只從父索引增量推導。
   */
  const parentIndex = ensureStateIncrementalSync(state);

  next.incremental = deriveIncrementalIndex(parentIndex, next, placedPieces, adjudication.newScoredKeys);

  next.incrementalPromise = Promise.resolve(next.incremental);
}

替換為：

js
if (backgroundIndex) {
  /*
   * 正式人類／AI 落子仍維持原有流程：
   * 先更新遊戲狀態與畫面，再排入正式增量索引佇列。
   */
  next.incrementalParent = null;
  next.incrementalPlacedPieces = null;
  next.incrementalNewScoredKeys = null;

  scheduleIncrementalIndex(
    state,
    next,
    placedPieces,
    adjudication.newScoredKeys
  );
} else {
  /*
   * MCTS/minimax 假想子節點改為延遲建立索引。
   *
   * 以前在每一次 analyseSearchMove()/排序時都立即複製完整索引，
   * 即使該子節點最後不會被展開也照樣支付全部成本。
   *
   * 現在只保存父局面與本回合差異；真正需要生成下一層候選時，
   * ensureStateIncrementalSync() 才會建立。
   */
  next.incremental = null;
  next.incrementalPromise = null;

  next.incrementalParent = state;
  next.incrementalPlacedPieces = placedPieces.slice();
  next.incrementalNewScoredKeys =
    adjudication.newScoredKeys.slice();
}

這項改動不會改變：

子局面的棋盤
庫存
分數
scoredVictims
合法回合
共活
單接
雙接
仲裁判定

它只改變索引建立時間：

原本：建立每一個假想子局面時立即建立
現在：真正展開這個子局面時才建立

五、必須修改 4：初始化狀態時加入延遲索引欄位

為了避免不同類型的 SearchState 欄位不一致，應在建立原始狀態的兩個位置加入三個欄位。

4.1 修改 `createRawSearchStateFromGlobals()`

找到回傳物件尾部：

js
version: ++committedStateVersion,
incremental: null,
incrementalPromise: null

替換成：

js
version: ++committedStateVersion,
incremental: null,
incrementalPromise: null,

// 正式根局面沒有延遲父索引。
incrementalParent: null,
incrementalPlacedPieces: null,
incrementalNewScoredKeys: null

4.2 修改 `createSearchStateForBoard()`

同樣找到：

js
version: ++committedStateVersion,
incremental: null,
incrementalPromise: null

替換成：

js
version: ++committedStateVersion,
incremental: null,
incrementalPromise: null,

incrementalParent: null,
incrementalPlacedPieces: null,
incrementalNewScoredKeys: null

這部分只是明確初始化欄位，不會改變現有流程。

六、建議修改 5：戰術預搜索必須遵守自己的截止時間

目前 runTacticalPresearch() 的第一個根候選掃描：

js
for (let i = 0; i < rootMoves.length; i++) {

裡面沒有在開始分析下一個候選前檢查 deadline。

因此即使設定：

const tacticalDeadline = ... timeLimit * 0.4

第一階段仍可能掃描全部候選並耗盡總時限，使 MCTS 根本沒有時間運行。

在 runTacticalPresearch() 中找到：

js
const tacticalRoots = [];

for (let i = 0; i < rootMoves.length; i++) {

替換為：

js
const tacticalRoots = [];

/*
 * 若直接戰術掃描未能完整處理全部根候選，
 * 不使用部分 tacticalScores，避免先被掃描到的候選
 * 得到不公平的排序加成。
 */
function createEmptyTacticalScores() {
  const scores = new Map();
  scores.rootPlayer = rootPlayer;
  return scores;
}

for (let i = 0; i < rootMoves.length; i++) {
  if (cancelAi) {
    return createEmptyTacticalScores();
  }

  if (performance.now() >= deadline) {
    return createEmptyTacticalScores();
  }

其餘迴圈內容保持不變。

這樣可以保證所謂「戰術搜索最多使用 40% 時間」真正生效，不會因根候選過多而吃掉全部 MCTS 時間。

七、建議修改 6：修正「背景更新」的註解與排程

目前：

js
function yieldIncrementalBackground() {
  return new Promise(resolve => setTimeout(resolve, 0));
}

以及：

scheduleIncrementalIndex(...)

並不是真正在背景執行。

setTimeout(..., 0) 只是把工作延後到下一個主執行緒工作，deriveIncrementalIndex() 開始後仍然會阻塞：

畫面更新
使用者操作
AI 搜尋
計時顯示

可以將 yieldIncrementalBackground() 替換成較友善的空閒排程：

js
function yieldIncrementalBackground() {
  return new Promise(resolve => {
    if (typeof requestIdleCallback === 'function') {
      requestIdleCallback(
        () => resolve(),
        {
          timeout: 100
        }
      );
    } else {
      setTimeout(resolve, 0);
    }
  });
}

這不會讓運算真正多執行緒化，但能降低正式落子後立刻與 UI 重繪競爭主執行緒的機率。

要做到真正背景運算，必須移到 Web Worker；但目前索引包含大量 Map、Set、棋子物件和函式依賴，直接改 Worker 涉及較大架構變更。為了不破壞現有正確流程，建議先完成上述延遲索引修改。

八、另一個需要注意的效能來源

目前 deriveIncrementalIndex()：

js
for (const [methodKey, method] of index.methods) {

仍會掃描所有舊活法。

此外：

cloneIncrementalIndex(parentIndex)

仍會完整複製所有配對 Map。

延遲索引修改可以避免大量「根本不需要展開的節點」建立索引，但真正被展開的節點還是要支付這項成本。

下一階段可以考慮：

依 SAT 格子建立空間索引，只檢查新棋附近活法。
coLivePairs 改由 byTarget 即時計算，避免每個子節點複製全部配對。
mutualPairs 使用 copy-on-write，而不是完整 new Map()。
對 (state.version, turnSignature) 快取 analyseSearchMove()。
把方法索引拆成不可變父層＋子層增刪集合。

但這些會改動較大，建議先不要和本次修復混在一起。

九、修改後預期改善

完成前四項必要修改後，預期會有以下效果：

MCTS 顯示真實經過時間。
搜尋次數少於 10 時仍可看到進度。
每約 100ms 更新一次，而不是固定每 10 次。
根候選不再重複完整分析。
候選排序不再為每個一次性子局面建立完整增量索引。
MCTS、Minimax 只對真正展開的子節點建立索引。
記憶體配置和垃圾回收次數明顯下降。
相同時限內完成的 MCTS 模擬次數應明顯增加。
正式落子、計分、合法性、仲裁、undo/redo 流程保持不變。

十、建議測試項目

修改後至少測試：

MCTS 設定 3 秒，確認時間由 0.0s 持續增加。
搜尋量低於 10 次時，確認仍有顯示。
中途按叉取消 AI，確認能停止且不落子。
AI 切換 Easy/Hard/Expert 後重新思考。
普通同目標兩子落子。
同一目標同一條邊應被拒絕。
跨目標且沒有得分結構應被拒絕。
跨目標且存在合法頂鑫結構應通過。
仲裁只承認共活的原有規則。
undo/redo 後再啟動 AI。
第一局結束切換第二局。
棋譜導入後啟動 AI。
AI 搜尋完成後正式 actionCheck() 再次驗證應通過。
比較修改前後相同盤面、相同秒數的 搜尋次數。
確認修改前後相同落子帶來的分數完全一致。

其中效能改善最大的修改是：

applySearchTurnToState() 不再立即執行 deriveIncrementalIndex()，改成在真正展開子節點時延遲建立。

🔧 MCTS搜尋修復改進

一、問題結論

1. MCTS 沒有即時顯示時間，是明確的程式錯誤

2. 即使使用定時器，也無法在同步重運算期間重繪

3. 增量運算後搜尋量降低的主要原因

4. analyseSearchMove() 造成大量不必要索引建立

5. MCTS 根候選被重複排序、重複分析

6. 顯示的「搜尋次數」不包含前置運算

二、必須修改 1：修復 MCTS 時間與搜尋量即時顯示

三、必須修改 2：避免 MCTS 根候選重複排序

四、必須修改 3：把搜尋節點索引改成延遲建立

3.1 替換 cloneSearchState()

3.2 替換 ensureStateIncremental()

3.3 替換 ensureStateIncrementalSync()

3.4 修改 applySearchTurnToState() 的搜尋分支

五、必須修改 4：初始化狀態時加入延遲索引欄位

4.1 修改 createRawSearchStateFromGlobals()

4.2 修改 createSearchStateForBoard()

六、建議修改 5：戰術預搜索必須遵守自己的截止時間

七、建議修改 6：修正「背景更新」的註解與排程

八、另一個需要注意的效能來源

九、修改後預期改善

十、建議測試項目

4. `analyseSearchMove()` 造成大量不必要索引建立

3.1 替換 `cloneSearchState()`

3.2 替換 `ensureStateIncremental()`

3.3 替換 `ensureStateIncrementalSync()`

3.4 修改 `applySearchTurnToState()` 的搜尋分支

4.1 修改 `createRawSearchStateFromGlobals()`

4.2 修改 `createSearchStateForBoard()`