試行錯誤方による死活判定は可能か　　２００２．１２．２４

詰碁をコンピュータを使って解く場合の問題点について特に同型反復問題に限定して現在までに分っていることをまとめてみました。以降に述べているように全ての問題が解消されている訳ではありませんので既に研究済みで解決されている等ご存知の方があればご意見をお待ちしています。

１．試行錯誤方概要

ある領域内で中の石に活きがあるかどうか判定する方法として攻める側と活きようとする側が囲碁の対局ルール（例えば日本囲碁規約）に従って打ち進めもし負ければ「待った」をして別の手を打つということを繰り返せば最終的にはどちらの勝ちか判定できるというものです。

最終状態を活きようとする側にとっては味方の石が全部なくなると負け、攻める側にとっては領域内の空き点が全て着手不能となり相手の石を攻める手が全くなくなると負けと定義することにします。

ある局面がそれ以降の全ての試行過程において最終負け状態に到達する場合負けと判定する。

このことは当然のように思えますが以下の条件を満たしている必要があります。

[条件1]負けと判定するためにはルール上着手可能な手を全て試行していること

[条件２]どちらかが負け状態と確定するまでの任意の手順の長さ（手数）が有限であることと

判定過程で手順を進めているとき以前出現した局面と全く同じ局面に戻ってしまうことがあります。これを同型反復といいますが同型反復を許すと手数が無限に伸びてしまうことになり手数の有限性が保証できません。判定可能にするためには手順内で同型が現れることを禁止しなければなりません（同型反復禁止則）。

手順内で同型を許さないことにすれば最大手数は高々［３（空き、黒、白の3状態）＾（領域サイズ）］になり有限性が保証できますが問題は対局ルールに規定されていない同型反復禁止則の導入は[条件1]に反しているようにみえることです。

２．同型反復

（１）コウ

簡単な例としてコウの取り返しも同型反復禁止則の一種で日本囲碁規約でも規定されていますが下図で黒番とすると△が直前に打たれたコウ取りであった場合は黒は打つ手がないので負け、そうでなければ黒は△をとることができ白は取り返しできないので黒の勝となります。

つまり全く同型であるのに判定が逆転してしまいます。

┌●△┬○●┬
○●●○○●┼
○○○○●●┼
●●●●●┼┼
├┼┼┼┼┼┼

有意な判定結果とするためにはこの領域外にあるコウ材の多寡を仮定する必要がでてきます。「詰碁」は限定された領域内での死活判定ではあるが他の部分も含む全局的状況を仮定しなければ解決できないことになります。

「コウ不利という条件で勝敗を判定しそれで勝なら無条件勝、そうでなければとコウ有利という条件で判定しそれで勝ならコウと判定すればよいのですが「三手ヨセコウはコウにあらず」という格言があるように無制限にコウ有利という条件は現実的でないので判定定数（N）を設けコウ不利な側もコウを取らずにN回手抜きすればコウを取れるという条件にしています。

（２）手抜き

手抜きは着手可能な手の一つで特に活きようとする側にとっては重要な一手ですが手抜きに対して手抜きすると同型反復になります。

詰碁における手抜きは判定対象領域外に打ったと考えるのが自然で一般の対局でのパスまたは着手放棄とは違います。

単純に手抜きに対する手抜きを禁止すると下図で白番とすると白が手抜きすると黒は自分の目を潰す手を打たざるを得なくなり死んでしまうので手抜きに関する詰碁のためのルールを作る必要がでてきます。

┌●●○┬
●┼●○┼
●●○○┼
○○○┼┼
├┼┼┼┼

攻める側は相手の石を全部取らないと勝てないというのが判定基準ですから相手の石がある限り手抜きはできないのが原則ですがコウ不利で取れないコウがある場合は手抜き可能とします。

逆に活きようとする側は相手が手抜きしている場合を除いて手抜き可能とします。

つまり一般対局と違って着手規定が非対称になります。

上記ルールによって下図の場合白がコウ不利な条件とすると白には手抜きの権利があり白に手抜きされると黒は手抜きできないのでどこかに打たざるを得ず結局打ち上げられることになり無条件死であることが説明できます。

┌●┬●○┬┬
●●●○○┼┼
○○○○┼┼┼
├┼┼┼┼┼┼

この白が活きる側になったとき（下図）は２手ヨセコウ（N=2で無条件活き、N=3でコウ）ということになります。

┌●┬●○┬●┬
●●●○○┼●┼
○○○○┼●●┼
●●●●●●┼┼
├┼┼┼┼┼┼┼

（３）４手以上に渡る同型反復

以下のような例があり日本囲碁規約では双方同意したときは無勝負としていますが同意しない場合については規定していません。この扱いについても新規ルールが必要になります。

┌┬●┬●┬●○┬
●●●●●●●○┼（三コウ　１サイクル６手）
○○○○○○●○┼
├○┼○●○●○┼
○●○●┼●○○┼
●●●●●●○┼┼
○○○○○○○┼┼
├┼┼┼┼┼┼┼┼

┌●┬●○○○○○○┬
●●●●●●●●●○┼（循環コウ　１サイクル８手）
○○○○○○○○●○┼
├○┼┼○●●○●○┼
●●○○●┼┼●○○┼
●●●●●●●●○┼┼
○○○○○○○○○┼┼
├┼┼┼┼┼┼┼┼┼┼

┌○┬●┬○●┬┬┬
●○○○●●○○┼┼（長生　１サイクル４手）
●●●●●○○┼┼┼
○○○○○○┼┼┼┼
├┼┼┼┼┼┼┼┼┼

特に長生型の同型反復は実戦ではあまり見かけませんが詰碁を解く過程ではよく現れます。

ア）白の手番
┌○┬●┬┬●┬┬┬
●○○○●●○○┼┼
●●●●●○○┼┼┼
○○○○○○┼┼┼┼
├┼┼┼┼┼┼┼┼┼

イ）黒の手番
┌○┬●┬△●┬┬┬
●○○○●●○○┼┼
●●●●●○○┼┼┼
○○○○○○┼┼┼┼
├┼┼┼┼┼┼┼┼┼

ウ）白の手番
┌○▲●┬○●┬┬┬
●○○○●●○○┼┼
●●●●●○○┼┼┼
○○○○○○┼┼┼┼
├┼┼┼┼┼┼┼┼┼

エ）黒の手番
┌○┬┬△○●┬┬┬
●○○○●●○○┼┼
●●●●●○○┼┼┼
○○○○○○┼┼┼┼
├┼┼┼┼┼┼┼┼┼

ここでで黒が２子を取るとア）に戻りますがこの場合は同型反復を回避しようとした方の負けになるので必然の手順です。同型に戻す着手を禁止するとア）図が問題として与えられた場合は黒の負けということになりますがイ）図が問題として与えられた場合はウ）エ）ア）と進みここでここで白はイ）の△を打てないことになるので白の負けとなり判定に一貫性がありません。

「詰碁研究」では同型反復は攻める側の責任（活きようとする側が同型に戻した場合活き側の勝）として無勝負を活きの一種としています。

この考え方には問題があって以下の長生モドキを例にすると。

ア）白の手番
○┬●┬┬●┬┬
├○○●●○○┼
○○●●○○┼┼
●●●┼○┼┼┼
○○○○○┼┼┼
├┼┼┼┼┼┼┼

イ）黒の手番
○┬●┬△●┬┬
├○○●●○○┼
○○●●○○┼┼
●●●┼○┼┼┼
○○○○○┼┼┼
├┼┼┼┼┼┼┼

ウ）白の手番
○▲●┬○●┬┬
├○○●●○○┼
○○●●○○┼┼
●●●┼○┼┼┼
○○○○○┼┼┼
├┼┼┼┼┼┼┼

エ）黒の手番
○┬┬△○●┬┬
├○○●●○○┼
○○●●○○┼┼
●●●┼○┼┼┼
○○○○○┼┼┼
├┼┼┼┼┼┼┼

ア）が問題図として白がイ）図の△に打つとウ）エ）と進み黒が２子を取るとア）の同型に戻されたので攻め側白の負けとなります。つまりイ）図の△では白は勝てないことになりますがイ）図が問題図として与えられた場合はア）の局面になったとき外ダメを詰めていれば白の勝なので黒に手は有りません。実際はこの４つの局面全て黒負けなのでイ）図を白負けとするのは問題があります。ア）の局面では白は手抜きでも黒に手はないのでイ）図の△を勝着点として認めないこと自体はそれほど問題ではないのですが「同型はその成立過程によらず同じ結果になる」という命題が成立しなくなるのが困った問題です。

（４）手抜きを含む同型反復（手損、手得）

下図のア）を白番としてイ）ウ）エ）の手順の後黒が手抜きするとア）と同型に戻ります。

ア）白の手番
┌●┬●○┬○●┬
○●●○○○●●┼
├○○○●●●┼┼
○○●●●┼┼┼┼
●●●┼┼┼┼┼┼

イ）黒の手番
△●┬●○┬○●┬
○●●○○○●●┼
├○○○●●●┼┼
○○●●●┼┼┼┼
●●●┼┼┼┼┼┼

ウ）白の手番
┌●┬●○┬○●┬
├●●○○○●●┼
▼○○○●●●┼┼
○○●●●┼┼┼┼
●●●┼┼┼┼┼┼

エ）黒の手番
┌●┬●○┬○●┬
△●●○○○●●┼
├○○○●●●┼┼
○○●●●┼┼┼┼
●●●┼┼┼┼┼┼
　

この場合一巡するごとに黒は外に一手打って稼いでいることになり明らかに白が悪いのですが違反が検出されるのがエ）の局面であるためイ）の△ではなくエ）の△が違反手となるのが問題です。

「詰碁研究」ではエ）の状態で黒の手得（一手抜いても同型、別の見方をすればアゲ石が１個増えている）として白に打ち直しを要求します（次項でのべる勝敗ペンディング）。

３．同型はその成立過程によらず同じ結果になる

この命題は試行錯誤する過程で既に出現した局面と同型になった場合以前の判定結果に従って以降の判定手続きを省略できるという意味で重要ですが本当に正しいかどうか疑問がありました。実際「詰碁研究」での処理過程を追跡してみると同型の勝敗判定が逆転するケースがあるからです。その原因は形としては負けパターンにもかかわらず相手が同型反復禁止則に違反して負けになったため勝と判定されていることによります。

下図の例が代表的なもので[成立過程２]が先に現れるとこの局面は白の負けと判定されているため[成立過程１]は白勝にも関わらず負けと判定してしまうものです。試行順位が判定結果を左右するのでは何のための試行錯誤かという疑問が沸いてきますが、コウは最後に取るべしという原則を守ればこの場合は回避できます。しかし全ての局面でこのような試行順位に関する原則が存在するかどうかは分かりません。これも今後の研究課題です。

ア）白の手番
●┬┬●┬●○┬┬┬┬
●●●●●○○┼●●┼
○○○○○○┼●●┼┼
●●●●●●●●┼┼┼
├┼┼┼┼┼┼┼┼┼┼

イ）最終局面
●┬○●○┬○●┬┬┬
●●●●●○○●●●┼
○○○○○○┼●●┼┼
●●●●●●●●┼┼┼
├┼┼┼┼┼┼┼┼┼┼
[成立過程１]（白：手抜き）-（黒：8の一）-（白：3の一）-（黒：8の二）−（白：5の一）

[成立過程２]（白：手抜き）-（黒：8の一）-（白：5の一）-（黒：8の二）−（白：3の一）

現在は同型反復があった場合その開始局面から同型に到るまでの過程で発生する局面の勝ち負けをペンディング（不確定で信用できない）にしてこの問題を回避していますが問題の原因はコウによる同型反復とコウ以外の同型反復に対する禁止規定に一貫性がないことによるので統合することも検討する価値があるかもしれません。同型反復を全てコウとして統一する考え方（Super ko）ですが循環サイクルが長い場合どの手に責任があるか特定することが難しく先ほど述べた寄せコウ論理を上手く組み込む原則を発見できるかどうかも疑問です。

５．まとめ

試行錯誤法での判定過程で同型反復がある場合その判定結果は信頼できない場合がありそれを避ける方法として

（１）別手順で現れた同一局面の判定結果を使わない。

（２）試行錯誤順序を保証する。

２つの方式が考えられますが（１）は同じ局面を繰り返し処理すると言う無駄が生じるので採用しがたく（２）は実現が難しいという問題が残ります。しかし着手評価の精度を上げることは時間短縮の観点からも重要な課題なので後者の方法を追及していきたいと考えています。