Steam 上で 14 Minesweper Variants というゲームがあるがこれがなかなか面白い。
ゲームの中身については Youtube の Gate 氏の動画がとても参考になる。
再生リスト:
https://www.youtube.com/watch?v=eGTILDZnMzs&list=PLmyjj-hv7yVGBKjp7YDr4zwDL-JAp7py_
一般的 (Vanilla) ルールもあれば、マスの価値の判断基準が違ったり、マスが判定する視野やフィールド全体単位の判定等もあってなかなか刺激的である。 14 Minesweeper Variants を解くプログラムを書くとしたらどのような作戦になるのかを考えてみた。
まず大前提が、Minesweeper を解くとしたら人間のように各数字マスに注目して切り分けを行うか、それとも爆弾配置を総当たりするかの方法になる。 14 Minesweeper Variants では一つのボード上で複数のルールが飛び交うことになるので今回は総当たりで実装することにする。
爆弾配置の総当たりは簡単に言えば「二進数 n ビットの配列のうち、1 が立っている状態が m 個あるものを全て作れ」という案件だ。
盤面が全て同じルールで構成される場合は「最初の部分が違反していたので類似パターンは全て省略」といった最適化が可能だが、 14 Minesweeper Variantsでは複数のルールが飛び交うためそう簡単にはいかない。
爆弾配置の総当たり計算 k-permutations
ビット配列の総当たりは "k-permutations" というアルゴルズムだ。この場合の "k" は規模可変、という意味らしい。
最近は 仕事で "k-anonymity" (k-匿名性) も使っているので "k-" さんにはとてもお世話になっているような気がする。他には "T-近似性" や "L-多様性" のような類似命名があるそうな。
<?php
function k_permutatons($remaining_bits, $length, $bit_array = Array()) {
if ($remaining_bits == 0) {
// 残りマスは全て 0
yield array_merge($bit_array, array_fill(0, $length, 0));
} else if ($remaining_bits == $length) {
// 残りマスは全て 1
yield array_merge($bit_array, array_fill(0, $length, 1));
} else {
// 今回は 1 のパターン
k_permutations($remaining_bits -1, $length -1, array_merge($bit_array, Array(1)));
// 今回は 0 のパターン
k_permutations($remaining_bits , $length -1, array_merge($bit_array, Array(0)));
}
}
14 Minesweeper Variants の場合、5x5 の爆弾数は 10個、 6x6 の爆弾数は14個、7x7 の爆弾数は20個、8x8 の爆弾数は 26個だ。 ゲーム開始序盤の空きマスが圧倒的に多い状態で 32bit以下とは言っても総当たりを計算して、その上で各生成盤面の正当性の確認をするとなると膨大な処理能力が必要となる。
GPU等を使った並列処理ができれば簡単かもしれないが、本件は処理ルールが複雑なので整理も兼ねてシングルスレッドで実装方法を検討する。
※ 実際には bit array の受け渡しはせず、「爆弾配置可能場所候補」順にマッピングした盤面を直に渡すと良いだろう。
Point of Interest の導入
爆弾配置の総当たりをする場合、配置先のマスが一つ増えると計算するパターンは倍加する。 5x5 や 6x6 ならまだ数分以内で計算可能だが、それ以上の盤面だと計算の負荷が上がりすぎるため Point of Interest を導入して配置マスを減らすのだ。
結局爆弾の配置の全パターンを計算するにしても、配置が有効であるかのチェックは数字が判明しているマス目の周辺しか行わない。それ以外のマス目の爆弾配置は一切処理されないのだ。最初にそれぞれのマス目から見える範囲を確認し、その見える範囲だけの爆弾配置を計算すれば良い。
| 3 | ||||
| 1 | ||||
| ? | 3 | 1 |
POIを使わない場合は爆弾配置可能マスは 20マスだが、POIを使う場合は10マスだ。ゲーム序盤ではとても役に立つことだろう。
ただし、Point of Interest の導入を行うと配置可能マスが減る関係でk permutationsの「残りマスは全て1」が誤発動するようになるのでこの最適化は行えない。
各マスの処理ルールの確定
14 Minesweeper Variants の場合は最初は盤面全体が同じルールだが、ゲームが進むと複合ルール化したり、各マスで適用されるルールが違ったりと難易度が変わる。 ゲーム内にある各ルールを個別に処理として実装すると実装量が増えるのでルールを整理する必要がある。
ルールを整理すると以下がわかる（一部）。
探索範囲、集計方法に影響するもの
計算結果に影響を及ぼすもの
- Negate: 白マスを 1、 黒マスを -1 で計算する
- Multiple: 白マスを 2、黒マスを 1 で計算する
- Lie: 演算結果と予想数が 1 ずれる
盤面全体に影響を及ぼすもの
- Quad: 2x2 マスの中は必ず爆弾が存在する
- Connect: 全ての爆弾マスが８方向で隣接する
- Three: 各方向で爆弾が３マス連続で並ばない
計算結果に影響を及ぼすものだけがルールと指定されている場合は集計方法は Vanilla がそのまま使用できる。
- Lie の判定方法は簡単だ。
abs(予想数 - 実際の数)が 0 か 1 になるかの判定で良い。Lie は予想数が一個の場合にしか使えないので Wall と Partition では使えない。 - 盤面全体に影響を及ぼすものは計算負荷が高いので一番最後に判定するために取り分けておく。
探索ルートの策定
k-permutations で爆弾の配置を総当たりで生成した後で盤面の判定処理を行うが、この判定処理を行う回数は最も多い。つまり一回分の処理の最適化が数万倍に効果を出すのだ。 n x n マスの毎回ループして判断対象を探すのはとても無駄なので、探索ルートを事前いきめて、そのルートで指定されたマスのみの判断を行うようにする。
探索ルートの決め方には前述の Point of Interest が強く関わってくる。
- 特定のマス目の Point of Interest の中に爆弾設置可能な空白がある場合はそれが「爆弾設置可能候補」としてマーキングされるのだが、そういった数字マスが探索ルートとなる。
- PoI の全てが既に配置済みのマスや、マス目の数字が ? のものは除外される。
- PoI に既に爆弾が配置済みの場合や数字マス（安全が確定）の場合は情報を事前に処理しても良い。
探索ルートの各項目は以下のような値となる
- x 軸座標
- y 軸座標
- 適用ルール
- 適用効果 (白マスの価値、黒マスの価値、結果の差分）
- 処理対象の PoI マス一覧
- 判定の初期値 (PoIマスを事前処理した場合は初期値を設定し、PoIマスを減らしておく）
- 処理負荷（未処理PoIマスの数量）
探索ルートの値をきめたら処理負荷（未処理PoIマスの数量）等でソートしておく。処理負荷でソートするならなら盤面全体の判定も探索ルートに含めても良い。
全体のフロー
全体のフローとしては以下のような流れになる。
準備段階
- 各マス目に適用されるルールを整理する。
- 爆弾の検出範囲を影響するもと、計算結果を影響するものと、盤面全体に影響するものとで分類する。
- 各マス目においての定石パターンを確認し、埋められるものは埋める。
- 各マス目の Point of Interest 範囲を特定する
- Point of Interest 範囲に空白が存在する場合は爆弾配置候補としてマーキングし、中央マスを探索ルートに追記する。
探索段階
- k permutations を用いて爆弾を候補地に総当たりで配置する。
- 探索ルートから処理ルールや座標の情報を取り出す。
- １マス分の判定処理を行う
- 全マスが判定を通過したら盤面全体のチェック処理を行う。
- 盤面が有効な場合は「爆弾設置率」「爆弾未設置率」の統計データに加える。
- 探索ルートから処理ルールや座標の情報を取り出す。
探索完了後
- 各マスの爆弾設置/未設置の統計を確認し、どちらかが 100% になるものを「爆弾確定マス」「安全確定マス」として出力する。
