PSP vitaの無料ゲーム、トレジャーパーク。
5×5のパネルのどこかに隠されたトレジャーを、ヒントを頼りに見つけ出すゲームです。（詳しい紹介はこちらなどを。）
ユーザ同士でステージを作ってnearやメッセージで交換できるのが魅力の一つ。
この手のパズルをプレイしていると、無性にソルバが作りたくなりますよね？
というわけでJavaScriptで作ってみました。
(もとは画面にメモできないのが不満で作った単なるメモ帳だったのですが、ヒント機能つけてるうちにソルバになってしまいました。)
http://neocat.jp/treasurepark-solver.html に置いてあります。
右上のフィールドにパネルの色を r(赤)/o(オレンジ)/y(黄)/g(緑)/b(青) の各文字を5行5列に並べて入力し、次いでヒントのピースの色も同様に1文字で入力します。あとはEvalボタンを押すと、次に開けるべきおすすめのパネルを教えてくれます。それを開けたら、パネルの状況を左の升目をクリックして設定し、再びEvalボタンを押す、というのを繰り返せばOK。
アルゴリズムとしては、パターンマッチでピースの位置を推定し、可能性のある配置の数を評価値としています（ただしトレジャーの候補は5倍でカウント）。次に、各パネルについて、それを開けることでどれだけこの評価値（配置の可能性）が減らせるかを求めます。何が出るかが複数考えられる場合、全てについて評価を行い平均値を求めます。これをもとに、最も早く評価値が減るパネルを次に開けるべきものとして表示します。一種の再急降下法みたいな感じ。ただし、爆弾を開けるわけにはいかないので、爆弾の可能性のあるパネルは評価値を+100したり、トレジャーやコインはちょっと評価値を下げるといった細工をしています。この辺の数値を変えてあげると、爆弾やトラップを慎重に避けるソルバになったり、トレジャーが早く絞り込めそうなら多少の危険は顧みないようになったり、性格付けが変わります。
今後の課題。パターンマッチのアルゴリズムがあんまり賢くないので、複数ピースの関係性を追いきれず、時々ありえない配置でも「あるかも」と判定されることがあります。いちおう背理法で候補をしぼったりしてはいるのですが、まだまだ。SATソルバを使えばもっと確実になるんでしょうなー。
5手以内で解ける割合はまあそこそこです。問題を作る時にソルバを使いつつ解けないように作ると、当然ながらこのソルバでは解けなくなりますが、意外と人間にはさくっと解けたりするのであんまり当てにならないのかもしれません。
ちなみに、これを使ってゲームをクリアしまくっても単なる作業でしかなく面白くないので全くオススメしません。
あ、ソルバ作るのは面白いのでオススメです。
