パズドラ問題

ちょっと前のことですが

友達がパズドラのサポートをするようなアプリを作っていたので

僕も楽しげなところだけ作らせてもらいました。

公開する気はないようなのですが

GUIまでわりとちゃんとつくっていました。

よくある大学の課題みたいなものなので

思ったよりよくできたので解き方を紹介。

まじめにやるとすごく難しくて時間がかかるので

簡単にできるところだけ作ってみた感じです。

もっとよい方法があったら意見いただけるとうれしいです。

解の可視化

なにはともあれ見えるようにします。

これはもう最終形態なので作っていく過程はないのですが

盤面を貰ってpath( 座標の配列 )を返す感じ。

乱数で盤面を作って結果を表示します。

方針

基本は木構造の探索と盤面評価

来た方向にもどらないとすると1手は3種類

最初は30種類なので

10マス動かすのに30*3^10=177万通り

枝狩りしない全数探索だとこれくらいが限界

ただ10マス動かしただけだとちょっと短すぎます。

外周2週で20マスくらいなので40マスくらい動かしたいところ。

横型探索すると枝狩りしやすいのですが

メモリを食うので縦型探索で掘っていきます。

一手を曲がらずに動かせる直線とみなして

1マス動かすごとに盤面評価して終わったら元に戻します。

ただこのやり方ではPCで10秒くらいを目安とすると

ざっくり8手の探索が限界です。

直線で進めるのが平均2.5マスとすると20マスくらい。

まだちょっと足りないのでやっぱり枝狩りは必須。

ここらで携帯に入れたところ処理時間がPCの10倍かかることが判明

1秒以内で解を出すのを目安にしました。

1手ごとに一定の深さで探索して最適解以外を全て削除。

探索のコストをO(n)に絞ります。

結果として毎回深さ6で探索して20手くらい掘ることにしました。

盤面評価

とりあえず簡単に隣り合う二つの石が自分の隣だったら加点

あとは同じ色が一箇所に集まるように

色ごとに重心を出してそこからの距離の総和が遠いと減点することにしました。

 開始位置

これが重要なのですが全部の点で同じ事をやると30倍時間がかかるので

同じ色が3つ以上合ってそれが重心から遠くにあるものを動かすようにしました。

 

チューニング

corei7のPCに比べてexperiaの最新版は約30倍遅い。

最終的にPCで3秒くらいの探索が携帯で90秒かかりました。

探索の葉の部分と評価関数で配列の初期化を全部なくしたら

それだけで10倍くらい早くなりました。

配列をnewするとすごく遅いんですね。

雑感

携帯が高機能になったといってもやっぱりPCに比べると遅い

newはすごく遅い

市場に同じようなアプリはあるんですが

やっぱり作ってる人はすごいですね。

あと意外と人間は賢くて状況に応じた解を出すのは

すごーくめんどくさそうです。

友達がもう少しやる気になったら改良しようと思います。