共享会话
下面是claude總結的「為何MCTS搜尋會很慢」的理由,其中第一點我已經請它更改。其餘的四點你是否同意?如果同意請給…
分享于 2026年9月2日 04:14下面是claude總結的「為何MCTS搜尋會很慢」的理由,其中第一點我已經請它更改。其餘的四點你是否同意?如果同意請給出修改方案。(明確給出所要修改的地方和所要替換的代碼)
我把 MCTSEngine(第 8531 行起)以及它呼叫的核心函式看了一遍,抓出搜尋每一步實際在做什麼,以及慢在哪裡。
搜尋的四個階段(runSimulation(),8702 行)
- Selection(選擇):從 root 沿著已展開的樹往下走,每層呼叫
selectChild()用 UCT+RAVE 選子節點。 - Expansion(展開):走到還沒展開完的節點時,展開一個新子節點。
- Rollout(模擬到終局):用啟發式挑選最多 80 步(
MAX_SEARCH_PLY),跑到終局或步數上限。 - Backpropagation(回傳):把結果沿路徑寫回
visits/value/ RAVE。
問題不在這個框架本身,而在於第 1、3 步裡反覆呼叫的 generateCoreActions()(8215 行)太重,而且完全沒有快取。
主要慢的原因
1. Selection 階段每次都重算合法走法,沒有快取(影響最大)
runSimulation() 的 selection 迴圈(8711 行)裡:
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 格 ×2popcountBigInt():逐位元清除迴圈 ×2
單次 actionHeuristic 大約要跑 800 次以上的位元運算。乘上第 2 點的候選數量,單次 generateCoreActions 在維諾階段可能就要跑上百萬次位元運算。
4. 這個重量級函式在 Rollout 階段也是每一步都全套重跑
Rollout 迴圈(8782 行)為了「只從前 12 個候選裡隨機抽一個」,卻還是呼叫同一個 generateCoreActions() 產生全部候選+排序,然後才丟棄大部分。而 rollout 最長可以跑 80 步 —— 相當於每次模擬光 rollout 就可能觸發幾十次上面第 2、3 點的昂貴計算。排序(sortActionsDescending)也是對全部候選排序,即使只需要前 12 名。
5. 棋盤用 100 位元的 BigInt 表示,所有位元運算都是多字組大數運算
black_A/B/C、white_A/B/C 都是 BigInt,且超過 64 位元,JS 引擎要用多 limb 的大數運算來處理每一次 &、|、^、比較。這類運算比原生 Number/Uint32Array 上的位元運算慢非常多(通常一個數量級以上),而且會有額外的記憶體配置與 GC 壓力。因為上面第 2–4 點本來就已經是熱迴圈裡數百萬次的位元運算,用 BigInt 等於是在一個已經很密集的迴圈上再乘上一個很大的常數係數。
小結(依影響力排序)
- Selection 階段對已展開節點重複呼叫
generateCoreActions,完全沒快取 → 浪費最嚴重。 - 「移動米諾+放維諾」與飛子的候選走法組合數本身很大(可到上萬種)。
- 每個候選都要跑一次不便宜的啟發函式(quickSquareScore/centerScore/popcount)。
- Rollout 每一步都重跑全套產生+排序,即使只用得到隨機抽出的一個。
- 底層用 100 位元 BigInt 表示棋盤,讓以上所有熱迴圈裡的位元運算都變慢。
這五點疊加起來,就是「每次模擬」的成本被放大很多倍,導致同樣的搜尋時間預算下,實際能跑的模擬次數非常少,感覺上 MCTS 就特別慢。如果你要,我可以針對第 1 點(節點快取合法走法)先做一版修改,這通常是投報比最高的優化。
QuanAI我看過附件中的目前版本;第 1 點的節點走法快取確實已經加入 MCTSEngine.actionCache 與 getNodeActions()。
結論
| 項目 | 判斷 | 說明 |
|---|---|---|
| 2. 分支數很大 | 同意,但原估算有誇大 | 真正嚴重的是「移米諾 × 放維諾」的笛卡兒積;飛子並沒有實際跑滿 100×100 |
3. actionHeuristic() 很重 | 完全同意 | 而且可以改成數學上等價的增量計算,不必犧牲棋力 |
| 4. Rollout 產生、排序所有行動 | 完全同意 | 應改成只保留前 12 名的 bounded top-K,避免完整排序及寫入所有候選 |
5. 100-bit BigInt 慢 | 部分同意 | BigInt 確實有額外成本,但「通常慢一個數量級」不能直接套用;100-bit 其實只有約兩個 limb,不建議現在全面重寫成 Uint32Array |
我建議依序套用:
- 增量化
actionHeuristic - 移除候選生成中的重複局面計算
- Rollout bounded top-K
- Progressive widening
- 最後才考慮 BigInt 的低風險優化
一、第 2 點:分支數確實大,但數字需要修正
目前 Vino 是 L 形三格棋子。雖然程式掃描:
4 * 100但每個方向真正不越界的錨點只有 9×9=81,因此幾何有效的 Vino 放置最多是:
4×81=324假設每人最多有 3 個 Mino,「移動後放 Vino」最多約:
3×4×324=3888這仍然很大,所以結論成立。
但是 Claude 對飛子的描述不準確。generateFlightActions() 中:
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() 每呼叫一次都會重新執行:
const occupied = getOccupiedBits(position);Fino/Mino 還會再次執行:
const ownNeighbors = neighborMask(getOwnerBits(position, player));這些資料在同一個 generateCoreActions() 中是不變的,應該移到迴圈外。
1. 修改 Fino/Mino 的候選生成
在 generateCoreActions() 找到:
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;
}替換為:
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 的合法性判定
在:
if (position.pendingMoved) {區塊中,把:
if (!isLegalPlacementMask(position, player, CORE_VINO, mask)) {
continue;
}替換為:
if (!mask || (mask & occupied) !== 0n) {
continue;
}因為 Vino 沒有「不能接觸自己棋子」的限制,只需要檢查越界及重疊。
3. 修改直接放置 Vino 的合法性判定
在:
// 直接放置 Vino。區塊中,同樣把:
if (!isLegalPlacementMask(position, player, CORE_VINO, mask)) {
continue;
}替換為:
if (!mask || (mask & occupied) !== 0n) {
continue;
}修改 2-B:不要為每個「移動+Vino」候選修改 position
目前的複合候選會反覆:
setTypeBits(position, player, CORE_MINO, movedMinoBits);
const movedOwn = getOwnerBits(position, player);
...
setTypeBits(position, player, CORE_MINO, oldMinoBits);而且內層每個 Vino 候選又呼叫 isLegalPlacementMask(),重新組合六個 bitboard。
找到整段:
// 移動一個 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);
}
}整段替換為:
// 移動一個 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
目前節點只要還有未展開走法,就永遠優先展開:
if (expanded < actionCount) {若 root 有 4,000 個候選,前 4,000 次 simulation 幾乎都只是在建立新 child,UCT 很久都沒有真正利用已搜尋的分支。
在常數區加入
放在:
const TREE_DECAY_FACTOR = 0.5;後面:
const PROGRESSIVE_WIDENING_BASE = 2;
const PROGRESSIVE_WIDENING_SCALE = 1.8;
const PROGRESSIVE_WIDENING_EXPONENT = 0.45;在 MCTSEngine 中加入方法
建議放在 dynamicExplorationConstant() 後面:
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() 中替換
找到:
const expanded = this.pool.expandedCount[node];
if (expanded < actionCount) {替換為:
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() 改為增量計算
這一點我完全同意。
目前:
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 初始化完成後,也就是:
for (let index = 0; index < 100; index += 1) {
...
}後面加入:
/*
* 每個棋盤格隸屬於哪些 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()
把原本的:
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);
}替換為:
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 名:
const heavyWidth = Math.min(12, actionCount);但 generateCoreActions() 仍然:
- 將所有候選寫入陣列
- 對所有候選完整排序
- 最後只取 12 個
應讓 rollout 模式在生成過程中只保留目前最佳的 12 個。
1. 加入 rollout 常數
在 MAX_ACTIONS 附近加入:
const ROLLOUT_WIDTH = 12;2. 替換 appendGeneratedAction()
把目前的:
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;
}替換為:
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() 後面:
function finishGeneratedActions(
actions,
scores,
count,
limit
) {
/*
* bounded top-K 在 append 時已經維持排序,
* 只有完整模式才需要做完整 quicksort。
*/
if (limit === MAX_ACTIONS) {
sortActionsDescending(actions, scores, count);
}
return count;
}4. 修改 generateFlightActions() 函式簽名
把:
function generateFlightActions(position, player, actions, scores, count) {替換為:
function generateFlightActions(
position,
player,
actions,
scores,
count,
limit
) {並把該函式內的:
count = appendGeneratedAction(
actions,
scores,
count,
encodeFlight(from, to),
heuristic
);替換為:
count = appendGeneratedAction(
actions,
scores,
count,
encodeFlight(from, to),
heuristic,
limit
);5. 修改 generateCoreActions() 函式簽名
把:
function generateCoreActions(position, actions, scores) {替換為:
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;接著保留原本的:
normalizeCorePosition(position);及其後內容。
6. 修改所有 append 呼叫
在 generateCoreActions() 及 generateFlightActions() 中,所有:
appendGeneratedAction(
actions,
scores,
count,
action,
score
)最後都要加上:
limit例如原本:
count = appendGeneratedAction(
actions,
scores,
count,
encodePlacement(requiredType, orientation, anchor),
actionHeuristic(position, player, oldOwn, newOwn)
);改為:
count = appendGeneratedAction(
actions,
scores,
count,
encodePlacement(requiredType, orientation, anchor),
actionHeuristic(position, player, oldOwn, newOwn),
limit
);Skip 同樣改為:
count = appendGeneratedAction(
actions,
scores,
count,
encodeSkip(requiredType),
-900,
limit
);所有直接 Vino、移動+Vino、Flight 都做相同修改。
7. 修改 generateFlightActions() 的呼叫
兩個位置都要改。
原本:
count = generateFlightActions(
position,
player,
actions,
scores,
count
);替換為:
count = generateFlightActions(
position,
player,
actions,
scores,
count,
limit
);8. 修改四個排序返回點
generateCoreActions() 中有多個:
sortActionsDescending(actions, scores, count);
return count;全部替換為:
return finishGeneratedActions(
actions,
scores,
count,
limit
);包括:
- Flight phase 返回點
- Fino/Mino 返回點
position.pendingMoved返回點- 函式最後的 Vino 返回點
9. 修改 rollout 呼叫
在 runSimulation() 的 rollout 中,把:
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];替換為:
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 陣列存取和四次運算,不保證一定更快。
全面改寫還會同時影響:
CorePositionCELL_BITSPLACEMENT_MASKSneighborMasksquareScorequickSquareScoresameCorePositioncorePositionHashgenerateCoreActionsapplyCoreAction- Alpha-Beta save/restore
- 對外的
getBitboards()
所以我不建議現在直接做完整 Uint32Array 遷移。
可以先做兩個低風險修改。
修改 5-A:預先建立清除單一格子的 mask
目前熱路徑反覆執行:
FULL_BOARD_MASK ^ CELL_BITS[from]在:
const CELL_BITS = Array.from(
{ length: 100 },
(_, index) => 1n << BigInt(index)
);後面加入:
const CELL_CLEAR_MASKS = CELL_BITS.map(
bit => FULL_BOARD_MASK ^ bit
);然後全域搜尋:
FULL_BOARD_MASK ^ CELL_BITS[from]替換為:
CELL_CLEAR_MASKS[from]例如:
const newOwn =
(oldOwn & CELL_CLEAR_MASKS[from]) | toBit;以及:
const movedMinoBits =
(oldMinoBits & CELL_CLEAR_MASKS[from]) |
CELL_BITS[to];這可以消除熱路徑中反覆產生相同 BigInt mask 的運算。
在前面第 2-B 點的程式中,也可把:
const clearFromMask = FULL_BOARD_MASK ^ fromBit;替換為:
const clearFromMask = CELL_CLEAR_MASKS[from];修改 5-B:用固定 16-bit lookup 替換逐 bit popcount
目前:
function popcountBigInt(bits) {
let count = 0;
let value = bits;
while (value) {
value &= value - 1n;
count += 1;
}
return count;
}它的迴圈次數取決於棋子格數。可以固定切成七個 16-bit chunk。
在 popcountBigInt() 前加入
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()
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 已不再出現在每個候選的熱路徑中,主要只剩:
normalizedPositionValue()每次 simulation 結束時計算兩次,因此全面替換 BigInt 的必要性會大幅下降。
建議的實施順序
第一批:不改變合法走法及 heuristic 結果
先做:
- 增量
actionHeuristic() - Fino/Mino/Vino 快速合法性判定
- 移動+Vino 不再暫時修改
position CELL_CLEAR_MASKS- lookup popcount
這一批基本上都是等價最佳化,風險最低。
第二批:Rollout 最佳化
加入:
- bounded top-12
- rollout 傳入
ROLLOUT_WIDTH
候選分數相同時,前 12 名中的同分 action 順序可能和原 quicksort 不完全相同,但 rollout 本來就是隨機抽樣,因此不構成實質問題。
第三批:搜尋策略最佳化
最後加入 progressive widening。
它不會刪除合法走法,但會改變 MCTS 展開順序,因此應單獨測試棋力。
最終判斷
最值得立即修改的是:
- 第 3 點:增量 heuristic
- 第 4 點:rollout bounded top-K
- 第 2 點附帶的重複 occupied/position 計算
- Progressive widening
第 5 點的 BigInt 確實有成本,但在完成上述修改後,它很可能已不再是最大瓶頸。現階段不建議直接把整個引擎改寫成四段 Uint32Array;先做 CELL_CLEAR_MASKS 和固定 chunk popcount 即可。