ICFPC 2020 galaxy.txt を読む (その 0: ICFPC 2020 振り返り)

一月ほど前の 2020/07/17-20 に ICFPC 2020 がありました。今年はここ最近多い対ゲーム的なものに加えて、ちょっと凝ったストーリーとちょっとした interpreter (Garaxy Pad) を作る必要がありました。

この Garaxy Pad に、開始数時間後に与えられる galaxy.txt を実行させると、対戦ゲームのチュートリアル的なことができたわけですが、多分コンテスト期間中に galaxy.txt を読もうとした人はほとんどいないと踏んで、解説を書いてみました。

ストーリー/仕様振り返り

まず galaxy.txt を読むのに必要な範囲でストーリーと Galaxy Pad の仕様を振り返りましょう。

ストーリー

宇宙から信号を受け取るところから始まります。これを、周波数で描画したあと、適当な間隔で改行してやると白黒ビットマップが得られます(こんな感じ)。この画像を心の目で見ると、Galaxy Pad の仕様がわかります。この解読はコンテスト本番中公式 discord でみんなでワイワイやっていて、大体全部解読が終わったタイミング(=全チームに仕様が公開されたタイミング)で運営が galaxy.txt を投下しました。参加者は仕様通りの Galaxy Pad を実装して、galaxy.txt を渡して実行する、というのが次のステップでした。

Galaxy Pad の仕様

galaxy.txt は Galaxy Pad で実行するプログラムが含まれているので、これを読むには Galaxy Pad の仕様を理解する必要があります。以下簡単に紹介します。

数字

数字は整数が与えられます。桁数は指定されていないのですが、現実的には 64 bit 符号付整数があれば多分大丈夫かと思います。正の整数は、2進表記でLSBから順に正方形に並べ、上と左にマーカーが付きます。

負の整数は、まず絶対値を正の整数と同様に表記し追加で 1 dot 左下に加えます。

整数演算

以下のものが提供されました。

inc (インクリメント), dec (デクリメント), add (2項加算), mul (2項乗算), div (2項除算), neg (単項符号反転), eq (2項等値比較), lt (2項小なり比較)

真偽値

Church encoding で定義されます。 

\texttt{true} = \lambda x \lambda y .x 
\texttt{false} = \lambda x \lambda y .y 

特に if (cond) { e1 } else { e2 } は cond e1 e2 で表現されます。重要事項として、式は遅延して評価されます。

コンビネータ

S, B, C, I コンビネータが与えられます。加えて true を K コンビネータとしても使います。

\texttt{S} = \lambda a \lambda b \lambda c . (a\,c)\,(b\,c)
\texttt{B} = \lambda a \lambda b \lambda c . a\,(b\,c)
\texttt{C} = \lambda a \lambda b \lambda c . (a\,c)\,b
\texttt{I} = \lambda a . a

Cons/List

Cons cell も Church encoding のものが使われます。

\texttt{cons} = \lambda a \lambda b \lambda f . (f\,a\,b)
\texttt{car} = \lambda c. c\, (\lambda a \lambda b . a)
\texttt{cdr} = \lambda c. c\, (\lambda a \lambda b . b)

また List は Cons cell を用いて type list = nil | cons (_, list) の形であらわされます。
この仕様では List は要素の型を持っているわけではないので、いろいろな型の要素が混ざった List も可能です(実際に galaxy.txt の中で使われています)。
末端の nil およびその判定関数 is_nil は以下で表現されます。

\texttt{nil} = \lambda c . \texttt{true}
\texttt{is_nil} = \lambda l . l (\lambda x \lambda y . \texttt{false})

Drawing

Galaxy Pad の仕様には描画命令もあります。描画結果はビットマップで、1 になる座標(x, y cons cell) のリストで表現されます。

Send, modulate, demodulate

galaxy.txt を読む分には関係ないので省略します。

Interact

galaxy.txt は描画されたビットマップを出力、(その画像上のクリックイベントを想定して)二次元座標を入力として、UI を提供します。
また、上で省略した send 命令をつかって、運営のサーバと通信をします。
仕様上は以下。

// list function call notation
f38 protocol (flag, newState, data) = if flag == 0
                then (modem newState, multipledraw data)
                else interact protocol (modem newState) (send data)
interact protocol state vector = f38 protocol (protocol state vector)

ap ap ap interact x0 nil ap ap vec 0 0 = ( x16 , ap multipledraw x64 )
ap ap ap interact x0 x16 ap ap vec x1 x2 = ( x17 , ap multipledraw x65 )
ap ap ap interact x0 x17 ap ap vec x3 x4 = ( x18 , ap multipledraw x66 )
ap ap ap interact x0 x18 ap ap vec x5 x6 = ( x19 , ap multipledraw x67 )

ap interact galaxy = ...

要約すると、以下の通り

  • galaxy 関数に state (初期値 nil) と、座標を渡し計算する。返り値は 3 要素 tuple で、flag, 次の state, data
  • flag が 0 の場合は data はビットマップリスト。描画して、ユーザの次のクリックを待つ。次のクリックが得られたら、galaxy 関数に、上で評価した返ってきた state とクリック座標を渡して、再度計算する。
  • flag が 1 の場合 data は運営サーバに送るデータ。結果を読んだあと、galaxy 関数に、上で評価した state とサーバから返ってきたデータを渡して、再度計算する。

Galaxy の中身

galaxy.txt を読み解くうえで、どういう挙動をしたかを理解しておく必要もあります。
さらっと振り返ることにすると、Galaxyはいくつかのステージからなっていました。

オープニング

最初は Galaxy マークをクリックすると、カウントが進みます。
次いで、十字が出てくるので、交点をクリックしていくと進みます。

メインページ

宇宙を背景に、エイリアンのアイコンが散らばっています。
中央の Galaxy マークをクリックすると、対戦履歴モードになります。
またエイリアンをクリックすると、大きなエイリアンが表示され、いくつかのエイリアンは右肩に別なアイコンが表示されており、
クリックすると対戦ゲームのチートコードが手に入るミニゲームモードにはいったり、武器のダメージ解説ページが開いたりします。

対戦履歴モード

まずは対戦ゲームの過去履歴が表示されるモードになります。
ここもギャラクシーマークをクリックしていくと対戦履歴が増えていき、さらにクリックするとチュートリアルモードに進みます。

チュートリアルモード

UIを使って自機をコントロールしつつ、ミニ課題(=相手を倒す)をクリアします。
自爆する、加速する、レーザーを撃つ、分裂する、引力に逆らう、などを体験します。

ミニゲーム

チートコードが入手できるミニゲームが二つありました。一つは回転/反転を許した神経衰弱で、もう一つは〇×ゲームでした。
神経衰弱はペアになっているものをクリックすると消えるので、消えうるものを全部消せればクリアです。
〇×ゲームは、負けない(勝っていなくてよい)形が12パターンあるので、対戦AIの挙動を多少誘導しつつ全パターン出せばクリアです。

まとめ

ここまで、ICFPC 2020 で galaxy.txt を読むのに必要なものをざっと復習しました。
次は実際に galaxy.txt を眺めます。