Solving Cho Chikun Life-and-Death Problems on a Single RTX 5090

A Cross-Generation 2×2 Benchmark (Hardware × Algorithm) of the Relevance-Zone L&D Solver — Technical Report v0.1

Date: 2026-07-19 / Status: v0.1 public technical report(英訳版は準備中)

Companion report (same RTX 5090, the opposite bottleneck): Solving 7×7 Killall-Go Opening JA.

Abstract (EN)

We reproduce the relevance-zone (RZ) based life-and-death solver of Shih et al. (IEEE ToG 2025, A Study of Solving Life-and-Death Problems in Go Using Relevance-Zone Based Solvers) on a single consumer machine (RTX 5090 / Core Ultra 9 285K, WSL2), and sweep the 117 bundled Cho Chikun problems under the paper’s own 5-minute limit. Holding the code, problems, and configuration fixed, we vary only (a) the hardware generation and (b) the algorithm (RZS-TT vs RZS-PT), yielding a clean 2×2 matrix that separates the hardware contribution from the algorithm contribution with no cross-machine confound. On the newer machine the proved count rises to 84/117 (RZS-TT) and 88/117 (RZS-PT), versus the paper’s reported 68/106 and 83/106. The same-machine TT→PT delta (+4, with 5 gains and 1 regression) isolates the pattern-table contribution. Crucially, the neural network is tiny (765,523 parameters) and the GPU sits at ~23% utilization: this is a CPU-generation benchmark (Haswell 2014 → Arrow Lake 2024, with a 12× larger per-core L2 cache), not a GPU one — the mirror image of our GPU-bound killall-go report. We additionally (i) find and fix a deterministic segfault in the USE_POTENTIAL_RZONE code path (upstream issue + patch), (ii) document that the USE_EARLY_LIFE/USE_PATTERN_EYE knowledge flags are unsound for proof purposes (they emit 0-simulation false positives), and (iii) establish a 28-problem frontier that resists seki-DB, RZ-reduction, and extra time. Update (§11, 2026-07-20): this “method-limited” conclusion is overturned — raising NUM_THREAD from 2 to 20 soundly cracks 27 of the 28 via parallel-search diversification, reaching 117/117 — every problem proved (the last holdout vol2_p262 fell on a fresh parallel run; it was borderline, not memory-bound).

要旨(JP)

RZ(relevance-zone)ベースの死活ソルバ(Shih et al., IEEE ToG 2025)を単一のRTX 5090 + Core Ultra 9 285K(WSL2)で再現し、同梱の趙治勲事典117問を論文条件(5分制限)でスイープした。コード・問題・設定を固定し、(a)ハード世代と(b)アルゴリズム(RZS-TT/RZS-PT)だけを変えることで、ハード寄与とアルゴリズム寄与を交絡なしで分離する2×2行列を得た。証明数は新機で84/117(TT)・88/117(PT)(論文報告値68/106・83/106)。同一マシン上のTT→PT差(+4、救済5・回帰1)がパターンテーブルの純寄与。NNは極小(765,523params)でGPU実利用率は約23%——本研究はCPU世代ベンチ(Haswell 2014→Arrow Lake 2024、L2キャッシュ12倍)であり、GPU律速のkillall-go編とは律速点が逆。加えて(i)USE_POTENTIAL_RZONE経路の決定的segfaultを特定・修正(upstream issue+patch)、(ii)USE_EARLY_LIFE/USE_PATTERN_EYE知識フラグが証明目的には不健全(sims=0の偽陽性)であることを実証、(iii)セキDB・RZ縮小・追加時間に抵抗する28問フロンティアを確定した。

⚡ 追記 (2026-07-20): 上記(iii)の「手法律速」という結論は覆った。ソルバのスレッド数を既定の2から20に上げるだけで、28問中27問がsoundに崩れ(健全性検証済み)、best-ofで117/117(全問)を証明した。当初残ったvol2_p262も別走行(シード変更)で陥落し、フロンティア全28問が並列で解ける境界問題だった(真のメモリ壁はゼロ)。全実験でスレッド数を2に固定していたことが、誤った「手法律速」結論を生んでいた。詳細は§11。

1. 背景

killall-goとの違い(重要): 姉妹研究のkillall-goソルバは大きめのPCN netでGPU律速だったため、per-slot 2.01×のクリーンなGPU世代比が出た。本死活ソルバはNNが極小でGPUがほぼ遊休。よって同じ5090上でも、こちらはCPU律速。同一ハードで律速点が逆になる好対照。

2. 実験設定

項目 本走行 論文参照(報告値)
GPU RTX 5090 32GB(Blackwell, 2025) GTX 1080Ti(Pascal, 2017)
CPU Core Ultra 9 285K(Arrow Lake, 2024, 24C) Xeon E5-2683 v3(Haswell, 2014, 14C/28T)
L2 / コア 3 MB 256 KB(≈12×)
L3(共有) 36 MB 35 MB(ほぼ据置)
探索スレッド NUM_THREAD=2 同cfg
制限 300 s / 問 300 s / 問
NN FTL 5B×64, 765,523 params(3.66 MB) 同一
ソフトウェア libtorch 2.11.0+cu130 / CUDA 13.2 / gcc 13.3 / WSL2 当時の環境
走行 1列直列(NW=1)、3走行(pass1 / ボーダー再走 / pass2) —

母数が異なる(本117問 vs 論文106問)ため、数の直接比較でなく率で読む。

3. 再現性の検証(3走行方式)

証明探索は並列非決定なので、全117問を pass1 → ボーダー再走(未解＋250s超を単独全リソースで) → pass2 の3走行で回し、「少なくとも1回証明」を合算した。RZS-TTでの走行間分散: pass1=80、pass2=79、両passで証明77問、片方のみ5問(vol2 p138/p142/p152/p166/p372=300s直下の時刻シード依存の境界問題)。分散は実在するが小さい。

4. 結果: 2×2マトリクス

  1080Ti + Xeon(論文) RTX 5090 + 285K(本機)
RZS-TT 68 / 106 (64%) 84 / 117 (72%)
RZS-PT 83 / 106 (78%) 88 / 117 (75%)

5. 律速はCPU、特にL2キャッシュ(実測)

走行中の実測: GPU sm利用率 21–27%で安定(mem-util 0%、VRAM 644 MB、143 W/575 W)、CGIは190% CPU(NUM_THREAD=2)、load ≈ 2.0。GPUはほぼ遊休で、律速はCPU側の証明探索(RZ展開・パターンマッチ・置換表アクセス＝ランダムなポインタ追跡＝キャッシュ遅延律速)。

sysfsで確認した実機キャッシュは L2 3 MB/コア(Xeon Haswellの256 KB/コアに対し約12×)。一方 L3は据置(36 vs 35 MB)。増えたのは私的L2だけで、置換表の hot working set が高速L2に収まりやすくなったことが、境界前進の有力な寄与と考える。ただしWSL2でハードウェアPMU(perf)が使えず、L2ミス率の直接測定はできていない——size contrast と access pattern に基づく仮説であり、clock・IPC・DDR5遅延の寄与とも交絡する。よって本ベンチは「GPU世代比」ではなくリグ世代比(CPU支配)と読むべきである。

6. 手法律速のフロンティア(28問)

TT・PT両方が全走行で未解の問題は 28問(vol1: p090/p098/p150の3、vol2: 25問、事典の最難問帯に集中)。これらは時間律速でなく手法律速であることを次で確認した:

→ この28問は「何が証明できるか」を変える手法の標的だが、候補として検討したセキDB・RZ縮小はいずれも不適合と判明した(§9)。

7. USE_POTENTIAL_RZONE の決定的segfaultと修正

文書化オプション USE_POTENTIAL_RZONE=true が、RZS-TT/PTいずれでも探索序盤で決定的にsegfaultする。gdbで追うと、WeichiQuickWinHandler の hasPotentialRZone/hasBensonSequence にある4つのコネクタ着手ループが、着手前の空点チェックなしに m_board.play() を呼び、占有点で null block を生成→WeichiBoard::updateSiblings(WeichiBoard.cpp:351)で参照して落ちる。同ファイル138行に作者自身の同じガード(if (grid.getColor() != COLOR_NONE) { continue; })があるのに、この4ループだけ欠落していた。

修正は各 play 直前に同ガードを移植(4箇所)。健全性検証: 既に健全に証明済みの9問を patched potential-RZ で再解 → 9/9 判定一致(全UCT_WIN)・実探索3.7k–34k sims・偽陽性0。クラッシュを除去し結果を変えない、正当性修正である(求解数は増やさない)。詳細と patch は upstream の issue/PR 参照。

8. 知識フラグの負の結果(soundnessの罠)

フロンティア攻略に USE_EARLY_LIFE=true + USE_PATTERN_EYE=true を試したところ、28問中26問が0.01秒で”UCT_WIN”となった。しかし中身は sims=0 / best=PASS / 木2.4 KB——探索ゼロで「もう活き」と即断した偽陽性である。同一問題をTT/PTは300s・60万simsを尽くしてUCT_UNKNOWN(未証明)としている。cfgコメントが明示するとおり、これらのフラグは健全なBenson活き判定をヒューリスティックに置換する(False: use Benson)。証明ソルバでは「落ちない」≠「正しい」であり、これらは proof frontier の拡張には使えない。教訓: フラグを足す前にsoundnessを確認すべし。

9. フロンティア28問の性質診断: 3候補すべて不一致(負の結果)

真フロンティア28問(§6)を崩すため、セキDB・RZ縮小・CGTの3候補を検討したが、診断の結果いずれも的外れであることが分かった。

9.1 セキ律速でない。 28問中、書籍解答ラベルまたは変化図に明示的なセキ(双活)の語が現れる問題は 0問。セキDBは的外れ。

9.2 コウルール律速でもない(切り分け実験)。 28問中9問は変化図にコウが登場する。「活き側のコウ拒否(disallow_ko)が邪魔しているだけで、コウを許せば(allow_ko)証明できるのでは」という仮説を検証するため、9問すべてで活き側のko_ruleをallow_koに反転して再走(RZS-TT.cfg)。結果: 9/9とも300sタイムアウトのまま(UCT_WINへの反転は0問)。むしろコウを許すと探索空間が広がり、simsが増加した問題もある(vol1_p150: 44万→102万sims)。→ コウは”解けない理由”ではなく、探索を重くする一要因に過ぎない。この9問も含め、フロンティアは枠組みの限界ではなく深さ/複雑度律速と確定した。

9.3 RZ縮小(arXiv:2510.00689)はNO-GO。 当初、「同一メモリ・時間で深く探索できる」効果を期待したが、原論文(Lin, Wei, Wang, Guei, Shih, Tsai, Wu, Wu; ACG 2025; study-LD-RZ/online-fine-tuning-solverと著者完全重複の同一研究室)を精読した結果、想定と異なることが判明した。

教訓: 数値の”向き”(圧縮率か縮小後の残存率か)と適用対象(解決済み前提か否か)は、要約でなく原論文の精読で確認すべきだった。当初「セキDB/RZ縮小/CGTのいずれかでフロンティアを崩せる」という前提自体が、この診断により大きく修正された。 (なお§11のとおり、フロンティアの大半は”手法”でなく”探索の並列性”で解けたため、この§9が前提とした「フロンティアを崩す手法」という枠組み自体が後に覆った。)

10. Threats to Validity / 今後

11. 追記 (2026-07-20): 並列探索でフロンティアを完全突破 — 117/117

§6・§9で「28問フロンティアは手法律速で、追加時間でも現行RZ手法でも崩せない」と結論した。この結論は誤りだった。 原因は、上記の全実験でソルバのスレッド数を既定の NUM_THREAD=2 に固定していたこと。これを 20 に上げるだけで、28問中 27問が UCT_WIN で崩れた。

機序

20スレッドの並列MCTSは virtual loss により各スレッドを強制的に異なるノードへ分散させる。2スレッドでは両者が同じ(極小の)方策ネットに引きずられて同一の不毛な部分木に嵌り、MAX_PAGE(512)を埋め尽くして UNKNOWN になっていた。20スレッドは急所手を早期に発見し、pool full 前に証明を閉じる。効いたのは「より多くの計算」ではなく「罠を抜ける多様化」で、必要 sims はむしろ激減した:

問題         2スレッド(既定)           20スレッド
vol1_p090   443,699 sims → UNKNOWN    1,521 sims → WIN
vol2_p124   (300s未解)                62,929 sims → WIN
vol2_p158   (300s未解)                955,442 sims → WIN (証明木265MB)

結果

全20+スレッド走行の best-of union で 117/117 を証明 (100%)。§6の28問フロンティアが全28問とも並列で崩れた。

                        proved
論文 RZS-TT (1080Ti)      68 / 106
本機 2スレッド RZS-TT      84 / 117
本機 2スレッド RZS-PT      88 / 117
本機 20-22スレッド          117 / 117   ★ 100%

健全性検証

新規WINは全て実 sims・実体ある証明木(947KB〜343MB)・crucial stones 付きで、§8の偽陽性パターン(sims=0/best=PASS/極小木)はゼロ。再現テスト(4問再走)で判定・crucial stones が一致(vol2_p124/p158は sims 数まで同一=ほぼ決定的)。既解問題のsanityも維持し、LOSS・書籍解答との矛盾はゼロ(全問 TOLIVE=活き側勝ちと整合)。並列AND/OR証明のrace由来偽陽性なら「判定がブレる・証明木が退化する」はずが、観測はすべて逆。独立プルーフチェッカーによる第三者検証のみ未実施(将来課題)。

最後の1問 vol2_p262 も陥落 ── 全28問が境界問題だった

p262は3走行(20スレ×2 + 22スレ600ページ×1)ともUNKNOWNで、一時は「証明木が48G超を要求する真のメモリ律速」と判定した。しかしこれは勇み足だった。 同一構成(22スレ・MAX_PAGE=600)でシードだけ変えた4回目の走行が、pool full前に急所を発見(証明木162MB < 前回の343MB)して121秒でUCT_WIN。つまりp262も他の境界問題と同型で、非決定的な並列探索が”当たり走行”を引けば解ける。28問フロンティアに真のメモリ壁はゼロであり、十分な回数試せば全問が解ける ── 最終的に 117/117 完全証明。

(教訓の上塗り: 3走行の失敗で「メモリ壁」と結論しかけたが、これも探索したサンプル数の内側でのみ有効な負の判定だった。非決定的な求解では、単発の未解を”壁”と即断してはならない。)

メモリ安全設計

全走行を cgroup MemoryMax(40〜48G, swap無効)下で実行。難問が上限に触れた際はカーネルが CGI プロセスのみ OOM-kill し、WSLは一度も落ちなかった。要点: 並列は「別々の問題を同時実行」(探索木が独立に増えメモリ×並列数=以前クラッシュした形)ではなく「1問に多スレッド(探索木を共有)」なのでメモリは増えない。問題間バッチは盤面TTの累積でOOMするため、1問ずつ独立プロセスで実行した。

教訓

「手法律速」と結論する前に、最も基本的なパラメータ(スレッド数)の掃引を怠っていた。負の結論は、実際に探索したパラメータ空間の内側でのみ有効である。 セキDB・RZ縮小を「フロンティアに不適合」とした§9の判断は手法単体としては正しくとも、フロンティアの大半が”手法”でなく”並列性”で解けた以上、その前提(手法でフロンティアを崩す)自体が失われた。

引用