はじめに

皆さん、こんにちは。
ゴブレットというボードゲームを御存じですか？
以下のQiita上のゴブレットに関する記事を見て興味を持ったので、ゴブレットというボードゲームを題材にしてみました。
ゴブレットゴブラーズは先手必勝？完全解析してみた【Python】
ゴブレットゴブラーズの必勝法解析を C++ でやってみた

ゴブレットのゲームAIを作るうえで重要になるであろう局面遷移に関して調べます。

使用した環境は以下の通りです。
Windows 11 Home
Visual Studio Community 2022 version 17.3.3 Visual C++
Visual Studio付属のCMake（参考）
boost 1.80.0
google test 1.12.1
Python 3.9.13
matplotlib 3.6.0

基本C++で書いていますが、グラフのプロットと統計情報を調べるところだけPythonで行っています。

ソースコード

使ったソースコードは以下のGitHubのURLに置いてあります。
多重ループを再帰で書いており、関数の引数にメモ化のための変数を含めているために、見にくくなってしまっていると思いますがコメントを出来るだけ細かく書いたので許して頂きたいです。

ゴブレットとは

3目並べを少し複雑にしたゲームです。
3目並べとは、駒に大きさの違いが存在して大きい駒を小さい駒に被せることができる点で異なります。
細かいルールは以下のリンクで読んでいただけたらと思います。
https://docs.racket-lang.org/games/gobblet.html

なお、盤面が4×4の場合は3×3の場合よりもルールが増えているようですが、今回は新たに増えているルールは考えないで計算しています。

本題に入る前に、用語の導入

説明を分かりやすくするために、用語に関して少し決めておこうと思います。

盤上にある駒の配置を局面と呼び、その数を 局面数 と呼びます。
上に被さっている駒が存在しない駒のことを 1番上にある駒 と呼びます。
上に被さっている駒が存在する駒のことを 下にある駒 と呼びます。
駒の大きさの種類のことを単に 駒の種類 と呼びます。
先手と後手の盤上にあるそれぞれの種類の駒の個数の組を 盤上にある駒の個数の組 と呼びます。
(例えば、4x4のゴブレットで、盤上に先手の駒が特大2個、大1個、中1個、小1個あり、後手の駒が特大3個、大2個、中1個、小0個あるとき、駒の個数の 組(2, 1, 1, 1, 3, 2, 1, 0) を 盤上にある駒の個数の組 と呼びます。)
局面Aから先手と後手が何回か交互に指して移ることができる局面を 局面Aから到達可能な局面 と呼びます。
(後述の仮定1より、局面Aから先手と後手のどちらが先に指すかは気にしなくてよいです。)

この記事における目標

ゴブレットの盤のサイズ、駒の種類数、各種類の駒の個数を変えて、
探索アルゴリズムの設計に関係する、ある局面から到達可能な局面数に関する事柄
を調べます。

目標を達成するための仮定

局面遷移を厳密に調べるのは難しいため、以下の2つの仮定のもとで局面遷移に関わる事柄を調べました。

仮定1
「局面Aから別の局面Bに到達可能である」 $\iff$
「駒の大きさの種類数を$m$とし、局面Aの盤上にある駒の個数を、駒の大きさが大きい順にそれぞれ$a_1, a_2, ... , a_m$、局面Bの盤上にある駒の個数を、駒の大きさが大きい順に$b_1, b_2, ... , b_m$とすると、任意の$1 \leq i \leq m$に対して、$a_i \leq b_i$が成り立つ。」

大雑把に言うと、ある局面から、盤上の各種類の駒の個数が同じor増える局面には到達可能であり、少なくとも1種類の盤上にある駒の個数が減る局面には到達することが不可能であるということです。

仮定2
「初期局面から到達可能である」 $\iff$
「先手、後手ともに、縦横斜めどの列も揃っていない、かつ
(盤上にある先手の駒の個数の和, 盤上にある後手の駒の個数の和)は(0, (1以上の整数))でも((2以上の整数), 0)でもない」

(盤上にある先手の駒の個数の和, 盤上にある後手の駒の個数の和)は(0, (1以上の整数))でも((2以上の整数), 0)でもない
という条件は先手後手ともに、最初の一手は必ず新しい駒を盤面上に置くということを表しており、そうでない局面を除外するためにあります。

今回行うこと

以下のことを行います。

総局面数：1列も揃っていない局面の総数を計算する。
条件付き可能局面数:盤上にある駒の個数の組を指定した時の、局面数を計算する。
条件付き到達可能局面数:盤上にある駒の個数の組を指定した時、その条件を満たすような局面から、到達可能な局面数を計算する。
条件付き到達可能局面数の割合:盤上にある駒の個数の組を指定し、その条件を満たすような局面に対して、その局面から到達可能な局面数/総局面数を計算する。
1.~4.で求めたものを使ってグラフをプロットし、考察をする。

1.が少しややこしいですが、2.~4.は全然難しくありません。

1. 総局面数の計算

方針

プレイヤーが交互に指して探索をすると、局面数が多すぎるためものすごく時間がかかってしまいます。
(ゴブレットゴブラーズの必勝法解析を C++ でやってみたという記事の1423法と同じ方法で大雑把にどれぐらい局面数があるかを計算できます。4×4では局面数は $10^{20}$ 以上です。)
なので、1列も揃っていない局面数を、それぞれのマスに対して駒の置き方を調べることによって求めることを考えます。
しかし、この方針でも単純に探索すると物凄く時間がかかってしまうので、もう少し工夫をします。

アルゴリズム詳細では、どのように1列も揃っていない局面数を数えたのかをより詳しく解説します。
興味がある方は読んでみてください。

アルゴリズム詳細

以下のようなアルゴリズムを使いました。コードでは、

ans = 0
(Step1の全探索){
    (Step2の全探索){
        tmp = 1
        (Step3の全探索){
            tmp = tmp * (Step3の計算結果)
        }
        (Step4の全探索){
            ans = ans + tmp × (Step4の計算結果)
        }
    }
}

のようになっています。(Step5はansに掛け算の答えを足しているところ。「さらに一工夫」から先の内容は入っていません。)

Step1

それぞれのマスに対して、マスに駒が置いてあるか、もし駒が置いてあれば1番上にある駒が先手の駒なのか後手の駒なのかを全探索します。
このとき、1列以上揃うようなものは除外して全探索します。

Step2

1番上に置いてある先手の駒のうち、それぞれの大きさの駒が何個あるのかを全探索し、後手の駒に対しても同様に全探索します。

Step3

この条件を満たす、1番上にある駒の配置が何通りあるのかを計算します。
また、この組み合わせは先手と後手で独立に考えることができます。
今からその計算方法を先手について考えますが、後手についても同様にします。

次の問題における組み合わせの総数を考えてみてください。

$n$個マスがあり、駒が$m$種類あります。
駒の種類に番号を$1, 2, ..., m$と割り当て、番号iの種類の駒は$a_i$個あるとします。
ただし、$a_1+a_2+...+a_m=n$とします。
マスに1個ずつ駒を置く置き方は何通りありますか？

このような場合の数は
$nCa_1×(n-a_1)Ca_2×...×(n-a_1-a_2-...-a_{m-1})Ca_m$
と計算できます。($nCm$は$n$個から$m$個を取り出す組み合わせです)
$n$を１番上にある先手の駒の数、$a_1,a_2,...,a_m$をそれぞれの種類の先手の駒の数とすれば、先手に関して求めたい組み合わせを求めることができました。

Step4

次に、下にある駒の置き方の場合の数を計算します。
駒の置き方の場合の数は、ゴブレット後退解析の記事の1423法のようにして駒の大きさごとに独立に計算することができます。
この場合の数を計算するために、それぞれの駒の大きさに対して、下の駒の個数を全探索し、それぞれの計算結果の積をとります。
下にある先手の駒は、大きさごとに、0個以上min((それぞれの種類の駒の個数)-(1番上に置いてあるその大きさの先手の駒の個数), (その大きさよりも大きい1番上に置いてある駒の個数) )個置くことができます。
後手も同様です

Step5

Step3で1番上にある駒の配置の場合の数を、Step4で下にある駒の配置の場合の数を、盤上で1番上にある駒の個数の組ごとに求めることができました。
あとは、盤上で1番上にある駒の個数の組ごとに、(駒の配置の場合の数)×(下にある駒の配置の場合の数)を計算し、その計算結果をすべて足せば、1列も揃っていない局面数を計算することができます。

さらに一工夫

こうして、それぞれのマスに対して駒の置き方を調べることで、1列も揃っていない局面数を計算できました。
ここから私はさらにもう一工夫しました。
注目することは、Step1で全探索して、1番上にある先手の駒の個数と後手の駒の個数が同じであれば、Step2以降の計算結果も同じだということです。
この事実によって、メモ化をして計算量を落とすことができます。

計算量

最後に計算量を大きく見積もります。
盤のマス目の個数を$N$個、駒の種類数を$T$種類、先後それぞれ駒が種類ごとに$C$個あるとします。
Step1の計算量は$O(3^N)$、Step2の計算量は$O((C+1)^{2T})$、Step3の計算量は$O(T)$、Step4の計算量は$O(T×(C+1))$、Step5の計算量は$O(1)$です。
メモ化も考慮すると、最終的に、このアルゴリズムによる計算量は$O(3^N+(C+1)^{2T}×(T+T×(C+1)))=O(3^N+T×(C+1)^{2T}×(C+2))$です。
$3^N$の部分は不適切な局面を枝刈りするのでもっと計算量が落ちます。
$N=16$, $T=4$, $C=3$であれば、$3^N+T×(C+1)^{2T}×(C+2) \fallingdotseq 4×10^7$です。
このことから、4×4のゴブレットであれば余裕で求められそうなことが分かります。

注意

このアルゴリズムでは、プレイヤーが交互に指していたら絶対にありえない、先手の駒が0個で後手の駒が1個以上や、先手の駒が2個以上で後手の駒が0個という場合を含んでいます。
2.では、これらの局面数を0にしています。

結果

総局面数は、
3x3のゴブレットで1484719012、4×4のゴブレットで4052027033345402485449でした。

2. 条件付き可能局面数の計算

次に、条件付き可能局面数の計算を行います。つまり、盤上にある駒の個数の組を指定した時の、局面数を計算し、これを盤上の駒の個数の組全通りに対して行います。
1.のStep4で下の駒の組み合わせを駒の大きさごとに独立に計算していたところを、大きさごとに下の駒の個数を探索すれば、指定された盤上の駒の組に対する局面の数が分かります。
このためには、盤上の駒の組ごとに計算結果を記録する必要があり、この記録にはC++のmapを使いました。

また、仮定2より明らかに初期局面から到達できない盤上の駒の個数の組の局面数を0にしています。

計算量

1.「アルゴリズム詳細」の、計算量の項目を読んだ方向けです。

「アルゴリズム詳細」と同様に、盤のマス目の個数を$N$個、駒の種類数を$T$種類、先後それぞれ駒が種類ごとに$C$個あるとします。
1.のアルゴリズムから変えたところを見て、計算量を求めます。

C++のmapのkeyに長さ$2T$のstd::arrayを入れていて比較演算子の計算量が$O(2T)$、mapの要素数は$(C+1)^{2T}$なので、mapへのアクセスの計算量が
$O(T log_2 (C+1)^{2T})=O(T^2 log_2 (C+1))$
です。
また、Step3の計算量が $O((C+1)^{2T})$に変わるので、このアルゴリズムの計算量は
$O((3^N+(C+1)^{2T}×(T+(C+1)^{2T}))×T^2 log_2 (C+1)) \fallingdotseq O((3^N+(C+1)^{4T})×T^2 log_2 (C+1))$
になります。

1番上の駒の個数の組が同じであれば、Step4の結果は同じです。
ここの部分をさらにメモ化すれば、新たにメモ化に使用するmapの計算量が$O(T log_2 (C+1)^T) = O(T^2 log_2 (C+1))$であるから、
$O((3^N+(C+1)^{2T}+T+(C+1)^{2T})×T^2 log_2 (C+1)) \fallingdotseq O((3^N+(C+1)^{2T})×T^2 log_2 (C+1))$
に計算量を落とすこともできるとは思います。
私の実装ではこのメモ化はしていません。

3. 条件付き到達可能局面数の計算

ここでは、盤上にある駒の個数の組を指定した時、その条件を満たすような局面から、到達可能な局面数（条件付き到達可能局面数）を盤上の駒の個数の組全通りに対して計算します。

今回求める到達可能局面数は、それぞれの大きさの駒の数が変わらないor増える局面には必ず到達することができると仮定した場合の到達可能局面数なので、到達可能局面数を求めるために2.の結果に対して多次元累積和をとればよいです。
多次元累積和はゼータ変換・メビウス変換を理解するの記事を参考にしました。

4. 条件付き到達可能局面数の割合の計算

3.の結果を総局面数で割るだけです。

5. 1.~4.で求めたものを使ってグラフをプロットし、考察をする。

到達可能な局面数に関して

到達可能な局面数/総局面数の統計は以下の通りです。

	3x3	4x4
count	1484719012	4052027033345402485449
mean	0.22499	0.17679
std	0.086693	0.058698
min	0.11871	0.10223
max	1.0	1.0

4.の結果を使って、横軸が到達可能な局面数/総局面数、縦軸が、到達可能な局面数/総局面数が横軸の値と一致する局面数のグラフをプロットしました。

3x3, 4×4のゴブレットの場合は下のグラフのようになりました。

縦軸方向を対数目盛にすると下のようになりました。

初期局面は到達可能局面数/総局面数が1であり、駒を新たに置くにつれて徐々に到達可能局面数/総局面数が小さくなります。
盤上の駒の個数が少ない局面数よりも、盤上の駒の個数が多い局面数の方が遥かに多く、このようなグラフになっていると予想できます。
4x4の方がその傾向が顕著です。
一方で、駒の個数が少ない局面数もある程度は存在することが片対数グラフから分かると思います。

盤上の駒の個数の組ごとに、(到達可能な局面数, 局面数)を座標とみなして散布図を書くと、下のグラフのようになりました。

縦軸を対数目盛にすると、下のグラフのようになります。

点の大きさが大きく見えているものは複数の点が固まっているところです。
3x3の方が4x4よりも盤上にある駒の個数の組が少ないので、3x3の方が点の個数が少ないです。

双方向に到達可能な局面数に関して

仮定1より、ある局面から双方向に到達可能な局面数は、盤上にある駒の個数の組が同じ局面の数です。
これは2.から簡単に求めることができます。

双方向に到達可能な局面数/総局面数の統計情報は以下のようになります。

	3x3	4x4
count	1484719012	4052027033345402485449
mean	0.031675	0.019548
std	0.035922	0.029905
min	6.7353e-10	2.4679e-22
max	0.11871	0.10223

横軸が、双方向に到達可能な局面数/総局面数、縦軸が、双方向に到達可能な局面数/総局面数が横軸の値と一致する局面数のグラフをプロットすると以下のようになります。

双方向に到達可能な局面数は、総局面数に比べて非常に少ないことが分かります。

縦軸を対数目盛に変えても大差がなかったので、片対数グラフは省略します。

戻ってこれないが到達可能な局面数に関して

仮定1より、ある局面から到達可能だが戻ってこれない局面数は、(到達可能な局面数)-(盤上にある駒の個数の組が同じ局面数)です。
これは2.、3.から簡単に求めることができます。

戻ってこれないが到達可能な局面数/総局面数の統計情報は以下のようになります。

	3x3	4x4
count	1484719012	4052027033345402485449
mean	0.19332	0.15725
std	0.11464	0.080776
min	-2.7756e-17	0.0
max	1.0000	1.0

3x3のときにminが負になっているのは誤差です。誤差がなければ0になるはずです。

横軸が、戻ってこれないが到達可能な局面数/総局面数、縦軸が、戻ってこれないが到達可能な局面数/総局面数が横軸の値と一致する局面数のグラフをプロットすると、以下のようになります。

縦軸を対数目盛に変えると以下のようになりました。

感想

4x4の場合は局面数が少なく見積もっても$10^{20}$であり、局面の遷移の様子を調べるのは難しいと思っていたのですが、条件を緩くしたら、工夫をすることによって様子を大まかに調べることができたことに驚きました。
もっと計算量を落とすことやほかの事柄を調べることも可能かもしれませんが、今回はこれで終わりにしたいと思います。
読んでいただき、ありがとうございました。

参考文献

https://docs.racket-lang.org/games/gobblet.html
https://qiita.com/yasagureprog/items/94c0cb01005b2b94b837
https://qiita.com/m-kasahr/items/e9bdda783a4c0e820e20
https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5

(この記事は研究室インターンで取り組みました：https://kojima-r.github.io/kojima/)