GDD2011, DevQuizのスライドパズルの解答コードを公開しました

Google Developer Day DevQuiz スライドパズル

去年の話になりますが、Google Developer Day 2011(GDD2011)に参加するために、DevQuizに挑戦しました。
お分かりの通り、開催されてから1年以上は経っているのですが、つい最近になって探索アルゴリズムの復習でもしようと思って(研究とは全く関係ない…)、もう一度初めからDevQuizを解き直してブログを書くことにしました。参加してた時に書けよっていうツッコミは勘弁して下さい… あれから時間はかなり経っているとは言え一度やっている問題だからなのか、少しプログラミングの腕が上達しているからなのか、去年よりも少し短い期間で、しかも6つの探索アルゴリズムの動作を比較できるくらいまでに実装できてしまいました。

■DevQuiz
さて、そのDevQuizについてですが、去年の問題の構成は、

問題

  • ウォームアップクイズ
    • クイズ：40点
  • 分野別クイズ(最大2問が得点に加算)
    • Web Game：30点
    • Go!：30点
    • Android：30点
    • Google Apps Script：30点
    • 一人ゲーム：30点
  • チャレンジクイズ
    • スライドパズル：50点

となっており、全部で合計150点満点だったのですが、その中でも一番難しかったチャレンジクイズの「スライドパズル」について、今回は自分の解答を公開したいと思います。

■スライドパズル
スライドパズルの問題について説明しておくと以下のようになります。

  • 幅3〜6、高さ3〜6マスのボードが与えられる
  • ボードの各マスには、パネル、壁、空白のいずれかが存在する(壁は0個以上存在)
  • パネルは1〜9あるいはA〜Z、壁は=、空白は0で表記される
  • 空白は上下左右のパネルと入れ替えられるが、壁とは入れ替えられない
  • 空白を上下左右のパネルと入れ替えることをそれぞれU, D, L, Rと呼ぶ
  • ゴールの状態は、左上から右下に向かって1, 2, 3, ..., 9, A, B, ..., Zのパネルが順番に並んで、最も右下のマスに空白が配置された状態
  • 与えられた初期配置をゴール状態の配置にまで移動させる解をU, D, L, Rの文字列で解答する
  • 問題数は全5000問で、パズルを1問解くごとに0.01点が加算される(つまり全問解くと50点になる)
  • 解答に使えるU, D, L, Rの総数にはそれぞれ上限があり、いずれか一つでも超えていた場合には0点となる

■探索アルゴリズム
先ほども述べたように以下の6つの探索アルゴリズムを実装したので、それぞれについて簡単に説明したいと思います。

・幅優先探索
幅優先探索ですが、最初に見つかる解が必ず最適解(最短手数の解)になるという手法です。全ての局面をまじめに探索するために計算時間が長くなってしまうだけでなく、局面をインデックス化して保存する場合にハッシュ値に変換しておかないと、ボードのパネル数が増えた場合に当然メモリが足らなくなってしまいます。おそらく普通にこの手法を使った場合、3×4あるいは4×3の11パズルを解くのが限界だと思います。

・双方向幅優先探索
双方向幅優先探索ですが、先ほど述べたように幅優先探索では膨大な計算時間が掛かってしまうので、スタートから探索するだけでなくゴールからも探索を行うことで、高速化を実現しようとする手法です。まだちゃんと試していないのですが、この手法なら4×4の15パズル以上を解くことも可能だと思います。

・深さ優先探索
深さ優先探索ですが、これは別名「山登り法（hill-climbing method）」とも呼ばれ、幅優先探索のように全ての局面を保存するなどせずに、ゴールまでの距離（コスト）を示す何らかの評価値に従って、常に評価値が高くなるように次の局面状態を選択します(ヒューリスティック探索)。局面を保存する必要がないためにメモリ消費量は少ないのですが、運悪く探索が行き詰まってしまうと最短手数で最適解に辿り着けなくなるだけでなく、極大値などが存在すると真のゴールに辿り着くことができなくなってしまいます。

・反復深化深さ優先探索
反復深化深さ優先探索ですが、深さ優先探索ではメモリの消費量は少ないのですが、最初に見つかる解が最短手数になるとは限りません。そこで、深さ優先探索の「深さ」に上限値を設定して、解が見つかるまで上限値を段階的に増やしていこうとする手法です。ただ、お分かりのように同じ探索を何度も繰り返すことになるため計算時間が増大します。そのため、枝刈りによって下限値を上手く設定することでパズルを高速に解く必要性があります。

・A*探索
A*探索ですが、深さ優先探索では局所的な局面状態の中から評価値の高い状態を選んで次の探索を進めますが、スタートから現在地点までのコストは考慮していません。そこで、A*探索では、現在地点に到達するまでのコストと、そこからゴールまでに推定されるコストに基づいて次の局面状態を選択しようとする手法です。詳細な証明は割愛しますが、この時にある条件を満たしていると、最初に見つけた解が最適解になります。おそらく今まで説明してきた探索アルゴリズムの中で一番良い手法だと言えます。

・双方向A*探索
双方向A*探索ですが、幅優先探索と同じようにA*探索でもスタートとゴールの双方から探索する手法が適用できます。これにより高速化も実現できます。

■隣接行列と隣接リスト
隣接行列や隣接リストは、あるマスが次にどのマスに移動可能であるかを示した行列やリストです。隣接リストの方が消費するメモリが少ないのですが、今回は隣接行列を用いて、5×5のパズルにまで対応できるようにしています。本来なら前の局面状態から次に移動できるマスが分かると思うので、おそらくスマートな手法ではないと思いますが…

■ヒューリスティック関数
深さ優先探索などで用いる評価値についてですが、最も有名なマンハッタン距離(全部のマスの最低限必要な手数の合計値)を評価値として利用することにしました。他にも下限値枝刈り法に利用できる評価値として転倒距離があります。まず転倒数と呼ばれる数字の並び順が逆になっている数を数えて、それを用いて最低限必要な上下動回数と最低限必要な左右動回数を計算します。それらの値を足し合わせたものが転倒距離になります。最終的にマンハッタン距離と転倒距離を比べてより厳しい方の値(大きい値)を下限値として採用するようにします。

■下限値枝刈り法
必要となる最低限の手数が明確に分かっている場合には、この手法は探索の計算時間に非常に大きな影響を与えます。パズルを解くのに最低限必要な手数を求めて、これを下限値として利用することにしました。1回に1つのパネルしか移動しないので、初期状態の下限値を求めておいて、動かしたパネルの差分だけ計算して下限値を更新するようにしています。

■その他
他にも、自作のハッシュ関数だったり、手数制限だったり、工夫していることはいくつかあったと思うのですが、思い出すのと説明するのがメンドイので気になる人はソースコードを見て下さい。

■ソースコード
解答コードはgithubに公開してあります。
PythonのようなLL言語でも良かったのですが、今回は実行速度と省メモリの観点から開発言語はC++を選びました。
https://github.com/Goto-youthK/search_algorithm/tree/master/devquiz_2011/slide_puzzle

ファイル名と探索アルゴリズムの対応は以下のようになっています。

コードの解説は中にコメントとして記してあるので、それを参考にして下さい。

■参考にしたページ
ホームページ移転のお知らせ - Yahoo!ジオシティーズ
１５パズル自動解答プログラムの作り方
blog.k11i.biz: GDD2011 DevQuiz のスライドパズルに挑戦してみました
DevQuiz 2011 - Coding Memorandum

今年はなぜかGDD2012はなかったのですが、来年はあるといいですね。
次はもう少し高得点を狙えるように頑張りたいです！！！