圍棋 : 是否能對應轉成 圖論 的問題 ?
前篇 : 圍棋 電腦解死活題研究 tsumego
在先前 用 Grok AI 寫程式讓電腦自己解死活題時，發現 AI 又開始 解完 A 發生 B bug, 解完 B 原本的 A bug 又回來的鬼打牆狀況, 覺得應該還是得從底層開始自己研究;
突發奇想，棋盤交會處下子是點, 相鄰的棋子或空為邊, 這樣是不是就是個 圖論
G = { V, E } ?
(自己字比較醜, 請 AI 幫我在內容儘量不變的情況下, 修改字跡^^)
剛好今天週二 reset , 又有 Usage 可以跑 AI 了;
和 AI 討論, 發現這想法不僅僅我有, 的確有前人有研究過;
隨後看到 AI 提到 Gnu GO 和其他數學圖論與程式,
於是和討論 AI 之後死活題的方向, 獲益良多;
都先記錄一下, 之後繼續研究 ^_^
=== Grok AI 提供的參考文件 ===
A CLASSIFICATION OF SEMEAI WITH APPROACH MOVES
Mathematical Go: Chilling Gets the Last Point
Learning on Graphs in the Game of Go
Unraveling Go gaming nature by Ising Hamiltonian and common fate graphs: tactics and statistics.
=== Grok AI 回答：
可以。圍棋本來就是定義在圖上的遊戲；你寫的 (G={V,E}) 與三色狀態，方向是對的。已有一整條文獻把規則、氣、串、眼、死活寫成圖與連通性語言。下面先對齊既有研究，再給一套可繼續往下推的完整對應，並修 正你目前定義裡最關鍵的一處。
一、已有研究：圍棋本來就被當成圖
標準棋盤就是 正交網格圖 (G_0=(V,E))：頂點是交叉點，邊只連上下左右（沒有對角線）。19 路是 (19) 網格；邊上度數 3、角上度數 2，正是你寫的三種型態。
把規則寫成「圖 + 著色 + 連通分量」的經典來源：
| 工作 | 圖論角色 |
|---|---|
| Tromp–Taylor 邏輯規則 | 用「同色正交路徑能否走到空點」定義氣；提子 = 清掉所有「走不到空點」的同色點。規則極短，卻涵蓋提子與自殺。 |
| Segerman, General Graph Go | 直接把圍棋定義在任意著色圖 ((V,E,f))，(f:V{B,W,})。串 = 同色相鄰關係的自反傳遞閉包等價類；氣 = 與該類相鄰的空頂點。標準棋盤只是特例。 |
| Landman, Eyespace Values | 串是棋盤圖的連通分量；給出 拓樸活棋（兩個單點眼 + 每串至少鄰接兩眼）() 靜態活棋。假眼 = 拓樸條件失敗。再把眼位做成組合博弈。 |
| GNU Go optics | 眼位只依賴底層圖的同構類：外形不同但圖同構的眼形是同一個局部遊戲，用來壓縮眼形庫。半眼用「關鍵點虛擬相鄰」改圖。 |
| Tromp 合法局面圖 | 合法局面（每串至少一口氣）當頂點，合法著法當有向邊，得到 博弈圖 (G(m,n))；一盤棋 = 這張圖上的簡單路（超劫）。 |
| CGT（Berlekamp–Wolfe 等） | 終盤與眼位拆成獨立局部遊戲；眼的「值」可以是 (0,1,2,{1}) 等，不只整數「幾隻眼」。 |
| 社群／命運共同體圖 | 把「串」再聚成 dragon／group（弱連接的同色塊），用邊介數等做分群。這對應你問的 (g_1,g_2,) 之上還有一層。 |
結論：規則層幾乎已完全圖論化；難的是「眼／活棋／對殺」——它們不是單純的連通分量，而要再加包圍、切割與博弈。
二、建議的完整對應（從棋盤到活棋）
分四層圖，不要只用一張 (G)。
---
適合作「零件與思路」，不適合作「整套拿來當求解器」。
若目標是「自動解應答死活題、還要盡量對」，GNU Go 的 Owl／optics
只能當骨架與啟發式，主引擎應走專門死活搜索那一條線。
GNU Go 擅長什麼、死活題要什麼
GNU Go 的死活分兩段，文件寫得很清楚：
- optics.c：局面已經「走完、眼位不再漲縮」時，把眼位編成圖、對
eyes.db查最少／最多幾隻眼。
- owl.c：眼位還能擴或被壓時，用攻擊／做眼模式庫雙方輪流下，下到靜態再交給 optics。
這套是為 19 路對局裡判斷一塊棋危不危險、要不要補 設計的，不是為「這題唯一正解、變化全列出來」設計的。
死活題額外要求：
- 搜索範圍通常是包圍圈內（外圍當活棋／不可動）。
- 要分清：無條件活、死、劫活、雙活、盤角曲四、差幾枚劫材。
- 正解常是冷門手筋，不在「常見做眼／點眼」模式裡。
- 最好能當 證明（這條變化之後必活／必死），不是「看起來像活」。
GNU Go 自己承認：眼形圖
不理會外氣不夠、包圍鏈的斷點；optics 說已有兩眼時，Owl
普通模式根本不會再啟動，只能靠另一份 owl_vital_apats.db
硬補。對殺模組錯得比普通 Owl 多。這些剛好是題目愛考的地方。
哪些可以搬、哪些不要當主幹
值得借的（而且和我們前面的圖模型一致）
| 部分 | 用途 |
|---|---|
| 棋盤、串、氣、提子、自殺、劫 | 規則層必須正確，GNU Go 的 board library 很完整 |
| 「先讀到靜態眼位，再圖匹配」 | 終端局面估值的好策略 |
| 眼形圖同構、nakade 庫 | 著法排序與靜態判定，不是證明 |
| Benson／無條件活（GNU Go 的 invincible / unconditional） | 搜索可以提前停：已兩真眼且周圍氣足 |
| 把「一塊棋」當 dragon 來看，而不是只看單串 | 題目裡常兩串共一眼 |
不要整段當求解核心
- Owl 的著法幾乎只來自三份模式庫 → 漏手筋就整題錯。
- 沒有「題目邊界／相關區域」的嚴格定義。
- 沒有系統性的外劫材計數（Wolf
後來專門為這件事寫過程序化定義）。
- 估值是對局用的「危不危險」，不是 boolean「活／死」。
- GPL：若直接抄程式，你的求解器也會被 GPL 綁住。思路可以學，代碼要自己寫或找相容授權。
專門解死活的路線（比 GNU Go 對口）
歷史上真正衝「解題正確率」的，不是下棋程式的死活模組：
GoTools（Thomas Wolf）
α-β 搜索，結果壓成 活／雙活 vs 死（boolean search）；劫則重搜「弱方需要幾枚外劫材」。另有單眼形大庫、掃題找書裡的錯。這是 1990–2000 年代死活求解的標竿。Tsumego Explorer（Kishimoto 等, 2005）
證明數／深度優先證明數那類搜索 + 置換表，論文寫在封閉題上勝過當時的 GoTools。相關區域搜索（RZS）
近年吳毅成團隊等：先圈出「跟死活有關的點」，只在圈內窮盡。2025 還拿趙治勳《死活辭典》對過，能找出與書不同、但確實做活的下法（有時活得較小）。這比 Owl 模式庫更接近「自動解題」。KataGo + 死活框
不是證明器，但實用。LizGoban 等工具會在題外圍補活棋／劫材框，再讓 KataGo 讀。中高級題很強，極端冷門形、要「證明沒有第二解」時仍可能漏。MCTS 給的是高置信，不是數學證明。
若你要自己做「自動答死活題」，建議架構
把 GNU Go 當參考實作，主幹不要抄 Owl。
規則核（圖論層 0–2）
串、氣、提子、合法著、劫。可對齊 Tromp–Taylor。題目模型
標出：目標塊、敵塊、可下區域、外圍是否視為已活、外氣是否算、允許幾枚外劫材。沒這層，程式會跑去盤外「逃」。終端判定（靜態，可大量用 GNU Go／圖論想法）
- 無條件活（兩真眼或 Benson）→ 活
- 無眼可做且被包死 → 死
- 其餘繼續搜
眼形圖、nakade 表放這裡當 快速剪枝。
- 無條件活（兩真眼或 Benson）→ 活
搜索（這才是解題引擎）
封閉小題：α-β 或 df-pn + 置換表。
著法產生：先相關區域（眼位內、點眼、扳、夾、緊氣、撲），模式庫只用來排序，不拿來排除「庫裡沒有的手」。
結果用 boolean：活／死／劫（並記劫材數）。不要一開始優化「活得最大」。輸出應答
第一手 + 主要變化樹 + 狀態標籤（活、死、劫、雙活）。人類題解還在乎目數，求解器可第二輪再在「已證明能活」的著法裡選地盤較大的。驗證
用 Wolf 的題庫、常見死活書、再抽 KataGo 對打。GNU Go Owl 可當弱基線：它解得出的題你一定要對；它解不出的題才是你存在的理由。
直接結論
- 做對局程式裡的「這塊危不危險」：GNU Go
思路夠用，optics + 有限讀棋很划算。
- 做自動解應答死活題：適合借用它的
串／氣／靜態眼圖／兩眼停搜，不適合把 Owl
當主求解器。
- 主幹應對齊 封閉區域 + 證明性搜索（GoTools／Tsumego
Explorer／RZS），眼形圖論當啟發式。
- 若只要「大多數題給出能用的答案、不保證證明」，包一層題框呼叫 KataGo 往往比重寫 Owl 快、也比較準。
若下一步要落地，可以先定題目規格（是否含劫、外氣、雙活、要不要證明無第二解），再決定搜索是 α-β 還是相關區域；規格一變，適不適合金用 GNU Go 的比例差很多。
留言
張貼留言