ゴドマチの詰め探索をするプログラムを書きました。
結構頑張ったのと、個人的に面白かったので使ったアルゴリズムについて書いてみようと思います。

ゴドマチって？

2人用の対戦型パズルゲームです。
ルールは考案された方のページでまとめられています。
単純なルールで気軽にできるゲームなので、やったことないという方は是非遊んでみてください。

j344.exblog.jp

　
と、宣伝をしたところで本題へ。

ゴドマチは完全情報ゲームで引き分けがないので、あらゆる局面は先手勝ちか後手勝ちか、両者最善を尽くした場合の結果が決まっています。
そう言われるとどんな局面がどっち勝ちか知りたくなってきますよね？ ...
少なくとも僕はなりました。それで5単位(ペントミノ)の全組合せ66通りと6単位(ヘキソミノ)の全組合せ595通りを手作業で解析したりしていたのですが*1、そんなことをするくらいならプログラムを書けばいいじゃないかということで探索プログラムを書き始めました。

詰め探索プログラム

作成したプログラムは、局面を入力すると、先手後手ともに最善手をとった場合にどちらが勝つか、何手で勝つかを出力するというものです。
言語は当時勉強しようとしていたHaskellで書きました。
え？Haskell？と不安になった方も、この記事ではコードは出てこないので安心してください。

コードはGitHubに置いてあります。あまり分かりやすいコードにはなっていませんが、Haskellが読めて実装を見たいという方はどうぞ。

GitHub - rkat0/Godomachi: A checkmate search program of Godomachi.

ここでは使用したアルゴリズムについてざっくりと説明したいと思います。
細かいことはいろいろあるのですが、

ポリオミノの列挙*2
あるポリオミノの切り方の列挙
詰め探索

あたりが主要なアルゴリズムだと思うのでこの辺をまとめたいと考えています。

ポリオミノの列挙

このゲームでは合同かどうかだけが重要なので、ここでやりたいことは、回転・反転した関係のものを同一視する、両面ポリオミノと呼ばれるものの列挙です。

回転や反転を同一視しない、向きを考慮したポリオミノの列挙はRedelmeierのアルゴリズムという効率の良さそうなアルゴリズムがありますが、両面ポリオミノの列挙は特に効率の良いものはないようです。
いろいろ調べていたらこんなものを見つけました。

Free polyominoes enumeration - Rosetta Code

いろんな言語でコードが載っています。
アルゴリズムはこのようなものです:

モノミノを用意する。
今、( $k$ -1)-オミノが列挙できているとする。それぞれに対し、どこかに1個ブロックを追加したものを列挙することで $k$ -オミノを作る。
回転、反転の変換によって同じとなるものは1つを残して除去する。
2,3を繰り返し、 $n$ -オミノになったら終了。

何も難しいことはしていなくて、1マスのモノミノから始めて1つずつ大きいポリオミノを作っていくという方法です。
細かい部分で効率化できそうな気もしますが、とりあえず先へ進みます。

ポリオミノの切り方の列挙

この記事のメインです。
ある局面から次の手を生成するとき、お互いのポリオミノに対して2つの連結部分に切り分ける方法を列挙し、その中から合同な破片を持つ組を探すという方法をとりました。ここで、ポリオミノの切り方を列挙することが必要になります。

アルゴリズムその1

まず、ポリオミノのブロックの隣接関係をグラフで表現します。
具体的には、ポリオミノの各ブロックを頂点とし、隣接しているブロックを枝で結んだグラフを作ります。

f:id:rkevindem:20180506034459p:plain:w400

　
切り方の特別な場合として、ポリオミノ $P$ から1マス $p$ を切り取る場合を考えてみます。
$p$ を切り取ることは、グラフ $G$ では対応する頂点 $v$ を取り除くことに対応します。このとき、残りのグラフ(＝残りの図形)は連結でないといけないので、 $p$ を取り除けるのは $v$ がグラフの結節点*3でないときだといえます。 (ちなみに、結節点の列挙は線形時間のアルゴリズムが存在します。）

f:id:rkevindem:20180506140549p:plain:w400

　
では次に、1マスの切り方を元に2マスの切り方を考えてみます。
1マス切り取れる各ブロックに対し、隣接するブロックを1つくっつけたものを列挙します。ここから重複を除けば2マスの候補が列挙ができます。これが切り取れる条件は、くっつけた方のブロックが、1マス切り取った後のグラフで結節点になっていないことです。

f:id:rkevindem:20180506142031p:plain:w400

f:id:rkevindem:20180506141756p:plain:w400

　
同じようにしてどんどん大きな切り方をつくることができます。ポリオミノを2つに分けるとき、必ず片方は元の半分以下のサイズになることから、切り取る図形は元の半分の大きさまで調べればOKです。

そして最後に、同等な切り方(同じ形に分ける切り方)を除去します。*4

これで終わり、だと楽だったんですが、さすがにそんなことはなかったです。

アルゴリズムその2

2マス取る方法はないけど3マス取ることはできる、みたいなものがあります。

f:id:rkevindem:20180506034955p:plain:w200

なぜこのようなことが起こるかというと3つ以上の連結成分を繋ぐような結節点があるからです。このような結節点は1方向から攻めている限りは切り取ることができません。

そこで、3つ以上の連結成分を繋ぐ結節点それぞれに対し、それを切り取るために必要な最小の塊*5を計算します。
その中で大きさが元( $n$ -オミノとします。)の半分以下のもの、例えば大きさ $k$ ( $\leq n\ /\ 2$ )のものが見つかったとしたら、上の方法で $k$ マス取る方法を列挙した後にリストに付け加えてやります。

結節点を切り取るために必要な最小の塊はどう計算するのかですが、
注目する結節点からつながっている各方向に向けて探索を行い、いくつのブロックがあるかを数えます。別の方向から出発したものが途中で合流したらまとめて1つとします。その中で一番大きいものを残した全てが最小の塊です。

f:id:rkevindem:20180506153903p:plain:w400

さて、これで今度こそアルゴリズム完成

...だと結構長い間信じてました。
これでも上手くいかないケースがありました。

アルゴリズムその3

この形。8単位、オクトミノで初めて現れる形です。

f:id:rkevindem:20180506024232p:plain:w200

これを4マスのLテトロミノ2つに分解してくれないのです。
原因は、プログラムの気持ちになって考えてみると分かります。

まず、結節点となるのは中央の4マスです。各結節点を取るための最小の塊である2マスの取り方は見つけられるのですが、そこから伸ばせる先は全て残りのグラフで結節点なので、そこで終了してしまいます。

f:id:rkevindem:20180509002547p:plain:w200

どうすればいいか考えた結果、最初のグラフに対して結節点を取り除くための最小の塊を計算していたところを、切り取った残りのグラフから結節点を取ろうとしたときに計算することにしました。ここでは「3つ以上に分かれる〜」という条件はつけません。

f:id:rkevindem:20180509003042p:plain:w200

少し無駄がある方法のような気もしますが、それがどの程度なのかは正直よく分からないです。
おそらくこれで間違いは無いと思いますが、証明はしてないのでもしかしたら上手くいかない場合があるかもしれません。今のところは上手くいっています。

最終的なアルゴリズム:

ポリオミノ $P$ の各ブロックを頂点とし、隣り合っているブロックを枝で表現したグラフ $G$ を作る。
$G$ の結節点でない頂点を列挙し、1マスの切り方を列挙。
$k-1$ マスを切り取る方法が列挙できているとき、 $k−1$ 個のブロックのどこかに接していて、残りのグラフ $G^\prime$ で結節点になっていないものを列挙してくっつけることでkマスの切り取り方を列挙。
3.で結節点を見つけた場合、 $G^\prime$ からその結節点を切り取るための最小の塊を計算し、 $k−1$ マスと足して全体の半分以下なら、そのマス数の切り方候補として覚えておく。
3.4.を繰り返して $P$ の半分の大きさまで切り方を探す。
同等な切り方を除去する。

アルゴリズムその4？

...今また別のアルゴリズムを思いつきました。検証ができたらまとめたいと思います。

詰め探索

いよいよ最後です。
コンピュータ将棋の(実戦の)詰め探索では証明数、反証数を用いた方法が使われたりするのですが、これで最短手数の詰みが見つかるのかなどよく分かっていない部分があるのでmini-max法で探索します。今まで以上にざっくりな説明になりますが、ゲーム木の探索についての解説はいろいろなところにあるので、必要ならそのようなものを参照していただければと思います。

mini-max法

mini-max法は、各局面に対して評価値が計算できるときに次の手を決めるアルゴリズムです。先手と後手の有利不利が対称的であることを利用し、先手は評価値が最大となる手を、後手は評価値が最小となる手を選んでいきます。つまり、お互いが最善の手を選ぶということですね。

ゴドマチは先後で取れる手が同じで、同じ最終局面を目指すので、詰み筋が奇数手で終わるなら先手勝ち、偶数手なら後手勝ち*6となります。そこで、評価値は、

短い奇数手詰み局面 > 長い奇数手詰み > 長い偶数手詰み > 短い偶数手詰み

となるようにします。
具体的な評価値の計算方法ですが、まず、 $n$ 単位マッチの場合は決着までの手数が必ず $n$ 手未満になります。これを利用し、 $k$ 手で詰んだ場合の評価値は、 $k$ が奇数なら $n-k$ 、 $k$ が偶数なら $k-n$ と計算しました。

ある局面の評価値は、先手の場合は次に移れる局面の中で最大の評価値、後手の場合は最小の評価値とし、最終局面に対してはそこまでの手数に対して上の計算式で点数をつけます。これであとは正しい実装をすれば詰め探索ができます。

よくあるmini-maxのイメージ:

$\alpha\beta$ 法*7

詰め探索は可能になりましたが、mini-maxだけでは全探索してしまうので、枝刈りをして高速化を図ります。

例えば、先手が5手詰めを見つけている場合、他の3手目を探索するときに、その時点で詰まなければその先は調べる必要はありません。4手目以降で負けるか、良くても5手詰めで、今より評価値が上がることはないからです。さらに、3手詰めを見つけた場合は、その3手目の探索を続ける必要はなくなります。後手に対しても全く同じことがいえるため、先後に関係なく、ある深さ $d$ の探索をする中で $d+2$ 手の詰みを見つけたら、それ以降は $d$ 手目で詰むかどうかを見ればよく、 $d$ 手詰めを見つけたらその深さ $d$ の探索は終了してしまってOKです。(他の手順での深さ $d$ の探索は打ち切れません。)

枝刈りのイメージ:
四角は先手番、丸は後手番を表し、数字はその局面から最善手をとったときの全体の詰み手数です。評価値ではないので注意してください。

さらに細かい点ですが、手を探すときに大きく切る方法から試していくと短い手数の詰みが初期に見つかりやすくなり、枝刈りがより効率的に働くと思われます。

まとめ

最初に示した3つのアルゴリズムについてざっくりとですが説明しました。
ポリオミノの切り方の列挙は他にもいろいろなやり方があると思います。
これを書きながら新しいアルゴリズムを思いついたりしたので、そちらも実装して検証ができたらまとめてみようと思います。
　

*1:完成したプログラムによって6単位の手解析に6個のミスが指摘されました。

*2:これは詰め探索には関係ありません。n単位マッチを全解析するときに使用しました。

*3:取り除くとグラフが連結ではなくなってしまう頂点。alias: 関節点、切断点

*4:途中の段階では切る位置が異なるものを区別する必要があります。

*5:最小の塊以外は必ず元の半分より大きくなることが証明できます。

*6:0手、つまり最初から合同の場合は後手勝ちとするルール「ゴドマチック天和」が提案されています。

*7:と呼んで良いのか分かりませんが、少なくとも同じような考え方です。

RK’s blog

ゴドマチの詰め探索アルゴリズム