イントロダクション
前回の記事で、「てくてくピクミン」というゲームをエクセルで再現した。
今回は、各問題をクリアするための最短コマンドをマクロで解析した時の考え方をまとめておく。
プログラムで解析した最短コマンド（暫定）は動画でまとめている
シンプルな「総当たり法」
最も古典的だが、シンプルで設計しやすいのが「総当たり法」である。
※セキュリティ用語では、ブルートフォース法ともいう。
このパズルゲームでは、プレイヤーが選択できるコマンドは↑→↓←の４択に限られる。
まず、スタートの状態からそれぞれ↑、→、↓、←（４通り）を押した場合に変化させる。
ここでゴールできなければ、次は↑↑、↑→、↑↓、↑←、・・・、←↓、←←（１６通り）を押した場合に変化させる。
さらに、ここでもゴールできなければ、１６×４＝６４通りのコマンドを試してみる・・・というように、ゴールできるまで、全てのコマンドを試してみれば、いずれ正解にたどり着けるだろう。
最短コマンドを探したい場合は、深さ優先探索ではなく幅優先探索を実施する必要がある。
膨大な試行回数となる「組み合わせ爆発」
例として下記のように赤ピクミン、岩の配置があったとする。
最短９回のコマンドでクリアとなるが、単純にコマンドを総当たりしていくと、正解を導くまでにおよそ２６万回の試行回数が必要となってしまう。
そのため、特定の条件の場合に、枝分かれを停止する（枝切り）を実施する必要がある。
枝切りの条件
１ ピクミンが死亡した場合
ピクミンが死亡した場合はゲームオーバーとなるので、以降のコマンドを試行する必要はない。
２ 短い手数でも同じマップにできる場合
例として、下記のステージの場合、↑↓とコマンドを押した場合は、ゲームスタート時点と同じ配置になってしまう。その時点で最短手数でのゴールは不可能となるため、以降のコマンドを試行する必要はない。
下記のイメージ図の場合、赤色、緑色のパネルのコマンドは、枝切り処理により、以降のコマンドを省略する。
以上２つの枝切り処理を適応したマクロで解析してみると、最短手数が１４手だと短時間で算出できた。
ちなみに、この解析での枝切り処理回数は４８回だった。
個別に枝切りルールを適用する
作成したマクロでは、半日で約６０万回の試行回数を解析できる。
上記の枝切り処理だけでは、ほとんどの問題を６０万回以内の試行回数で解析できなかった。
なので、各問題の１つ１つに追加で特有の枝切りルールを適用して、試行回数を減らす必要があった。
例として、問題５３のステージについて考えてみる
宝に行くためには、全員を青ピクミンにする必要がある。青い花は４つしかないので、各ピクミンをそれぞれ青い花に入れる必要がある。
なので、赤ピクミン、黄ピクミン、白ピクミンがいる状態で青い花が無いという状態は、ゲームオーバーになる（枝切りする）というルールを追加して解析した。
この場合は、558,755回の試行回数から、最短手数が27手だと解析できた。
他の問題で適用した特別ルールは下記のとおりである
・一番遠いピクミン同士が、横〇マス以上離れた場合はダメ
・白ピクミンがいない場合、１コマンドでゴールできるピクミンは１匹に限られる。例えば自己ベストが２１手で、ピクミンがスタート時に３匹いる場合は、20手目で残り2匹になっていないと自己最短記録を超えられないので、枝切り処理できる。
・（問題５６）三匹白ピクミンになるとダメ
・（問題５８）赤ピクミンが白花をとるとダメ。青ピクミンが紫花になるとダメ。白ピクミンが白花を取るとダメ。
まとめ
ディープラーニングとかのアルゴリズムを適用できれば、もっと短い手数でクリアできる問題があるかもしれないが、個人の限界ではここまでである。
コメント