ICFPC2017

ICFPC2017にチームAdlersprungで参加しました。Adlersprungとはドイツ語でEagle Jumpという意味です。どこかで聞いたような名詞ですね。メンバーは

  • mkut
  • osa_k
  • pepsin_amylase
  • y3eadgbe
  • yuusti
  • kawatea

の6人でした。去年は8人いたけど、人数が多すぎて話がまとまらなかったりして面倒だったので少なくしました。それでも一般的なICFPCチームよりは多いという説があります。

リポジトリはこちら： github.com

概要

今年の問題は、対戦型ゲームのAIを作るというものでした。グラフGが与えられ、一人ずつ交互に辺を取って自分の色で塗っていきます。Gに含まれる頂点の部分集合L (Lambda Mine)ではラムダが産出するため重要度が高く、この頂点を起点としたパスを作るのが目的となります。具体的には、∀(l, v) ∈ L×V(G)について、(lからvまで自分の色の辺だけを通って到達できるか ? 1 : 0) × (lからvまでのG上での最短経路長)2を合計したものが点数となります。mkutがTicket to Rideだと言ってたけど、自分は1回しかこのゲームをやったことがないので、どれくらい似ているかは不明です。

自分はAI作成にはほとんど関わらず、ひたすらインフラをいじって遊んでいました。第一目標はもちろん優勝ですが、裏目標として

あたりを想定していました。

以下作ったものと知見です。

Ka Dingel

先史文明期の遺産であるところのJenkinsです。なんだかんだ言ってプロセスをWebインターフェースから走らせられたり、手軽にログの残るcronを仕掛けられたりするので重宝します。中にはたくさんのフレンズと数人のイーグルジャンプ社員が住んでいました。

f:id:osa_k:20170813220137p:plain

GitHubにpushされた変更はとりあえず自動でビルドしておくという運用になっていたのですが、ビルド結果をコミットメッセージとともにSlackで通知するようなスクリプトをpepsin_amylaseが書いたところ、Slackの治安が終わりました。

f:id:osa_k:20170813225054p:plain

Sandstar

AI担当のyuustiとkawateaはC++しか書かずJSONを読めない（boostがあるので頑張れば読めるはずだけどよく知らない）ので、触れたJSONをいわゆる競プロ形式に変換するRubyスクリプトが生まれ、Sandstarと名付けられました。いろいろな仕様をこのスクリプトで巻き取った（頂点IDは0〜N-1の連番とは限らない、ゲームの状態はシリアライズして保存する必要があるためグラフの管理をする等）ので地味に面倒くさく、Rubyで書き始めてしばらくしてから後悔しました。一度書き終えてからは大きなバグもなく安定していたものの、終盤ではこいつのI/OがボトルネックになってTLEする可能性を指摘されて冷や汗をかいた（結局AI側の高速化によって回避された）ので、こういう用途にスクリプト言語を使うべきではないなぁと思いました。Rustで書いていれば……。

Alpaca

ジャパリカフェ前に生えている草をむしることで、対戦結果を可視化してくれるフレンズです。Sandstarを書いていたらpepsin_amylaseが対戦をぶん回すためのスクリプト（Fennecと呼ばれていた）を書き上げていたので、じゃあ後はビジュアライザだなーということで書きました。Riot.jsがSVGを特殊なやり方でハンドルする（riot-cxのようなattribute名にしないとコンソールがエラーで溢れる）ので少しハマったものの、概ねサクサクと書き上がりました。Riot.jsいいですね。Intellijで正しくハイライトできないけど……。

AIをあまり触らなかったことの弊害で、あると超便利系の機能がAI班に言われるまで実装がほったらかしになっていたりして、相変わらずうまく行かないなぁと思いました。ユーザが6人であってもドッグフィーディングしないと分からないものですね。

f:id:osa_k:20170813221806p:plain

Time Vault

ターンを溜めるすごいアーティファクトです。2日目が終わるあたりでSplurgeというルールが追加され、Sandstarの修正は済んだもののあまりやることがなくて暇だったので、機能テストがてらSplurgeを使うAIを実装しました。これは通常1ターンに1本しか辺を塗れないところ、直前Nターンをパスしておくと最大N+1本からなるパスを一気に塗れるというもので、一気に高得点が入るのでロマンがあります。本物のTime Vaultは自力では1ターンしか溜められないけどゆるして。

基本的には一番遠いLambda同士を一気に繋げるようになるまでターンを溜めて解放するというAIです。無理だったら一番点数の増えそうな辺を取ります。当時はすでにmkutのArtemis（めっちゃつよい）とkawateaのkawatea-v3（めっちゃつよい）が争っている魔界になっており、疎なグラフでターンを溜めていると橋を取られて死ぬという状況だったのであまり成果は残りませんでした。

Kaban

知能が発達しているためMySQLを読み書きできます。2日目の半ばあたりまでは対戦のログはすべてFS上に生のJSONとメタデータの組み合わせで保存されていたのですが、ランダムで大量のマッチをスケジュールするFennecが現れて、これAlpacaのトップページを表示するたびに数千ファイルを舐めることになるけど大丈夫か、みたいになったのでログをMySQLに突っ込むことになりました。最終的にMySQLだったから良かったという処理はしなかったので、かなり無駄だった気がします。MySQLにするとローカルでのデバッグがクッソ面倒くさくなるし……。あとgo getがちゃんと動くようなディレクトリ構成がわからずハマりました。今も良く分かっておらず、雰囲気でディレクトリを決めてGOPATH=pwd go getしたら動きました。

総括

やったことはこんな感じです。1日目はひたすらインフラを整えていて、3日目はやることないのでTime Vaultを強くしていたのですが、2日目に何やったか完全に覚えていません。pepsin_amylaseから飛んでくるインフラの拡張要求に対応してたのかな……。

目標は概ね達成できたと思います。自己対戦インフラがちゃんと組めたので2015年よりは成長してるかなと思いましたが、Unagiは数百CPUとか回してたらしいので、まだ思い切りが足りなかったかなと思います。 あっ思い出した、CPUめっちゃ増やそうとしたらGCPのQuotaにぶち当たって諦めたんだった。増やして〜ってリクエスト送ったら増やしてくれたんではないかとは思いますが、そんなにたくさんいらんやろと言われたのでそっか〜と思って16CPUで満足してしまった。

Riot.jsはいいですね（2度目）。個人プロジェクトでWebpackなんか使いたくないし、なんならBabelとかBrowserifyも使いたくないので、ファイル1個置いておくだけでお手軽にWeb Componentsライクなタグとかモジュール化の恩恵を受けられるのはかなり良い。

インフラはやはり日頃から慣れ親しんでいるかによって、ハマったときの対応力が全然違うなぁと思いました。Jenkinsからnohupでdaemonを起動しようとしたら普通に殺されるという現象もしばらく気付かなかったし、気付いてからsystemd対応するのも結構時間がかかった。ユーザ単位のsystemd使おうとしてsudoするとXDG_RUNTIME_DIRが定義されなくて死ぬのとか、前もやったのに全く覚えていなかった。

コンテストそのものは、問題文を読んだ瞬間はLambda Lifterの再来かと思って身構えたけど、やってみると意外と面白かったです。AIに関わってないとはいえ、mkutやkawateaやyuustiが書いたAIの挙動を見比べているだけでも楽しかった。ただ、公式のスコアボードがないのはコンテスト感がないというか、何と戦っているのか分からないし自分がどれくらいうまくやっているのかも推測できないので、ゲーム性を下げてしまっていたと思います。