圍棋官子最好一手電腦能不能算？

對一個 CGT 局部 $G$，定義：

• 左停止值 $LS(G)$：黑先動、之後雙方最佳對弈、終局得分。
• 右停止值 $RS(G)$：白先動、之後雙方最佳對弈、終局得分。
• swing $\Delta(G) = LS(G) - RS(G)$：先動 vs 後動的得分差。
• 溫度 $T(G)$：對 simple switch $\{a \mid b\}$ 而言 $T = (a-b)/2 = \Delta/2$；一般 hot 局部用 thermograph 之 mast 高度（BCG Ch. 6）。

Hotstrat（標準 CGT 啟發式）：當盤面是多個獨立局部之和 $G_1 + G_2 + \cdots + G_m$，永遠先下 $\arg\max_i T(G_i)$。

BCG 1982 的標準定理：在「all-small」或「無共享威脅」假設下，Hotstrat 是最優的。本研究關心的是這假設失效時——即 mixed sum with hot follow-up——Hotstrat 何時與最佳對弈分歧（§5 反例）。

設盤面分解 $\{R_i\}_{i=1}^m$，定義「黑強制先動 $R_j$ 之後續最佳對弈終值」：

$$V_j = RS\Big( R_j^{L^*} + \sum_{i \neq j} R_i \Big), \quad R_j^{L^*} = \arg\max_{R_j^L} RS\big(R_j^L + \textstyle\sum_{i \neq j} R_i\big)$$

對 simple switch $R_j = \{a_j \mid b_j\}$，$R_j^{L^*}$ 唯一為 $a_j$（一個 number），故：

$$V_j = a_j + RS\Big( \sum_{i \neq j} R_i \Big)$$

三讀法：

• D-must：top-k by $V_j$ descending——「黑該下哪手最有利」。
• D-avoid：top-k by $V_j$ ascending——「黑絕不能下哪手」。
• D-sign-flipping：依 $|V_j - V_0|$ 排（$V_0$ = 無 first-move-constraint 之終值）；本研究將此讀法之 reduction 與算法列為開放問題（§9.4 #9）。

定理 B：在 (a)「BW 標準形狀 + ko-free + 局部可分解」或 (b) $|R_i| = O(1)$ 之 promise 下，BEST-MOVE-X 為 $O(n^2 + m \log m)$，X ∈ {B, C, D-must, D-avoid}。

算法 2.3（D-must，最複雜的版本）：

1. 分解 $s$ 為 regions $\{R_i\}$（$O(n^2)$）。
2. 對每塊 $R_i$ 由 BWFormula 算 $(LS_i, RS_i, T_i, \mu_i, m^*_i)$（$O(n^2)$）。
3. 對 hot regions（$\Delta_i > 0$）依 Δ 降序排為 $\sigma$（$O(m \log m)$）。
4. 預處理 4 個 prefix/suffix arrays（$O(m)$）：
   • $P_a^{\text{even}}[p] = \sum_{l \leq p, l \text{ even}} a_{\sigma(l)}$
   • $P_b^{\text{odd}}[p] = \sum_{l \leq p, l \text{ odd}} b_{\sigma(l)}$
   • $S_a^{\text{odd}}[p] = \sum_{l \geq p, l \text{ odd}} a_{\sigma(l)}$
   • $S_b^{\text{even}}[p] = \sum_{l \geq p, l \text{ even}} b_{\sigma(l)}$
5. 每個 $V_j$ 由 $O(1)$ 公式： $$V_j = a_p + P_a^{\text{even}}[p-1] + P_b^{\text{odd}}[p-1] + S_a^{\text{odd}}[p+1] + S_b^{\text{even}}[p+1]$$ 其中 $p = \sigma^{-1}(j)$。
6. 對 $V_j$ 排序得 $\pi$，回傳 top-k regions 與其 $m^*$。

正確性：由引理 H（hotstrat-on-switches）之 saddle-point 對弈序列保證；prefix-sums 公式為其 closed-form 求和。

$\Delta = (10, 8, 6)$，$\mu_i = 0$，故 $(a_l, b_l) = (5, -5), (4, -4), (3, -3)$。

預處理：

• $P_a^{\text{even}}: [0, 0, 4, 4]$
• $P_b^{\text{odd}}: [0, -5, -5, -8]$
• $S_a^{\text{odd}}: [\_, 8, 3, 3, 0]$
• $S_b^{\text{even}}: [\_, -4, -4, 0, 0]$

計算：

• $V_1 = 5 + 0 + 0 + 3 + (-4) = 4$ ✓
• $V_2 = 4 + 0 + (-5) + 3 + 0 = 2$ ✓
• $V_3 = 3 + 4 + (-5) + 0 + 0 = 2$ ✓ （$V_2 = V_3$，符合 F2）

陳述：在「局部可分解」promise 下，對 X ∈ {B, C, D-must, D-avoid}，BEST-MOVE-X 為 PSPACE-hard。

證明骨架：從 Generalized Ladder Game (GLG) 之 PSPACE-completeness（Crâșmaru & Tromp 2000）reduce。每個 GLG instance $(B, s_0)$ 對應一個 BEST-MOVE-X instance。

關鍵：Lemma A.1（Swing 控制）。給定 GLG instance，建構 region $R_\Phi$（含 ladder 嵌入 + swing booster gadget）使：

• GLG = YES：$\Delta(R_\Phi) = D_Y = 6k$（其中 $k$ 為 ladder chase 長度，$|B|$ 之多項式）
• GLG = NO：$\Delta(R_\Phi) = D_N \leq 4$

故 $D_Y - D_N \geq 6k - 4 = \Omega(|B|)$，可 polynomial 校準。再加上一塊 calibration switch $R_*$，使「Δ 最大者 = $R_\Phi$」⟺ GLG = YES。

此 reduction 對 X ∈ {B, C, D-must, D-avoid} 共用一個建構（每個 X 各有校準參數）。

(D-sign-flipping 之 reduction 因 baseline $V_0$ 之循環依賴問題列為開放問題。)

計算複雜度階層大致：P ⊆ NP ⊆ PSPACE ⊆ EXPTIME。

• P：多項式時間可解（電腦算得快）
• NP-hard：至少跟「找答案不知怎麼找、但檢驗答案很快」之最難問題一樣難
• PSPACE-hard：至少跟「QBF（量化邏輯式滿足性）」一樣難——QBF 是 $\exists x_1 \forall x_2 \exists x_3 \cdots$ 之嵌套交替量化，本質上是「我必須對所有對手回應都有對策」之博弈問題
• EXPTIME-complete：n×n 圍棋全局（不限官子）已知為 EXPTIME-complete（Robson 1983）

本研究的官子問題卡在 PSPACE-hard 而非 EXPTIME——比全局簡單一些，但仍然超出 NP，超出多項式時間。實務上 PSPACE-hard 問題通常用 heuristic（如 KataGo）而非保證最優算法。

$P = G + H$ 之 L-options（B 動）：

• $L_1$: B 動 $G^L = 10$ → $P^{L_1} = 10 + H$
• $L_2$: B 動 $H^L = 8$ → $P^{L_2} = G + 8$

$RS(P^{L_1}) = RS(10 + H)$：W 動 $H^R = -8$ → 終值 = $10 + (-8) = 2$。

$RS(P^{L_2}) = RS(G + 8)$：W 動 $G^R = Y = \{0 \mid -100\}$ → $LS(Y + 8) = LS(Y) + 8 = 0 + 8 = 8$。

故 $LS(P) = \max\{2, 8\} = 8$，最佳第一手為 $L_2$（動 $H$）。

Hotstrat 衝突：$T(G) = 10 > T(H) = 8$ 預言動 $G$ → 終值 2，比最佳少 6 目。✓

C 與 D-must 給出正確答案：$\Delta(G) = 10$, $\Delta(H) = 16$ → C-top-1 = $H$ ✓；$V_G = 2, V_H = 8$ → D-must-top-1 = $H$ ✓。

抽象 CGT 反例 $G + H$ 可在 19×19 實現：

• $H$ 之實現：右下角 1×16 corridor，雙端對方活子封閉，調 $\ell$ 使 $\Delta = 16$。
• $Y = \{0 \mid -100\}$ 之實現：左上角構造一個未活的黑大塊（約 50 子），含 100 目地之潛在地盤。B 補一手做活得 0；W 動關鍵點殺死大塊，B 損 100 目。
• $G = \{10 \mid Y\}$ 之實現：右上角中型半實地，含 follow-up 結構。B 取 10 目地（保 follow-up 之選擇權）；W 引發 $Y$ 之活死競爭。

三塊位於不同角落，相距 ≥ 5 子，氣不互動。具體棋形需 tsumego solver 驗證精確死活，但結構性反例不依賴此細節（per BW 1994 Ch. 4 之 mixed-sum examples）。

由 §3 算法 2.3 之 prefix-sums 公式，$V_{\sigma(p)}$ 之 closed-form 為：

$$V_{\sigma(p)} = a_{\sigma(p)} + \sum_{l=1}^{p-1} \begin{cases} a_{\sigma(l)} & l \text{ even} \\ b_{\sigma(l)} & l \text{ odd} \end{cases} + \sum_{l=p+1}^{m} \begin{cases} a_{\sigma(l)} & l \text{ odd} \\ b_{\sigma(l)} & l \text{ even} \end{cases}$$

對 $p = 2k$ 與 $p = 2k+1$ 比較：

• Prefix 差：$V_{\sigma(2k+1)}$ 之 prefix 多一項 $l = 2k$ even → $a_{\sigma(2k)}$；故 prefix 差 = $-a_{\sigma(2k)}$。
• Suffix 差：$V_{\sigma(2k)}$ 之 suffix 多一項 $l = 2k+1$ odd → $a_{\sigma(2k+1)}$；故 suffix 差 = $+a_{\sigma(2k+1)}$。

加總： $$V_{\sigma(2k)} - V_{\sigma(2k+1)} = (a_{\sigma(2k)} - a_{\sigma(2k+1)}) - a_{\sigma(2k)} + a_{\sigma(2k+1)} = 0$$

故 $V_{\sigma(2k)} = V_{\sigma(2k+1)}$。✓ ($\square$)

定理 F1（C-top-1 = D-must-top-1, sum-of-simple-switches）：對 sum of $m$ non-degenerate simple switches，$\arg\max_j \Delta_j = \arg\max_j V_j$。即「先動 vs 後動差最大那塊」與「強制黑先動之得分最高那塊」第 1 名相同。

定理 F3（C-top-1 ≠ D-avoid-top-1, substantive 分歧）：構造盤面使「Δ 最大那塊」與「絕不能下那塊」嚴格不同。例：$m = 3$ switches with $\Delta = (10, 8, 6)$，C-top-1 = $\sigma(1)$，D-avoid-top-1 = $\sigma(2)$ 或 $\sigma(3)$（V 最小者），兩者區分性可達 $\Omega(\Delta_1)$ 目。

故四種定義之關係：

• top-1 上：B = C = D-must（在 simple switch sum 下，per F1）
• top-1 上：D-avoid 可與 C 不同（per F3）
• full ranking 上：D-must 出現成對 ties（per F2），C 為 strict

研究記錄了若干開放問題（per proof.md §9.4），擇要列出：

1. D-sign-flipping 之 reduction：baseline $V_0$ 之循環依賴問題未解。
2. BW 標準形狀之經驗覆蓋率：實戰 19×19 終局多大比例真的乾淨？需收集 KGS / GoQuest 終局資料統計。
3. Hotstrat 失效之 worst-case 上界：本研究給出 6 目顯式反例；最壞情況下 Hotstrat 可損多少目？
4. 結構性 ties (F2) 之擴展：能否擴到 corridor sums 或一般 BW 標準形狀？
5. 含劫之 quasi-polynomial 算法：本研究排除 ko；含 ko 但 ko 數 $O(\log n)$ 之上下界？