Re: 改下哥尼斯堡網頁程式
发表于 ： 2026年 4月 10日 23:59
去掉MAX_PATH_LENGTH，改為：首先算出當前一次移動最多能走幾個點，設為max_path_length，之後在1到max_path_length之間隨機選一個數字，作為當前運算的深度。只需告知所要更改的地方。
代码： 全选
根據您的要求，我將修改蒙地卡洛搜尋的邏輯。主要更動為：移除固定的 `MAX_PATH_LENGTH`，新增一個計算最長路徑的函式，並在每次模擬時隨機決定步數長度。
以下是需要更動的四個地方：
### 1. 修改 `PARAMS` 參數
移除 `MAX_PATH_LENGTH`，保留其他模擬參數。
```javascript
const PARAMS = {
SIMULATIONS_PER_MOVE: 50,
MAX_DEPTH: 8
};
```
### 2. 新增 `getMaxPathLength` 函式
在 `runMCTS` 函式外部新增此工具函式，用來動態計算當前位置出發，不重複經過節點的最長路徑長度（點的數量）。
```javascript
function getMaxPathLength(state) {
let start = state.turn === 0 ? state.p0 : state.p1;
let maxL = 1;
function dfs(curr, visitedSet) {
maxL = Math.max(maxL, visitedSet.size);
// 取得所有可通行的鄰居 (空地或已有橋樑)
let neighbors = (state.empty_map[curr] || []).concat(state.arrow_map[curr] || []);
for (let nxt of neighbors) {
if (!visitedSet.has(nxt)) {
visitedSet.add(nxt);
dfs(nxt, visitedSet);
visitedSet.delete(nxt);
}
}
}
dfs(start, new Set([start]));
return maxL;
}
```
### 3. 修改 `runMCTS` 的第一步搜尋邏輯
將原本固定的搜尋深度改為隨機選取的深度。
```javascript
// 在 runMCTS 內部：
let maxPossibleLen = getMaxPathLength(rootState);
// 在 2 (最少移動一格) 到最長長度之間隨機選一個數字作為當前深度
let randomTargetLen = Math.floor(Math.random() * (maxPossibleLen - 1)) + 2;
// 取得所有長度剛好等於 randomTargetLen 的合法路徑
let rootMoves = getLegalMoves(rootState, randomTargetLen).filter(m => m.length === randomTargetLen);
```
### 4. 修改 `playout` 隨機模擬函式
將隨機推演的過程也改為動態長度。
```javascript
function playout(state, maxDepth) {
let currState = state;
for (let d = 0; d < maxDepth; d++) {
let maxL = getMaxPathLength(currState);
if (maxL < 2) return 1 - currState.turn; // 無路可走，判負
// 隨機決定這次移動要走幾個點 (2 ~ maxL)
let k = Math.floor(Math.random() * (maxL - 1)) + 2;
let moves = getLegalMoves(currState, k).filter(m => m.length === k);
if (moves.length === 0) return 1 - currState.turn;
let randMove = moves[Math.floor(Math.random() * moves.length)];
let result = applyMove(currState, randMove);
if (result.terminal) return result.winner;
currState = result.state;
}
return -1;
}
```
### 調整建議與注意事項
1. **隨機性的影響**：由於現在每一步的「深度（路徑長度）」是隨機選取的，這會增加搜尋的廣度，但可能會降低對「極端長路徑」的覆蓋率。如果您發現推薦的路徑都太短，可以將隨機權重往高處調整。
2. **效能警告**：`getMaxPathLength` 使用了 DFS 窮舉。在節點非常多且全連通的複雜盤面上，計算最長路徑可能會稍微增加運算負擔。如果點擊後出現卡頓，建議將 `SIMULATIONS_PER_MOVE` 調低至 `30`。
3. **合法性**：遊戲規則通常要求必須建立新橋或移動。在隨機選取長度為 `1` 時（即不移動），邏輯上是不合法的，因此程式碼中我將隨機範圍限定在 `2` 到 `max_path_length` 之間。