精選文章
圍棋 電腦解死活題研究
單純先記錄一下, 之後再來整理：
--
圍棋死活題果然很難, 寫個程式直接把兩週的Grok 算力用量燒光了 (馬斯克為了慶祝 Grok 4.6 有多送了一週用量 ) 而且還沒做對... 明天週二 reset 後繼續...
--- Grok AI 的回答
是的，針對圍棋**詰棋**（死活問題，Life-and-Death / tsumego）的解題搜尋，目前已有不少研究提出加速方法，從傳統搜尋演算法優化，到結合神經網路的現代技術，都有顯著進展。
### 1. 經典搜尋導向方法
早期代表性工作是 **Tsumego Explorer**（Kishimoto & Müller, 2005, AAAI）。
- 核心是增強版的 **depth-first proof-number search (df-pn)**。
- 特別處理圍棋特有的**劫爭（ko）**與位置重複（GHI problem）。
- 強調「高效搜尋」而非大量領域知識，在封閉死活題上大幅超越當時最強的 GoTools（總體快約 2.8～20 倍以上，尤其在較難題目上優勢明顯）。
其他傳統加速技巧還包括：
- 置換表（transposition tables）、killer heuristic、null-move pruning
- 靜態眼形判斷、強制著手辨識、領域知識剪枝
### 2. 近期最重要的加速方向：Relevance-Zone Based Search (RZS)
這是目前最活躍、效果最突出的研究方向，主要由台灣陽明交通大學吳毅成（I-Chen Wu）團隊主導（2021–2025）。
**核心概念**：
- **Relevance Zone（相關區域）**：自動找出只影響死活結果的關鍵區域。區域外的著手可安全視為「null move」，大幅剪枝搜尋空間。
- 與傳統 lambda search 不同，RZS 先搜尋有希望的著手，再**事後**判定是否為 null move，更優雅且容易整合到現代 MCTS / AlphaZero 框架。
**重要配套技術**：
- **Faster to Life (FTL)**：修改 AlphaZero 訓練目標，讓神經網路偏好「更快勝利」（較短證明路徑），顯著縮小解樹深度。
- **Relevance-Zone Pattern Table（RZT / 相關區域模式表）**：用 radix tree 儲存並重用已發現的局部模式，取代傳統置換表，進一步加速。
**實驗效果**（在專業死活題集上）：
- 從 Cho Chikun《死活辭典》選取的 106 題 19×19 死活題：RZS + FTL 可解 68 題，僅用 RZS 解 36 題，而舊的 Tsumego Explorer 只解 11 題。
- 使用模式表後，在相同硬體上平均加速約 **4.74 倍**，部分複雜題目可達 **近 30 倍**（節點數從數十萬降到一萬多）。
2025 年底還有後續分析論文，深入探討 RZS 在實際詰棋上的行為（包括發現罕見模式、甚至找出與書中不同的合法解）。
### 3. 其他現代方法
- **改良 MCTS**：專門針對詰棋調整的蒙特卡洛樹搜尋（例如 Smargo 等開源專案），調整 playout、回報函數與結構，使其更適合「確定死活」而非全局勝負。
- **Expected Work Search (EWS, 2024)**：結合 MCTS 的勝率估計與 Proof-Number Search 的證明大小估計，用「預期計算量」導向搜尋。已成功解決空 5×5 盤（positional superko 規則下）等問題。
- 神經網路引導搜尋、平行化 MCTS、局部模式資料庫等也持續被研究。
### 總結
目前加速詰棋搜尋的主要思路可歸納為：
1. **空間剪枝**（Relevance Zone 自動限制搜尋範圍）
2. **深度縮短**（FTL 偏好短勝利路徑）
3. **重用加速**（模式表、置換表）
4. **搜尋導向改良**（df-pn、EWS、專門化 MCTS）
其中 **RZS + FTL + 模式表** 是近年最成功、也最貼近實際應用的技術路線，已能大幅提升專業級死活題的解題效率與可解題數。
留言
張貼留言