「ゼリーのパズル」ソルバーを作る（A＊）

2025-01-13
#algorithm #puzzle

「ゼリーのパズル」というパズルゲームを初めてやった時は初期のステージからあまりの難しさに悶絶した。 それだけに解けたときの満足感は半端ない。

しかしながら純粋な思考型パズルゲームは時間をかけて考えれば解けるというものでもなく、詰まるとまったく先に進めなくなってしまい辛い。 てなことでプログラムで解いてみることにした。

ゼリーのパズルについて

ゼリーのパズルはたつなみ氏が作ったパズルゲームで、 かわいい・とぼけた見た目に反してものすごく難しいのが特徴だと思う。

ゼリーのパズル

といってもステージがあからさまに難しそうってんじゃなく一見簡単そうに見えて 「こうすれば解けるだろう」と進めると罠が用意されている、という具合でどのステージも凝っている。

またシンプルなルールで、やみくもにギミックを増やすわけじゃなく少ない構成要素のままなところがすごい。

ゲームのルール

  • 目的：
    • 同じ色のゼリー同士をすべてくっつけるとステージクリア
  • メカニクス：
    • 同じ色のゼリーが隣り合うとくっついて一体になり、形状はそのまま維持される
    • ゼリーは左右にのみ動かせる
    • 上に乗ってるゼリーは一緒に移動されない
    • 動かしたゼリーの先に他のゼリーがある場合、押すことができる
    • 下に床がないと落下する
  • ギミック：
    • 壁に固定されて動かせないゼリー
    • 黒いブロック：持ち運び用、黒ブロック同士はくっつかずクリア条件にも関わらない
    • ゼリーが黒いブロックにリンクされて、一緒に動く
    • 壁や黒ブロックにゼリーが埋め込まれいて、接すると出現する
      • それを利用して、持ち上げることが可能
      • すべて出現させて回収する必要がある

パズル解法アルゴリズム

プログラムでパズルを解くには開始の状態から可能な手を愚直にすべて調べ上げるという方法で行う。 具体的には箱入り娘を解くときにやったように幅優先探索(BFS)を用いる。 BFSはキューから取り出した局面に対して可能な手を列挙して、それらを次の局面としてキューに積むということを繰り返して、解けた局面に到達したら終了となる。

ゼリーのパズルで可能な手はゼリーを左か右に動かすことだけなので、それほど手が広いわけではない。 また重力があるため下に床がなければ落下してしまい盤面全体で自由に動かせるわけではなく持ち上げることも（自由には）できないので、そこまでべらぼうに探索すべき局面が広いわけではない。 とはいえクリアまでの手数が長かったりゼリーや黒ブロックの数が多い面ではかなり時間がかかってしまうので対策が必要。

A＊を適用する

対策としてA＊を適用してみることにした。 A＊は迷路探索やゲーム内の敵がプレイヤーを追うときとかによく使われて、目的位置がなんとなくわかる場合に使える。 局面を探索する順を単なるBFS・キューに積んだ順ではなく、目的地に近いと思われる局面を優先的に探索する。 これまでの距離とゴールまでの残り推定距離を加えたものが小さい局面を優先して探索することで、早期に発見できるものと期待できる。

A＊の注意点としては残りの推定距離は実際のゴールまでの距離かそれ未満にする必要がある。 理由は実際より長い距離になる場合があると最初に見つかった解が最短経路とはならない可能性があるため。

ゼリーのパズルでいえば各色のゼリーがすべてくっついた状態がステージクリアなので、その状態に近づく手が優先されるようにすればいいんじゃないかということで、 ゼリーの色ごとに横方向に一番離れた距離を合計したものを残り距離としてみた （途中のものは最善で道中に回収できるものとして）。 縦方向には自由に動かせないので考慮外。 また埋め込まれたゼリーがある場合にはそれらを回収する距離も考慮する。

パズルゲームでは闇雲にゴールに向かえばステージクリアに近づくということはまずないが、それなりに効果があるっぽい。

例）ステージ8：BFSの場合局面数93,679、11.8秒　→ A＊の場合局面数74,489、10.4秒

優先度付きキュー

A＊を実装する場合には優先度付きキューというデータ構造が使える。 実体は二分ヒープで、要素の追加や先頭要素の取り出しが計算量O(log n)で行える （Wikipedia には追加の計算量は「上向きに2, 3レベル動かすくらいですむ」から平均O(1)と書かれているがこの用途では追加される優先度がランダムではないのでその限りではないと思う。 実測したところ0.1〜0.3log nくらいはあった。 英語版ではθ(log n)となっていた）。

枝刈り

他に高速化の手段として、もうどうやってもクリアできない「詰んだ」状態になったらその局面以降の探索を打ち切れる。

ゼリーのパズルの場合、ゼリーを持ち上げることが（上に飛び出すゼリーがない限り）できないので、 例えば壁に固定されたゼリーの高さに届かない位置に落ちてしまったらクリア不可になる。

他にも頑張って、左右断絶されて渡れないとか判定できればいいんだけど、手付かず…。

例）ステージ15：枝刈りなしの場合局面数95,024、15.6秒　→ 枝刈りありの場合局面数28,180、2.1秒

実装に関して

優先度付きキューの実装

Rubyは標準で優先度付きキューが用意されてないので、はじめはRubyGemsで探してダウンロード数の多い pqueue を使ってみた。 BFSに比べて探索する局面数は減るがかかる時間は増えてしまうこともあってそういうもんかとも思ったがどうもおかしいので実装を見てみると、 二分ヒープではなくソート済み配列に挿入する方式で、それだと数が増えると結構重くなるようだった。

他のもいろいろ問題で、

  • PriorityQueue Macではインストールに失敗する
  • priority_queue 優先度ごとに別の配列
  • priority_queue_cxx 速度は申し分ないが、キューへの追加時に優先度を指定する方式で通常のキューと使用法が異なってしまうので断念

あれこれ探し回った結果、「Rubyで優先度付きキューを実装した」のものを利用させてもらった。

状態更新処理

ステージから手を進める状態更新の処理に手こずった。 ゼリーやブロックなどをクラスのインスタンスとして保持しているが、手を進めるときに分岐させるためにインスタンスを複製する必要がある。 状態のオブジェクトすべて複製するとメモリ消費量が不安なので更新が必要なインスタンスだけを複製したかった。 しかしそうしたことで書き換えていいのか複製すべきか判定して、複製が必要だったら他の参照も書き換える処理が必要になってしまい、抜けてるとバグるという問題が出た。

計算時間

ステージによってまちまちで、数秒〜数分〜数十分〜数時間かかるものも。 唯一ステージ50が解くまで待ちきれず、断念…。 探索する局面が増えるに従ってGCで固まる時間が増えていき、プロファイラで測ってみると20~30%までにも達していて、どうしたもんか。

あとがき

  • 複雑な面以外はそこそこ解けて満足
  • ゲームルールの実装が思ったよりもだいぶ苦労した…単純な矩形じゃない可能性があるので押す処理や落下処理が案外難しかった
  • 埋め込まれたゼリーが出現する処理も相手を動かすだけじゃなく自分が動く場合もあり得る
  • 状態の複製が混乱を極めた
    • 下手に書き換えないようにRubyのfreezeが使えたのはよかった
  • 場合によってはA＊だと最短手順になってないかも？（距離推定が手抜きなので多くなる可能性があるかも）
  • BFSとA＊の切り替えがキューのオブジェクト変更だけでできるの素敵
  • 局面を上下とか左右のくびれ部分で分割して、状態数が乗算じゃなく加算にして減らせたりしないか？
  • Rubyから別言語にしたら2,3~10倍くらい速くなるだろうか？

リンク

関連記事

新着記事