ICFPC2020

ICFPC2020にnegainoidoで参加してた

コンテスト前

コンテスト一週間前より公式Twitterが message-from-space.readthedocs.io/en/latest/index.html に言及を始める. 当時は12章くらいまでだけが公開されており, それから徐々に内容が増えた. このストーリーを真面目に読むと, 宇宙から電波がキャッチされ, まずそれをビット画像になおして, そこからさらにギャラクシー語として解釈できるということらしい. 第1フェーズとして電波 (wav) から画像に変換する作業, 第2フェーズとして画像からギャラクシー語 (Lisp) に変換する作業があり, コンテストが始まるまでにその第1フェーズは一応は完了していた(チームメンバーが作業していた).

ところでコンテストが始まってもないのにこんな情報が出るのはおかしい. 少なくともこんなの知らなくても有利不利にならないように配慮されるはずだ, といったメタ読みが始まったが, 考えてもしょうがない.

コンテスト1日目

先のドキュメントが増えた. 今は章ごとにギャラクシー語 (Lisp コマンド) に名前がついてるが, 初めは単に ??? という名前で公開され, 中身の解釈もまるで分からなかったが, 今回は discrod 上で公式の下で参加者たちがこの内容を解読(エスパー)しあい, 次第に内容が判明し, 今では名前がついている. 今年のICFPCは協力ゲーだった?

果たして, 電波から画像, 画像からギャラクシー語への変換は無意味だった. 全てに名前がついた時点で, 運営はギャラクシー語に変換済みの, 巨大な galaxy.txt を手に入れたと, 公開した. そして今回のコンテストのエッセンス(以上のもの)全てがこのテキストファイルの中に詰め込まれていた.

まず我々がスべきことはギャラクシー語の処理系だった.

今年我々はRustで参加することに事前に決めていた. したがって処理系もRustで書いた. トークン列までにはすでになっているので, 適切に構文木にし, 適切にevalするだけの作業であり, そんなに難しいことはなかった. call-by-name が必要だと判明するまでは.

コンテスト2日目

おそらく評価するとループを含む箇所があり, または評価すると死ぬ(プログラムとして破綻する)箇所があり, 本当に必要なところだけを順序よく評価する必要があった.

他のチームメンバーによりHaskell製処理系が実装された. これが最後まで使われた.

galaxy.txt は全てが詰め込まれたプログラムであり, とある宇宙戦争ゲームのチュートリアル及びヒント集だった. しかし一切説明がなくどこをクリックすれば次に進めるのかといったことを自分で全て推測シなければならなかった. そもそもゲームのチュートリアルであること自体を察しないといけないなどなど.

コンテスト3日目

ICFPC本番. チュートリアルで遊んだゲームのAIを書けというもの. 細かな仕様(ダメージ計算とか各パラメータの意味とか)は galaxy.txt にあったらしいが, そんなものは分からずにカンだけで適当にやった.

ゲームはというと, 1vs1のシューティングゲームであり, 宇宙を飛びながら一方はアタッカーとなりもう一方を打ち倒せば勝ち. 一方はディフェンダーとなって時間まで逃げ切れば勝ちというもの. 出来る操作として, 加速, ビーム, 自爆, 分身. アタッカーはディフェンダー全てを倒す必要があるので, ディフェンダーは分身で最大100体(くらい)まで増やしておくのが有利. アタッカーはビームの仕様をよく知っておく必要がある. 撃つ意味のないビームを打っても無駄な消費をする(自機の温度を無闇に上げて自滅するだけ、相手にダメージを与えられない). しかし我々は結局この仕様が分からず, 最初はマンハッタン距離で適度に近かったら打つなどしていた. どうもそうではないことが観察から分かり, 自機の温度がゼロだったら限度いっぱいの出力で打つことにした.