Google Developer Day 2011に参加するための DevQuiz というクイズがあるのですが、それを解いてみました。
今年の問題は、
- ウォームアップクイズ(4 択問題)
- 分野別(4 問あって、うち 2 問を選択)
- チャレンジクイズ(5000 問のスライドパズルをひたすら解く)
という 3 本立てになっていて、スライドパズル以外は満点であたりまえ、スライドパズルをどれだけ解くか、という勝負でした。
で、どうだったかというと、いろいろトラブルがありつつも、なんとかスライドパズルを 1472 問解いて、ボーダーラインは超えたようです。
どんなトラブルがあったかというと、
- 解の判定処理がバグってて、3x3 しか解けない
- 締切 24 時間前ぐらいにメインの PC が起動しなくなる
- 盤面の評価関数がバグってて、ヒューリスティックが働かない
という感じでした。特にメイン PC が壊れたときは、どうしようかと思いました。 結局 Amazon EC2 で c1.xlarge インスタンスを作って、2 時間だけ回してパワー不足を補いました。
また、途中まで全然計画とか立てずに、闇雲に探索していたので、それでかなり時間をロスしていました。 盤面が小さい、解きやすい問題から解いていった方が良かったです。
今回の反省点は、
- 問題をよく見て、戦略を練ってから問題を解くべき
- 基本的な部分にバグがあると後で困るので、十分にテストしておく等で対処するべき
という点でした。
やっつけなコードですが、一応アップしておきます。 探索は、深さ優先の反復深化でやってます。 A*も試したんですが、 今回のデータ構造だと Open リストが膨れてしまい、メモリに乗らなくなる感じでした。
もうちょっと時間があれば、データを切り詰めたり(std::string 使ってる時点でありえない)、 評価関数を凝ったり、いろいろできたとは思うのですが、まあ、こんなもんかなーと。