QuanAI只读快照

共享会话

下面是claude總結的「為何MCTS搜尋會很慢」的理由,其中第一點我已經請它更改。其餘的四點你是否同意?如果同意請給…

分享于 2026年9月2日 04:14
提问者

下面是claude總結的「為何MCTS搜尋會很慢」的理由,其中第一點我已經請它更改。其餘的四點你是否同意?如果同意請給出修改方案。(明確給出所要修改的地方和所要替換的代碼)

我把 MCTSEngine(第 8531 行起)以及它呼叫的核心函式看了一遍,抓出搜尋每一步實際在做什麼,以及慢在哪裡。

搜尋的四個階段(runSimulation(),8702 行)

  1. Selection(選擇):從 root 沿著已展開的樹往下走,每層呼叫 selectChild() 用 UCT+RAVE 選子節點。
  2. Expansion(展開):走到還沒展開完的節點時,展開一個新子節點。
  3. Rollout(模擬到終局):用啟發式挑選最多 80 步(MAX_SEARCH_PLY),跑到終局或步數上限。
  4. Backpropagation(回傳):把結果沿路徑寫回 visits / value / RAVE。

問題不在這個框架本身,而在於第 1、3 步裡反覆呼叫的 generateCoreActions()(8215 行)太重,而且完全沒有快取

主要慢的原因

1. Selection 階段每次都重算合法走法,沒有快取(影響最大)

runSimulation() 的 selection 迴圈(8711 行)裡:

js
const actionCount = generateCoreActions(this.workCore, this.actions, this.scores);

這一行在每一層、每一次模擬都會執行,即使這個節點早就展開完畢、局面完全沒變。也就是說 root(以及其他高訪問次數的節點)在成千上萬次模擬裡,每次都重新跑一次完整的「產生所有候選走法+算啟發值+排序」流程,結果其實每次都一樣。這是典型的「該快取卻沒快取」,直接把有效模擬次數砍掉一大截。

2. generateCoreActions 本身分支數量非常大,尤其是「維諾階段」

以維諾(vino)階段、且尚未搬動米諾為例(8301–8361 行):

  • 直接放置維諾:4 方向 × 100 個錨點 = 400 種
  • 「先搬米諾、再放維諾」:最多 3 個米諾 × 4 個方向 × 400(方向+錨點)≈ 最多 4800 種組合
  • 若已放過維諾,還會再疊加飛子產生(generateFlightActions,100×100=10000 組合)

單一節點光是「維諾階段」就可能要評估幾千到上萬種候選走法。

3. 每個候選走法的啟發值計算(actionHeuristic,8087 行)本身也不便宜

每次呼叫都會做:

  • quickSquareScore():掃過 294 個正方形遮罩 ×2(新舊局面)
  • centerScore():掃過 100 格 ×2
  • popcountBigInt():逐位元清除迴圈 ×2

單次 actionHeuristic 大約要跑 800 次以上的位元運算。乘上第 2 點的候選數量,單次 generateCoreActions 在維諾階段可能就要跑上百萬次位元運算。

4. 這個重量級函式在 Rollout 階段也是每一步都全套重跑

Rollout 迴圈(8782 行)為了「只從前 12 個候選裡隨機抽一個」,卻還是呼叫同一個 generateCoreActions() 產生全部候選+排序,然後才丟棄大部分。而 rollout 最長可以跑 80 步 —— 相當於每次模擬光 rollout 就可能觸發幾十次上面第 2、3 點的昂貴計算。排序(sortActionsDescending)也是對全部候選排序,即使只需要前 12 名。

5. 棋盤用 100 位元的 BigInt 表示,所有位元運算都是多字組大數運算

black_A/B/Cwhite_A/B/C 都是 BigInt,且超過 64 位元,JS 引擎要用多 limb 的大數運算來處理每一次 &|^、比較。這類運算比原生 NumberUint32Array 上的位元運算慢非常多(通常一個數量級以上),而且會有額外的記憶體配置與 GC 壓力。因為上面第 2–4 點本來就已經是熱迴圈裡數百萬次的位元運算,用 BigInt 等於是在一個已經很密集的迴圈上再乘上一個很大的常數係數。

小結(依影響力排序)

  1. Selection 階段對已展開節點重複呼叫 generateCoreActions,完全沒快取 → 浪費最嚴重。
  2. 「移動米諾+放維諾」與飛子的候選走法組合數本身很大(可到上萬種)。
  3. 每個候選都要跑一次不便宜的啟發函式(quickSquareScore/centerScore/popcount)。
  4. Rollout 每一步都重跑全套產生+排序,即使只用得到隨機抽出的一個。
  5. 底層用 100 位元 BigInt 表示棋盤,讓以上所有熱迴圈裡的位元運算都變慢。

這五點疊加起來,就是「每次模擬」的成本被放大很多倍,導致同樣的搜尋時間預算下,實際能跑的模擬次數非常少,感覺上 MCTS 就特別慢。如果你要,我可以針對第 1 點(節點快取合法走法)先做一版修改,這通常是投報比最高的優化。

vino2266.htmltext/plain · 307.8 KB预览下载
QuanAI

我看過附件中的目前版本;第 1 點的節點走法快取確實已經加入 MCTSEngine.actionCachegetNodeActions()

結論

項目判斷說明
2. 分支數很大同意,但原估算有誇大真正嚴重的是「移米諾 × 放維諾」的笛卡兒積;飛子並沒有實際跑滿 100×100100\times100
3. actionHeuristic() 很重完全同意而且可以改成數學上等價的增量計算,不必犧牲棋力
4. Rollout 產生、排序所有行動完全同意應改成只保留前 12 名的 bounded top-K,避免完整排序及寫入所有候選
5. 100-bit BigInt部分同意BigInt 確實有額外成本,但「通常慢一個數量級」不能直接套用;100-bit 其實只有約兩個 limb,不建議現在全面重寫成 Uint32Array

我建議依序套用:

  1. 增量化 actionHeuristic
  2. 移除候選生成中的重複局面計算
  3. Rollout bounded top-K
  4. Progressive widening
  5. 最後才考慮 BigInt 的低風險優化

一、第 2 點:分支數確實大,但數字需要修正

目前 Vino 是 L 形三格棋子。雖然程式掃描:

js
4 * 100

但每個方向真正不越界的錨點只有 9×9=819\times9=81,因此幾何有效的 Vino 放置最多是:

4×81=3244\times81=324

假設每人最多有 3 個 Mino,「移動後放 Vino」最多約:

3×4×324=38883\times4\times324=3888

這仍然很大,所以結論成立。

但是 Claude 對飛子的描述不準確。generateFlightActions() 中:

js
for (let from = 0; from < 100; from += 1) {
  if (!(minoBits & CELL_BITS[from])) {
    continue;
  }

  for (let to = 0; to < 100; to += 1) {

內層 to 迴圈只會對真正存在的 Mino 執行。若最多 3 個 Mino,約為 300 次檢查,而不是 10,000 次。


修改 2-A:不要在每個候選中重新計算 occupied

目前 isLegalPlacementMask() 每呼叫一次都會重新執行:

js
const occupied = getOccupiedBits(position);

Fino/Mino 還會再次執行:

js
const ownNeighbors = neighborMask(getOwnerBits(position, player));

這些資料在同一個 generateCoreActions() 中是不變的,應該移到迴圈外。

1. 修改 Fino/Mino 的候選生成

generateCoreActions() 找到:

js
if (requiredType === CORE_FINO || requiredType === CORE_MINO) {
  const orientationCount = requiredType === CORE_MINO ? 1 : 4;

  for (let orientation = 0; orientation < orientationCount; orientation += 1) {
    for (let anchor = 0; anchor < 100; anchor += 1) {
      const mask = PLACEMENT_MASKS[requiredType][orientation][anchor];

      if (!isLegalPlacementMask(position, player, requiredType, mask)) {
        continue;
      }

替換為:

js
if (requiredType === CORE_FINO || requiredType === CORE_MINO) {
  const orientationCount = requiredType === CORE_MINO ? 1 : 4;

  // 同一個局面中的 occupied/ownNeighbors 不會改變,
  // 不應對每個候選重新計算。
  const ownNeighbors = neighborMask(oldOwn);

  for (let orientation = 0; orientation < orientationCount; orientation += 1) {
    for (let anchor = 0; anchor < 100; anchor += 1) {
      const mask = PLACEMENT_MASKS[requiredType][orientation][anchor];

      if (
        !mask ||
        (mask & occupied) !== 0n ||
        (mask & ownNeighbors) !== 0n
      ) {
        continue;
      }

後面的 appendGeneratedAction() 保持不變。

這個替換和原本的合法性判定等價。


2. 修改 pending Vino 的合法性判定

在:

js
if (position.pendingMoved) {

區塊中,把:

js
if (!isLegalPlacementMask(position, player, CORE_VINO, mask)) {
  continue;
}

替換為:

js
if (!mask || (mask & occupied) !== 0n) {
  continue;
}

因為 Vino 沒有「不能接觸自己棋子」的限制,只需要檢查越界及重疊。


3. 修改直接放置 Vino 的合法性判定

在:

js
// 直接放置 Vino。

區塊中,同樣把:

js
if (!isLegalPlacementMask(position, player, CORE_VINO, mask)) {
  continue;
}

替換為:

js
if (!mask || (mask & occupied) !== 0n) {
  continue;
}

修改 2-B:不要為每個「移動+Vino」候選修改 position

目前的複合候選會反覆:

js
setTypeBits(position, player, CORE_MINO, movedMinoBits);
const movedOwn = getOwnerBits(position, player);
...
setTypeBits(position, player, CORE_MINO, oldMinoBits);

而且內層每個 Vino 候選又呼叫 isLegalPlacementMask(),重新組合六個 bitboard。

找到整段:

js
// 移動一個 Mino,再放置 Vino。
const oldMinoBits = getTypeBits(position, player, CORE_MINO);

for (let from = 0; from < 100; from += 1) {
  if (!(oldMinoBits & CELL_BITS[from])) {
    continue;
  }

  for (let direction = 0; direction < 4; direction += 1) {
    const to = normalMinoDestination(occupied, from, direction);

    if (to < 0) {
      continue;
    }

    const movedMinoBits = (oldMinoBits & (FULL_BOARD_MASK ^ CELL_BITS[from])) | CELL_BITS[to];

    setTypeBits(position, player, CORE_MINO, movedMinoBits);

    const movedOwn = getOwnerBits(position, player);

    for (let orientation = 0; orientation < 4; orientation += 1) {
      for (let anchor = 0; anchor < 100; anchor += 1) {
        const mask = PLACEMENT_MASKS[CORE_VINO][orientation][anchor];

        if (!isLegalPlacementMask(position, player, CORE_VINO, mask)) {
          continue;
        }

        count = appendGeneratedAction(
          actions,
          scores,
          count,
          encodeMoveVino(from, to, anchor, orientation),
          actionHeuristic(position, player, oldOwn, movedOwn | mask) + 3
        );
      }
    }

    setTypeBits(position, player, CORE_MINO, oldMinoBits);
  }
}

整段替換為:

js
// 移動一個 Mino,再放置 Vino。
// 不修改 position;直接計算移動後的 occupied/own bitboard。
const oldMinoBits = getTypeBits(position, player, CORE_MINO);

for (let from = 0; from < 100; from += 1) {
  const fromBit = CELL_BITS[from];

  if ((oldMinoBits & fromBit) === 0n) {
    continue;
  }

  const clearFromMask = FULL_BOARD_MASK ^ fromBit;

  for (let direction = 0; direction < 4; direction += 1) {
    const to = normalMinoDestination(occupied, from, direction);

    if (to < 0) {
      continue;
    }

    const toBit = CELL_BITS[to];

    const movedOccupied = (occupied & clearFromMask) | toBit;
    const movedOwn = (oldOwn & clearFromMask) | toBit;

    for (let orientation = 0; orientation < 4; orientation += 1) {
      for (let anchor = 0; anchor < 100; anchor += 1) {
        const mask = PLACEMENT_MASKS[CORE_VINO][orientation][anchor];

        if (!mask || (mask & movedOccupied) !== 0n) {
          continue;
        }

        count = appendGeneratedAction(
          actions,
          scores,
          count,
          encodeMoveVino(from, to, anchor, orientation),
          actionHeuristic(position, player, oldOwn, movedOwn | mask) + 3
        );
      }
    }
  }
}

這個修改:

  • 不改變合法走法集合
  • 不改變 action 編碼
  • 不影響 applyAIAction()
  • 不必修改 UI
  • 消除大量 setTypeBits()getOwnerBits()getOccupiedBits()

修改 2-C:MCTS 加入 Progressive Widening

目前節點只要還有未展開走法,就永遠優先展開:

js
if (expanded < actionCount) {

若 root 有 4,000 個候選,前 4,000 次 simulation 幾乎都只是在建立新 child,UCT 很久都沒有真正利用已搜尋的分支。

在常數區加入

放在:

js
const TREE_DECAY_FACTOR = 0.5;

後面:

js
const PROGRESSIVE_WIDENING_BASE = 2;
const PROGRESSIVE_WIDENING_SCALE = 1.8;
const PROGRESSIVE_WIDENING_EXPONENT = 0.45;

MCTSEngine 中加入方法

建議放在 dynamicExplorationConstant() 後面:

js
progressiveWideningLimit(node, actionCount) {
  const visits = this.pool.visits[node];

  const allowed = Math.floor(
    PROGRESSIVE_WIDENING_BASE +
      PROGRESSIVE_WIDENING_SCALE *
        Math.pow(visits + 1, PROGRESSIVE_WIDENING_EXPONENT)
  );

  return Math.min(actionCount, Math.max(1, allowed));
}

runSimulation() 中替換

找到:

js
const expanded = this.pool.expandedCount[node];

if (expanded < actionCount) {

替換為:

js
const expanded = this.pool.expandedCount[node];

const expansionLimit = this.progressiveWideningLimit(
  node,
  actionCount
);

if (expanded < expansionLimit) {

效果大約是:

節點 visits允許展開 children
1約 4
100約 16
1,000約 42
10,000約 116

所有合法走法仍然保留在快取中,只是逐步開放,不是永久剪枝。

這也會順帶降低:

  • selectChild() 掃描 child 的成本
  • updateRave() 掃描 child 的成本
  • node pool 使用量
  • 每個 simulation 前期只擴張、不利用的問題

二、第 3 點:將 actionHeuristic() 改為增量計算

這一點我完全同意。

目前:

js
function actionHeuristic(position, player, oldOwn, newOwn) {
  const squareDelta = quickSquareScore(newOwn) - quickSquareScore(oldOwn);
  const centerDelta = centerScore(newOwn) - centerScore(oldOwn);
  const cellDelta = popcountBigInt(newOwn) - popcountBigInt(oldOwn);

  return squareDelta * 24 + centerDelta * 0.36 + cellDelta * 4 + (player === 1 ? 0.001 : 0.002);
}

實際上一次 action 只會改變少數格子:

  • 放 Mino:1 格
  • 放 Vino:3 格
  • 放 Fino:5 格
  • 移動 Mino:2 格
  • 移動+Vino:最多 5 格

所以只要重新檢查「包含這些變動格子的正方形」即可。


1. 建立每格所屬的 quick square 清單

CENTER_WEIGHTS 初始化完成後,也就是:

js
for (let index = 0; index < 100; index += 1) {
  ...
}

後面加入:

js
/*
 * 每個棋盤格隸屬於哪些 QUICK_SQUARE_MASKS。
 * action 只改變少數格子,因此只有包含變動格子的正方形
 * 才可能改變完成/未完成狀態。
 */
const QUICK_SQUARES_BY_CELL = Array.from(
  { length: 100 },
  () => []
);

for (
  let squareIndex = 0;
  squareIndex < QUICK_SQUARE_MASKS.length;
  squareIndex += 1
) {
  const squareMask = QUICK_SQUARE_MASKS[squareIndex];

  for (let cell = 0; cell < 100; cell += 1) {
    if ((squareMask & CELL_BITS[cell]) !== 0n) {
      QUICK_SQUARES_BY_CELL[cell].push(squareIndex);
    }
  }
}

/*
 * 一個 square 可能同時包含多個變動格子。
 * 使用 stamp 去重,避免同一個 square 重算多次。
 */
const QUICK_SQUARE_VISIT_STAMPS = new Uint32Array(
  QUICK_SQUARE_MASKS.length
);

let quickSquareVisitStamp = 0;

function nextQuickSquareVisitStamp() {
  quickSquareVisitStamp = (quickSquareVisitStamp + 1) >>> 0;

  if (quickSquareVisitStamp === 0) {
    QUICK_SQUARE_VISIT_STAMPS.fill(0);
    quickSquareVisitStamp = 1;
  }

  return quickSquareVisitStamp;
}

這段只在載入頁面時計算一次。


2. 完整替換 actionHeuristic()

把原本的:

js
function actionHeuristic(position, player, oldOwn, newOwn) {
  const squareDelta = quickSquareScore(newOwn) - quickSquareScore(oldOwn);

  const centerDelta = centerScore(newOwn) - centerScore(oldOwn);

  const cellDelta = popcountBigInt(newOwn) - popcountBigInt(oldOwn);

  return squareDelta * 24 + centerDelta * 0.36 + cellDelta * 4 + (player === 1 ? 0.001 : 0.002);
}

替換為:

js
function actionHeuristic(_position, player, oldOwn, newOwn) {
  const changed = oldOwn ^ newOwn;

  if (changed === 0n) {
    return player === 1 ? 0.001 : 0.002;
  }

  let squareDelta = 0;
  let centerDelta = 0;
  let cellDelta = 0;

  const stamp = nextQuickSquareVisitStamp();

  for (let cell = 0; cell < 100; cell += 1) {
    const cellBit = CELL_BITS[cell];

    if ((changed & cellBit) === 0n) {
      continue;
    }

    const ownedAfter = (newOwn & cellBit) !== 0n;

    if (ownedAfter) {
      centerDelta += CENTER_WEIGHTS[cell];
      cellDelta += 1;
    } else {
      centerDelta -= CENTER_WEIGHTS[cell];
      cellDelta -= 1;
    }

    const squareIndexes = QUICK_SQUARES_BY_CELL[cell];

    for (
      let listIndex = 0;
      listIndex < squareIndexes.length;
      listIndex += 1
    ) {
      const squareIndex = squareIndexes[listIndex];

      if (QUICK_SQUARE_VISIT_STAMPS[squareIndex] === stamp) {
        continue;
      }

      QUICK_SQUARE_VISIT_STAMPS[squareIndex] = stamp;

      const squareMask = QUICK_SQUARE_MASKS[squareIndex];

      const completedBefore =
        (oldOwn & squareMask) === squareMask;

      const completedAfter =
        (newOwn & squareMask) === squareMask;

      if (completedBefore === completedAfter) {
        continue;
      }

      const squareValue = QUICK_SQUARE_VALUES[squareIndex];

      squareDelta += completedAfter
        ? squareValue
        : -squareValue;
    }
  }

  return (
    squareDelta * 24 +
    centerDelta * 0.36 +
    cellDelta * 4 +
    (player === 1 ? 0.001 : 0.002)
  );
}

這個版本與原本的 heuristic 數學上等價,但:

  • 不再對每個候選掃描 294 個 square 兩次
  • 不再掃描棋盤 100 格兩次
  • 不再做兩次完整 popcount
  • 只處理真正改變的 1~5 格

這應是剩餘修改中投報比最高的一項。


三、第 4 點:Rollout 改成 bounded top-K

目前 rollout 只使用前 12 名:

js
const heavyWidth = Math.min(12, actionCount);

generateCoreActions() 仍然:

  1. 將所有候選寫入陣列
  2. 對所有候選完整排序
  3. 最後只取 12 個

應讓 rollout 模式在生成過程中只保留目前最佳的 12 個。


1. 加入 rollout 常數

MAX_ACTIONS 附近加入:

js
const ROLLOUT_WIDTH = 12;

2. 替換 appendGeneratedAction()

把目前的:

js
function appendGeneratedAction(actions, scores, count, action, score) {
  if (count >= MAX_ACTIONS) {
    throw new Error(`AI action buffer overflow: ${MAX_ACTIONS}`);
  }

  actions[count] = action;
  scores[count] = score;

  return count + 1;
}

替換為:

js
function appendGeneratedAction(
  actions,
  scores,
  count,
  action,
  score,
  limit
) {
  /*
   * 完整生成模式:
   * MCTS tree、Alpha-Beta 仍然先全部寫入,最後一次排序。
   */
  if (limit === MAX_ACTIONS) {
    if (count >= MAX_ACTIONS) {
      throw new Error(
        `AI action buffer overflow: ${MAX_ACTIONS}`
      );
    }

    actions[count] = action;
    scores[count] = score;

    return count + 1;
  }

  /*
   * bounded top-K 模式:
   * 陣列始終依 score 由大到小排列,最多只保留 limit 個。
   */
  if (limit <= 0) {
    return 0;
  }

  if (count < limit) {
    let insertAt = count;

    while (
      insertAt > 0 &&
      score > scores[insertAt - 1]
    ) {
      actions[insertAt] = actions[insertAt - 1];
      scores[insertAt] = scores[insertAt - 1];
      insertAt -= 1;
    }

    actions[insertAt] = action;
    scores[insertAt] = score;

    return count + 1;
  }

  /*
   * 已有 K 個候選,而且新候選不比目前第 K 名好。
   */
  if (score <= scores[limit - 1]) {
    return count;
  }

  /*
   * 插入新候選並淘汰原本第 K 名。
   */
  let insertAt = limit - 1;

  while (
    insertAt > 0 &&
    score > scores[insertAt - 1]
  ) {
    actions[insertAt] = actions[insertAt - 1];
    scores[insertAt] = scores[insertAt - 1];
    insertAt -= 1;
  }

  actions[insertAt] = action;
  scores[insertAt] = score;

  return count;
}

3. 加入統一的完成函式

放在 appendGeneratedAction() 後面:

js
function finishGeneratedActions(
  actions,
  scores,
  count,
  limit
) {
  /*
   * bounded top-K 在 append 時已經維持排序,
   * 只有完整模式才需要做完整 quicksort。
   */
  if (limit === MAX_ACTIONS) {
    sortActionsDescending(actions, scores, count);
  }

  return count;
}

4. 修改 generateFlightActions() 函式簽名

把:

js
function generateFlightActions(position, player, actions, scores, count) {

替換為:

js
function generateFlightActions(
  position,
  player,
  actions,
  scores,
  count,
  limit
) {

並把該函式內的:

js
count = appendGeneratedAction(
  actions,
  scores,
  count,
  encodeFlight(from, to),
  heuristic
);

替換為:

js
count = appendGeneratedAction(
  actions,
  scores,
  count,
  encodeFlight(from, to),
  heuristic,
  limit
);

5. 修改 generateCoreActions() 函式簽名

把:

js
function generateCoreActions(position, actions, scores) {

替換為:

js
function generateCoreActions(
  position,
  actions,
  scores,
  maxReturned = MAX_ACTIONS
) {
  const limit = Number.isFinite(maxReturned)
    ? Math.max(
        1,
        Math.min(MAX_ACTIONS, Math.floor(maxReturned))
      )
    : MAX_ACTIONS;

接著保留原本的:

js
normalizeCorePosition(position);

及其後內容。


6. 修改所有 append 呼叫

generateCoreActions()generateFlightActions() 中,所有:

js
appendGeneratedAction(
  actions,
  scores,
  count,
  action,
  score
)

最後都要加上:

js
limit

例如原本:

js
count = appendGeneratedAction(
  actions,
  scores,
  count,
  encodePlacement(requiredType, orientation, anchor),
  actionHeuristic(position, player, oldOwn, newOwn)
);

改為:

js
count = appendGeneratedAction(
  actions,
  scores,
  count,
  encodePlacement(requiredType, orientation, anchor),
  actionHeuristic(position, player, oldOwn, newOwn),
  limit
);

Skip 同樣改為:

js
count = appendGeneratedAction(
  actions,
  scores,
  count,
  encodeSkip(requiredType),
  -900,
  limit
);

所有直接 Vino、移動+Vino、Flight 都做相同修改。


7. 修改 generateFlightActions() 的呼叫

兩個位置都要改。

原本:

js
count = generateFlightActions(
  position,
  player,
  actions,
  scores,
  count
);

替換為:

js
count = generateFlightActions(
  position,
  player,
  actions,
  scores,
  count,
  limit
);

8. 修改四個排序返回點

generateCoreActions() 中有多個:

js
sortActionsDescending(actions, scores, count);
return count;

全部替換為:

js
return finishGeneratedActions(
  actions,
  scores,
  count,
  limit
);

包括:

  1. Flight phase 返回點
  2. Fino/Mino 返回點
  3. position.pendingMoved 返回點
  4. 函式最後的 Vino 返回點

9. 修改 rollout 呼叫

runSimulation() 的 rollout 中,把:

js
const actionCount = generateCoreActions(
  this.workCore,
  this.actions,
  this.scores
);

if (actionCount <= 0) {
  break;
}

const heavyWidth = Math.min(12, actionCount);

const selectedIndex = Math.floor(
  Math.pow(Math.random(), 2.25) * heavyWidth
);

const action = this.actions[selectedIndex];

替換為:

js
const actionCount = generateCoreActions(
  this.workCore,
  this.actions,
  this.scores,
  ROLLOUT_WIDTH
);

if (actionCount <= 0) {
  break;
}

const selectedIndex = Math.floor(
  Math.pow(Math.random(), 2.25) * actionCount
);

const action = this.actions[selectedIndex];

Tree selection、節點快取及 Alpha-Beta 不傳第四個參數,所以仍然使用完整模式。

這項修改會得到

  • Rollout 不再完整排序數百至數千個 action
  • Rollout action buffer 最多只寫入 12 個結果
  • 仍然得到真正的 heuristic 前 12 名
  • 不需要改變 rollout 的隨機抽樣邏輯

它仍然會檢查所有可能候選;但是套用前面的增量 heuristic 和快速合法性判定後,每個候選已經便宜很多。如果之後 profiler 顯示 rollout 生成仍是第一名,才建議再做「只隨機抽樣 24~48 個合法候選」的近似 rollout。


四、第 5 點:BigInt 只部分同意

BigInt 確實有以下成本:

  • immutable,運算結果通常是新值
  • 不能直接使用 JS 的 32-bit bitwise 最佳化路徑
  • &|^、shift 需要 BigInt 路徑

但目前只有 100 bit,大致是兩個 64-bit limb。改成四個 Uint32 後,每一個操作都要變成四次 JS 陣列存取和四次運算,不保證一定更快。

全面改寫還會同時影響:

  • CorePosition
  • CELL_BITS
  • PLACEMENT_MASKS
  • neighborMask
  • squareScore
  • quickSquareScore
  • sameCorePosition
  • corePositionHash
  • generateCoreActions
  • applyCoreAction
  • Alpha-Beta save/restore
  • 對外的 getBitboards()

所以我不建議現在直接做完整 Uint32Array 遷移。

可以先做兩個低風險修改。


修改 5-A:預先建立清除單一格子的 mask

目前熱路徑反覆執行:

js
FULL_BOARD_MASK ^ CELL_BITS[from]

在:

js
const CELL_BITS = Array.from(
  { length: 100 },
  (_, index) => 1n << BigInt(index)
);

後面加入:

js
const CELL_CLEAR_MASKS = CELL_BITS.map(
  bit => FULL_BOARD_MASK ^ bit
);

然後全域搜尋:

js
FULL_BOARD_MASK ^ CELL_BITS[from]

替換為:

js
CELL_CLEAR_MASKS[from]

例如:

js
const newOwn =
  (oldOwn & CELL_CLEAR_MASKS[from]) | toBit;

以及:

js
const movedMinoBits =
  (oldMinoBits & CELL_CLEAR_MASKS[from]) |
  CELL_BITS[to];

這可以消除熱路徑中反覆產生相同 BigInt mask 的運算。

在前面第 2-B 點的程式中,也可把:

js
const clearFromMask = FULL_BOARD_MASK ^ fromBit;

替換為:

js
const clearFromMask = CELL_CLEAR_MASKS[from];

修改 5-B:用固定 16-bit lookup 替換逐 bit popcount

目前:

js
function popcountBigInt(bits) {
  let count = 0;
  let value = bits;

  while (value) {
    value &= value - 1n;
    count += 1;
  }

  return count;
}

它的迴圈次數取決於棋子格數。可以固定切成七個 16-bit chunk。

popcountBigInt() 前加入

js
const POPCOUNT_16 = new Uint8Array(1 << 16);

for (let value = 1; value < POPCOUNT_16.length; value += 1) {
  POPCOUNT_16[value] =
    POPCOUNT_16[value >>> 1] + (value & 1);
}

完整替換 popcountBigInt()

js
function popcountBigInt(bits) {
  const chunkMask = 0xffffn;

  return (
    POPCOUNT_16[Number(bits & chunkMask)] +
    POPCOUNT_16[Number((bits >> 16n) & chunkMask)] +
    POPCOUNT_16[Number((bits >> 32n) & chunkMask)] +
    POPCOUNT_16[Number((bits >> 48n) & chunkMask)] +
    POPCOUNT_16[Number((bits >> 64n) & chunkMask)] +
    POPCOUNT_16[Number((bits >> 80n) & chunkMask)] +
    POPCOUNT_16[Number((bits >> 96n) & chunkMask)]
  );
}

套用增量 actionHeuristic() 後,popcount 已不再出現在每個候選的熱路徑中,主要只剩:

js
normalizedPositionValue()

每次 simulation 結束時計算兩次,因此全面替換 BigInt 的必要性會大幅下降。


建議的實施順序

第一批:不改變合法走法及 heuristic 結果

先做:

  1. 增量 actionHeuristic()
  2. Fino/Mino/Vino 快速合法性判定
  3. 移動+Vino 不再暫時修改 position
  4. CELL_CLEAR_MASKS
  5. lookup popcount

這一批基本上都是等價最佳化,風險最低。

第二批:Rollout 最佳化

加入:

  1. bounded top-12
  2. rollout 傳入 ROLLOUT_WIDTH

候選分數相同時,前 12 名中的同分 action 順序可能和原 quicksort 不完全相同,但 rollout 本來就是隨機抽樣,因此不構成實質問題。

第三批:搜尋策略最佳化

最後加入 progressive widening。

它不會刪除合法走法,但會改變 MCTS 展開順序,因此應單獨測試棋力。


最終判斷

最值得立即修改的是:

  1. 第 3 點:增量 heuristic
  2. 第 4 點:rollout bounded top-K
  3. 第 2 點附帶的重複 occupied/position 計算
  4. Progressive widening

第 5 點的 BigInt 確實有成本,但在完成上述修改後,它很可能已不再是最大瓶頸。現階段不建議直接把整個引擎改寫成四段 Uint32Array;先做 CELL_CLEAR_MASKS 和固定 chunk popcount 即可。