ICFP Prorgamming Contest のチーム戦テクニック集

Competitive Programming (2) Advent Calendar 2018 の 10 日目の記事です。

概要

ICFP Programming Contest (ICFPC) で好成績をおさめるための、おもに年度にまたがって再利用可能なノウハウについて説明します。ワイワイ合宿して72時間プログラミングし続けるのは単純にクソ楽しいのでみんなにも同じ沼にハマり込んでもらうためにこの記事を書きました。

2013年以降の出題傾向

問題形式

大きく分けて Problem Solving (2013, 2015, 2016, 2018) と Game AI (2014, 2017) の2種類があります。Problem Solving はある問題クラスとそのインスタンスが複数与えられるのでそれに対する解を出力するというもので、要するに普通のマラソンマッチです。Game AI は対戦ゲームのAIを開発して強いほうが勝ちというやつ。

取り組みやすいのは Problem Solving です。この記事も主に Problem Solving 系に適用できる話をしていきます。

Game AI が難しいのは主に次の理由によります

  • 強さの評価が難しい
  • 必然的にリモート実行になる(後述)

強さが1つの軸に乗って評価できるようなゲームが出題されることはまずなく、つまりAI同士に相性があったりするので、強さを定量的に評価するのがまず難しいです。それでも大まかな目安があると助かるのは間違いないので、多くのチームでは自動対戦システムを用意してイロレーティングなどで強さを評価しているようです。

実行環境

  • 手元 (2013, 2015 予選, 2016, 2018)
  • リモート (2014, 2015 決勝, 2017)

リモートは計算資源をどれだけ使えるかが明確でないのがキツいです。2017年は実行環境のVMが配られましたが、年によっては実行環境も明確でない場合もあります。

2018年の出題方針としてリモート実行は避けようというのがあった(https://icfpcontest2018.github.io/assets/report.pdf)ので、これが引き継がれるなどすれば来年以降も手元実行になるんじゃないかと予想しています。

ICFP的要素

  • Theorem proving (2013)
  • Compiler development (2014)
  • Concurrency (2018)

個人的にはあると普段やらないタイプのプログラミングをすることになって楽しいので好きです。勝敗にはあまり影響しないと思います。

事前準備

ICFPC の準備は会場選定から始まります。以下の条件を満たすところがいいでしょう。

  • 高速なインターネット
  • 十分な空間
  • いつでも食事や休憩ができる設備

学生の場合だと食料を買い込んで大学の研究室に引きこもるのがいいと思います。社会人勢は開発合宿に行くのもアリ。

まず AWS なり GCP なりのアカウントを用意して強いマシンを1台借ります。複数台のマシンを管理するのはだるいのでクラウドで借りるインスタンスは強いのを1台だけのするのがおすすめです。そこでさえプログラムが動けば全く問題ないようにすることでインフラ管理の負担を最小化します。そこに Jenkins を立てます。AWS の場合は公式にステップバイステップのガイドがあるのでそれに従うといいです。 

docs.aws.amazon.com

Jenkins というと、学生競技プログラマーの場合イケイケ社会人エンジニアが使う謎のイケイケツールという印象しかない人もいると思いますが、今回はこれをたんに「ブラウザからプログラムを実行してそのログがあとから見れるやつ」として運用します。

ソースコードの管理は Git で行うと Jenkins が勝手に最新のコードでプログラムを実行するようにできるので便利です。コンテスト終了後に公開するのも簡単です。学生なら GitHub で無料でプライベートリポジトリが作れます。

チーム編成

ICFPCにおけるタスクは大きく分けてAI開発とAI開発のためのサポートツール開発(以下インフラと呼ぶ)です。

AI班: 人数を増やして多様性で殴る

Problem Solving にせよ Game AI にせよ AI 開発メンバーの絶対数が多ければ多いほど有利だと思います。増やしたAI担当に何をさせるのがいいかというと、それぞれがかんがえたさいきょうのAIを書かせるのが72時間コンテストではベストのように感じます。問題の多様性やゲームAI相性問題に対してAI開発者の多様性で対処する作戦です。

AI担当が多いほうが嬉しいもう一つの理由としてはコミュニケーションコストの問題が挙げられます。この戦略ではAI開発は独立に行われるためAI担当者どうしのコミュニケーションはあまり行われないことになります。全員が使うであろうコード部品やデータ構造や問題の基本的な考察などは共有されますが、AIの方針は各位で異なっていてそれらに向かってひとり黙々と開発を進めていくことになります*1。3日間という超短期のプロジェクトで成果を出すにあたってはコミュニケーションコストを削るためにもAIに人数を置くほうがいいという考え方です。

インフラ班: 競技webサービス開発

タスクは2つです。

  • サーバー管理
  • ツール作成

サーバー管理はコンテスト開始前に Jenkins などを立てた人がやるといいでしょう。必要なソフトウェアをインストールしたり、必要に応じて Jenkins Slave を追加したり*2、ツール開発で作られた web サービスを実際に立てて管理したりします。

ツール作成の最初の大きなゴールは、AI班の人のAI開発以外の仕事を自動化することです。そのために必要なのは

  • AIプログラムの入出力仕様
  • 過去のAIプログラムの計算結果を管理するいい感じのデータベース
  • Jenkins からAIプログラムを実行する仕組み
  • 問題の入力などを可視化
  • 公式サーバーをスクレイピングしていろいろやる
  • これらを一覧できるポータルサイト

あたりです。これらを AI 班の非自明AIが出来上がり始める頃には揃えておきたいので開幕はかなり忙しいです。

AIプログラムとの入出力仕様は、うちのチームの場合メンバーがみんな競プロ勢なので競プロっぽい入出力フォーマットを策定しています。

過去の結果を管理するデータベースは必ずしも MySQL のような RDBMS である必要はありません。出力のファイルとそのメタデータを記した json ファイルとかで十分なケースもあります。これをしょぼエンジニアリングと呼ぶか72時間動けばいいICFPCならではの割り切りと呼ぶかは微妙なところ。

可視化は近年の問題の場合だと公式からブラウザ上で実行できるビジュアライザが配られます。それでも(意図的にか意図せずか)十分な機能がついてないことが多いので、フロントエンドに強い人が一人いると強いビジュアライザができたり公式ツールの改造がはかどったりして便利です。

公式ツールの再利用は結構重要なテクニックです。いちからビジュアライザを書くのはだるいというのもそうなんですが、公式ビジュアライザは正しいことが保証されたシミュレータでもあるからです。2018年は公式ビジュアライザで計算したスコアと自前のスコアラーの結果が一致するかを確かめるのが重要なテクでした*3。公式側でこういう利用を対策している場合もあり、2016年は有理数座標での折り紙でしたが公式シミュレータは内部計算に浮動小数点数を使っていました。

大量に同時実行したAIの出力を POST リクエストでポータルサイトに投げるような設計をした場合はその負荷にも注意が必要です。ポータルサイトボトルネックになって計算結果が失われるという悲しいながらも割と起こる事故があります。ISUCONするはめにならないよう。*4

スタートダッシュで基本的なツールを揃えたら、AI班の人と相談しながらビジュアライザを強化したりほしそうなツールを作ったりします。

実際の編成

最近は osa_k がサーバー管理をやり、amylase, y3eadgbe, osa_k がインフラツールの開発に邁進、kawatea, mkut, yuusti が AI 開発という(おおまかな)分担になっています*5

実際の初動としてはみんなで問題を読んでそれぞれの感想を言いあい、なんとなく上のような分担に収束して各自手を動かすという感じです。

コンテスト終盤の動き

注力するべき問題を絞る

終盤になってくるとどういう問題が難しくてどういう問題なら手が出せそうか、そしてそれぞれの大まかな効果が見積もれるはずです。例えば最適解の点数がわかるタイプの問題なら改善の余地があとどれくらいあるかはその入力インスタンスの重要性を示す重要な指標です。

残り16時間くらいの段階でチーム全体で時間をとって優先度付けするといいと思います。

インフラからAIに転職

基本的にインフラツールの仕事はどんどん減っていきます。そうなると無限に仕事があるAI班に転職するわけですが、弊チームでの転職事例を思い起こすと、

  • すでにある出力を後処理して細かく改善する
  • 人間ソルバーになる
  • 高速化

が手を付けやすいタスクだと思います。特に人間ソルバーはプログラムではどうしようもなかった問題に対する唯一の解決策なので意外と重要です。

AI 班の人にノウハウを教えてもらって新規開発してもいいけどこっちは難易度高め。

まとめ

プログラミングコンテストが好きな人なら、何か一つは面白そうなタスクがあったと思います。ひたすらAI書いてたい、イケてるビジュアライズをしたい、作業を自動化してチームの生産性が向上するのが見たい、手でパズル問題を解きたい……

同じことを感じた人たちでチームを作ってひと夏の思い出づくりに合宿してみませんか?

ちなみに

ICFPC 2018 の Lightning 1位, 2位 と Full Contest 3位, 4位 は1人チームでした。他人と群れるのは嫌いだ、という方にも ICFPC はおすすめです。

おまけ: 過去の失敗集

サーバーのストレージを使い尽くす (2015)

つらい。3日だと大した額にならないからでかいEBSつけましょう

Unagi の潜伏に引っかかる (2016)

仮に潜伏だとわかっていても勝てなかったわけではありますが、気をつけましょう(何に?)

インフラコードとAIコードの管理がグダる (2017)

この年は Game AI で、インフラ用のコードとAI用のコードをまとめて git に置き、タグを付けたコミットを成果物として扱い、自動対戦の対象とするようにしていました。しかし時と共にインフラの前提や必要なインフラコードが置き換わっていき、一方で過去のコミットのインフラコードは変化しないので……

インフラコードとAIコードは基本的に入出力以外でコミュニケーションしないのでリポジトリを分けたほうが安全だと思います。

会場のインターネットがゴミ (2017)

airbnb で確保した物件の「インターネットあり」がモバイルwifiで、コンテスト開始通信制限に引っかかりました。

開発合宿の実績があるところにしましょう。

インフラアプリのパフォーマンスが足りない (2015, 2018)

ISUCON しないように(2回め)

 

*1:むしろ下手に基本的方針を共有するとAI開発者の多様性が失われて不利になる気がする

*2:コンテスト開始前に必要な処理系などのインストールを済ませてインスタンスイメージを作っておくと便利

*3:一部チームは selenium で動かしてそれをスコアラーとしたようです。そっちのほうがかしこい

*4:個人的にはこういう設計がそもそもダメなんじゃないかという気もします。jsonメタデータを書くしょぼエンジニアリング最強なのでは??

*5:同じ人が二人いますが、よく知られているように優秀な人は分身します

ICFPC 2018: Team manarimo

昨日までの3日間、例年通り ICFP Programming Contest にいつものチームで出た。今年のチーム名は manarimo。

公式サイト: ICFP Programming Contest 2018

成果物 (github)

github.com

今年はメンバーの1人である osa_k がアメリカで出稼ぎ労働者をしていることから、日本の5人と osa_k は Goole Hangouts で会話しながら作業していた。

-n日目

チーム結成

昨年に引き続き同じ6人チーム。

osa_k, y3eadgbe, kawatea, mkut, yuusti, pepsin_amylase

会場選定

去年は越後湯沢のスキー客向けリゾートマンションを airbnb で確保したけど周辺施設がなにもない上にインターネットが貧弱*1で、温泉以外はいまいちだった。この経験を踏まえ、今年は利便性が高いところがいいという話をしていた。

y3eadgbe が社会性を発揮してオフィスマネージャーと交渉し、コンテスト期間中に勤務先の一番大きい会議室が独占的に使用できることとなった。

-1日目, 0日目

勤務先でハッカソンが行われたので睡眠調整を兼ねて徹夜。ハッカソンに飽きたチームメンバーと一緒にクソなぞなぞを解いていた。

www.nazomap.com

72問目を解いているときに、誰かが答えを思い浮かばず「マナリモって藻、存在しそうじゃない?」と苦し紛れに言ったのを聞いたぼくが即興ででたらめな設定*2を付け加えたところ結構ウケて、あとでチーム名として採用することとなった。

1日目

チームメイトが問題を読んでいる間に回答の提出方法を読んで submit.py を実装。公式の dfltTracersL.zip をそのまま提出してテストしようとするも、コンテスト開始3時間までは提出できずに怒られたりした。

submit.py のテストを済ませたあと、生成した回答などを管理する web アプリを立てることにした。

ナナチ

熟慮の末今年の ICFPC ではメイドインアビスからツール名を取ることにし、管理アプリをナナチと命名。2015年に書いた響のコードをコピペして必要な改修を加えていった*3

energy の計算をやっている公式ツールの再利用を試みたがブラウザから剥がすのは難しそうだった(ICFPC2018あるある)ので、公式ツールを手で実行させたときに得た結果を JavaScript で抜き出してナナチに生やしたエンドポイントを通じて MySQL に突っ込むという仕組みを考案し、osa_k と分業してこれを実装した。

ナナチに登録したデータがすぐに反映されないという問題が発生。どうも MySQL の Isolation Level が REPEATABLE READ であることに起因しているっぽく、いたるところで commit して強引に解決するなどした。

2日目, 3日目

Lightning が終了したので一旦帰って寝た。休んでいる間に既存の Trace を後処理で改善するというアイデアを得たのでこれをやることにした。

ミーティ

既存のファイルはすべてバイナリの .nbt ファイルで保存していたので、後処理器に食わせるためにチーム内で使用しているアセンブラフォーマットに戻すツールを書いた。ミーティと命名。これは他にも壊れた nbt ファイルを生成した他のソルバーのデバッグに役立った。

ナナチ炎上

Lightning が終わった頃からナナチが頻繁に死ぬようになる。osa_k が jenkins を使ってすべての問題に対してソルバーをぶん回してナナチに提出する機能を作ったのだが、これを使うと何問か提出したところでナナチが止まってしまう。

一応再起動すると治るので、死ぬたびに再起動で生き返らせていた。こっちの名前をミーティにしておけばよかったと少し後悔する。

osa_k を消耗させることにより、コネクションプールを使ってないことやらナナチのプロセス数が足りないことやらどうも nbt ファイルをバイナリブロブとして突っ込んでいることやらが怪しいのではないかとなり、治してもらった。

ウェブアプリの負荷耐性を上げるという事実上の ISUCON をすることになったのでちょっと面白かった。これは2015年のチームの反省会の話題に出た(らしい)のだけど、ICFPC で使うインフラは意外と負荷がかかるので、動けばいいという気持ちでやるのはあんまりよくないっぽい。

ボンドルド

後処理器その1にボンドルドと命名。命令を1つ前のwaitと交換するのを貪欲に繰り返し、すべてがwaitだけになったターンをスキップすることで圧縮を図る。だいたい数%から10%ほどの energy 節約効果があった。

yuusti のハローワークや mkut のスプラシューターコラボ、kawatea のシヴァと組み合わせてハロワボンドルド・スシコラボンドルド・シヴァ神ボンドルドというソルバーにするなどしてチームの成果物に組み込まれた。

プルシュカ

ボンドルドは一定の成功を収めたものの、生成された出力を見ると順番を入れ替えられないばかりに長々と待たされている状況があることに気がついた。

そこで、本当に入れ替えてはいけない依存関係と同時に実行しなければならない依存関係を解析して DAG を生成し、ここから適切に命令列をつまんでいくという賢しらかつ ICFP っぽい手法を考案した。プルシュカと命名。

入力の命令列は harmonics やら volatile check が正しいという仮定を置くと、だいたい以下のような依存関係に気をつければいい気がしてくる: 

同時実行制約
  • グループで実行する命令: GFILL, GVOID, FUSIONP, FUSIONS
  • 同時に実行される FILL / VOID
順序制約
  • 別のターンに実行された FILL / VOID はその順序を保つ
  • 同じボットの中では移動系 (SMOVE / LMOVE) と場所に依存した効果を持つ命令の間ではその順序を保つ(場所依存命令の場所を変化させないため)
  • すべての命令はそのボットを生成した FISSION より後
  • すべての命令は FUSIONS / HALT より先

FILL / VOID の同時・順序制約は harmonics チェックをサボるために入れた雑な条件。これを実装してボンドルドを過去にするぜ、と息巻くも実行すると途中でエリア外に出る命令を実行しようとしたり、実行できる命令がなくなったりしていまう不具合に遭遇した。

エリア外に入れるやつはどうも移動命令の順番を入れ替えるのが悪いっぽく、同じボット内での移動命令どうしに順序制約を入れると治ったが、最初の目論見である移動の大胆な最適化が予想以上に難しいことを示しており動揺した。

実行できる命令がなくなってしまうのは、よく調べてみるとどうもデッドロックらしいことが明らかになった。例えば、2つのボットがお互いの場所へ移動しようとする SMOVE 命令を構えている場合、どちらかを先に実行することはできない。分散処理の有名問題を踏み抜いてしまい、ICFPC らしさと絶望を感じた。

どちらかを邪魔にならない場所にどかすよう命令を追加するという雑な方法で回避するアルゴリズムを実装したが、これのバグは取り切れず、バグを踏まなくてもこれによって最適化の結果ターン数がかえって長くなってしまう現象などが発生し、この時点で完全に心が折れてプルシュカの方針は諦めることにした*4

コンテストの残り時間はボンドルドの改良に費やしたり唯一神の訃報に驚いたりしていた。

感想

非ゼロの貢献ができてよかったけれど、ナナチはかなり負債を残して osa_k や y3eadgbe に苦労をかけたし、プルシュカは投入した時間に見合う成果ではなかったのが残念。

毎年 webapp をコピペしていることを考えると ICFPC 用 webapp ライブラリが作れるのではないかとちょっと思ったりした。

宿題

  • プルシュカの方針は実現可能なのか。

特にデッドロックを依存グラフから検出できるか。移動命令の制約を保っているので各命令での場所はわかるはずだが、グラフに WAIT が現れないのでどうなんだという感じ。

  • MySQL のコネクションの動作やブロブの扱い方を学ぶ。

*1:モバイルwifiで提供されていて、mkutが音楽を聞きながら作業しようとして一瞬で通信量を使い果たした

*2:github の README に書いてある

*3:響を改造したのでヴェールヌイにしようかと思ったけど熟慮の末やめた

*4:一応ごく一部の成功例は最終提出に使われた

AtCoder Grand Contest 022 C - Remainder Game を解くときに考えたこと

背景

chokudai.hatenablog.com

こういう記事が出ました。で、ぼくが気になったのが、実際のところこの記事で言及されている問題(C - Remainder Game)を解くときに人々はどういう思考をするんだろう? ということでした。多分他の人も気になっていると思うので、先ず隗より始めよということで自分が考えたことを書きます。無駄なこともいろいろ考えてて長くなりますが、おつきあいください。

筆者について

amylase - AtCoder

これを書いているとき AtCoder Rating 2302 です。700 点問題なら時間さえあればまあ解けるんですが、コンテスト中に確実に通せるかと言われると……というのが最近の実感です。

 

では始めます。

初手の決定

(典型っぽい要素から出てきたアイデアを太字で強調します)

1回のコストは 2^k ということからいかにもビットで考えてくださいという雰囲気を感じ取り、同じ k を2回以上使う必要がないならビット列の辞書順最小なるなあとまず思います。辞書順最小には文字を先頭から小さい順に試して可能かどうか判定するという典型があるので、これに落ちると嬉しいということを意識しました。

つぎに k を選んで操作するのを繰り返すという点ですが、これについては元記事にもあるように k の順序や回数に便利な制約をつけられると嬉しい気持ちになりました。コストの部分でも言ったように2回以上使わないという制約があるといい感じですし、順番についてもいい感じの制約をつけられないか考えることにしました。

操作列に関する考察

いきなり全体で考えると頭が爆発するので、ぼくがよくやるのは部分問題について考えることです。これが解けないと話にならないし、部分問題の考察結果が活用できることはよくあります。で、今回考えた部分問題が n = 1 かつ出力が -1 かどうかのみ判定するというやつで、これについては a / 2 より大きい k を選ぶことを考えると  b が x / 2 未満であることが必要十分だとわかります。が、これだけではどうこうできる感じでもありません。

コストについても考えていきたいので、引き続き n = 1 で k の列の制約について考えます。n = 1 なので mod は必ず取るとしてよいことに留意しつつ、たとえば 2, 3, 2 の順でやることに意味はあるのか……と想像していくと、なんとなく同じやつは2回やっても無駄な感じがしますが、証明できる感じはしません。

(ここで結構考える)

具体例で色々計算しているうちに、小さい k で mod を取ったあとでそれよりと同じか大きい k を選んでも値は変化しないことに気が付きます*1 。すなわち、意味のある操作列は k_1 > k_2 > k_3 > ... を満たすということで、辞書順最小の典型に落ちることが分かりましたし、この結果を得たときにこの問題が解けそうだという感触を得ます。

判定問題

 今までに考えてわかったことをまとめると、次のようなコードを書けばいいことになります。

  • 各要素についてコスト無視で可能かどうか判定してダメなものがあれば -1 *2
  • k として max(a) から 1 まで大きい順に、「それがないとダメか判定」して必要なら入れる
  • 必要な k のコストの総和を出力

あとは「それがないとダメか判定」を詰めればいいわけです。

部分問題から考えて1個ずつ、k 未満を全部使っても b にはならないかどうか判定し、もしそうなら a を x % k で書き換えていけばいいかなと考えます。たとえば、次の入力

2

17 10

8 1

に対して、k = 9 は 17 に対して絶対必要なので使用します。

ここで気になったことが出てきて、ある k が必要だとわかったときにそれをほかの a  の要素を書き換えるのに必要かどうかは定かではないということです。先程の例だと 10 を k = 9 で 1 に書き換えれば終わりですが、これの b_2 が 1 ではなく 2 だと書き換えないほうが得です。

書き換えてループを回す戦略がうまく行かなさそうなことがわかったのでこの方針を捨て、辞書順最小の典型で判定問題を書くときに利用できるすでに決定した列の情報を利用することを考えます。

n = 1 で k の操作列が与えられたときに a を b にできるか考えると、これは部分和問題の足し算を mod k に置き換えたものだと気がつき、同じような動的計画法を実装すればいいことがわかります *3

実装

https://beta.atcoder.jp/contests/agc022/submissions/2408219

これをコードにすると上のようになり、これで AC です。a < b のケースを見落として 1 WA 食らいました……。

dp 関数が部分和問題を変形した動的計画法の部分で、ok 関数が判定問題の部分です。

最後に

他の人が解いた過程も知りたいので他の人も書いてください!!!

他の人

AGC022 とか reminder game atcoder でググって出てきた皆さんです。判定問題の部分で解説にあるようなグラフ構築でやってる人が多いです。

noimin.hatenablog.com

hamko.hatenadiary.jp

kurkur.hatenablog.com

thaim.hatenablog.jp

d.hatena.ne.jp

(22:08 追加) 各操作が最大1回ってのが見えるの速くてビビる あとぼくも時間計っておけばよかった

tozangezan.hatenablog.com

*1:これが典型に思える人だと10分ACが見えてくるのだと思います

*2:最初に考えた部分問題の結果をそのまま利用します

*3:実際にはなんか有名 DP っぽいと思ったところで実装がイメージでき、今これを書くときに部分和問題の名前を思い出しました

項目応答理論を用いた音楽ゲームの譜面難易度推定における一次元性の確認

導入

心理学的な量を測定するための理論の1つである項目応答理論においては、(多次元拡張されていなければ)応答が一次元性を持つこと、すなわち測定しているただ1つの量のみによって応答が説明できることを仮定しています。例えば TOEFL は項目応答理論を用いて語学力という心理量を測定する試験ですが、すべての問題について、それが解けるかどうかは各人が持つ語学力によって決まっているという仮定をおいていることになります。

項目応答理論の応用としては、語学力の他にも音ゲーの譜面難易度推定というものがあります*1。こちらにおける一次元性はどうでしょう、地力という心理量があってそれを測定していると考えてもよいのでしょうか。SOUND VOLTEX なら地力はつまみ力・鍵盤力・片手力などの要素に分解して議論することが一般的です。IIDX 出身のプレイヤーが14 *2 が半分も埋まらないうちにあっさり大宇宙ステージ [EXH] をクリアするなど、一次元性に反しそうな例も知られています。ボルテの応答は先に挙げた要素からなる多次元量によって説明するほうがよいという考え方もありえます。果たしてボルテのデータセットに一次元の項目応答理論をそのまま適用するのは妥当なのか、検討しました。

手法

プレイデータに対して主成分分析を行い、それぞれの主成分の解釈を行いました。

SDVX III のスコアツールに登録されているデータのうち twitter 上で収集できたものをもちいました (プレイヤー数 2375) 。このデータ上でクリアレート *3 が 95% 以下の 351 譜面を対象として、プレイヤーが譜面を通常ゲージでクリアしていれば 1、そうでなければ 0 とした反応行列を生成しました。プレイヤーをデータ点とし、各譜面のクリア反応が説明変数です。

このデータをもちいて、各譜面のクリア反応のペアの相関を求めて相関行列とし、これの固有ベクトルを計算しました。

結果

寄与率(各固有値固有値の総和に対する割合)は次のとおりです。

f:id:pepsin-amylase:20170317040856p:plain

寄与率が低い順にソートしています。とても偏っていることがお分かりいただけるかと思います。

f:id:pepsin-amylase:20170317040900p:plain

こちらが上位 5 成分について拡大したものです。第1主成分だけで 0.5 以上ありますし、この 5 つの寄与率の和は 0.722 にもなります。

各プレイヤーの第1主成分得点を横軸に、第2主成分得点を縦軸に取った散布図は次のようになります。

f:id:pepsin-amylase:20170317041402p:plain

なんだかものすごくきれいな曲線が見えます。

同様に、縦軸を第3主成分得点や第4主成分得点に置き換えると次のようになります。

f:id:pepsin-amylase:20170317041607p:plain

f:id:pepsin-amylase:20170317041640p:plain

ここにもきれいな曲線が見えます。

また、各種成分ベクトルの要素は、第1主成分については全て正、それ以外は正の要素と負の要素がだいたい半々でした。

議論

寄与率のグラフを見ると、全体の分散のほとんどは少数の主成分で説明できることがわかります。特に、第1主成分の寄与率が0.5を超えており、これだけでも一次元性が成り立っていると言ってもいいかもしれません。

しかも、この第1主成分はただひとつ要素が全て正です。これはクリア力の主成分であると解釈できます。

より興味深いのは主成分得点です。主要主成分の方向に射影するととてもきれいな曲線が出てきます。この現象を説明する1つの仮説を以下に説明します。

簡単のため、レベル14・レベル15・レベル16の3譜面からなるデータセットで同様の実験をしたと考えます。これらの譜面の難易度には十分な一次元性があるとすると、データ点の分布は次のようになるはずです。

f:id:pepsin-amylase:20170317044424p:plain

ここに主成分、つまり分散が大きくなる方向を書き加えると、

f:id:pepsin-amylase:20170317044452p:plain

こうなります。これは第1・第2主成分得点の散布図に近い感じがします。第3主成分は、15と16の軸を取り替えて *4

f:id:pepsin-amylase:20170317044643p:plain

こんな感じになっている気がします。

結論

主成分分析を行うことにより、寄与率 0.5 を持ち、しかも地力と解釈できる主成分を得ました。第2主成分以下についても、一次元性を仮定すれば難易度を別の形で表現したものであるとして説明できる可能性を示しました。SOUND VOLTEX のクリアデータは一次元性を仮定して解析してもよさそうです。

今後の課題

  • 他の反応(ハードクリア、UC *5 など)での一次元性
  • 他のゲームに置ける一次元性
  • 譜面属性は経験的には明らか。今回はノイズとの分離に失敗しただけかもしれない。一般的に考えられている属性が偏った譜面だけをデータセットに集めたら主成分にそれが現れるかも *6
  • 「仮説」は主成分得点の散布図が特定の曲線上以外にも点を持つことを完全には説明できていない。

 

 

 

*1:強引な導入です

*2:III 基準。実験をしていた頃は IV はリリースされていませんでした。

*3:プレイしたことのあるプレイヤーのうちクリアした人の割合

*4:どちらか一方の重みをマイナス1倍することに対応する?

*5:フルコンボのことです

*6:簡便な実験法としてはボルテでテカリと松戸の譜面を集めてくるなどが考えられます

ISUCON6: Team イーグルジャンプ

ISUCON6 の予選に ICFPC のときのチームのサブセット (osa_k, mkut) で出ていました。

予選大敗北で、個人的にはデータに基づかずに適当に改善していっていた & ログ解析環境の準備を軽視した結果ボトルネック (クソデカ正規表現) に取り組むのがとても遅くなったのが敗因だと思っています。来年参加する人や実務で高速化する人は気をつけようね!

 

以下、チーム Slack で展開されたイーグルジャンプの心温まる会話集です(チーム名に合わせたアイコンを使ってるうちに気分がノッてきてなりきりをやっていました)。

イーグルジャンプの日常

f:id:pepsin-amylase:20160922001436p:plain

今までなりきりをやるのは頭のネジが足りない人だと思っていたのですが、いざやってみるとあたかも自分が美少女になったような気分になり、やってる人の気持ちがわかりました。 みんなもやりましょう。

f:id:pepsin-amylase:20160922001926p:plain

デプロイは osa_k 謹製 hubot aoba によって自動化されていましたが、本番時にうまく動かなかったのが残念。

f:id:pepsin-amylase:20160922002042p:plain

いやあ素敵な会社だなあ、おっとこんなところに Javascript のコードがあるぞ、実行してみよう……?

f:id:pepsin-amylase:20160922002335j:plain

ところがどっこいっ... 現実ですっ...これが現実っ…!

ICFPC 2016: Team 天羽々斬

EDIT 2016/9/22: !!! 最終順位も2位でした !!! やったぜ

 

ICFPC 2016 に出ていました。ランキング凍結時点で2位でした。優勝してるといいな〜、1位は凍結前で我々の3倍だったり1問を除いて全問解いたりしてますが。

 

ぼくは基本的にはアルゴリズムを考えて実装する係でした。この記事では自分のやったことについて書きます。インフラ周りについては @osa_k がきっと何か書いてくれると思います。

EDIT 2016/8/12: @osa_k が書いてくれました。さすが!

osak.hatenablog.jp

問題: http://icfpc2016.blogspot.jp/2016/08/task-description.html

凍結前のランキング: http://2016sv.icfpcontest.org/leaderboard

ソースコードhttps://github.com/osak/ICFPC2016

書いたツール

今年は SOUND VOLTEX からツール名を取りました。

rasis

チーム slack 用のコマンドラインインターフェイス。各人が思い思いの口調で喋らせてキャラ崩壊してたのがおもしろかったです。

ちなみにこのツールはコンテスト開始前に @osa_k が slack を立てた時に作りました。準備は大事。

f:id:pepsin-amylase:20160809070122p:plain

 

maxima

汎用ソルバー。facet(折り紙の折れ線で作られる多角形)が何枚重なっているのかやそれらの表裏や接続関係を全探索して正方形に復元できるかをチェックするアルゴリズムです。

コンテスト開始3時間後のお昼ごはんを食べている頃に思いついてチームメイトに言ってみると軒並み「確かに解けそうだけどバグる要素しかない(線分アレンジメント・双対グラフ構成・動的計画法による重なり枚数の列挙・全域木の全列挙・折り紙の復元)」という反応でしたが開始直後でやる気にあふれていたこともあり気合で実装しました。

Lightning が終了してもバグが取りきれず、一眠りしたあとでデバッグがおおまかに完了しましたが、結局折る回数が2回を超えると計算量が爆発してまともに解けませんでした。凸でないケースが解けるという強みがありましたが、それも @yuusti 作の天空の夜明けで解ける範囲であってこのツールは結局得点にほとんど貢献しませんでした。

いくらやる気にあふれていても事前に実装難易度や計算量を見積もっていれば結末はある程度予測できたはずで、今回の反省点になりました。

grace

すでに解いた問題とシルエットが合同(すなわち平行移動・回転・鏡像反転して得られる)な問題を探してきて解くソルバー。回転行列の導出がやや面倒である以外は、solution の生成で mkut が作った gideon が利用できたこともあってサクッと実装できました。

他のチームが古事記の再利用やそれらに少し手を加えただけの合同な問題を出していることが多かったので、少ない労力で高い効果を得ることができ maxima とは対照的な存在となりました。

また、この合同性を用いてまだ解かれていない問題をクラスタリングし、そのクラスターから得られる得点が多い順に我がチームが誇る折り紙職人が解いていくという戦略にも使用され、こちらも高い効果を発揮しました。

f:id:pepsin-amylase:20160809072948p:plain

grace cluster を報告する rasis

逆羅刹 (@osa_k 作の管理用サーバー) にもクラスタ一覧を見るページを付けてもらい、最終的にはぼくが何もしなくても職人が解くべき問題を探せる状態になっていました。

tsumabuki

@yowa さんチームが出した問題専用のソルバー。

すべての問題をビジュアライズして眺めていた @yuusti が、Team yowa からの問題は合同でなく grace では効率的に処理できないけれどもかなり規則的な生成法で生成されていることを発見しました。

他のチームもあまり解いていなかったこともあり、専用ソルバーを開発することになって書かれたのがこのツールです。終了8時間前くらいから実装を始めましたが、コンテスト終了までにバグを取り切って目標の問題を全部解き切れました。

反省

maxima をすぐに書き始めずに考え続ける精神力と判断力が必要でした。実装しているときは結構楽しかったけどね。

職人用に grace でクラスターを生成するとかすべてのビジュアライズされた問題をまとめて表示して比較・研究するというアイデアを出すなど、問題そのものでなく問題を解きやすくするための考察をできたのはよかった点です。チームに TopCoder 赤い人が2人もいるので問題考察力以外での貢献をすべきだと考えていましたが、無事達成できました。

来年は Unagi が殿堂入りしてくれたら優勝できるんですかね……。

 1位だったときにチームで出前の寿司をとって食べました。この時は楽しかったなあ。