代码: 全选
Now let's fix the final move-selection at the root, since "most visits" can pick a worse move over a child we've now *proven* exact:它應該回填一個**用 negamax 方式精算出來的精確值**,而不是放任被標記那一刻、由隨機取樣平均出來的舊值凍結在那裡。修好後過程中還連帶挖出兩個更嚴重的衍生 bug,一併修了,說明如下。
## 精確值該怎麼算
程式碼裡 `node.wins / node.visits` 的既有慣例是:**「走到這一步的那位棋手」視角下的價值**(不是 `node.player`——`node.player` 是接下來要走的人,也就是這個值的對手)。
所以,當 `node` 的所有子節點都已經 `isFullyExplored`(等於窮舉了 `node.player` 所有能走的棋):
- `node.player` 會挑對自己最有利的子節點,而子節點的 `wins/visits` 恰好就是從 `node.player` 視角存的值 → 直接取 `max`
- 換算回 `node` 自己(走到 `node` 這一步的對手視角)→ 取負號
```js
function backupExactValue(node) {
if (node.children.length === 0 || node.visits === 0) return;
let best = -Infinity;
for (let c of node.children) {
let v = c.wins / c.visits;
if (v > best) best = v;
}
node.wins = -best * node.visits; // 保留 visits 供顯示用,只修正 wins 讓比值等於精確解
}
```
這就是標準的 negamax 回溯公式:`value(node) = -max(value(children))`。我把它接到兩處原本只單純 `isFullyExplored = true` 的地方(Selection 迴圈"找不到 bestChild"時、以及 Backprop"所有子節點都窮舉完"時),兩份程式碼(正式對局 `triggerAITurn` 與偵錯用「AI搜尋」面板)各有兩處,共四處都補上了 `backupExactValue(...)`。
## 修這個順便抓到的兩個連帶 bug
**1. 終端節點(沒有合法著法)其實從沒被抽樣過,`wins/visits` 永遠是 `0/0`**
`MCTSNode` 建構子裡 `this.isFullyExplored = this.unexpanded.length === 0;` 對於"遊戲/本回合已結束"的終端節點,一出生就是 `true`。但 Selection 迴圈是 `if (c.isFullyExplored) continue;`——這代表終端節點**從出生那一刻就永遠不會被選中、永遠不會真的跑一次 Simulation**,`wins`/`visits` 會一直停在 `0/0`。而它的父節點在判斷"是否所有子節點都窮舉完"時,只看 `isFullyExplored` 這個布林值,完全沒管它有沒有真的被評估過——於是父節點會拿一堆從沒被賦值的 `0/0` 去做我這個 `max()` 精算,直接壞掉(`NaN`)。
修法:終端節點在建構子裡就直接用 `calculateScores()` 算出確定的比分差,立刻給一個精確值(`visits=1`),不必也不該靠隨機模擬:
```js
if (this.isFullyExplored) {
let scores = state.calculateScores();
let scaledAdvantage = (scores.p1Score - scores.p2Score) / 20.0;
this.wins = player === 1 ? -scaledAdvantage : scaledAdvantage; // 跟原本 backprop 用同一套慣例
this.visits = 1;
}
```
**2. 最終選子時用「訪問次數最多」,反而會讓已證明是精確解的好棋輸給普通估計值**
`triggerAITurn` 最後選要下哪一步,原本是單純比 `visits`:
```js
for (let c of root.children) {
if (c.visits > mostVisits) { mostVisits = c.visits; bestChild = c; }
}
```
問題是:一個子節點一旦 `isFullyExplored`,就會被永久跳過、不再累積 `visits`;而其他還沒解完、持續被抽樣的子節點 `visits` 只會越滾越多。結果就是:即使某個子節點已經被**證明**是最佳解,也可能因為它比較早窮舉完、`visits` 數偏低,在"比訪問次數"時反而輸給一個只是被抽比較多次、其實沒那麼好的未解子節點。
修法:精確解一律直接用「值」比較(反正它是精確的,不怕比較),未解的仍用"訪問次數最多"當代表估計值,兩邊都有時再互相比值取較高者:
```js
let solvedBest = null;
let unsolvedBest = null, mostVisits = -1;
for (let c of root.children) {
if (c.isFullyExplored) {
if (!solvedBest || c.wins / c.visits > solvedBest.wins / solvedBest.visits) solvedBest = c;
} else if (c.visits > mostVisits) {
mostVisits = c.visits;
unsolvedBest = c;
}
}
let bestChild = solvedBest && unsolvedBest
? (solvedBest.wins / solvedBest.visits >= unsolvedBest.wins / unsolvedBest.visits ? solvedBest : unsolvedBest)
: (solvedBest || unsolvedBest);
```
這三處修改是連動的:沒有第 1 點(終端節點賦值),`backupExactValue` 的 `max()` 一遇到沒被抽樣過的終端子節點就會吃到 `NaN`;沒有第 2 點,就算上面的精確值都算對了,最後選棋步時還是可能因為"比訪問次數"而白白浪費掉這個精確解。
已更新到檔案裡,語法也跑過 `node --check` 確認沒問題。有個小地方想跟您確認:偵錯用的「AI搜尋」面板裡,樹狀圖顯示時的排序仍然是 `sort((a,b)=>b.visits - a.visits)`(只影響顯示順序,不影響上面選棋的邏輯),要不要也讓已解出的節點優先排到前面顯示?