テストステ論

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

終局自動化アルゴリズム

以前から囲碁の終局をどうすれば自動化出来るかの悩みがあるわけだが, 前に書いたポストとは別のアイデアを思いついた

終局処理アルゴリズムアイデア - テストステ論

囲碁というのは, 全部の盤面が埋まった状態で終局するものではなく, ところどころ空きがある. これは, 打っても無価値なダメと呼ばれるもの, 双方どちらか打っても得にならないセキという形など色々ある. セキは死活の一種であるが, 頻度としてはそう多いものではなく, 大抵は明白にどちらかが死ぬ.

自動化の最終目的は, どこが黒地でどこが白地かという陣地分けを明白にすることであるが, これには石の生き死にの判定を行う必要がある. 例えば, 黒模様の中に白石がパラパラとある場合, これが死んでいるなら取り除いた上で地の確定を行うのだが, 実はこの白石が生きてるか死んでいるかは人間にも分からない. なので一般には, 明らかに活きないというところまで打ち切って, やっぱ活きなかったと確認するわけだが, 対局者というのはいやしいもので, 終局に合意する段階になって「いやこの石は生きている」などとごねるわけだ. そもそも, 石が生きてるかどうかというのはその石団が二眼を持っているかによるわけであるが, 初心者である場合はその判定が付かないことがあり, トラブルとなることがある. セキはなおトラブルのもとである. 終局の自動化はこの終局におけるトラブルを回避するためにある.

  • 空きがあっても打っていい/打って悪いがある
  • 死んでいる石を判定しなければいけない

というのが囲碁終局アルゴリズムの難しさなのであるが, 終局に合意した盤面が, 双方合意したものであり, もし終局アルゴリズムが提示した陣地分けに不満があるならばさらに打てばいいという見地に立つと(例えば, 一手目で終局合意した場合を考えてみよう. どっちが勝つのであろうか?わからないからさらに打つしかない), 完璧ではないがまぁまぁのものは作ることが出来そうである.

アルゴリズムの基本的なアイデアは, 終局盤面からなるべく無難な方法でプレイアウトさせることを繰り返して, もっとも頻度の高い結果を採用するというものである.

まず, セキの形が確定するには, 局所的に完全に打ち切ってるものと仮定する. セキというのは2手勝ちや1手勝ちという一般的な死活ではなく, ドローの状態である. これは非常にきわどいので, 局所的に打ち切らないと判定は出来ない(もちろん, 途中でセキになることは読みとしては分かるが, きわどいことなので, 通常は確定させる). その時, 打ってはならない空点はまわりに黒と白がいる点である.

そこで, アルゴリズムではまず, 終局盤面における空点の集合Sから, まわりに黒と白がいる点に「もう打たないマーク」をつける. ここはプレイアウトにおける着手点から除外される. その後, 眼形となりうる点に打たないようにプレイアウトさせる. すると, 最後には, もう打たないマークかあるいは目のみが残る. この段階で, 目にはそれぞれ自分の色の石を埋めて, 終局とする. 中国ルールに従い, 盤面の黒石白石の数をカウントして結果とする.

このアルゴリズムの良い点は, どのような局面からでも何かしらのそれらしい結果を出せることである. さらに, その結果に不服であれば単に打ち進めれば良いだけなので, 公平性も高い. アルゴリズムによっては, ある一定量打ち進めていなければ計算が全く出来ないということにもなりうる. その場合, ユーザには何が問題なのか分からず, 自動終局は糞という結論になる.

これで正しく動作するかどうかはよくわからないが, 実装は難しくないのでとりあえずやってみて, 正しく終局出来るか小さな盤面で試してみようと思う. 例えば, 5路盤で正しく黒勝ちを算出出来るかどうかは良い具合の試金石ではないかな