Google Developer Day 2011 に参加するために、DevQuiz に初めて挑戦してみました。ウォームアップクイズ、分野別クイズはさておき、一番やりがいのあった「スライドパズル」について、自分の戦略などを書き残しておこうと思います。
ソルバーのソースコードは、http://code.google.com/p/k11i-gdd2011jp-slidepuzzle-solver/ にて公開しています。
言語
- 回答期限までそこそこ時間があった
→コーディングに多少時間がかかっても OK。
- 計算・空間効率を追求する必要がありそう
→言語自体の実行性能が高いこと。またある程度、内部の挙動を把握できる、かつ効率化のポイントを把握していること。
などの理由により、開発言語は Java を選びました。
ソルバーの戦略
ソルバーのプログラムは「ただひたすらにパズルを解く」ステージと、「利用可能な L/R/U/D の上限値をもとに、前ステージで得られた答えを取捨選択する」ステージに分けました。
パズルを解く戦略
「ただひたすらにパズルを解く」ステージは、当初から探索ベースの手法を前提としていろいろと試行錯誤した結果、「A* アルゴリズム」と「双方向探索」を組み合わせた実装となりました。この二つのアルゴリズムの組み合わせは、M.Hiroi さんの Algorithms with Python / ヒューリスティック探索 のページ内容をかなり参考にさせてもらっています。
この「A* + 双方向」の組み合わせでは最適解（最短手数）を求めるのが難しいのですが、それぞれを単体で利用する場合よりも圧倒的に速く問題を解くことができる（たいていの問題が 1 秒以下で計算可能）特徴があります。
A* アルゴリズムに限りませんが、幅優先的な探索アルゴリズムはメモリを富豪的に使うので、何も制御せずに問題を解かせると OutOfMemoryError をスローしてしまう可能性があります。今回のソルバーでは、展開される状態数に上限値を設けて、その上限値に達したところで解の計算を諦める制御ロジックを組み込んでいます。
A* アルゴリズムのヒューリスティック関数には、「マンハッタン距離」を用いています。ただ、壁の存在があるため、実際には単純なマンハッタン距離ではなく、壁を回避してたどり着く最短経路での手数を距離としています。なので、壁が一つもなければ、常にマンハッタン距離と等しくなります。
回答を選ぶ戦略
算出された各問題の答えの集合から実際に提出する回答を選ぶ処理は、貪欲なロジックで実装しています。つまり、既定の L/R/U/D 利用上限値をすべて下回るまで、L/R/U/D それぞれの利用が多い答えを捨てる仕組みとなっています。しかしながら、今回のソルバー/実行環境では、この機能が実行されることはありませんでした…
処理効率の最適化
上記の戦略に基づくソルバーをそこそこの性能の PC で実行して、40 点前後のスコアを 1～2 時間で獲得することができました。もう少し高いスコアを目指すために、これより先はひたすらアルゴリズム以外の最適化に手を尽くしました。
状態保存の空間効率向上
当初のソルバーでは、盤面上のパネルの配置状態を 1 つのパネルにつき 1 バイト消費するようにしていました。しかし実際には、最大の 6x6 パズルにおいて 1 パネルの配置状態を 6 ビットで表すことができます。このため、4 バイト（32 ビット）で 5 つのパネルを表現するように実装を改めました。これにより、6x6 = 36 バイト必要だった盤面の状態表現を、約 4/5 の 32 バイトで表現できるようになりました。
また盤面のパネル配置状態のみならず、付随的な複数の情報（双方向探索の探索向きや、手数、距離コスト）も、（C でいうところのビットフィールド的なアプローチで）1 つの 32 ビット数値で効率よく表現するようにしました。
ハッシュ値の計算効率化
パネルの配置状態をハッシュ表（HashMap）に記録して探索の重複チェックを実現していたので、上記の 4 バイトで 5 パネルを表すようにする改修に合わせて、ハッシュ値の計算を 1 パネルずつではなく 5 パネルまとめて計算するようにしています。また、一度計算したハッシュ値はキャッシュすることで、ハッシュ値の計算コストを低く抑えるようにしています。
ライフサイクルの短いオブジェクトを再利用する
オブジェクトの生成は Java にとってそれなりにコストのかかる処理なので、いったん生成してすぐに不要になってしまったオブジェクトを再利用する（フィールドだけごそっと入れ替える）仕組みを組み入れました。もともと immutable に実装したクラスを無理矢理こじ開けて mutable にしたりと、あまり気持ちのいいものではないですが。
ハッシュ表を自作する
Java クラスライブラリの HashMap は汎用的に作られているため、今回のソルバーとしては余計な機能が付いていたり 1 エントリあたりのヒープ消費に Map.Entry が加算されてあまりうれしくないので、HashMap を簡略化したものを開番地法で実装しました。これにより計算効率と若干の空間効率の向上が達成できます。
古臭い・妖しいコーディング
「for (int i = 0;...) が許されるのは JDK 1.4 までだよねー」とか言われかねなけど、for-each 文を使わなかったり、オブジェクトの等価判定に == 演算子を使ったり、メソッドのインライン展開を狙って final 修飾子をつけてみたりしました。効果のほどは定かではないですが。
JVM を 64 ビット化
32 ビットの JVM では、利用できるメモリ空間が小さいため、Java の環境を 64 ビットの JDK に差し替えました。これにより 8 GB の物理メモリ＋ページファイルのサイズ分、ヒープを確保することができるようになりました。また、計算効率も 32 ビット版に比べて心なしかよくなったように思います。
そのほか試してみたこと
ヒューリスティック関数の(デ)チューニング
A* のヒューリスティック関数を前述のマンハッタン距離ベースのものから、パネルの位置によって重みを加えてみたものに変えてみたり、距離を +1 してみたりと、試行錯誤してみました。特に距離 + 1 のヒューリスティック関数は、通常のマンハッタン距離のものよりも早く答えを見つけ出せる（代わりに手数は多くなる…）など面白い結果が確認できたのですが、処理時間が遅くなるなどの理由で結局採用しませんでした。
Simplified Memory-bounded A* (SMA*) への差し替え
ヒープの大量消費がソルバーの悩みの種だったので、コアとなる探索アルゴリズムを SMA* に差し替えようと検討してみました。しかし、答えを出力するための履歴をどのように保持するべきかが把握できなかったのと時間的制約により、あえなく断念しました。
Java VM のパラメータチューニング
JVM を 64 ビット化してヒープをよりたくさん利用できるようになったものの、オブジェクトポインタも 4 バイト→ 8 バイトになっているようで、オブジェクトを大量に生成した場合にかなりの勢いでヒープを大量消費してしまう様子がうかがえました。JDK 6 のいつかのバージョンからか、オブジェクトポインタを圧縮できる仕組みが備わったようで、それを有効化（-XX:+UseCompressedOops）してみましたが、結果は変わらず。仕方がないので、ページファイルを利用してヒープ領域の拡大する方向に突き進みました。
やり残したこと
マルチコア化
ソルバーの調整については終始、計算効率を気にしながら行っていましたが、その割にマルチコア CPU を一切有効活用せず、シングルコアでひたすら頑張る構成にしてしまったのがちょっと残念でした。すべてのコアを活用できれば、2～3 割は速くなったはず…
人間的なアルゴリズムで解く
メモリの大量消費するような問題を解く場合、人間的なアプローチで問題を完全に解く、あるいは上・左半分など途中まで解く（以降は A* + 双方向で計算する）アルゴリズムを組み込めばよいのでは？ と考えていたのですが、「壁」の存在によりこのアルゴリズムを一般化することができませんでした。
最終結果・感想
最終的に物理メモリ＋ページファイルで 20G のヒープを構成して実行し、4832 問を 3 時間ちょっとで解けるまでになりました。メモリさえあれば、5000 問全問解くのも難しくはなさそうです。メモリさえあれば…。でも、この結果には満足しています。A* アリゴリズムとか、大学の講義で聞いただけで業務で使うことなんて今まで一度もありませんでしたが、実際に触れてみるとなかなか楽しいものです。機会があれば業務でも使ってみようかな？ ないと思うけど。
