Hatena::Grouptopcoder

not's memo

 | 

2014-07-30

ICFPC2014参加記

23:25 | はてなブックマーク - ICFPC2014参加記 - not's memo

Nakachan+3というチームでICFPCに参加してました。

チームメンバは@kawatea03、@not_522、@pepsin_amylase、@simezi_tan、@wistery_k、@y3eadgbeです。強い(確信)

コンテスト中の様子

・1日目

コンテスト開始直前に某I研に集合。

コンテスト開始。問題文くっそ長い。

どうやらパックマンAIを書くらしい。ゴーストAIは追加来るなーみたいな話をする。

問題文をだいたい読み終えたのでamylaseさんに全体のシミュレータを任せる。

GCCのプロセッサをkawateaさんに任せる。このプロセッサは結局最後まで一度もエンバグしなかった。やばすぎ。

wisteryさんはゼミがあって寝不足だったらしいので先に寝てもらう。

GCCについてコンパイラ作る?どうする?みたいな話になる。

スタックマシンでtiny-Cを書くって課題がネットに転がっててコードの一部が公開されてたので、y3さんがそれでなんとかしようとする。

とりあえずGCCでタプルをスタックに積むコードを僕が書く。

y3さんがn回挫折した後、何とかなりそうとのことなので頑張って書いてもらう。

コンパイラが律速になってるけど、僕には分からない世界の話なので早めに寝る。

起きたらコンパイラもうちょっとでできそうみたいな話になってる。すごい。

朝食後y3さんが寝てsimeziさんとwisteryさんが配列とタプルの実装をしていた。

僕のやることが無くなってきたのでてきとうにビジュアライザをJavaで書く。半分寝ながらだったので3時間くらいかかった。

ついにコンパイラが完成したらしいのでいろいろ書いてみる。いろいろバグってる。

何とか書けそうだったのでAI書いてみたら途中でGCCのコードが消える謎バグに遭遇。

2時間くらい格闘した後、ネットに落ちてたコードが200命令までしか対応してないことが発覚…。

ギリギリ提出までいけるか?というところまで行ったけど、結局間に合わず、lightning divisionは正の点を取れなかった…。

・2日目

とりあえずAIのデバッグを進める。

lightning division終了後2時間でsampleクリアに到達。惜しかった…。

追加仕様は予想通りGHC。あまりに予想どおりなのでさらに追加が来るのかなぁとか考える。

とりあえずGCCからGHCを解釈するのは無理でしょという結論になる。

amylaseさんはシミュレータのGHC周りの実装、y3さんとwisteryさんがGCCコンパイラの修正、kawateaさんはTCOをしていた。simeziさんと僕は就寝。

(これ以降、コンテスト終了後まで僕はほとんど寝ていない)

起きてからビット演算を四則演算で処理できることを示したけど、やっぱりGCCからGHC読み込むのは非現実的だよなぁという話になる。

とりあえず生GHCを書いてみる。

if文くらい欲しいなぁと思ったのでインタプリタを書く。

while文とかrand関数とかも作る。

夕方ごろにkawateaさんが戻ってきてゴーストのAIを書いてくれる。

kawateaさんのコードを見ながらインタプリタを改良する。変数とか演算子とかを使えるようにする。

いつの間にかBASICもどきみたいなものが完成していた。

そのころ、コンパイラ係はGCCコンパイラのどうでもいい改良を行っていた。

simeziさん「GCCプリプロセッサ(を自作して)使えば?」

y3さん「(GNU C Compilerのプリプロセッサ使うのか。)しめじたん頭いい!」

というわけでdefineとかincludeとかできるようになって、repマクロが使えるようになった。どうでもいい。

コミットログ「bunmei no shouri」

まぁ2次元配列使えるようになったのはだいぶ楽になりました。

コミットログ「ninngennteki」

私物のプロジェクタを持ち込む。

https://twitter.com/pepsin_amylase/status/493392302589489152

ICFPC公式アカウントにRTされる。

※プロジェクタは壁に投影して使いました。

・3日目

kawateaさんが縦に動くAIと横に動くAIを混ぜれば良い感じに包囲できることを発見する。ゴーストAIはこれ以降細かい修正のみ。

とりあえずラムダマンもゴーストもだいたい満足できる状態になる。

ラムダマンがでかいマップの時に落ちるという問題を解消しなければならないことに気づく。

昼食後、他の5人が死んでいる横で周囲32×32マスだけを見る・1回のBFSで全部の処理をするように修正する。

後はひたすらAIの微調整。何故か自殺することがあったので無理やり修正したり、invisibleの処理をちゃんとやったり。

kawateaさんのゴーストAIが改良されて、ラムダマンがPowerPillの隣にいたらまだ取ってなくても逃げるようにしたり、PowerPill取っても残り時間を推定して食われそうにないなら迫るようになったりした。強い。

ラムダマンAIもBFS1回で処理してるとは思えないほど複雑な動きをし始めて知性を感じるとか言ってた。

コンパイラにSIMD的なものが実装されてマップの周囲4マスを1度に取れるようになる。

結局命令数はあんまり減らせなかったけどおそらく256×256でも動いてるだろうという結論になって、最終提出に向けて微調整をする。

READMEに2次元配列作ったとかSIMD作ったとか書いて提出。

kawateaさんのゴーストAIにamylaseさんとy3さんとkawateaさんが手動で挑んで全員負けたりしていた。

Twitter見てみんな配列作ったんだなーとか言いながら打ち上げして終わり。

感想

数年前からやってみたいなぁと思いつつ敷居が高くて参加できなかったのでけっこう嬉しかったです。

低レイヤの経験が全然ないので、コンパイラさくっと書けなくてすいませんとか地下勢頭おかしい…とか思ってました。

役割分担は

コンパイラ係:y3,simeji,wistery

シミュレータ:amylase

ラムダマンAI・GHCインタプリタ・ビジュアライザ:not

ゴーストAI・GCCプロセッサ:kawatea

と、そこそこいい感じになったと思います。(もうちょっとみんなAI書くべきだったかもしれない?)

lightningで正の点が取れなかったあたりはみんな意気消沈してたけど、結局それなりのAIができて楽しかったです。

来年も機会があれば参加しようかなぁ。

ゲスト



トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/not522/20140730
 |