日々の流転

λ. ICFP Programming Contest 2012 “Lambda Lifter”

連休中は ICFP Programming Contest 2012 を割と頑張ってた。 いつものメンバーのTeamSampouで参加(使用言語はHaskell)。 今回は仕様も簡単でとっつきやすくて良かった。が、結局今年も大したことはできなかったけれど。

• レポジトリ: <URL:https://github.com/msakai/icfpc2012>

今回は昨年の田中さんたちを真似て、githubのプライベートレポジトリを使ってみた。(コンテスト終わったので、公開済み)

概要

問題文

採掘ロボのプログラムを書く問題で、2次元のマップが与えられていて、穴を掘ったりして地中にあるラムダをすべて回収して、ゴールに移動するのが目的。ただし、障害物として岩があって、下が安定しない岩はある規則にしたがって下に落ちたり転がったりして、岩の下にいると潰されて壊れたり。岩の下を掘ると岩は不安定になるし、あと岩を押して動かしたりもできる。 問題文を読んで(& そこで使われているレトロなドット絵を見て)、ディグダグと倉庫番を連想。といっても、どっちもちゃんと覚えていないので、どれくらい似てるのかは良くわからんけど。

戦略

色々考えていたことを、忘れないうちにメモしておくく。

最初に考えたこと

• 最初に漠然と考えたこと

  1. スタート地点と各ラムダとゴールの間の距離を(貪欲法なりなんなりで)近似計算
  2. 巡回セールスマン問題を解いて回る順番を決める
  3. その上で岩に潰されたりしないよう経路を局所的に調整

  ただ、サンプルのマップをみると、結構パズル的要素が強く、局所的な調整では調整しきれないだろうなぁという印象だったので、断念。

• 次に考えたのは、岩を動かしてパズルを解くのが倉庫番に似ていて、倉庫番はPSPACE完全で、同じくPSPACE完全な QBF satisfiability のソルバ(QBFソルバ)を使って解けないかというもの。ただ、ググってみてもQBFでパズルを解いたりとかいう情報はあまりなかったので、断念。
  • 参考: QBF Solver Evaluation Portal

実装した戦略

• ランダム
  • ランダムは制限時間までランダムなプレイをひたすら生成して、一番スコアの良かったものを返す
  • 本命ではなく、あくまでチームメイト向けのアルゴリズムの書き方のサンプルというつもりだったので、あまりやる気なかった。
  • とりあえず1ステップ先読みはして、1ステップ後に壊れるやつは選ばないように
• 幅優先
  • 部分タスクではなく全体を幅優先で探索するやつ。当然だけど、メモリを食い尽くして死ぬ。
  • これもサンプル的に書いたつもり。あと、後で部分タスクを解く部品として再利用するつもりだったけど、結局使わずじまい。
• 深さ優先で一番近いラムダに向かうやつ
  • これもサンプル＆後の再利用向けに書いたけど、結局使わず仕舞い。
• モンテカルロ木探索的なもの。
  • 割と本命だったんだけど、うろ覚えで書いたら、うまくいかず。

モンテカルロ木探索的なものを書くのに時間がかかってしまって、その割にうまくいかず、結局ランダムなやつが一番成績が良かったので、それを投稿。 なんか最近こういうパターンが多い気が……

ただし、時間切れ直後にトランポリンへの移動をすべて枝刈りしてしまっているというアホなバグが発覚…… orz

実装したかったこと

実装したかったけど、できなかったこと。 実装しようと思っていた順。

1. 複数アルゴリズムのポートフォリオ
2. AI/CSP的アプローチ、プランニング
   • conflict analysis と nogood の学習
   • うまくいった手筋の記憶と再利用。うまくいった手筋の「事前条件」を解析しておいて、盤面がそれを満たすならそれを優先的に試すなど
   • 最初のタスクの集合は、スタートと各ラムダとリフトの間の移動としておいて、あとはconflict analysisの結果から、タスクを追加
3. SAT(やPBO)で有界モデル検査(Bounded Model Checking; BMC)
   • conflict analysis とか学習とかしだすと、自分で書くよりもSATソルバの内部に実装されているものを活用した方が速いのではという発想。SATソルバ速いし。
   • ただ、「各ステップの各セルが各種類」という風に変数をとると、共通の原因であってもステップが違うと違う補題になってしまって、学習結果の再利用が効かなそう。エンコードの工夫をしないといけないかも。(良く知らないんだけど、SatplanみたいなSATベースのプランナーは、その辺りを考慮したエンコーディングをするのかな？)
   • 完全なソルバを使うことしか考えてなかったけど、今考えるとwalksatやGSATみたいな不完全なソルバを使う手もあったかも。
4. GA等のメタヒューリスティクス
   • 詳しくないので自分には難しいだろうと思い断念してた。

反省?

今回のは、少なくとも以下の5人くらいで分業できると良かったのかなぁと思った。

1. シミュレーターの改良(高速化と新仕様の取り込み)をする人
2. 盤面の評価関数やスコアの上界値計算を書く人
3. 部品としての探索アルゴリズムを書く人
4. 部品を利用した上位の戦略を書く人
5. 人手で問題を解いて、色々考えたり、同時にシミュレーターのバグを見つける人

アホなバグの件に関して思ったこと:

• バグの箇所は最初に書いたっきりずっと使ってなくて、仕様変更への追従漏れしてて、後半に使いだしたため。こういう使ってないコードはいっそ消すかコメントアウトするかしておいた方が、変更漏れしたまま使ってしまう危険を避けられるのかなぁ。
• シミュレーターに関してはHUnitを使った簡単なテストをしてたんだけど、問題のあった箇所はシミュレーターでは使っていなかった箇所だった。また、探索アルゴリズムについては、最初のころに書いていたのはサンプルくらいのつもりだったので、テストを用意していなかったし、終盤は逆にテストを書いてる余裕がなくなってしまっていた。