從迷信MCTS到質疑MCTS

[ejsoon]

對於抽象策略遊戲，沒有運氣成分的零和遊戲而言，是否不是所有遊戲都適合使用MCTS？

對於無運氣成分的零和抽象策略遊戲（Abstract Strategy Games），**確實不是所有遊戲都適合直接使用蒙特卡洛樹搜尋（MCTS, Monte Carlo Tree Search）**。

雖然 MCTS 在圍棋（Go）等遊戲中取得了巨大成功，但在處理某些特定類型的抽象策略遊戲時，它會遇到顯著的瓶頸：

### 1. 陷阱極多或「一失足成千古恨」的遊戲（Tactical / Trap-heavy Games）

* **問題點**：傳統 MCTS 依賴隨機模擬（Rollout/Playout）來評估局勢。如果遊戲中存在大量「只要走錯一步就瞬間必敗」的戰術陷阱（例如西洋棋中的殺局、五子棋的連續衝四勝），隨機模擬極難隨機走出一套精確的連續防守或攻擊動作。
* **結果**：MCTS 可能會誤以為某個看似優勢的棋局很安全，從而忽視隱藏的致命戰術陷阱。在這種情況下，傳統的 Alpha-Beta 剪枝搜尋（Alpha-Beta Pruning）結合良好的評估函數通常比純 MCTS 更高效且精準。

### 2. 狀態空間與搜尋深度極淺的遊戲

* **問題點**：對於分支度低、棋盤較小、能在短時間內完全遍歷或搜尋到極深層數的遊戲（例如井字棋 Tic-Tac-Toe、Connect Four、或小棋盤的翻轉棋）。
* **結果**：傳統的 MiniMax / Alpha-Beta 搜尋能夠直接找到確定性的必勝/必和解（Solved Games），完全不需要 MCTS 的統計估計。

### 3. 缺乏漸進式回饋（Gradual Feedback）的遊戲

* **問題點**：MCTS 的核心機制是透過勝負結果向後傳播（Backpropagation）來調整節點的價值估計。如果遊戲的局面無法給出漸進式的勝率回饋（即勝負完全取決於最後一步的某個隱蔽機制），MCTS 在搜尋前期會呈現近乎盲目的隨機探索。

---

### MCTS 何時才真正強大？

MCTS 最適合滿足以下特徵的抽象策略遊戲：

1. **分支度極高**：每一步的可選動作極多（如圍棋），導致 Minimax / Alpha-Beta 的剪枝效率大幅下降。
2. **難以撰寫人工評估函數**：局勢的好壞難以用傳統公式（如「計算子力價值」）來量化。
3. **戰術與戰略並重**：長期的陣勢佈局比短期的一兩步殺局更影響最終勝負。

### 現代解決方案：MCTS + 深度神經網路（AlphaZero 模式）

為了解決純 MCTS 在戰術敏感度上的缺陷，現代人工智慧（如 AlphaZero）結合了**神經網路**：

* 用策略網路（Policy Network）引導搜尋方向，避免隨機模擬走入無效分支。
* 用價值網路（Value Network）直接評估局勢，取代隨機模擬（Rollout）。

這種結合讓 MCTS 能夠應用於西洋棋等傳統上不適合純 MCTS 的遊戲中，但若不結合神經網路，傳統 MCTS 在許多精密戰術型的抽象策略遊戲中表現確實不如傳統搜尋演算法。

那麼對於抽象策略遊戲，沒有運氣成分的零和遊戲而言，tensorFlow或PyTorch是否一定要跟MCTS配合使用？

**不一定**。TensorFlow 與 PyTorch 作為深度學習框架，主要用途是**訓練與推論神經網路**（如卷積神經網路 CNN、殘差網路 ResNet、 Transformer 等）。在抽象策略零和遊戲中，神經網路可以單獨使用，也可以與許多其他搜尋演算法配合， MCTS 只是其中一種組合方式。

神經網路與演算法配合常見的幾種模式：

### 1. 純神經網路（Direct Evaluation / Model-Free RL）

神經網路可以直接輸入當前盤面，輸出當前最佳走法（Policy）或局勢勝率估計（Value）。

* **無搜尋策略**：在實際對弈時，直接選擇神經網路輸出機率最高的走法。這種方式反應極快，但缺乏前瞻思考能力，容易在關鍵時刻犯下戰術錯誤。
* **應用範例**：早期的簡單 Reinforcement Learning 模型，或對即時性要求極高（沒有時間進行樹搜尋）的場景。

### 2. 神經網路 + Alpha-Beta 剪枝搜尋（Alpha-Beta / Minimax）

在傳統西洋棋或幾何棋類軟體中，Alpha-Beta 搜尋是非常強大的演算法。

* **取代傳統靜態評估函數**：傳統 Alpha-Beta 搜尋依賴人類寫死的評估函數（例如：棋子分數加權）。你可以使用 TensorFlow/PyTorch 訓練一個高精度的深度評估神經網路（NNUE 或深度價值網路），用來取代傳統評估函數。
* **典型代表**：現代許多強大的西洋棋引擎（如 Stockfish 的 NNUE 架構）就是將深度學習（或神經網路評估）與 Alpha-Beta 搜尋相結合，而非使用 MCTS。

### 3. 神經網路 + 其他搜尋演算法

除了 MCTS 和 Alpha-Beta，神經網路還可以配合：

* **A* 搜尋 / IDA* 搜尋：用於求解特定狀態空間圖（如解謎類或狀態轉移清晰的遊戲）。
* **Beam Search（束搜尋）**：在每一層搜尋中僅保留前 $N$ 個最優狀態，適合分支度極高但搜尋深度有限的場景。

---

### 什麼時候「必須」或「非常建議」搭配 MCTS？

雖然不是唯一選擇，但將 **TensorFlow/PyTorch（神經網路）與 MCTS 結合（即 AlphaZero / Leela Chess Zero 模式）**，在以下情境會發揮最大威力：

1. **分支度極高且缺乏人類先驗知識**：對於圍棋這類無法撰寫精準手工評估函數的遊戲，神經網路提供「局勢直覺」，MCTS 提供「前瞻算力」，兩者結合能產生遠超單獨演算法的棋力。
2. **自我對弈訓練（Self-Play Learning）**：MCTS 在搜尋過程中產生的改進策略（Search Policy）可以作為 TensorFlow/PyTorch 訓練時的高品質標籤（Target），讓神經網路透過自我對弈持續成長。

### 總結

TensorFlow 與 PyTorch 是**工具（負責「直覺」與「評估」）**，MCTS 是**演算法（負責「前瞻與推理」）**。你完全可以只用神經網路，或者將神經網路結合 Alpha-Beta 剪枝等其他傳統搜尋演算法。選擇哪種組合，完全取決於該抽象策略遊戲的分支度、戰術敏感度以及計算資源。

[ejsoon]

重寫AI思考部分

代码： 全选

重寫AI思考部分
首先定義一些術語：

孤獨棋：當一個棋子被其它棋子的實邊或棋盤邊緣圍困在一個小正方形時，它將成為孤獨棋。

氣：當一個棋子開口處朝向一個空棋位，則這個空棋位就是它的氣。

氣口：當一個棋子開口處朝向一個空棋位，則這個空棋位對準這個棋子的方向就是它的氣口。

共氣：當一方的棋子跟另一方的棋子的開口處都朝向同一個空棋位，則這兩個棋子為共氣。

戰爭：當一方的棋子與另一方的棋子開口處相連，成為一個棋群，而且這個棋群並沒有封閉，則為戰爭。

下面是AI思考重做的步驟

一，當場上沒有戰爭，也沒有棋子共氣時

隨機選擇以下選項落子：

把本方的一個「圍三」接到一個本方的「雙二」或「角二」的氣口，或連接到對方的有三口氣的「單一」的氣口，或連接到一個「叉零」。（80%機率）

把本方的「雙二」或「角二」落在一個能有兩氣，不會有棋子與之共氣，且有一個實邊貼在對方一個「雙二」或「角二」的開口處；

把本方的「雙二」或「角二」落在一個能有兩氣，不會有棋子與之共氣，也沒有一個實邊貼在對方一個棋子的開口處；

用本方的「雙二」或「角二」連接本方場上已有的「雙二」或「角二」的氣口。

二，當場上沒有戰爭，但有棋子共氣時

如果用一個「角二」或「雙二」連通雙方共氣棋子爆發戰爭後，我方三角形數量大於對方，則可連接；

如果能用一個「圍三」放到共氣位置，連接本方棋子氣口，則更為優先。（80%）

如果用一個「角二」或「雙二」連通雙方共氣棋子爆發戰爭後，對方三角形數量大於或等於本方，則改為不連通，只用一個「角二」或「雙二」接到本方棋子氣口，並用實邊封住對方氣口，防止戰爭。


三，當場上存在戰爭

如果戰爭中我方棋子三角形數量大於或等於對方，而且我方能夠在戰爭的兩個或多個氣口處放上一個圍三，則優先考慮（80%），也可以把一個「雙二」或「角二」接到氣口處擴大戰爭（20%）。

如果戰爭中我方棋子三角形數量小於對方，而且我方能夠在戰爭的氣口處接上一個圍三，則直接考慮。如果不能，則如果在把一個「雙二」或「角二」或「單一」接到氣口能封閉這個方向的氣口，則優先考慮。如果還不能，則如果用一個「雙二」或「角二」或「單一」的實邊封堵一個氣口後這個棋子存在兩氣且不與其它棋子共氣，則優先考慮。如果還不行，則用「叉零」來封閉戰爭的其中一個氣口。

四，當過了12回合之後，開始MCTS搜尋

如果存在以上的棋型，其仍將向MCTS提供優先候選。

MCTS應用絕對分差，而不要歸一化，因為一分之差定輸贏。

MCTS只需要隨機落子，搜尋到最後面提子完畢，但在落子階段結束時的分數作主要的評分，而提子階段的分數只能是落子階段的選項中分數都相等時才用來選擇。

當到達落子階段的倒數2回合，則開始採用alpha-beta算法，限時36秒，超過限時仍回退到MCTS搜尋。這個2回合和36秒可在AI設置窗口中設定，所有AI強度都用同一個設定。

不同的AI強度，應只有「MCTS搜尋時間」的差異，簡單3秒，困難6秒，專家12秒，自訂24秒。

回答要求：給出修改代碼的python腳本。