ICFPC 2014 参戦記 - @nojima's blog

ICFP Programming Contest 2014 に @cos65535 さん, @qwerty__ さん, @seikichi さんとチームを組んで参加した。

レポジトリ: https://bitbucket.org/kmc-ob-icfpc-2014/icfpc2014

25日(金)

21:00　コンテスト開始。問題を読み始める。
- パックマンみたいなゲームの AI を書け、という問題。
- ただしゲームの AI は GCC という謎の LISP マシンの上で動く。（それ専用の機械語が定義されているので、それを使って AI を書かないといけない）
- また、ゴーストの AI も書く必要がある。ゴーストの方は GHC というわりと普通な感じの機械語の上で動くが、メモリが 256 バイトしか使用できず、また、プログラムも 1024 命令しか実行できない。
21:30　夕食を食べに行く。
23:40　seikichi さんが到着。

26日(土)

0:00　方針を決める。
- AI を直接 GCC (与えられた Lisp マシンにおける機械語) で書くのはかなりキツい。高級言語からコンパイルしたい。
- 機械語が Lisp っぽいので Lisp からコンパイルするのが自然なのではないか。Lisp なら構文解析が楽そうだし。ということで、Lisp から GCC へのコンパイラを作ることに。
- また、与えられた機械語で配列（定数時間で任意のインデックスに読み書きもの）が実現できないことが判明する。2分木を使った配列もどきライブラリを作らないといけないという話になる。
- ということで、以下の4つの作業を分担してやることになった。
  - Lisp から GCC へのコンパイラの作成
  - GCC のシミュレータの作成
  - ゲームのシミュレータの作成
  - Lisp 用のライブラリの作成
- 自分はコンパイラを作ることになった。
2:00　GCC の仕様書を読みながら幾つかのプログラムを手コンパイルしてみる。
- DUM と RAP の意味がいまいちわからないが、一応コンパイラはなんとか作れそうな気分になる。
- 実装言語を決める。速度はどうでも良さそうなので Python にした。
5:00　構文解析まで実装終了。寝る。
11:00　起きる。
13:00　(+ 1 1) がコンパイルできるようになる。

15:00　define の実装でつまる。

以下のコードをどうやってコンパイルしたらいいかわからない。

;; カリー化された add
(define add (lambda (x) (lambda (y) (+ x y))))
; 部分適用
(define inc (add 1))
;; 42 が返る。
(inc 41)

16:00　DUM で予め領域を確保しておき、後から ST でクロージャを入れていけば define が実装できることに気付く。
- lambda の中で define してもちゃんとレキシカルスコープ的に正しく動作する。
17:00　lambdaの実装が完了。
17:20　ifの実装が完了。
17:30　ラベルをアドレスに変換する部分を実装し、Lisp コンパイラが完成。
20:30　seikichi さんが Lisp でそれっぽい AI を実装し、ライトニングラウンドにサブミット。

27日(日)

土曜日の反動でだらだらしてしまった日。

0:00　seikichi 先生が Gauche の macroexpand を使ってマクロを展開してからコンパイラに投げるプログラムを書く。
- これにより、define-macroで簡単に構文を拡張できるようになる。
- let, and, begin, cond などのおなじみのマクロが自由に使えるようになる。
- さすが Lisp …。
1:30　末尾関数呼び出しの最適化を実装。
2:00　寝る。
10:00　起きる。
14:00　コンパイラのデバッグ + (define (foo x y) ...) のような構文の実装。
- かなり普通の Scheme っぽく書けるようになってきた。ぱっと見では見分けがつかない。
15:00　コンパイラでやることがなくなってきたので、GCC のシミュレータのデバッグを手伝う。
18:00　GCC のシミュレータが動くようになる。
- cos さんが作ったゲームのシミュレータと合わせると、Lambda Man の AI を動作させる環境が完全に揃ったことになる。
20:00　再びやることがなくなってたので AI の作成を始める。
21:30　BFS をする AI を書いた。が、バグっていて動かない。
22:30　Scheme の関数の引数の数を間違っているところがあったのを修正。
- 単純なバグのデバッグに時間がかかりすぎるので、コンパイラを修正して関数の引数の数を間違えたらコンパイルエラーになるようにした。
22:30　ゴーストが弱い場合はマップをクリアできるようになった。
- AI は動くようになったがやけに重い。最初はシミュレータのパフォーマンスが悪いのかと疑ったが、実はそうではなく、BFS の実行に時間がかかりすぎているようだった。
- 32x32 程度のマップを BFS するのに 170 万命令かかっていた。AI の 1 ステップの命令数の上限が 300 万命令程度なので、これはかなり危ない (というか 256x256 のマップが来たら即死する）状況だということを認識する。
- とりあえず、適当に最適化をしてみたが、ほとんど改善しなかったので、qwerty さんにプロファイラの実装をお願いする。

28日(月)

2:00　プロファイラのおかげで組み込み関数の呼び出しに時間がかかっていることが判明したので、コンパイラを改造して最適化。
- この改修で 170 万命令 → 140 万命令。
- 次のボトルネックはvector-refだが、作者が寝てしまっていたので、放置して寝ることにした。
8:30　起きる。
10:30　seikichi 先生がひたすら関数をマクロでインライン展開する。
- 140 万命令 → 40 万命令。
11:00　移動
13:30　BFS AI のループ回数に上限をつけた。これで 256x256 のマップでも一応動作するようになった。
14:00　近くにゴーストがいるときはゴーストからに逃げるようにした。
- これで結構 AI っぽくなった。
14:30　ゴーストを殺せるときは殺しに行くようにした。
18:40　方向にスコア付けして一番高いスコアの方向に行くようにした。
- 複数のゴーストに同時に襲われたときに逃げられる確率が上がった。たぶん。
- Lambda-Man Hall of Fame の ghostbusters でランクインした。
19:00　cos さんがいつの間にか DFS をするゴーストの AI を書いていた。
19:45　フルーツを食べに行くようにした。(by seikichi 先生)
20:30　パラメータの調整など
20:50　AI 提出！！

まとめ

最初はどうなることかと思ったが、意外とまともな AI を書けたような気がする。
- やはり高級言語は偉大。
- あと macroexpand 偉い。
プロファイル大事。
コンパイラのエラーチェックを真面目に作っておいたおかげでデバッグコストが結構低かった。
qwerty さんの予約してくれたホテルが快適だった。環境大事。