とあるダイソーのボドゲの実現可能局面数を見積もってみた（バーンサイドの補題）

お久しぶりです。今日は Tokyo Doves とはまた別のダイソーのボドゲについてお話しします。

今回のテーマ
ざっくり概観
単純にカウント
対称性を考える
対称性を加味して改めてカウント
- s=16 のケース
- s=15 のケース
対称性を加味してざっくりカウント
結果の吟味
追記 (2023/12/19)

今回のテーマ

今回取り扱うのは、こちらの記事でも紹介されている、「セカンドベスト」というボードゲームです。
bodoge-nya.hatenablog.com
何度か遊んでみていますが、シンプルながら先を読み通すのが難しい、非常によくできたゲームだなという感想を持っています。
楽しいゲームを見つけると、ついつい「完全解析したい・・・！」と思うのは自然な考えかなと思います。え？思わない？私は思います。
今回は解析に先立って、このゲームの可能局面数をおおよそ見積もってみることを考えてみます。

ざっくり概観

一定程度慣れた状態でルールに従ってゲームを進めていくと、概ね以下のような流れになります:

黒と白が交互に石を置いていく
それぞれの手持ちの8個の石をすべて置いた状態になる
石を動かしていく
ある瞬間に唐突にゲームが終了する

このゲームの進行上現れる各局面は、少なくとも次を満たすことが分かります。

(黒を先手番として) 黒石は白石と同数か、または1個多い
ボード上に置かれている石の数は0個以上16個以下
同じポジションに重なっている石の数は0個以上3個以下
同色の石は区別しない

この条件を満たすものをすべて数え上げれば、可能局面数の悪くない上界を与えるだろうと予想します。まずはこれを数えてみましょう。

単純にカウント

各ポジションに 1~8 と番号を付け、各ポジションに置かれる石の数を $a_{1}, a_{2}, ..., a_{8}$ とします。このとき

$a_{1}+a_{2}+\dots+a_{8} \leq 16$
$0 \leq a_{i} \leq 3$ $(i = 1, 2, \dots, 8)$

という条件を満たすことが分かります。この $a_{1}, a_{2}, \dots, a_{8}$ への値の割り振り方 (=石の色を区別しない配置の総数) は
$(1 + x + x^{2} + x^{3})^{8}$ の $x^{s}$ の係数 (ただし $s = a_{1} + a_{2} + \dots + a_{8}$ )
となります。この値を $c_{s}$ とします。
白石の個数は $\left\lfloor \dfrac{s}{2} \right\rfloor$ なので*1、各々の割り振り方に対する石の並べ方は
${}_{s}\mathrm{C}_{\lfloor s/2 \rfloor}$
となります*2。よって、求めたい総数は
$\displaystyle\sum_{s=0}^{16} c_{s} \cdot {}_{s}\mathrm{C}_{\lfloor s/2 \rfloor}$
で求まります。
各々の項を気合で計算すると、以下のような結果になります:

$s$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
$c_{s}$	1	8	36	120	322	728	1428	2472	3823	5328	6728	7728	8092	7728	6728	5328	3823
${}_{s}\mathrm{C}_{\lfloor s/2 \rfloor}$	1	1	2	3	6	10	20	35	70	126	252	462	924	1716	3432	6435	12870
$c_{s} \cdot {}_{s}\mathrm{C}_{\lfloor s/2 \rfloor}$	1	8	72	360	1932	7280	28560	86520	267610	671328	1695456	3570336	7477008	13261248	23090496	34285680	49202010

一番下の段の総和を求めると 133,645,905 となります。ハトのボドゲと比べると*3、この時点でもかなり少ないですね。

対称性を考える

さて、実際に解析を行う際は、ルール上区別されない全く同じ局面は同一視することを考えます。例えば以下のいずれかを満たすような局面のペアは同じものと考えてよさそうです。

ポジションをひとつずらして一致する局面のペア
ある対称軸に対してポジションを入れ替えると一致する局面のペア

このように対称性を課した際の個数を数えるときに便利なのが、以下のバーンサイドの補題です*4。
ja.wikipedia.org
主張だけ抜き出すと、以下の通りです。

群 $G$ が集合 $X$ に作用しているとする。各 $g \in G$ に対し、 $g$ で不変な $X$ の元全体の集合を $X^{g}$ とする。このとき以下が成り立つ:
$|X/G| = \dfrac{1}{|G|} \displaystyle \sum_{g \in G} |X^{g}|$

今回のケースに適用するなら、群 $G$ は「ポジションを1つ分となりに回転させる」と「ポジションをある対称軸について反転させる」で生成される変換の群になります。これはちょうど正8角形の二面体群と同型になります (したがって $|G|=16$ )。また $X$ はまさに前節で計算した場合全体に対応します。対称性を加味して省いた局面数は $|X/G|$ に対応するので、そのままこの補題が使えることが分かります。

対称性を加味して改めてカウント

群 $G$ の元は以下の6種類に分類されます:
(a) 単位元 (ポジションを変えないもの)：1個
(b) ポジションを180°回転させるもの：1個
(c) ポジションを90°回転させるもの (時計回り・反時計回り)：2個
(d) ポジションを45° または 135°回転させるもの (時計回り・反時計まわり)：4個
(e) ポジションを通らない対称軸で反転させるもの：4個
(f) 二つのポジションを通る対称軸で反転させるもの：4個
ここで、同じ分類に属す $g$ については $|X^{g}|$ は共通です(証明は省きます)。よって各分類に対して $|X^{g}|$ を数えればよさそうです。
以下では数が比較的多い $s=15, 16$ の場合について数えてみることにします*5。

s=16 のケース

白黒共に8個ずつボードに置かれている局面です。

(a) 単位元

$|X^g|=49202010$ (対称性を課さないケースで計算済み)

(b) ポジションを180°回転させるもの

この変換で対象な割り振り方は $a_{i}=a_{i+4}$ ( $i = 1, 2, 3, 4$ ) を満たすもので、この総数は
$(1 + x^{2} + x^{4} + x^{6})^{4}$ の $x^{16}$ の係数 $= 31$
となります。各割り振り方への白石の割り当て方は
${}_{8}\mathrm{C}_{4} = 70$ 通り
なので $|X^{g}| = 31 \times 70 = 2170$ となります。

(c) ポジションを90°回転させるもの (時計回り・反時計回り)

この変換で対象な割り振り方は $a_{i}=a_{i+2}=a_{i+4}=a_{i+6}$ ( $i = 1, 2$ ) を満たすもので、この総数は
$(1 + x^{4} + x^{8} + x^{12})^{2}$ の $x^{16}$ の係数 $= 3$
となります。各割り振り方への白石の割り当て方は
${}_{4}\mathrm{C}_{2} = 6$ 通り
なので $|X^{g}| = 3 \times 6 = 18$ となります。

(d) ポジションを45° または 135°回転させるもの (時計回り・反時計まわり)

この変換で対象な割り振り方は $a_{1}=a_{2}=\dots=a_{8}$ を満たすもので、これは1通りです。各割り振り方への白石の割り当て方は
${}_{2}\mathrm{C}_{1} = 2$ 通り
なので $|X^{g}| = 2$ となります。

(e) ポジションを通らない対称軸で反転させるもの

この変換で対象な割り振り方は (番号を適当に付け替えて) $a_{i}=a_{9-i}$ ( $i = 1, 2, 3, 4$ ) を満たすもので、この総数は
$(1 + x^{2} + x^{4} + x^{6})^{4}$ の $x^{16}$ の係数 $= 31$
となります。各割り振り方への白石の割り当て方は
${}_{8}\mathrm{C}_{4} = 70$ 通り
なので $|X^{g}| = 31 \times 70 = 2170$ となります。

(f) 二つのポジションを通る対称軸で反転させるもの

この変換で対象な割り振り方は (番号を適当に付け替えて) $a_{i}=a_{9-i}$ ( $i = 2, 3, 4$ ) を満たすもので、この総数は
$(1 + x + x^{2} + x^{3})^{2} (1 + x^{2} + x^{4} + x^{6})^{3}$ の $x^{16}$ の係数
となります。ここで $(1 + x + x^{2} + x^{3})^{2}$ は $a_{1}, a_{5}$ の割り振り、もう一方は残りの割り振りに対応します。
ただ、このケースは割り振り方によって白石の割り当て方に違いが出てきます。
対称軸の通るポジションに置かれる石の総数を $p$ , それ以外を $2q$ とすると、 $p + 2q = 16$ となります。これを用いると、白石の割り当て方は
$\displaystyle\sum_{k = 0}^{ 4 } {}_{q}\mathrm{C}_{k} \cdot {}_{p}\mathrm{C}_{8-2k}$ 通り
となります*6。各 $(p, q)$ の組み合わせに対応する値は以下の通りです。

$(p, q)$	$(0, 8)$	$(2, 7)$	$(4, 6)$	$(6, 5)$
$\displaystyle\sum_{k = 0}^{ 4 } {}_{q}\mathrm{C}_{k} \cdot {}_{p}\mathrm{C}_{8-2k}$	70	70	150	310

さて
$(1 + x + x^{2} + x^{3})^{2} = 1 + 3x^{2} + 3x^{4} + 1x^{6} +$ (その他の項)
となり、各項がそれぞれ $p = 0, 2, 4, 6$ に対応する割り振りを表していることを考えれば
$|X^{g}| = (1 \cdot 70 + 3 \cdot 70 x^{2} + 3 \cdot 150 x^{4} + 1 \cdot 310 x^{6})(1 + x^{2} + x^{4} + x^{6})^{3}$ の $x^{16}$ の係数 $=9690$
となります。

総計

以上の計算をまとめると
$|X/G| = \dfrac{1}{16} \left( 49202010 + 2170 + 18 \cdot 2 + 2 \cdot 4 + 2170 \cdot 4 + 9690 \cdot 4 \right) = 3078229$
となります。

s=15 のケース

黒石が8個、白石が7個ボードに置かれている局面です。

(a) 単位元

$|X^{g}| = 34285680$ (対称性を課さないケースで計算済み)

(b) ポジションを180°回転させるもの

いずれかの石の数が奇数の場合、この対称性を持つ配置はありません。

(c) ポジションを90°回転させるもの (時計回り・反時計回り)

いずれかの石の数が4の倍数でない場合、この対称性を持つ配置はありません。

(d) ポジションを45° または 135°回転させるもの (時計回り・反時計まわり)

いずれかの石の数が8の倍数でない場合、この対称性を持つ配置はありません。

(e) ポジションを通らない対称軸で反転させるもの

いずれかの石の数が奇数の場合、この対称性を持つ配置はありません。

(f) 二つのポジションを通る対称軸で反転させるもの

$s=16$ の場合と同じ記法を用いると、今回は $p + 2q = 15$ なので

$(p, q)$	$(1, 7)$	$(3, 6)$	$(5, 4)$
$\displaystyle\sum_{k = 0}^{ 3 } {}_{q}\mathrm{C}_{k} \cdot {}_{p}\mathrm{C}_{7-2k}$	35	75	155

となります。さて
$(1 + x + x^{2} + x^{3})^{2} = 2x + 4x^{3} + 2x^{5} +$ (その他の項)
となり、各項がそれぞれ $p = 1, 3, 5$ に対応する割り振りを表していることを考えれば
$|X^{g}| = (2 \cdot 35 x + 4 \cdot 75 x^{3} + 2 \cdot 155 x^{5})(1 + x^{2} + x^{4} + x^{6})^{3}$ の $x^{15}$ の係数 $=7140$
となります。

総計

以上の計算をまとめると
$|X/G| = \dfrac{1}{16} \left( 34285680 + 7140 \cdot 4 \right) = 2144640$
となります。

対称性を加味してざっくりカウント

$s=15, 16$ の場合について説明してきましたが、きっちり計算するのはそこそこ面倒くさいことが分かります。ただよく計算内容を観察してみると、ほぼほぼ (a) の数値÷16になっていることがわかります。(a) の数値はすなわち対称性を加味せずカウントした数に他なりません。なので、ざっくり考えれば、対称性を課したカウントは、対称性を課さない数値を16で割れば大体外さないでしょう。この値は
$133,645,905/16 \approx 835,2869 \approx 8 \cdot 10^{6}$
となります。

結果の吟味

対称性を加味した上ですべての局面を保存するのにどれぐらいの保存容量が必要か考えてみます。仮にひとつの局面を保存するのに4バイト必要だと考えると*7、おおよそ32MBあれば十分であることが分かります。これぐらいであればそのへんのノートPCでも余裕でメモリに乗る範囲でしょう。ハトの解析で必要になって128GBのメモリを積んだ身としては、全然楽勝そうだなと思えます。
気が向いたら、このボドゲも解析したいと思います。

追記 (2023/12/19)

プログラムを使って実際にカウントしてみました。
(石の総数)⇒(パターン数) と表記しています。

0 => 1
1 => 1
2 => 6
3 => 27
4 => 139
5 => 478
6 => 1826
7 => 5487
8 => 16933
9 => 42192
10 => 106332
11 => 223700
12 => 468444
13 => 829912
14 => 1444680
15 => 2144640
16 => 3078229
Total = 8363027

*1: $\lfloor x \rfloor$ は $x$ 以下の最大の整数を表します。