ICFP Programming Contest 2020 に参加した

updated: 2021-07-14

ICFPC galaxy

ICFP Programming Contest 2020 に参加した感想を書く。 感想のみを書き、技術的なことはほとんど書かない。

基本的に、いわゆる「お気持ち」の記事である。

コンテストの概要

まずコンテストの概要を説明する。

コンテストのストーリーの背景設定

コンテストの背景、つまりフレーバーテキストについて説明する。

コンテストの発端は、「宇宙からの電磁波を受け取って、バイナリ列になおして見ると絵が出現した。これは何かの法則で符号化したメッセージらしいので皆で解読しましょう」という設定である。

詳しいことは省くので、符号化されたメッセージについて知りたければ公式 Documentを参照してほしい。

コンテストの進行・構成

コンテストの進行は、例年のように Lightning Division という最初 24 時間と Full Division の残り 48 時間に分かれている。

Lightning と Full に形式上は分かれていたが、 2020 のコンテストにおいては、 Lightning Division で 0 でない得点を得たチームはかなり少なかったように思う。

Lightning/Full にこだわらず、2020 Contest 全体を見てステップ分けすると、以下のような 3(4) 段階があった。

  1. 符号化されたメッセージを読めるようになる（僕たちは「銀河エンコーディング」などと呼んでいた）
  2. メッセージ自体がプログラミング言語となっていて、このプログラミング言語を実行する処理系（インタプリタ）を作る
  3. メッセージ自体を自作の処理系で実行して、宇宙人（という設定の存在）とどういう通信が行われているかを解読する
  4. 宇宙人と対戦ゲームをプレーしていることがわかるので、この対戦ゲームに勝つために AI を実装する

また、各段階ではコンテスト運営者によって情報が少しずつ公開されており、進みの遅いチームを補助していたように思う。 ただし、運営が想定するチームの想定速度があまりにも速すぎて、だいたいのチームが運営の想定する速度よりも遅かったようにも思う。

感想

ここから、前項で述べた概要およびコンテストの構成、その他感想を雑多に述べる。

コンテストのフレーバーテキスト・設定の感想

コンテストの設定として以下の 2 点はとても好きだった。

  • 宇宙からのメッセージが来た。という背景
    • 高周波と低周波で 2 値にする前（という設定）の wav ファイル をアップロードしているのもフレーバーの説得力を増していた
  • メッセージをビット列にして、ビットを 2 値の画像のピクセルとして配置すると絵が出現したという設定
    • 「よくわからないビット列が宇宙から飛び込んできて、それを再配置すると絵になる」という話はアレシボ・メッセージであるし、出題者が天文台の人ということなのでとても自然だった

一方で、フレーバーおよび設定がよく作り込まれていることを悪く受け取ってしまった側面もあった。

  • どこまでがフレーバーでどこまでがコンテストのルールなのかがわからない
    • コンテストの進行で徐々にルールが明らかになっていくので開始段階では本当に何も判別できなかった
    • あまり詳しくはないが、 Codeforces の algo コンテストだと「A君は奇妙な数列を貰いました。この数列を奇妙じゃない数列にしたいです。」くらいの薄い設定しかないので、コンテストでやることとフレーバーの分離が楽である

コンテストの進行・構成の感想

コンテスト概要で述べたように、コンテスト中にいくつかの段階をクリアする必要があった。各段階についてなかなか異なる感想となるので個別に書く。

0. 符号化されたメッセージ

銀河エンコーディングされたメッセージを読むところは面白かった。

特に、符号化されたメッセージの構文がシンプルであったため、符号方式をすぐに覚えることができてドット絵を見るだけでなにの記号であるかを読み取れるようになった瞬間などが楽しかった。

また、このフェーズでは銀河エンコーディングされたメッセージを画像として描画するプログラムなども構築する必要があったはず。 ICFP Contest では明確に GUI を作ることは求められないが、人間が問題を理解するために GUI を用意することが暗黙的にほとんど当たり前のように要求されるので作っていた。単純な GUI を作るフェーズであり、実装したものが動いてることが可視化されるので達成感は楽に得やすい。

今回のコンテストでは必要なかったが、「もう少し開催期間が長かったら、『宇宙から送られてきた音声 (wav) ファイルをビット列に直す』ところもプログラム組ませるのは絶対あったよね」と話していた。

自チームではないが、おなじことを思っている人はいた。

https://twitter.com/kakira9618/status/1285206547686014976

1. メッセージが示すプログラミング言語の処理系（インタプリタ）を実装

「宇宙からのメッセージは実はプログラミング言語だったので処理系を作っていきたい。各単語がどういう命令（関数）なのかを解き明かしつつ処理系を作ってくれ」というフェーズである。

銀河メッセージは関数型言語なので関数型言語の処理系を作るというフェーズであるが、符号化されたメッセージを読むフェーズと合わせて、各単語が何を表すかを想像・仮説・検証するフェーズであったので、競技プログラミングというよりは謎解きという雰囲気が強かった。嫌いではない。

ちなみに、この謎解きは Discord チャットで積極的に他チームへも共有してくれと言われていたし、運営チームによって「新たにわかってきた。○○は××という意味だ」という助け舟も出されていた。

2. 宇宙人とどういう通信が行われているかを解読する

正直、前フェーズまでで既についていけてなくて、このフェーズについてはあまり語ることがない。

ただし、運営が処理系の参考実装を公開するという助けも出していて、動作確認はできるくらいになった瞬間があった。

描画された盤面を見て「どうやら、1on1 の対戦ゲームが実装されているらしい？ これはキャラクターの選択画面らしい？？」などと言っていた時はそこそこ達成感があった。

3. 対戦ゲームに勝つために AI を実装する

ノーヒントでこのフェーズに至ったチームは参加 300 チームのうち 10 チームあるかないかくらいだと思う。

対戦ゲーム自体は、自分と相手の宇宙船が恒星の周りを航行していて、恒星から遠ざかりすぎず/恒星に衝突せず居続けると勝ちというゲームであった。

このフェーズに突入すると、対戦ゲーム AI を作成することに集中できるので、よくあるマラソンマッチとなったと思う。

最初からこのマラソンマッチのフェーズを楽しみたかった人が多かったんだろうなあ。

全体的な進行・題材・その他色々について

好きな点と好きではない点およびその理由を列挙する。

  • 関数型言語の処理系実装という題材が好き
    • ICFP(International Conference on Functional Programming; 関数型プログラミング国際学会)が主催するコンテストの題材として非常にマッチしていると感じた
    • 2019 は、フレーバーの中に Lambda Coin という名前が存在する程度であったように思う
    • 2021 は、 λ の形などは出てきたが関数型プログラミングと関わりがあるかというと今ひとつピンと来ない
  • 前半の謎解きフェーズで他チームとの情報共有・協力を求められる点は好き
    • 謎の関数型プログラミング言語の謎解きを、世界中の見知らぬプログラマーと協力して行う謎の一体感は得難いものだったと思う
    • 一方、チーム同士の競争であるマラソンマッチを想定して参加すると、他の参加者に情報共有するということの意義がわからないとは思う
  • 運営が想定する考察・実装の速度が速すぎるのがつらかった
    • 速度が遅いチームの補助のためか、運営から順次解説が共有されるが、大多数のチームが運営の補助無しでは勧めていなかったように思う。想定レベルが高すぎる……
    • 運営に追いついていないチームとしては「全然追いつけてない、置いてきぼりだ……」という感想になるだろう
    • 運営より先を行っている上位チームは「せっかく苦労して解読した情報を、運営が解読できてない他チームに共有するなよ」という気持ちにもなるだろう
      • 実際にこういう文句は Discord 内で見かけた

このコンテストに参加した知り合いを見ると、2019 に比べて賛否両論あるように感じている。

賛否両論あることについては

  • マラソンマッチ（フェーズ 3）を期待して参加すると、そこに参加するまでのハードル（フェーズ 0,1,2）が長すぎる

    • 「マラソンマッチをしたかったのに何故インタプリタを書かされているんだ？」
    • 「謎解きに参加したつもりはないんだけど……」
    • 端的に言うと、参加者のマラソンマッチへの期待と運営のギャップが大きかったのだろう

  • チーム間での情報共有が明示的に推奨されている

    • 自分で謎を解かなくても共有されてくるのを待てば楽で良い
      • 謎解きの貢献度みたいなものを可視化・競争できると良かったのかなと思う
    • 運営からの助け舟もあるので本当に何もしなくても徐々に情報が公開されてくる
    • “Contest” を名乗る以上、他チームとの競争であるという意識を捨てることは難しい
    • “ICFP Programming Challenge 2020” とかだったらマシだったかもしれない（伝統の名前を変えるわけにはいかなかっただろうけれど）
    • フレーバーテキストでは「宇宙人 vs 地球人」であり「対戦ゲームの地球代表チームを決めるために、参加チームの中の対戦で上位になったチームに宇宙選手権に出てもらう」と言っているので、フレーバーを真に受けるなら順当であると言い張ることはできると思っている

など考えている。

That’s ICFPC.

賛否両論あり、開催中も Discord で文句を言っている人がそこそこいた。そんな中で、ある参加者が “That’s ICFPC.” と発言して文句を牽制していてチームメンバーとともに爆笑した。

まあ、何があっても、こういう感じのコンピュータ・サイエンス的な要素全部盛り込んで実装も重くて要求知識もキツいバカみたいなコンテストが ICFP Programming Contest だよねという印象ではある。

https://twitter.com/rian_tkb/status/1285210174194499585

That’s ICFPC.

リンク集

site top