【Tokyo Doves】実現可能局面数をざっくり見積もってみる

引き続き Tokyo Doves のシリーズです。今回は Tokyo Doves の実現可能局面数について見積もってみます。

実現可能局面数とは？

実現可能局面数とは、実際にゲームの進行で実現しうる盤面の状態すべての数です。参考までに他のボードゲームの実現可能局面数の概数を列挙すると

○×ゲーム: $10^3$
チェッカー: $10^{20}$
(8x8)オセロ: $10^{28}$
将棋: $10^{68}\sim 10^{69}$ (?)
囲碁: $10^{170}$ (?)
どうぶつ将棋: $2.5 \times 10^{8}$

ぐらいらしいです。ちょっと自分で調べるのをサボって以下の動画から数字をコピペしました(なので正確に知りたい方はご自分で文献を探してください)。この動画はどうぶつ将棋の解析について紹介しています。
www.youtube.com
実現可能局面数の大きさの多寡によって、そのボードゲームを完全攻略するための難易度をおおよそ見積もることができます。例えば通常の 8x8 オセロは未だ完全解析されていないそうですが、6x6オセロは既に完全解析が完了しています(4目差の後手必勝)。6x6オセロの実現可能局面数はおよそ $3.6\times 10^{12}$ だそうなので*1、この付近がギリギリ頑張れるラインかな、と考えることができます。

超ざっくり見積もり

まずはあまり難しいことを考えず、どんぶり勘定で数えてみます。Tokyo Doves は4x4の範囲に入るように常に進行するので、各ハトの位置はそれぞれ4x4の16個のマス目のどこかに位置すると考えることができます↓

x	x	x	x
x	x	x	x
x	x	x	x
x	x	x	x

赤組のボスハトと緑組のボスハトは常に盤面上にあります。これらの配置の仕方は ${}_{16}\mathrm{P}_{2}$ 通りあります。それ以外のハトは両組合わせて10羽いて、そのうち0羽以上10羽以下が盤面に配置されます。配置されるハトの数を $k$ 羽とすると、配置されるハトの選び方が ${}_{10}\mathrm{C}_{k}$ 通り、これらのハトの配置の仕方が ${}_{14}\mathrm{P}_{k}$ 通りとなります。以上を足し合わせると

$\sum_{k = 0}^{10} {}_{16}\mathrm{P}_{2} \cdot {}_{10}\mathrm{C}_{k} \cdot {}_{14}\mathrm{C}_{k} = 4,545,963,055,440 \sim 4.5 \times 10^{12}$
となります。値は Python の以下のコードで計算しました。答えは一瞬で出ます。

from math import comb, perm
print(sum(perm(16, 2) * comb(10, k) * perm(14, k) for k in range(11)))

超ざっくりならこれでいいのですが、ルール上同じ局面を複数回数えている部分があります。例えば x, y, z をなんらかのハトとするとき

x	z
		y
			x
			x

と

x
	x	z
			y
x

はルール上同じ配置ですが、この数え方だとそれぞれ別の局面として数えています。また

x	z
		y
			x
			x

と

x
z
	y
		x	x

と

		x	x
	y
z
x

はパッと見違う形ですが、相対的な位置関係は同じなので、事実上同じ局面と言って良いでしょう。つまり回転・反転によって同じ形になるもの同士は同じ局面として数えるのが自然です。またハトが孤立するようなパターンの排除したいです。こうなると、もはや簡単な計算式では対処できません。そこでもうすこしガッツリプログラミングを使って数えてみます。

作戦

$4.5\times 10^{12}$ 通りをすべて検査して重複を取り除いたり孤立するものを取り除いたりしてもよいのですが、かなり時間がかかってしまうので、ここでは別の作戦を取ってみます。具体的には

4x4 のマス目のうちハトを配置するマスはどれか
↑のマスにどのようにハトを配置するか

の二段階に分けて考えることにします。前者と比べると後者はシンプルな数え上げで、かなりの部分を数式で処理できます。その分前者の数え上げの総量が抑制されて、楽に答えを得られる、という寸法です。

ハトの置き場所が与えられたときにハトをどう配置するかの総量

具体例から考えましょう。以下のような配置場所が指定されたとします。

x	x		x
		x
	x		x
		x

x がハトを配置するべき場所です。xに順に配置していくのですが、その順序は先ほどと同様「両軍のボスハトを配置する→それ以外のハトを配置する」で行います。ボスハトが ${}_{7}\mathrm{P}_{2}$ 通り、残りのハトは5羽で ${}_{10}\mathrm{P}_{5}$ 通りとなります。
次に以下のような配置場所の場合はどうでしょう。

x
		x
	x		x
		x

同じ考えで数えると ${}_{4}\mathrm{P}_{2} \cdot {}_{10}\mathrm{P}_{2}$ 通りと言いたくなるところですが、今回は配置場所の対称性があるため、これだと数えすぎになってしまいます。回転・反転で一致するものは同じ局面とみなす、と言ったのですが、今回は回転・反転をどのようにしても形状が変わりません。回転・反転で作られる数は8通り( $90^{\circ}$ 度回転を4回+反転で2つ)あるので、全てのパターンで8回重複して数えていることになります。なのでこの配置での局面数は ${}_{4}\mathrm{P}_{2} \cdot {}_{10}\mathrm{P}_{2} / 8$ 通りとなります。
もうひとつぐらい具体例を挙げておきます。

x
x
	x	x	x
		x

こちらの配置だと反転で一致するのみなので、先ほどの例では8で割っているところを2に変えればOKです。つまり ${}_{4}\mathrm{P}_{2} \cdot {}_{10}\mathrm{P}_{2} / 2$ 通りとなります。
以上から、ハトの配置場所とその対称性が与えられれば、一つひとつ列挙しなくても、数式でハトの配置が何通りあるかを数えることができます。いえ、より正確には、(配置するハトの数, 配置の対称性) のペアが与えられれば十分です。

ハトの置き場所の列挙

重複しないハトの配置場所とその対称性を数え上げればあとは簡単、ということが分かりました。そこでここから頑張って配置全体を列挙する方法を考えていきます。
まず16マスに以下のように数字を付けます。

15	14	13	12
11	10	9	8
7	6	5	4
3	2	1	0

そして数字の組み合わせによって配置場所を表現することにします。例えば前章で出てきた配置場所の例なら {1, 4, 6, 9, 12, 14, 15}, {1, 4, 6, 9}, {1, 4, 5, 9} になります。こうすることによって、0~15の16個の数字からいくつか取り出す組み合わせ全体を総当りで調べれば終わることが分かります。この総当りは
$\begin{equation} \sum_{k = 2}^{12} {}_{16}\mathrm{C}_{k} = 64822 \end{equation}$
通りなので、コンピュータなら一瞬でできそうです。
あとは平行移動・回転・反転で一致するものを取り除くこと、孤立ハトがあるものを取り除くこと、対称性を数えることです。これを実装するためにビットボードというものを考えます。

ビットボード

ボードゲームの状態をビット列で表現して、ビット演算でボードゲームを管理する、という手法があります。このようなビット列で表したボードをビットボードと呼ぶようです。以下のサイトではオセロをビットボードとして実装する方法を丁寧に紹介しています。
zenn.dev

ビットボードを使ってハトの位置のパターンを数え上げることを考えます。16個の位置に「ある」か「ない」かの2つの値をもたせたいので、16bitのデータを考えればよいでしょう。例えば Rust では u16 という型で表現できます。以下は Rust での実装例です。

// 可視化用
fn u16_to_square(x: u16) -> String {
    let flat = format!("{:0>16b}", x);
    let mut chars = flat.chars();
    let mut lines = Vec::with_capacity(4);
    for _ in 0..4 {
        let line: String = (&mut chars).take(4).collect();
        lines.push(line);
    }
    let square = lines.join("\n");
    square
}

// 可視化用
fn print_u16_in_square(x: u16) {
    println!("{}", u16_to_square(x));
}

fn main() {
    let v = vec![1, 4, 6, 9, 12, 14, 15];
    let mut board = 0_u16;
    for x in v {
        board |= 1 << x;  // 番号のところに bit が立った数字を記録
    }
    print_u16_in_square(board);
}

上記を実行すると以下が標準出力されます:

上下左右に1マスシフトするような関数も定義しておきます。この関数は「平行移動すると同じパターン」といったものを省くのに使えます。

fn shift_n(x: u16) -> u16 {
  // 上に1マス
  x << 4
}

fn shift_s(x: u16) -> u16 {
  // 下に1マス
  x >> 4
}

fn shift_w(x: u16) -> u16 {
  // 左に1マス
  (x & 0x7777_u16) << 1
}

fn shift_e(x: u16) -> u16 {
  // 右に1マス
  (x & 0xeeee_u16) >> 1
}

<< や >> はシフト演算子とよばれるもので、ビット列を右辺の数だけシフトする演算です。シフトしてできる余白は0で埋められます。上下方向のシフトは単純に4bit分のシフトとして表現できます。左右に関しては少しだけ工夫が必要です。例えば左方向への1シフトの実装を単に x << 1 としてしまうと、元から左端にあったものが右側からぴょこっと現れてしまいます。これを防ぐためには、シフトの前に

という u16 の数字と bit ごとの and を取ってしまって、その後シフトすればうまくいきます。0111 は十六進法で表すと7なので、この数値は 0x7777_u16 と表現することができます。同様に右方向へのシフトは

をあらかじめ and しておいてからシフトすればうまくいきます。こちらは十六進法なら eeee なので Rust での表記は 0xeeee_u16 となります。
これらの関数を駆使して、可能な限り右下に寄せる関数を定義してみます。つまり右側に余白があれば右に寄せ、下側に余白があれば下に寄せるという操作を可能な限り行います。Rust は当然再帰的な関数をサポートしているので、例えば以下のような書き方ができます。

fn limit_shift_se(x: u16) -> u16 {
  if x == 0 {
    0
  } else if x & 0x1111_u16 == 0 { // 右側に余白あり
    limit_shift_se(shift_e(x))
  } else if x & 0x000f_u16 == 0 { // 下側に余白あり
    limit_shift_se(shift_s(x))
  } else {
    x
  }
}

次に反転と回転ですが、これはビットボードを使わないほうが簡単に実装できます。例えば {1, 4, 6, 9, 12, 14, 15} のボードは

x	x		x
		x
	x		x
		x

で、これの転置形である

x
x		x
	x		x
x		x

は {1, 3, 4, 6, 9, 11, 15} に対応します。このとき転置前の位置と転置後の位置の対応関係を考えておけば、前者から後者を得るための写像が求まります。具体的には

$1 \mapsto 4, \quad 4 \mapsto 1, \quad 6 \mapsto 9, \quad 9 \mapsto 6,$
$12 \mapsto 3, \quad 14 \mapsto 11, \quad 15 \mapsto 15$
となります。この対応を追えるなら、他のマスも同様に対応関係を決められることも分かりますね。
反転・回転は合計で8種類あるので、この対応関係を与える配列を定数として持っておきます。またこの対応関係を使って Vec を変換する関数も準備しておきます。

const MAP: [[usize; 16]; 8] = [
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15],
    [3, 2, 1, 0, 7, 6, 5, 4, 11, 10, 9, 8, 15, 14, 13, 12],
    [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15],
    [12, 8, 4, 0, 13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3],
    [3, 7, 11, 15, 2, 6, 10, 14, 1, 5, 9, 13, 0, 4, 8, 12],
    [15, 11, 7, 3, 14, 10, 6, 2, 13, 9, 5, 1, 12, 8, 4, 0],
    [12, 13, 14, 15, 8, 9, 10, 11, 4, 5, 6, 7, 0, 1, 2, 3],
    [15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0],
];

fn get_congruents(x: &Vec<usize>) -> [Vec<usize>; 8] {
  let mut cons: [Vec<usize>; 8] = Default::default();
  for elem in x.iter() {
    for (i, map) in MAP.iter().enumerate() {
      let new_elem = *map[*elem];
      cons[i].push(new_elem);
    }
  }
  cons
}

最後にハトが孤立するかどうかの判定について考えます。各ハトの周りを見て、一羽もいないやつがいなければだめ、となるわけですが、ビットボードを使えばかなり効率よく判定することができます。言葉で説明するよりコードを読んだほうが早そうなので、まずコードをご覧ください。

fn is_isolated(x: u16) -> bool {
  let x_n = shift_n(x);
  let x_s = shift_s(x);
  let x_w = shift_w(x);
  let x_e = shift_e(x);
  let x_nw = shift_n(x_w);
  let x_ne = shift_n(x_e);
  let x_sw = shift_s(x_w);
  let x_se = shift_s(x_e);
  let surroundings = x_n | x_s | x_w | x_e | x_nw | x_ne | x_sw | x_se;
  (x & surroundings) != x
}

コードに出てくる x_* はいずれも元のビットボードを8方向のいずれかに移動させたものです。これらの or をとったものが surroundings です。もしハトの位置が surroundings で 1 となっているマスにいれば、それはすなわち他のいずれかのハトが周りにいることを表します。逆に surroundings で 0 となっているマスにいるとしたら、周りに他のハトがいないため孤立することを表します。ということは「孤立している」の必要十分条件は「x と surroundings の and が x から欠損する」となるので、上記のような実装になる、というわけです。
ビットボードでなければ、ひとつひとつハトを取り出して処理して・・・となるところが、ビットボードでは見かけ上並列計算っぽい処理になりました。こういった場面があるため、ビットボードで実装しておくと計算効率の点でメリットを享受しやすいです。

改めて列挙の戦略

ここまでで道具は揃いました。これらを使ってハトの置き場所全体を列挙する流れを整理します。

(1) 0~15 から n 個 (2≦n≦12) の組み合わせを全列挙
... Rust では例えば itertools というクレート*2を使って実現できます。
(2) 各組み合わせに対して、その反転・回転で作られる8つを作る
(3) 8つをそれぞれ u16 のボードに変換し、右下に寄せるように平行移動する
(4) ハトが孤立するパターンであれば棄却し、(1) の次の組み合わせに進む。
(5) 孤立しないことが分かったら、(3) で作ったボードを全て記録しておく
... Rust なら HashSet などを使えばいいでしょう。
(6) 今回作ったボードが新しく記録されたものであれば (つまり (5) の直前に未登録状態なら)、有効な新しいパターンなので、対応する組み合わせの数を加算する
... 8つのボードで何個ずつ重複するかが「対称性」に対応します。ハトの数は n と分かっているので、このパターンで何通り数えればよいか求まります。

以上をコードに落とし込めば数え上げは完了です！

結果

そして完成したコードがこちら・・・とすればいいんですが、ちょっと人に見せられるようなコードが手元にないので、結果だけ記しておきます。以上の計算を実行すると、求まる局面数は
$509,462,034,903 \approx 5.1 \times 10^{11}$
となります。最初の超ざっくり評価より1桁ぐらい落ちました。計算は一瞬で終わります。
ちなみに、前回の記事*3で紹介したように、

両方同時囲いは直前に指したほうが負け
履歴による千日手禁止ルールは無し

というルールの下では、両者が最善手を指したとすると、両方のボスが囲まれている状態は実現しません。さらに相手の手番で指した結果、相手のボスが囲まれているという状況も起こりません。したがって、いずれのボスも囲まれていないか、自分のボスのみが囲まれているものが事実上実現されうる局面と考えてもいいでしょう。この条件の下で数え上げると、
$318,195,819,783 \approx 3.2 \times 10^{11}$
となりました*4。これらが全て実現可能かはまだわかりませんが、ざっくりと $10^{11}$ ぐらいなんだな〜と思えば大きくは外さないようです。

まとめ

全局面数を数え上げるために、本当に全てのものを数え上げるのではなく、ハトの配置パターンとそのときの数え上げを分離し、後者を理論的に計算することで、計算量を大きく下げるようにしました。配置パターンを列挙する際はビットボードというものを使い、シフト演算子や and を有効活用していきました。特にハトが孤立するかどうかの判定では、ビットボードならではの効率化も見えました。
結果として局面数はざっくり $10^{11}$ ぐらいになりました。完全解析されている 6x6 オセロと比べても悪くない数字で、それなりに解析も不可能ではないと感じさせる結果となりました。次回以降ではより本格的な探索の情報について書いて行けるといいなぁと思っています。

*1:ソースは wikipedia です(ソースと言えないやつ) コンピュータオセロ - Wikipedia

*2:itertools - Rust

*3:【Tokyo Doves】自滅しない手が常に存在することの証明 - ぷりんの雑記帳

*4:囲まれているかどうかの処理は少し工夫が必要です。ビットボードで頑張るなら、ボスハトの上下左右の4マスだけが1になっているビットボードを作って、元のボードの not と and を取れば基本は大丈夫です。ただこれだと 4x4 の壁の有無の処理が足りないので、もう少し頑張る必要があります。ちょっと書くのが面倒なので、読者の演習問題とします(=丸投げ)。