はじめに
ゴブレットゴブラーズ (Gobblet Gobblers, 別名 Gobblet! Jr.) というボードゲームをご存知でしょうか。2 人プレイで 3 x 3 マスの盤上に、自分の駒が一列揃えたら勝ち。「○×ゲーム」(あるいは「三目並べ」) によく似ていますが、もっとずっと奥が深いです。
もし両プレイヤーが完璧に指したら、先手と後手どちらが勝つのでしょうか? 気になって、後退解析で全局面をくまなく調べるプログラム を C++ で組んでみました...といっても、既に別の方による Python での解析結果が挙がってますけど (先越されました 笑)。めげずに本記事では、C++ 版の解析プログラムの紹介を兼ねつつ、ゴブレットゴブラーズに限らず後退解析のプログラムを作成する際にヒントとなりそうな技術的トピックをまとめてみました。
あらためて、ゴブレットゴブラーズとは
海外製品には説明書が簡素すぎてルールが曖昧なものもあるようですが、ココのページの記述にしたがって実装しました。特に注意すべきは、次の点でしょうか。
- (駒を動かそうと) 自分の駒を持ち上げた瞬間に相手の駒が一列揃ったら、相手がただちに勝利する。
- パスはできない。駒を今いたマスへ移動させること (動かしたフリ) もできない。
後退解析とは
完全解析を行うために、今回は後退解析 (retrograde analysis) という手法を用いました。ゲームの最終局面から解析を始め、一手ずつ戻りながら探索するという解析方法です。
ゴブレットゴブラーズは局面を一見しただけでどちらが勝ったかすぐ分かりますので、終了局面を探し出して「この局面は先手 (または後手) の勝ち」と印を付けるのは容易です。後はひたすらそこから逆に辿っていけば良いので、有効な解析方法といえます。
後退解析について詳しくは、田中哲朗氏による論文『「どうぶつしょうぎ」の完全解析』や前述の Python による完全解析の記事を参照して下さい。
局面をどう ID 化するか
完全解析では「先手必勝」「後手必勝」「未確定」etc. といった、各局面に対する解析結果を記録する管理表が要ります。というか、この表に書き込むことが解析処理といってもいいでしょう。そうなると、ゴブレットゴブラーズの各局面を ID、つまり一意な整数値か何かで表現して、次のように管理表へ記入しようという考えに、おそらく誰でも至ると思います。
| 局面 ID | 解析結果 | 終局までの手数 |
|---|---|---|
| 0 | 先手必勝 | 12 |
| 1 | 未確定 | - |
| 2 | 後手必勝 | 13 |
| 3 | 後手必勝 | 13 |
| ・・・ | ・・・ | ・・・ |
ただどうやって、ID で表現できるでしょうか。
ゴブレットゴブラーズの盤上の各マスには、大・中・小の駒を1個ずつ乗せることができます。大・中・小それぞれで {オレンジの駒が乗っている、青の駒が乗っている、駒は乗ってない} の 3 通りの状態があるので、3³ = 27 通りの乗せ方があります。盤は 9 マスですから合計で 27⁹ = 7兆6255億 9748万4987 通り。さらに、盤上の状態が同一でもどちらのプレイヤーの手番なのかで局面としては異なりますから、倍の 15兆2511億9496万9974 までの整数値を ID として採用すれば、全局面を表せます。...が、これだとかなり無駄が多いです。
色もサイズも同じ駒は 2 つずつしかありませんが、この方法では全マスに同じ駒を置いた局面も表現できてしまいます。実際のところ、15兆個のエントリという広大な管理表のかなりの部分は、ゲームのルールから逸脱しているため使わない領域で占められます。
ID の有効値 (上述のやり方では 0 ～ 27⁹-1) の範囲が広くなればそれだけ解析時間もかかりますし、メモリも消費します。なので、不使用な ID は無いに越したことはありません。そこで次に紹介するのは、勝手に名付けましたが「1423 法」という、もっと効率の良い ID 化の方法です。
1423 法
気づきにくいかも知れませんが、小サイズの駒 4 つ (オレンジ、青 2 個ずつ) のゲーム中における置き場所の組み合わせが何通りあるかは、中や大サイズの駒の配置には、影響されません。同様に、中サイズの駒 4 つの置き場所の組み合わせ数も、大サイズの駒の配置には影響を受けません。
「いや、大の駒があるマスに置かれていたらそこに小や中の駒は置けないんだから、大の駒の配置場所によって、小や中の配置場所の組み合わせ数は増えたり減ったり影響されるだろう」と考えてしまいそうですが、小の駒の後で中や大の駒を置けば局面自体は出現しうるのです。駒のサイズによらず、小・中・大のそれぞれ駒 4 つの配置の組み合わせ数は、同じになります。具体的には、次の表の値を合計した 1423 通りです。
| 盤上の駒の数 | 組み合わせ数 (式) | 組み合わせ数 (値) |
|---|---|---|
| オレンジ0, 青0 | ₉C₀ | 1 |
| オレンジ0, 青1 | ₉C₀ ₉C₁ | 9 |
| オレンジ0, 青2 | ₉C₀ ₉C₂ | 36 |
| オレンジ1, 青0 | ₉C₁ ₈C₀ | 9 |
| オレンジ1, 青1 | ₉C₁ ₈C₁ | 72 |
| オレンジ1, 青2 | ₉C₁ ₈C₂ | 252 |
| オレンジ2, 青0 | ₉C₂ ₇C₀ | 36 |
| オレンジ2, 青1 | ₉C₂ ₇C₁ | 252 |
| オレンジ2, 青2 | ₉C₂ ₇C₂ | 756 |
小・中・大それぞれ 1423 通りなので、全体では 1423³ = 28億8147万3967 通りとなります。さらに盤上の駒の配置がまったく同じでも、そのときの手番が先手と後手どちらのプレイヤーかによって局面は別々なので、局面数の合計では倍の 57億6294万7934 通になり、局面 ID は 0 ～ 57億6294万7933 の範囲になります。
先ほどの 15 兆に比べれば圧倒的に減りました。ただ、工夫してもっと減らせないか考えてみましょう。
さらなるダイエット 1 - プレイヤーを入れ替えた局面
ある局面からプレイヤー同士の駒をすべて入れ替え、「現在どちらが手番なのか」の情報も入れ替えた局面というのは、元の局面と本質的に同じです。そこで 2 つの局面を 1 つに集約することにしました。局面の数が半分になるので、やらない手はないです。これで局面数は 1423³ = 28億8147万3967 通りになります。局面 ID は 0 ～ 28億8147万3966 の範囲です。
ただしこの工夫を取り入れると、局面の管理表には「先手必勝」「後手必勝」と記すのではなく、「いまこの手番のプレイヤーの必勝」「手番でないほうのプレイヤーの必勝」と書くことになります。これが少し厄介で、プログラミングしていてよく混乱しました。先手・後手はゲームを通じて不変なのに対して、「いま手番かのプレイヤー」は一手毎に入れ替わるのですから。
さらなるダイエット 2 - 対称形の扱い
以下のように、ある局面を反転や回転させたものは元の局面と実質的に同じなので 、ID が一番小さくなるものだけを解析対象としました。後退解析の準備処理で、当該局面には管理表に「対称形」とだけ記し、後は一切の解析をしません。局面 ID の数を純粋に減らす工夫ではありませんが、解析の処理を減らすのに有効です。
| # | 対称形 | 備考 |
|---|---|---|
| 1 | 時計回り 90° 回転 | |
| 2 | 時計回り 180° 回転 | |
| 3 | 時計回り 270° 回転 | |
| 4 | 左右反転 | |
| 5 | 左右反転 + 時計回り 90° 回転 | = 右上-左下の対角線反転 |
| 6 | 左右反転 + 時計回り 180° 回転 | = 上下反転 |
| 7 | 左右反転 + 時計回り 270° 回転 | = 左上-右下の対角線反転 |
さらなるダイエット 3 - 局面 ID の後ろのほう
局面 ID (0 ～ 28億8147万3966) の後半部分の局面にはすべて、より小さな ID が割り当てられた対称局面が存在します。そこで、これら「後ろのほうの ID 」はすべて管理表の記録対象から除外して、表自体のサイズを切り詰めることにしました。これにより、解析対象の局面数はさらに 45% ほど減り、15億7337万1256 通りになります。
さらなるダイエット 4 - 起こり得ない局面の洗い出し
以下の局面は実際のゲームでは起こり得ないので、「矛盾している」と印を付けて解析対象から外しました。1423 法の ID 体系はかなりスリムですが、それでもムダな局面は混じっているのです。
- 手番の開始時時点で、既に手番プレイヤーの駒が一列に揃っている局面
- 手番の開始時時点で、既に手番プレイヤーの駒だけが盤上に置かれている局面
- 手番の開始時時点で、既に相手プレイヤーの駒だけが複数個 盤上に置かれている局面
ダイエットの取り組みは、以上です。
ステイルメイトの扱い
最後に細かな話題を取り上げます。前述したようにゴブレットゴブラーズでは、自分の駒を持ち上げた瞬間に相手の駒が一列揃ってしまうと負けになります。この「持ち上げた瞬間に負け」の手しか指せない状態を、チェスから借用して「ステイルメイト (stalemate)」と本記事では呼ぶことにします。
ゴブレットゴブラーズにも、ステイルメイトは存在します。双方のプレイヤーが示し合わせて誘導しない限り起こることはないと思いますが、ルールに反することなくステイルメイトの局面まで進行させることは可能です。
完全解析ではプレイヤー同士は完璧にプレイするのが前提ですから、うっかりした負けはありません。そのため「持ち上げた瞬間に負け」になる手は、手番プレイヤーの指すことができる手から除外して解析しても通常は問題ないのですが、ステイルメイトの局面だけは考慮が要ります。そうしないと、解析結果が「この局面はどちらのプレイヤーが勝つかどうか未確定だが、指せる手は一つもない」という状態になってしまいます。
おわりに
以上、完全解析を行うプログラムを作成中に気づいた点をまとめてみました。「で、結局お前のプログラムでは、ゴブレットゴブラーズは先手と後手どっちが勝つと出たのかね?」と思われた方は、ぜひ一度ビルドして動かしてみて頂けると幸いです。