退職&転職しました
要約: 雑に仕事をやめて雑に新しい仕事を始めました。
退職しました
2022年5月にIndeed Japan株式会社を退職しました。リクルートに在籍していた時期もあわせて、新卒から7年間勤めていた会社でした。つい最近レイオフが発表されたIndeedですが、少なくとも自分が辞める時はソフトウェアエンジニアの楽園なのではないかと思うような素晴らしい職場でした。一人前のソフトウェアエンジニアとして育ててもらったし英語力もついたしで、最初のキャリアとしてはベストだったと思っています。
やめたきっかけはIndeedを先に辞めていたチームメイトからスタートアップを手伝ってくれないかと誘われたことでした。ちょうど30歳を過ぎて人生にあたらしい刺激を入れたいと思っていたこと、ダメでもしばらくニートできる貯金があったことから誘いを受け、フィットネス系のアプリの開発をしばらくやっていました。
また退職しました
アプリ開発は8月ごろにとりあえず動くようになったところでモチベーションが尽きてしまいました。そもそもフィットネスが自分にとって関心領域のド真ん中というわけでなかったのが最大の理由だと思っています。誘ってくれた人に謝ってまた退職し、束の間のニートをエンジョイしていました。
その後すぐにスプラトゥーン3が発売され、サーモンランを毎日8時間ほど仕事のごとくやり続けました。当時のテッキュウは強敵でしたね……
バイト始めました
このころにTwitterを見ていたところ、Optunaの開発をしながらお金がもらえるなんとも都合のよいアルバイトがあることを知りました。応募してみたところ無事採用され、PFNで週2回、クマサン商会で週3回バイトする生活が続きました（クマサン商会はもっと多かったかも）。OptunaからSciPy依存を消したりムニ・エール海洋発電所でカンストしたりと充実していました。
転職しました
10月ごろにAtCoder社のYouTube配信を見ていたら、学生に問題を解かせまくったデータを蓄積している変な会社が出てきました。AtCoderの難易度推定を通じてテスト理論に自信ニキだったので、コメント欄でそういう話を書いてアピール（？）のようなことをしていたら、配信後に@akenshoからDMで「そんなに興味があるなら応募せえ（筆者による要約）」と言われたのが転職先であるモノグサ株式会社との出会いでした。
こちらも応募してみたところ採用され、2023年1月から業務委託という形で学習履歴の分析に関わることになりました。最初に作っていたフィットネスのアプリのようなシード期ではないにせよモノグサもスタートアップであり、Indeedのような大企業ならあるものも全然なかったりします*1。そういう環境が不思議と楽しく感じられたし自分の力を発揮できそうだとも思えたので2月ごろにはフルタイムで働くことを考え始め、4月から実際に正社員に切り替えて働いています。
ダラダラ転職活動を振り返って
緩い雇用形態で短期間働いてみるのを合計3回やったわけですが、事業・業務の内容や会社の文化とのマッチング度合いがかなり正確にわかるので転職活動としては非常によかったと思っています。なんとなく面白そうな方向にふらふら寄ってみるのを繰り返していただけで意識的にやっていたわけではないのですが、振り返ってみると時間に余裕があればこういうやり方もあるなと感じます。結果的に半年くらいで辞めることになった最初の2社には申し訳なく思っていますが、緩い雇用形態なので許してほしいです。
CMの時間です
モノグサは、記憶という広大で未開拓な領域を共に探求する仲間を求めています！
*1:学習履歴の解析をする話だったのにそもそもデータ基盤が全然ないのでまずそれを作るところからだったり
2021年の実績解除リスト
ちょっと気が早いけど今年の振り返り。コロナの割には意外と思い出があった。
FF14 零式踏破
会社の同僚たちがやっている固定のメンツが一部抜けた入れ替わりに誘われて始めた。
最初は「GCDを回す」という行為がまず難しかった。やってない人向けに説明すると、FF14の戦闘では2.5秒に1回コマンドが入力できる。しないこともできるがただ損するだけなので高難易度のレイド（零式というのも高難易度レイドの一種である）では常にコマンドが切れないようにする必要があり、これを俗にGCDを回すという。ところで、レイドにはボスが存在するのでコイツの攻撃を避けないといけない。つまりFF14の戦闘はコマンド入力と攻撃回避のマルチタスクをやらせることによって難易度を上げているのである。
練習が素直に成果に反映されるゲーム性と我慢強い固定メンバーのおかげで楽しく実力を伸ばし、6月には再生編零式を踏破。
Typhonの占星術師です: https://jp.finalfantasyxiv.com/lodestone/character/33316029/
スノーボード
スノボは何もわからないのでスキー場でレッスンを頼んだところ、コロナのせいで他の客がいないのか集団レッスンなのに生徒が自分ひとりだった。コスパは尋常でなくよかったけれど経営が心配になってしまう。またかつてのようにインバウンドで荒稼ぎできるようになってほしい。
スノボの方は1日で初心者コースを滑れる程度になったがそこで体力を使い果たし、翌日以降はゲレンデに行きはするもののほとんど滑る気にならなかった。もう30歳なのでそろそろ体力を考慮した日程にするべきだ。
北海道に住んでみた / 原付を買った
コロナが広まってから勤務先の会社がフルリモートを許すようになったので、この自由を最大限活かそうという気持ちになった。北海道にある父の実家が、祖母が亡くなって以来誰も住んでなかったので需要と供給がマッチして6月から11月まで住むことにしてみた。
夏なら涼しいかと思ってたけど、昨今の地球温暖化のせいで暑い時期は本当に暑く、最高気温が35度とかでびっくりしてエアコンを買いに行ったりしていた（それまではついてなかったのだ）。とはいえ、京都の実家と年に1回往復することにすると快適な気候で過ごせる時期を最大化できるので全体としてはやってよかったと思っている。
地方で足がないと買い物がほぼ不可能になるので、原付を買った。軽自動車は「当たり判定」がデカくて恐いという気持ちと維持費を理由に買わなかった。広い国道で風を切って走るのが気持ちよく、仕事が煮詰まったときに用もなく近所を走り回ったりしていた。この歳で初めて原付に乗ってはしゃぐのは変だったかもしれないが、今年一番の買い物が何かと聞かれたら間違いなく原付だ。
ICFPC Judge's Prize
いつものメンバーでICFPC。今年はオーガナイザーがベテラン参加者だったからか、問題がここ数年の良回のエッセンスを集めて作られており、したがって良回であった。
チームメンバーの中では手動めんどくさがり度が高いので、手動ソルバーは人に任せて細かいプログラムを書いていた。そのうちの一つである各インスタンスの解を整数計画でうまく組合せるプログラムがジャッジの琴線に触れて Judge's Prize をもらえることになった。自分が書いたプログラムが理由に挙げられていたのが特にGood。
ひょっとしたら我々が3位と僅差の4位だったのでジャッジがなんとか理由を見つけて賞を恵んでくれたのかもしれないけど、事情はともかく今年1年はICFP公認でextremely cool hackerですので皆さんよろしくおねがいします。
beatmania IIDX SP九段
北海道に引っ越して原付を買った結果、日常の行動圏内にゲームセンターが入るようになった。本当はボルテが再開したくて行ってみたら弐寺しかなかったので最初は仕方なくやってたんだけど、そもそもよくできたゲームであるし昔ハマっていたこともあってすぐにまたのめりこんでしまった。
1ヶ月ほどでSP八段を取り直してリハビリが完了してからは（今八段ボスってギガデリじゃないんですね、七段はあいかわらずサファリだったけど……）、☆11をひたすらEasy埋めしていた。京都に戻ってからINFINITAS環境を整え、これまたひたすら練習して先日INFINITASの九段に合格した。CastHour九段は傲慢で落ちた。
2022年に狙うべき実績？
ICFPC優勝したいんだけど、Unagiだけじゃなくてtouristを含むヤバチームが出現してますます難しくなってるからどうしようかなほんと……
IIDXのSP皆伝はその威信と難易度こそあいかわらずだけれど練習環境と上達ルートが整備されてきているので実は狙い目なんじゃないかと思っている。来年中はまず無理だけど、中長期的にはやるべきことをやっていけば可能性があると思う。一番の障壁はモチベ。やめたら絶対に皆伝取れないので。
原付に乗ったら面白かったけれど原付一種の制限速度があまりにも低くて窮屈でもあったから上位の免許をとってツーリングなんかに行くと面白いかもしれない。
実績解除というからには全くやったことがないことにも手を出したい気持ちはある。
スプラトゥーン2 ガチエリアXになった
昨今のコロナでただでさえ長かった在宅時間が更に伸びました。それでスプラトゥーン2を再開してガチエリアのウデマエがXになったので、今考えていることを文章化しておきます。
成し遂げたぜ pic.twitter.com/bxwcK5emPs
— amylase伯爵 (@pepsin_amylase) 2020年12月12日
最大の目的はあとから振り返って読んでその時の自分と比較することで、たとえば他の人にXになる方法を説明するなどは意図しているわけではないです（でももしかしたら役に立つかもしれないですね）。
前提条件
ゲームの3状態
ガチエリアのゲーム状態は以下の3つです。
- 不利状態: 相手チームがエリアを支配している・できそう
- 拮抗状態: どちらのチームもエリアを支配していない
- 有利状態: 味方チームがエリアを支配している・できそう
もっと細かい状態を定義することも可能ですが、次の行動を決めるために状態を認識するという目的においてはこれで十分だと考えています。
不利状態
この状態からはいわゆる打開によって有利状態に持ち込むことを狙います。これはもういろんなひとが言っていることが正しくて*1、
- 味方が4人前線に復帰した状態で、
- （できればスーパーチャクチではない）2枚以上のスペシャルを撃ってエリアを奪回する
ように動きます。
バレルスピナーリミックスの場合は必要スペシャルが190と重くなくメインが結構塗れるので、死にさえしなければ打開に遅れることはないはずです。敵が前線を上げないように牽制射撃をしつつ味方を待ちます。
ナイスダマはエリアに投げるのがほとんどのケースで正解です。エリアのやや敵陣側に投げて敵をエリアからどかしつつ味方の短射程が自陣側を塗り替えしてくれて奪回、という展開になります。投げる前にエリアが取れた場合はもう少し奥に投げて前線をあげます。
拮抗状態
ゲーム開始時の状態で、打開が中途半端になるとゲーム途中でもこの状態になりますが、開始時以外の出現頻度はそれほど高くないです。人数差がつくか、どちらかの打開行動によって状態遷移します。
有利状態
相手に打開を開始させない、または打開を失敗させることを狙います。
打開を開始させないためには不利状態で自分が目指す状態を妨害すればいいので、相手をキルするか分断すればよいです。キルは無理にしても分断は頑張りたいところで、ナイスダマが貯まっていればそれを敵に投げて分断を狙います。相手の後衛をめがけるとうまくいきやすい印象です。
残念ながら相手が打開を開始できそうになったときには失敗を狙います。スペシャルが貯まっている相手を倒すのが手っ取り早いですが、ナイスダマが貯まっていれば相手のスペシャルを打ち消すことを考えます。ボムピッチャー系・バブルランチャーにナイスダマを重ねると消えるので、相手のスペシャル構成によってはあらかじめチャージしておくといい場合があります。
まあ、五分の実力で不利側が正しく動けば打開はだいたい決まるので失敗しても気にせず取り返しに行きます。
人数差による状態遷移
誰かの奮闘により人数差が生まれることはよくあります。不利側が人数有利ならキル打開が決まって状態遷移します。
画面上部のアイコンに気を配って、人数有利なのに引っ込んでたり人数不利なのに前に出過ぎたりしないようにします。
対面テクニック
メインの使い方
基本的にはスペシャルで盤面を動かすことを軸に考えているので対面はキルが取れたらラッキーくらいに考え、牽制射撃で相手を近づけないようにします。
自分より射程が長くガチエリア採用率の高いハイドラント・スプラチャージャー・リッター4Kの3兄弟が相手にいる場合は常に位置を把握する勢いで意識します。基本的にこちらからは手出しできないので、抜かれないようにしつつエリア塗るなり他の敵に牽制を浴びせるなりしておきます。
射程が長く塗り性能があるので、エリアに干渉する能力が高いです。エリア塗りを起点に局面を動かせるので、とりあえず塗れそうなら塗っておきます（雑）。
ポイントセンサーの使い方
自分を見ている短射程に当てて追い払う、気がついた潜伏・裏取りを味方に報告する用途が強いです*2。不利状態では潜伏がよくいる場所に投げて事故を減らす、有利状態では裏取りルートに気を配って入ってきた敵にぶつける用法を意識します。
インク消費がバカにならないので、やみくもに投げる用法は弱いです。
他のルールへの所感
ガチヤグラはヤグラの支配者と位置でゲーム状態が決まってエリアの次にシンプルだと思います。ゲームスピードがヤグラの速度で律速されて速くないので次の手も考えやすいです。
ガチホコ・ガチアサリはゲーム状態が複雑でその遷移も速く、ガチアサリに至ってはステージ全体で戦闘が発生するので今のところゲーム展開についていけていない感じがしています。この2つ難しくない？
Codeforces Grandmaster になった
概要
これはいわゆる色変記事*1です。
先日の Codeforces Round 687 で Contest Rating が 2402 になり、Grandmaster (赤) になりました。来年4月には私の Codeforces アカウントが10周年を迎えるので、せっかくだから振り返りをします。
2020年12月1日現在 Grandmaster の自分のアカウントです。これだけでも見てくれ！
自己紹介*2
2013年にあの東京大学理学部情報科学科を卒業しました。学科の同級生だけでも複数の赤経験者、Kaggle Grandmaster、ICPC 日本大会のジャッジがおり、競技プログラミングをやっていて赤タッチしたことがなかったのを少し引け目に感じていたくらいです。
現在は数年前に競技プログラマーを大量に吸収した例のI社でソフトウェアエンジニアをやっています。
実力向上に寄与したこと
過去問・バチャ
私見ですが、ある程度の実力（AtCoder R2000, Codeforces R2100 くらい？）がある人だと知識はだいたい揃っていて、勝敗を分けているのは見たことがある考察パターンの引き出しの数だと感じます。みなさん賢いのでだいたいの問題は十分に時間があれば解けるんですが、競技プログラミングで与えられる制限時間は2時間程度、1つの問題にかけられる時間だと30分程度とかなり短く、この制約をクリアするには類題を過去に見たことがある必要があります。
パターンをたくさん見てコンテスト本番で引き出せるように身につけるためには、やはり実際に問題を解くのが効率がよかったと感じます。パターンを引き出す練習にもなるので、限界効用はかなり逓減しにくいと思います。
昔に比べて練習環境はよくなっていると感じます。練習用の問題が圧倒的に多いこととそれによって適切な難易度が選びやすくなっていることは大きいです。TopCoder 全盛期に練習しようとして、使いにくい TopCoder Arena をなんとか開いて取り組むのが簡単すぎる Div. 1 Easy と難しすぎる Div. 1 Medium でモチベが切れてやめる、というのを何回かやった身としてはかなり練習しやすさを感じます。
強い人の練習量を見る
心が弱ってくると、「実は自分は天才なので何もしなくてもコンテストに出続けているだけで強くなれるのでは？」という邪念が湧いてきます。*3
ですが、例えば AtCoder 赤や Codeforces IGM の人の Twitter アカウントを見ると、こちらが心配になるくらい練習ばっかりしているのが分かります。どっちが正しいかは明らかですね？
昔は赤い人達は天才だから……みたいな信念が広がっていたように思いますが、近年は上位陣の練習量がきちんと可視化されたおかげで「邪念」に惑わされにくくなっているように感じ、これもよい変化だと思っています。
実力向上に寄与しなかったこと
労働
時間と体力が吸われます。最悪。
実は10月から3ヶ月間無給休暇を取ることができ、ここで生まれたリソースを練習に突っ込んで赤に届いたので、労働の有無とレーティングの向上には因果関係があることが証明されました。
今後について
今年いっぱいで休暇が終わってしまうので、労働を再開したら深夜の Codeforces に出るのは難しくなると思います。AtCoder は日本人に優しい時間にあるので続けるつもりです。橙はタッチしたことがあるので次にこういう記事を書くとしたら赤ですが、かなり遠いので次も10年掛かってしまうかもしれないですね。それでも続けることが一番効果的だと今なら思えるので、ゆっくりやっていこうと思っています。
AtCoder Problems の難易度推定について
https://adventar.org/calendars/3865
Competitive Programming Advent Calendar 2019 の12月5日分です。この記事を書いた2019年12月時点でのAtCoder Problemsの難易度推定について、思いつく限りの話題を書きます。
あなたは誰？
AtCoder Problems に難易度推定をつけた人です。AtCoder社の人の次くらいにレーティングシステムに詳しいと思います。
AtCoder Problems の Difficulty ってなんですか？
現在の内部レーティング*1がこの値の人がコンテストでその問題を見たら50%の確率で解けると考えられる値です。過去のコンテストの結果から推定しています。
DifficultyがX色という表現をたまに見ますが、これは AtCoder Problems 上でそれぞれの問題が難易度に対応するレーティングカラーで表示されていることによります。
推定難易度の横に試験管の絵文字（🧪）がついている問題があります。これは公式のレーティングシステムが導入される以前の問題に対して、やや強引な手法で難易度を推定したものです。様々な理由で絵文字がない問題よりも推定の信頼度が低いと考えられます。
Twitterで見かける反応へのお返事 (Q&A)
Recommendation で絶妙な難易度の問題が出てきて便利、すごい、シンギュラリティ！
いえーい、ありがとうございます。
古い問題の推定難易度が高すぎない？（= 見た目の値よりも簡単に解ける）
公式レーティングを使った推定難易度とそれ以前の難易度 *2は、推定のもとになっているレーティングに連続性がないのでたぶん絶対的な水準がずれています。でもどう補正したらいいか見当がつかないので放置されています。
2020-03-15 追記: Experimental の推定に使っているレーティングの計算を見直して、どの問題も400くらい下がりました。なんとなくよくなった気がします。
参加者の少ないオンサイト決勝などで推定が変なことになってるよ
データが少なかったり全員がACしてるとおかしなことになります。こういう単純な場合は機械的なチェックで弾いてますが、それ以外にもどう見てもおかしいだろというのがあれば @pepsin_amylase までお知らせください。
X色になるにはX色の問題が毎回解けないとだめなの？ / X色の問題がコンテスト中に解けたらX色パフォが出るってこと？
X色タッチを目指す人にとってX色の問題はかなり難しいと思います。というのもX色の問題はX色の人が取り組んでだいたい正解率50%だからです。したがって、X色の問題が解けた回は平均的X色よりもよい成績だったと考えられますから、X+1色くらいのパフォーマンスが出ていても不思議ではありません。
2020-03-15: X色の問題を安定して特にはX+1色くらいの腕前が必要なようです。
AtCoder ProblemsのDifficulty（=50%の確率で解けるレート）と90%の確率で解けるレートを比較したら、だいたいレート400くらいの差があるっぽい pic.twitter.com/SdDqdtUCDT
— not (@not_522) 2020年3月6日
Difficulty がより低い問題の Solve Probability が高いとは限らないのはどうして？
正解率推定モデルのパラメータには difficulty（難易度）のほかに discrimination（判別力）というものがあり、これはレーティングと難易度の差が正解率にどれだけ影響するかの指標です。難易度が非常に低くても判別力も低ければ正解率はそれほど高くなりませんし、同じくらいの難易度で判別力が高ければ正解率はそれより高くなります。
音ゲーの難易度推定っぽい
世の中の音ゲーの難易度推定やレコメンドと同じ手法（項目応答理論）を使っているからだと思います。*3
以上がユーザー向けの情報です。以下はいわゆる開発者向け情報で、具体的なモデルと未解決問題の話になります。
モデルについて
公式のレーティングシステムが導入された後の問題は、コンテスト本番の (ユーザー, 問題) の対を1つのデータ点として内部レーティングを説明変数、その問題に正解したかを被説明変数とするロジスティック回帰によって正解予測モデルを作っています。このモデルで正解率が50%になる内部レーティングを difficulty としています。
公式レーティング以前については、AtCoderサービス開始時点から現在と同じ仕組みのレーティングシステムがあると仮定して仮想のレーティングを計算し、その値を用いて同様に難易度を決定しています。この仮想レーティングは間違いなく公式レーティングとズレがあるのですが（ないと考える理由がないので）、どうズレてるか計算する方法がわからないので Experimental Estimate と称してそのまま公開しました（カス）
正当化
Elo レーティング
相対的な強弱を測る統計的手法として広く用いられている Elo レーティングというものがあります。勝率はプレイヤー間のレーティング差のシグモイド関数で決まるという仮定（Elo仮定）から導き出されるモデルです。
ところで、Elo仮定を用いると AtCoder のパフォーマンスレートとはその順位となるような確率を最大化するレーティング、すなわち最尤推定であることがわかります。したがって、AtCoder のレーティングはある種の Elo レーティングと解釈できるわけです。
項目応答理論との整合性
実は、レーティングをロジスティック回帰に放り込むと結構うまくいくことは前々から知られていました。
これらの先行研究ではどちらも項目応答理論 (IRT) を利用したと説明しています。項目応答理論のうちのロジスティックモデルは、さきほどの Elo レーティングとの対比を意識した言い方をすれば、受験者のある問題の正解確率はレーティング差のシグモイド関数で決まるという仮定（IRT仮定）を用いて問題と受験者のレーティングを決定する方法というふうになります。
本来のIRTであれば受験者の能力も難易度と同時に推定しなければならないはずですが、どちらの事例でも能力値をレーティングで置き換え、それでとてもうまく行っています。これはなぜか。
それはIRT仮定（+α）からElo仮定を導けるからです。コンテスタントA, Bが問題Pのみのコンテストで勝敗を決することを考えます。ペナルティのタイブレークはなしで、両方の正解数が同じ時は別の問題を選んで決着がつくまで繰り返すとします*4。このとき、勝率は選んだ問題に関係なくAとBのレーティング差のシグモイド関数になります。これはElo仮定にほかなりません。
IRTはEloの矛盾しない拡張だったので、Eloで決まったレーティングを用いて難易度を推定してもうまく行ったというわけでした。
蛇足: 「レーティングは強さの対数」
物理量でいう次元のようなものが崩壊してます。レートは強さの対数とったものなので、exp(レート) と他の値をかけましょう。
— rng_58 (@rng_58) 2019年9月28日
これは統計的にはどういうことかというと、強さの比較モデルとしてBradley-Terry Modelを採用しているという意味になります。つまり、（人間・問題間/人間・人間間）勝率が exp(レート) の相対的な割合とするとIRTもEloもそこから導かれます。
AtCoder以外の事例
Codeforces はほぼ同様の手法で難易度を推定していると考えられます。
Codeforces: Problem Difficulties - Codeforces
正解確率のモデルがレーティング差のシグモイド関数なので、変なことをしてなければ推定手法もほぼ同じだと思います。
paiza は最近 Glicko ベース*5の手法を導入しました。
プログラミング問題を解けばエンジニアの戦闘力がわかる！？レーティング機能公開 - paiza開発日誌
勝ち負け（ユーザー同士なら順位、ユーザーと問題の間なら解けるかどうか）がレーティングのシグモイドで決まるというのは Glicko でも同じですので、これもだいたい同じですね。paiza の場合はユーザーが好きなときに問題を解けるという性質があるので、対戦ゲームなどで使われるオンラインなレーティング更新法を採用しているようです。エンジニア戦闘力は Bradley-Terry Model での強さそのものです。
未解決問題
具体的な解法がわかってるやつは issue にしてあります。興味があればぜひ！
Issues · kenkoooo/AtCoderProblems · GitHub
この先はかなり謎で、脳内研究ノートたれ流し状態です。謎度が低い順に行きます。
時間の経過によるレーティングの水準変化
Eloレーティングとその派生シリーズの有名な弱点として、過去と現在のレーティングを比較できないというものがあります。これはレーティングがプレイヤー間の相対評価で決まっていて、プレイヤーの実力とその分布は時間の経過とともに変化していると考えるのが自然だからです。
これがチェスのような対戦ゲームの場合は打つ手なしですが、競技プログラミングや項目応答理論が想定する問題・解答者のペアの場合は問題が時間に対して不変ですので、これを基準に使えます。*6 具体的には、基準となる問題に対して複数の時点での結果データがあれば、その時点間で共通の難易度軸が得られるので、これに合うように各時点のレーティングを補正します。
この基準となる問題をどうするか。難易度推定をやり始めた2019年8月頃だと2つくらいアイデアがあって、1つ目は AtCoder Virtual Contest の結果を利用するもの、2つ目はAtCoder公式さんサイドに復習コンテストと称して過去のコンテストをそのまま再放送してもらうものを考えていました……
が、つい最近こんな機能が公式に実装されました。
さすがに目立つのでもう気付いてる方もいますが、バーチャル機能ができました。 #AtCoder pic.twitter.com/rj9XUtm3Gz
— ꑄ꒖ꐇꌅꏂ🐈 (@snuke_) 2019年11月28日
というわけですので、公式バチャのデータが十分集まったら直せるかもしれないから気長に待ってください。もしかしたらこれで仮想レーティングの補正もできるかもしれません。
問題を解くことによるレーティングへの介入効果
今のところ Moderate Recommendations は正解率が50%に近い問題を推薦しています。
50%の確率で解ける問題そのものがほしい場合は別にこれでいいのですが、多くの場合、本当にほしいのは学習効果、もっと直接言えばレーティングのはずです。それなら、ある問題をある人が解いたときのレーティング変化を予測して、それが最大になる問題を推薦すればいいことになります。
正直なところ、正解率50%の問題で精進しても最適な場合に比べて大幅に損しているとは思わないのですが、練習にふさわしい良問がこの研究で明らかになると面白そうです。
競プロ精進データセットで人間の学習を研究
問題演習の学習効果について先行研究がないか適当に調べてたのですが思いの外見当たらず、原因について考えてみたところそもそもデータセットがないのではないかという疑念を抱きました。つまり、
- 定期的に学力試験を繰り返していて
- その結果が公開されていて
- 問題演習の履歴もある
データセットって競技プログラミング以外にあるんですかね、これ実は教育学の研究ネタになったりしませんかね（超適当）？ 先行研究を教えてくれるのも大歓迎なので人間の学習に詳しい方を切実に募集しています。こういうのって心理学の守備範囲？
謝辞
使ってくださる方全員に感謝しています。Twitter でエゴサしまくって感想読みまくってます。フィードバックや怪しい推定値があったときもためらわずに教えて下さい。
kenkoooo さんにも感謝します。彼は作ったモデルを使ってもらう場を提供し、その維持費も払ってくれる聖人です。莫大な金銭を得たら余った1億円ほど寄付します。
AtCoder の問題を解くのにかかる時間をモデリングした
概要
AtCoder の問題に取り掛かってから AC するまでにかかる時間の対数の平均値は、レーティングの1次式で表現できると考えられます。
理論的導出
この記事の説明にあるように、AtCoderのパフォーマンスは、他の人に対する勝率が内部レーティング差のシグモイド関数で決まると仮定したときの内部レーティングの最尤推定値です。
ここから、2人がある1問の早解き競争したときの勝率も内部レーティングの差のシグモイド関数になると仮定します。この仮定を満たすような解答時間の確率分布を考えていくと、次の分布がその要件をだいたい満たすことがわかります（天下り）。
- 対数正規分布
- 期待値はレーティングの1次式
- 分散はレーティングによらない定数
早解きの勝敗は内部レーティングの差を正規分布の累積密度関数に与えたものとなります。正規分布の累積密度関数はシグモイド関数に似ているので、近似ということにします。
データで確認
分布を決定するには、内部レーティングから解答時間の対数に単回帰すればいいです。AtCoder Beginner Contest 138 の6問について、実際にやってみました。以下のグラフは、
- 縦軸を正解までの秒数
- 横軸をコンテスト開始前の内部レーティング
- 青い点が1人のAC
- 赤い線が求めた回帰式
- 黄色い線がユーザーをレーティング100ごとに区切ったときの平均値
です。なんかいい感じになっているのがわかります（適当）。Fはデータが足りなそう。
実験に使ったコード
ツイッターに書いた難易度推定の続きなので、両方ともここにあります。
その他
wacchoz さんによるレーティングを能力パラメータとしたロジスティック項目応答モデルでの難易度推定がうまく行くのは、上の理論的導出とだいたい同じ説明ができます。1問勝負で引き分けを無視してどちらか一方だけが正解する確率がレーティング差のシグモイド関数になるので、引き分けの部分は解答時間の勝敗がシグモイド関数で決まると思うと全体の勝敗もシグモイド関数になって（たぶん。ちゃんと計算してない）整合的です。
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 の場合は公式にステップバイステップのガイドがあるのでそれに従うといいです。
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回め）
