テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

終局処理アルゴリズムアイデア

ネット対局を実装するに当たって, 地の計算を自動で出来ることは大変良いことだ.

ではどこまで自動にやるかということだが, もっとも良いのは, 両者がパスした時点から, コンピュータが最善手を打ち続けることであることは明白である. しかしこれは,「では一手も打たずに両者パスしたら神の一手が分かるんかい」というひねくれはなしにしても, 難しいだろう.

現在最強の囲碁ソフトウェアはヨセ以降についてはプロ並と聞く. そういう意味では, 十分進んだ図からの終局であれば, コンピュータはほぼ最善の手を打ち続けることが出来る. しかし, 理屈上最善ではない. そもそも, 終局処理が何時間もかかるのも論外である.

終局をいくつかのステップに分ける. ルールは中国ルールを採用する.

  1. 両者パスする.
  2. ダメを詰める(中国ルールでは, ダメにも一目の価値がある)
  3. 死に石を確定する(1とは順序逆でも良いだろう)
  4. 地を計算する(盤面にある石の数で判定出来るのが中国ルールの簡単さだ)

仮に3まで出来ていれば, 自陣を自色で埋めることが出来る. 「連を広げていく」アルゴリズムだ. 簡単にいうと, ある色の石を置く時は同じ色の隣にしか置けないという制約を課して置いていく. もちろんセキに考慮する必要があるから「石をとる手は置けない」ということはいうまでもない. これを実装するのはそう難しくない. 冗長に作っても, 一手100msくらいでは計算出来るだろうと思う. 100手10秒なら, そう悪くはない. 対局者は一手30秒のスケールで打ってる. 何をいまさら10秒を気にする理由がある?

というわけで問題は2と3である.

3については, ネット碁においてよくある方式は「対局者が合意する」方式である. 中国ルールでは, 仮に不満があるならば打ち続けろということが出来るが, セキはどうしようもない. これに対する解決策としてまぁまぁ有力なのは, 注目する領域に死活の網を張り, その中でのみコンピュータが最善の決定を下すというものである. この網については合意をとりやすいだろう. まぁまぁ面白いので, やってみようかとは思っている. いずれにしろ, 詰碁エンジンは実装した方がいい. 汎用かつ最速のものを作り出すことは難しい領域である直感があるが, 少なくともこの話については遅いものでも問題ない. 領域が限られていれば愚直に全読みすることもそんなに難しくない.

対局者によっては, ダメを埋めることを嫌う場合もあるだろう. 特に日本では, 終局においてもダメを詰めないことを美徳とする傾向があるから, ダメを詰めないといけない対局システムは, 誰も使ってくれない.

というわけで, 自動でダメを詰めていくだけだが, これは, 自陣を詰めるよりは難しい.

まず, そこがダメであることを判定出来る必要がある. 仮にダメを判定出来れば, 一手一手交互に詰めていけばいい. (計算上は, 詰めなくてもいい. どうせイーブンであることが分かっているので. しかし詰めた方が分かりやすい)

ダメの判定法としてもっとも楽そうなのは, 「その点から四方にRayを飛ばして, 突き当りが全部同じ色だったらダメ」というものだ. これは, 一見するとむちゃくちゃ遅そうだが, そんなに悪くない. なぜならば, ダメを計算するのは終局時に一度だけだからである. Rayの長さが合計で100もいかず, 点はたかだか361点しかないので, 36000回くらい軽度な判定すれば済むレベルだ. 1秒程度では間違いなく終わる. もっと高速化するには, ダメを見つけたらその隣接点を再帰的に空点か?と判定を繰り返すことだが, たぶんオナニーだろう.

なんとなく穴はある気がするが, 死活がどうにかなればあとは自動的にやれる目処は立った. 最終的にはOCamlでウェブアプリを作ってローンチする予定だ. ローンチと言ってみたかった.

他に, モンテカルロ木探索に関連して, バンディットアルゴリズムにも興味がわいてきた. コンピュータ碁と関連技術については, もしかしたらどっかで勉強会をしたいかもしれない. 少なくとも社内勉強会のいち候補である.