ICFP初日

5 Jun
20040619-IMG_0962.JPG

プログラミングコンテストICFP2004が5日の午前1時からだったから、4日の夜に学校に行った。

左の写真はたぶん初日にとったもの。

コンテストの詳しい内容は続きで。整理して書きます。

作業全般:
全てICFP時間で書きます。(コンテスト開始後の経過時間)

5日午前1時、問題発表。英文で15ページもあった。問題発表ページが重くなったりもしたけど、たくさん印刷してみんなで読んだ。
簡単に言うと、アリの本能を設計して、他人のアリと戦ってより多くのエサを自分の陣地に持って帰った方が勝ちということらしい。

アリの本能を記述するステートマシンの文法は書きにくくて、とてもじゃないけど知能を書く事なんてできそうにない。

2時(午前3時)くらいのミーティングまでにだいたい何をすればいいかが分かった。
・シミュレータ作成
これは必須。
それから、アプローチとしては
・アリの本能を表すステートマシンを出力するコンパイラの作成
・手でがんばって書く
・遺伝的アルゴリズムで生み出す
・手で書いたもののムダを省くオプティマイザを作る。
ってところだろう。
順にやっていく事に。
大急ぎでU野とシミュレータの仕様を決めて、各班に仕事を割り振った。
徐々に出来上がってきて、S藤のJavaグラフィック能力のおかげで地図を拡大したりもできるっぽい。そろそろ眠い。
問題はシミュレータの精度。想定されている動きと違ったらまずい。途中経過を全部出力して、コンテスト主催者側から提供されている経過と比較しないと。
でも、この辺でぼくは2時間くらい睡眠へ。

起きたら、シミュレータが完成していた。気になっていたシミュレーション精度は完璧だったらしい。途中経過を記録したテキストファイルは40MB(テキストファイル40MB!)あったけど、それが完全に一致したらしい。すばらしい。
C班の努力に感謝。バグがなかったのはペアプロのおかげか?

シミュレータができたので次はアリの本能を書くためのプログラミング言語の設計へ。
とりあえずは逐次処理ができるように。前命令に次に処理する行番号をつけるなんてとんでもない。必要なところにはラベルをつけてジャンプするように。それから、関数化とループができるように。その時手の空いていた数人で仕様を決めたけど、プログラミング言語の使用を決めるのはなかなか面白い。
FUNCTION foo
bar
ENDFUNCTION
とか。昔VisualBasicをやっていたのが見て取れる(笑)

16時くらいまでにコンパイラ完成。T橋さんによってA++(アリ++)と名付けられた。人数が多いだけあって、仕事の随所にギャグが練り込まれている。

これでやっとアリの本能を書きはじめられる。

T見がA++の弱点を克服したいと強く主張してA班は新たなる言語APPngの開発へ。

20時くらいまでにはいくつかのアリが誕生。K岡製の異様な速さで動くけど、途中からムダな動きしかしないアリfastverや、T橋さん製の食料をまったく取りにいかずにせめて来た敵を倒して食料にするだけのnianなど。

24時にlightning division。すなわち、途中(1/3)の時点での結果も競おうというもの。これを出して、一段落。

コンパイラに関わっていないC班によって自分の巣の方向をマークしながら歩くアリmark012やその改良版fast012が生み出されたり。
コンパイラの中心部を作っているA班はS藤が家に帰ったまま来ない!しかし学校にいた2人が黙々とコンパイラ作成作業を継続。B班はコンパイラのパーサー(構文解析)部分の精度を向上させていく。
ぼくとU野(D班)はアリの本能をプログラムしやすいように、ツールを作る。シミュレーターの機能向上やらなにやら。

A++の関数ライブラリを構築するためにAFLの仕様とコーディング規則を決め、B班にパーサーを改良してもらって関数の再利用を可能に。でも、実際にコーディングしているA班から関数化は無理との報告があり、アリの行動の種類1つ1つをライブラリとして登録する方式に変更。

敵の陣地を囲んでしまい、相手が自分の巣に戻れないようにするfirewallアルゴリズムや、逆にfirewallから自分の巣を守るmyfirewallなどのアルゴリズムが提案、実装される。

36時すぎ頃、APPngが完成して、当然の如くA#と命名された。それに伴って特殊なマークの付け方をするアリmarknetの仕様を考え、C班が開発を担当。B班はA#パーサーを改良しながら、ありの団体行動の可能性を研究。A班はやっとJavaから抜け出してアリの行動を記述してみはじめる。D班は遺伝的プログラミング手法によるパラメータ設定(オプティマイズ)システムAMIの開発へ。

48時。2/3が終わった。A#のバグもほとんどなくなり、究極のアリと考えられたmarknetが完成に近付いてきた。AMIは64-100台のコンピュータが強調動作するシステムなので、ぼくは必死で100台にloginしてサーバー側ソフトを実行。パスワードを打つのが速くなった;この頃3時間ほど睡眠。さすがに眠すぎた。

60時。marknetは完成し、集団行動についてもnianの改良やroundなどある程度研究成果がでてきた。A班による超高速firewall形成種dragonwallが登場。でも、そろそろ提出物のドキュメントを書いたり、資料をまとめたりしなくちゃ。遺伝的アルゴリズムは実験してみてもなかなかいい結果がでないので、総当たり方式に変更した新システムAMI2を開発。そろそろ睡眠時間が足りな過ぎで、自分で書くより他人に説明して書いてもらった方が早いという状況に。

70時頃までにはだいたいの作業が完了し、提出する事に決まった種marknettrinianとnianhikkyの最後の改良やオプティマイズが行われた。T見のツールのドキュメント作業も終わり、構成作業も完了。

71時45分。やっとの思いで提出。つかれたー。

Leave a Reply

Your email address will not be published.