大型詰碁を解くための対策(部分活き型について)  2002.12.16

「詰碁研究」は試行錯誤を繰り返し判定対象領域内での石の生死を確定するのですが、領域が広くなると試行錯誤回数(評価すべき局面数)が増大しそれに比例して判定時間が長くなります。単純には一路増えるごとに3倍(空き、黒、白の組み合わせ)になる理屈ですがそれでは着点が30路、40路を超える大型の詰碁をとくことは絶望的になります。このような場合の対応策は事象が独立している領域に分割して評価し結果を総合評価することです。

領域が外周勢力によって分割された場合は比較的簡単で分割領域のどこかで活きれば活き、全ての分割領域で活きがないことが証明された場合は死となります(この機能はV5の初版から導入しています)。しかしこのようなケースは頻繁に発生するわけではなく効果はそれほど期待できません。

現在開発しようとしているのは活きようとする側の石によって分割された領域の独立判定機能です。

可能性があると考えている理由は碁の特性として石が活きるために必要な広さは対象領域の広さとは無関係で一定であるということです。ただし難しい問題があるのは事実です。

V502で導入したのは第1ステップですが何人かの方の協力も頂きまして数多くの問題が見つかっています。

以下に概略を記載します。

 

1.概要

この方式は以前から持っている、別手順でも既出の勝ち負けが決まった局面と完全に一致した場合以降の処理を省略する処理を拡大し部分領域が活き型と一致すれば活きる側の勝ちを確定するものです。

具体的には下図の局面1で▲5子によって領域が左右に2分され、この後の変化で黒が左側だけで活きることが確定すると左半分を部分活き型として登録します。以後白が▽を右側の領域のどこに打っても左半分の領域が活き型と一致するため以降の判定処理を省略し黒の勝ちを確定します。

(例題)

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


(局面1)

┌┬○▲┬┬┬┬┬┬
├●○▲▽┼┼○○┼
├┼┼▲○┼┼●○┼
├●┼▲┼○┼●○┼
├┼┼▲●┼●●○┼
├○○○●●●┼○┼
├○┼○┼┼○○○┼
├┼┼○○○○┼┼┼
├┼┼┼┼┼┼┼┼┼

2.活きるための領域の確定

この方式の成否は活きるために必要とした(する)領域を確定できるかに掛かっています。難しいのはこれには目になった領域を囲んでいる石のような直接的着点だけでなく相手にある着点に打たせなかったというような間接的な領域も含める必要があることです。当初は活きるために必要とした(する)領域は勝ち手順の中で打った着点と考えていたのですがそれほど単純ではなくかなり難航しました。

現在までに指摘された誤判定は上記領域の収集もれとバグによって収集情報を消していたことなどによるものです。

『余談ですが「必要とした」と過去形で表現しているのは勝敗確定論理の中では手数が進んだ状態が先に確定しますので「過去は確定未来は不定」という通念を適用すると時間の流れは手数が多い状態から少ない状態に向かって流れているとも考えられるのです。通常どおり手が進む方向に時間が流れているとすれば「未来は確定しているが過去のことは不定」というおかしな世界になります。思考過程とはそのようなものかもしれませんが。』

 

(例1)外部にコウがある場合

図1−1は△で囲まれた領域で無条件で活きており活きが確定する過程でこの領域外に打つことはありませんので部分活き型の条件を満たしているように見えます。しかし図1−3もこの部分が同型であり外ダメの数も同じなので活きと判定すると誤判定(V503)になります。

(図1−1)白番−−手抜き            (図1−2)黒コウ取り

●┬△△┬▽▼┬┬┬┬      ●┬△△▼┬●┬┬┬┬
├●●△○●┼┼●●┼      ├●●△○●┼┼●●┼
●△△△○●┼●●┼┼      ●△△△○●┼●●┼┼
△△●○○○●●┼┼┼      △△●○○○●●┼┼┼
●●●●●●●●┼┼┼      ●●●●●●●●┼┼┼
├┼┼┼┼┼┼┼┼┼┼      ├┼┼┼┼┼┼┼┼┼┼

(図1−3)白番

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

図1−1では▽▼の交換を打っているので▽も活きるために必要とした領域のように見えますがある局面の勝敗が発生過程(この配石になる前に打った手)に影響されるのは変な話です。発生過程の問題ではなくコウの特殊性(コウ取りに対しては特別な制約を与えていること)によるものと考えています。

特別な制約というのは、無条件勝ちが有るかどうかの判定フェーズでは、図1の状態では白は内部のコウを取れないが黒が外部のコウを取る(図1−2の▼)と白は内部のコウを取れる状態になるというような人工的に作ったルールのことです。

部分領域外にコウが存在する場合そのコウも活きるために必要な領域と考えざるを得ません。この場合領域全体が一致しない局面は活きと判定できないことになります。

 

(例2)外部に着手不能点がある場合

図2−1はこの局面以降の活きる過程で▲の左側領域には着手しないで活きており図2−2は▲の右側は完全に図2−1一致しているけれども活きていない。両者の違いは発生過程で打った■なのでやはり発生過程の配石も含めて一致していなくてはならないように思えますがこれも発生過程の問題ではなく相手の着手不能点によって繋がっている■が作った目が活きるために必要な領域と考えることにします。なぜ拘っているかというと活きた石と繋がっていない石はどこにあってもいいはずだからです。

(図2−1)

┌●┬●▲┬┬○┬
■●●○▲┼●○┼
○○○○▲┼●○┼
├┼┼○▲▲○○┼
├┼┼○○○○┼┼
├┼┼┼┼┼┼┼┼

(図2−2)

■●┬●▲┬┬○┬
├●●○▲┼●○┼
○○○○▲┼●○┼
├┼┼○▲▲○○┼
├┼┼○○○○┼┼
├┼┼┼┼┼┼┼┼

3.この方式の効果

全ての問題に対して効果がある訳ではないが冒頭の例題での比較では以下の通り処理した局面数が1/5に減少しています。

機能を有効化した場合の処理局面数:195408

機能を無効化した場合の処理局面数:964172

この方式による効果を完全に引き出しているともいえませんが有効性があるといえます。