Flow Free を自動で解く
子どもが「なんかゲームしたい」と言うので、子どもでも出来そうなスマホゲームを探してみた。すると Flow Free というゲームが目に留まった。一言でいうと迷路みたいなゲームで、実際4歳児でも楽しく遊べる感じであった。しかし、問題の規模が大きくなるにつれて大人でも解くのが難しくなる。NP hard っぽさがある。ってことで大人らしく Flow Free のソルバーを書いてみたメモ。これができたらクラスのヒーロー間違いなし。
Flow Free とは？
まずはゲームの説明をする。問題では以下のようなパネルが与えられる。
見ての通り、同じ色の石が２つずつ存在する。クリアの条件は、これらのペアを結ぶ経路ですべてのマスを埋め尽くすことである。たとえばこの問題の正解は以下である。
なんとも簡単である。考える時間は3秒もあれば十分だろう。
しかし、難易度が増すと以下のような問題が出てくる。
これが難しい。「どの色から手を付けようか？」「つないだ経路が間違ってたらいつ気付けるのか？」そんなことばかり考えてマジでなかなか解けない。
アルゴリズムの方針
この問題を自動で解くためのアルゴリズムを考えたとき、まず初めに、問題から必要十分な制約を抽出して SMT ソルバーに投げることを考えた。各マスに対応する変数に値を割り当てる問題として捉えれば解けそう。しかしこの方針はあまりワクワクしないので気が向かなかった。
次に考えたのは探索ベースの手法である。パネルの状態を遷移させながら正解にたどり着くまでトライ&エラーを繰り返すアプローチである。人間が解く時と同じような発想であり、アルゴリズムの実装しがいがありそう。ってことでこっちを採用した。
問題を解くコツを知るため、自分自身で簡単な問題から難しめの問題までいくつか解いてみた。すると、以下の3つの手順の繰り返しでだいたいの問題が解けそうなことが分かった。
これらの手順をすべてのペアが経路でつながるまで繰り返せば終わり。ってことで各手順の詳細を説明する。
手順1. 現在の状態から正解に到達可能か？
探索が進むなかで現在の状態が正解に到達しうるものかを判定する方法を説明する。
まず、以下のようなコの字型の行き止まりが出現した場合は枝刈りを行う。理由は簡単で、2点を結んだ結果すべてのマスをカバーすることが問題を解くために必要であるが、行き止まりが1つでも存在したらすべてのマスを埋め尽くせないからである。
次は微妙なパターンだが、色々な問題を手で解いてみたところ、隣接した4マスを1色でたどる経路は正解に含まれなかった。Flow Free の隠された制約だろう。ってことで以下のパターンが現れたら探索の枝刈りを行う。
そして、以下のパターンが出現したら枝刈りを行う。理由は、この形によって残された2マスを辿るには、上記の隣接4マスの経路が必要になるからである。
最後に、すべての色のペア同士が到達可能であるかを調べる。ある経路によってパネルが複数の 連結成分 に分離された場合、同じ色のペアは同じ連結成分に属する必要がある。たとえば以下の状態では黄色のペアが到達不可能なので正解に至ることはない。
手順2. 決定論的な状態遷移
つぎに「この状態のときはこう状態を遷移させるしかない」というパターンを説明する。ただ説明が面倒なので2つのパターンだけ抜粋して紹介する。
まず、経路の伸ばし方が1通りしかない石があればそれを伸ばす。以下の例の左上の青色はその例である。左上の青色は経路を下に伸ばすしかない。なので下に伸ばす。
あとは、行き止まりを生み出さないことを考えると状態遷移が1通りに定まるパターンがある。たとえば以下の画像はパネルに右上の隅あたりを示したものである。この状態からは緑を右に伸ばす必要がある。というのも、右以外に伸ばすと右上のマスが行き止まりになってしまうからである。
手順3. 非決定論的な状態遷移
いよいよ non-deterministic に状態を遷移させるところまで来た。方針は簡単で、状態を見て経路を伸ばすとよさそうな石を決め、可能なすべての次の状態に遷移させるだけである。
「経路を伸ばすとよさそうな石」の決め方は「状態遷移の選択肢がもっとも少ないもの」とした。左右上下の4つに経路を伸ばせる石より、右と上の2つにしか経路を伸ばせない石を優先するといった感じである。探索問題において自由度の低いところから優先的に分岐させていくのは常套手段である。こうすることで、自由度が高いと思われていた部分の状態遷移も、探索が進むにつれて選択肢が限られてくるものである。
1つの石に着目してすべての状態遷移を列挙するので正解が探索空間から漏れることはない。探索アルゴリズムを設計するときはこういう観点は重要。英語だとアルゴリズムの completeness って言うようね、きっと。
実装してみた
上記の方針でこの規模の問題を解くソルバーを自作した。Rust で書いた。ソースコードは Gist に置いた。
そして冒頭で述べた問題を解いてみる。以下のような配置であった。
ソルバーに食わせるため以下のように文字列にエンコードする。
- - - - A - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - B - - - - - - - - C - - D E F - - G - - - - - - D E - - - - - - - - - - - - - - - - - B - - - - - H - I - - - - - I - - - - - - - - J - - - - J - - - - - - - - - - - - A - - - - - - K - - - - - - - - - - - - - - - - L - - K - G - M - - - - - - - N - M - F - C - - - - - H - - - - - L - - - - - - - - - - - - - N O - - - O
そしてソルバーを実行すると約5秒で以下の結果が得られた。
A A A A A F F F F F F F F F A F F F F F C C C C C C C F A F C C C C C B B M M M C F A F C D D D E F B M G M C F A F F D E E E F B M G M C F A A F F F F F F B M G M C F H A I I I I I I I M G M C F H A A J J J J J J M G M C F H H A A A A A A M M G M C F K H K K K K K M M G G M C F K H K L L L K M G G M M C F K H K K N L M M F F C C C F K H H K N L L L L F F F F F K K K K N N N N N O O O O O
これを元の問題にプロットしてみると以下のようになった。
解けてる。めでたし。
所感
Rust に慣れていこうということで今回はソルバーを書いてみたが割と楽しかった。Rust は速いので安心感がある。今回はデータ構造とかあまりちゃんと考えていないのでデータのコピーとか大量発生している。メモリ上のデータを再利用とかすればもっと速くなると思う。そこまでエンジニアリングの気力は無かったが。
Flow Free のソルバーを書いた例はわりとあるらしく、たとえば以下のページでかなり細かく解説されている。自分も実装が終わった後にこのページを見てみたが、本記事で紹介したアイデアがすべて網羅されているように見えた。どう考えても自分以上のコンピュータサイエンス力がありそうな人だ。世の中にはスゴい人がいるなぁ。
