【マルチデバイスチームブログリレー4日目】

こんにちは、エムスリーエンジニアリンググループマルチデバイスチームの藤原です。
業務ではiOS/Androidのネイティブアプリ、またはそれに関係するサーバサイドアプリケーションの開発をしたり、たまにインフラを触ったりしています。

今回は私の趣味である競技プログラミングに関する話をします。競技プログラミングの話といっても焦点を当てるのは問題を解くためのアルゴリズムの話ではなく、タイトルにある通りレーティングシステムの話です。マルチデバイスチームのブログリレーの記事ですが、チームの活動とは無関係です。また、弊社採用プロセスで行なっているコーディングテストとも全く関係ありません。完全趣味の話です。

競技プログラミングのコンテストを開催している各サービスではユーザの強さを数値で表すレーティングシステムを採用していることが多いです。その数値はコンテストの結果が良いと上がり悪いと下がるという性質は同じですが、アルゴリズムの細かいところは実はサービスごとに違っています。

では、どのような違いがあるのか図解して比較してみましょう！

図でざっくり理解することを目的としているため、この記事では細かい数式は扱いません。また、コンテスト初参加となる場合の初期値や例外的な微調整のための計算についても触れません。あくまでざっくり理解して比較してみるのが目的です。

本題に入る前に余談ですが、ブログリレー4日目の1月19日が私の誕生日ということで、本日が私の担当になるようチーム内で調整していただきました。もしよろしければブクマやシェアなどしていただけると嬉しいです（笑。

今年は卯年。広島県にある大久野島は別名「ウサギの島」としても知られ、多数のウサギが生息している。（本文には関係ありません）

（zamojojo [CC BY-SA 2.0], ウィキメディア・コモンズより）

イロレーティング

競技プログラミングのレーティングシステムそのものに触れる前に「イロレーティング」に触れなければいけないでしょう。イロレーティングとはチェスのために考案されたレーティングシステムで、「イロ」は考案者の名前に由来します。

現在のあらゆるレーティングシステムはイロレーティングをベースにしていると言っても過言ではありません。実際、オンライン対戦ゲームでもイロレーティングそのものか簡易版、またはイロレーティングをベースに改良されたアルゴリズム（グリコレーティング、グリコ2レーティングなど）を使っているものがほとんどです。

イロレーティングでは各プレーヤーの強さを表す評価値は正規分布に従うような確率変数とするモデルを使っており、勝負するときはその確率変数から「せーの！」で値を取ってきて大小比較して行います。細かい説明は省きますが、イロレーティングはその定義からレートの値の差から勝敗比が決まるという性質を持ちます。また、レートが明らかになっているプレーヤーがいれば、統計的推定によりそのプレーヤーとの対戦結果の勝率から他のプレーヤーのレートを導き出すことができるというわけです。

つまり以下のことが言えます。

対戦するプレーヤーのレート差から勝率を予想することができる
レートが明らかなプレーヤーとの対戦結果（勝率）から、レートが未知なプレーヤーのレートを推定することができる

競技プログラミングのレーティングシステムへの応用も基本的にはこれら考え方を元にしているようです。

さて、レートの更新がどうなっているかというと、とてもシンプルな計算式になっています。「プレーヤーのレート差から予想される勝利確率（ほぼ勝ちなら0.9、五分五分なら0.5、ほぼ負けなら0.1のような値）」と「実際の勝敗（勝ちなら1、引き分けなら0.5、負けなら0）」の差を定数倍して足し引きするのみです。

この更新を繰り返すことで真のレートに近づいていきます。また、予想を裏切るような結果ではレートが大きく変化し、予想通りの結果には小さな変化が起きることもわかると思います。

競技プログラミングのレーティングシステム

イロレーティングは１対１の競技であるチェスのために考案されたレーティングシステムでした。競技プログラミングのコンテストの場合は基本的に多人数で競う形式のためそのまま適用するのは難しそうですが、どのように考えれば良いでしょうか。

イロレーティングではレートから勝率が予想できましたが、競技プログラミングの場合は順位を予想します。どのようにするかというと、順位を予想したい参加者とそれ以外の参加者とのレート差から勝率が導き出せるので、1から勝率を引いた値（つまり負ける確率）を足していくのみです。例えば負ける確率0.5の相手が2人いたら、（0.5+0.5=1なので）順位は1つ下がるだろうといった具合です。またイロレーティングのように結果順位からレートを導き出すことも可能になります。

つまり、以下のように応用できます。

コンテスト参加者のレートから順位を予想することができる
レートが明らかな参加者とのコンテストの結果順位から、レートが未知な参加者のレートを推定することができる

これを踏まえて各競技プログラミングサービスのレーティングシステムを見ていきます！

Codeforces

まず Codeforces です。前述の通りコンテスト参加者のレートから各参加者の順位が予想できます。その予想順位と実際の順位とに差分があるとき、コンテスト前のレート値と真のレート値に差分があると思われるため、この差分を小さくする方向に更新したいわけです。そためにまず順位の世界で考えます。具体的には予想順位と実際の順位の相乗平均を求めます。そして平均をとった順位から推定されるレート値を計算し、その値と更新前のレート値との単純平均を取ったものが更新後のレート値となります。

一口にいってしまうと、予想と実際の順位の真ん中（相乗平均）を取り、その順位から推定されるレートとコンテスト前のレートの真ん中（単純平均）を取る、といった形です。確かに更新後の方が真のレートに近づきそうです。

図にするとこんな感じです。

LeetCode

プログラミング学習サイトの側面の強い LeetCode ですが、競技プログラミングのコンテストも開催しています。そのレーティングシステムは Codeforces とほぼ同じですが、最後の単純平均をとっているところが加重平均となっています。重みづけは過去のコンテスト参加回数が多いほど、更新前の値に重みを置くようになります。

加重平均の重みづけをする理由はコンテスト参加回数が多い人のレートは真の値に収束してきているだろうという考えからきていると思われます。つまり、たまたま調子が悪い回があっても調子がいい過去の参加回数が多いとレートの下がり幅は抑えられることになります。しかし逆に、精進して真の評価値が上がったとしても腕が上がる前の過去参加回数が多いとレートに反映されづらいという側面もあります。

Topcoder

Topcoder では LeetCode のようなコンテスト回数からくる重みづけの代わりに変動率という概念があります。変動率はレーティングと同じように参加者一人一人が持つ値で、コンテストに参加するごとに更新されていきます。コンテスト参加回数が少ないほど、また過去の成績が安定してないほど大きな値となります。この変動率とレーティングを使って、チャレンジファクターという値が計算されます。イロレーティングのレーティング更新で使用された定数の部分に当たる値で、コンテストの全参加者のレーティングの信憑性とばらつき具合に基づいて変化する値となっています。この値も参加者の変動率が大きいほど、またレートのばらつきがあるほど大きな値となります。

さて、さらに Topcoder ではパフォーマンスという概念もあります（色々ある！）。これは順位を正規化（0〜1に範囲に収まるように）したものを正規分布の累積分布関数の逆関数にかけたものです。なぜこんなことをしているのか。私の想像ですが、順位は一様分布になりますが実際の「強さ」は一様分布ではなくものすごく強い/弱い人は少なく平均に近い人は多い分布になるはずだという考え方に従ったものだと考えられます。そのパフォーマンスの世界で予想と実際の差分を出し、チャレンジファクターをかけ合わせたものをレート変動幅としています。

AtCoder

AtCoder のレーティングシステムでもパフォーマンスという概念がありますが、Topcoder のそれとは全く異なります。AtCoder のパフォーマンスとは特定のコンテストに対する結果を数値化したものであり、過去参加したすべてのコンテストのパフォーマンスの加重平均がレートとなります。重みづけは直近のものが重くなるような形を取ります。また、パフォーマンスを計算するための内部レート/内部パフォーマンスという概念も存在します。さらに、レートを指数変換した世界も存在しており、これらを行き来することでレートの更新を行なっています。

AtCoer以外のサービスでは「レートから順位を予想」「順位からレートを推定」というやり方をしてきましたが、AtCoder では順位予想をしていないのが特徴と言えるかもしれません。実際の順位とコンテスト前の参加者の内部レートから内部パフォーマンスにあたる値を計算し、その加重平均を取ったものがコンテスト後の内部レートとなります。そして内部パフォーマンスを決められた上限値で切り捨てたものがパフォーマンスとなり、パフォーマンスと更新前のレートを一旦指数変換した世界に持っていって加重平均をとり対数変換で元の世界に戻ってきたものが更新後のレートになります。この指数変換された世界はいいパフォーマンスにより重みをつけるために存在しているそうです。

指数変換を使った「いいパフォーマンスにより重みをつける」手法ですが、参加者側からするととても優しさを感じる設計だと思いました。コンテストは時間制限があるため普段なら解けるような問題でもちょっとしたバグを混ぜ込んでしまったがために正答できなくなってしまうことはたまによくあり、それは重要視して欲しくないわけです。しかし、難易度の高い問題が偶然解けてしまうことは少ないためなるべく成功は重要視してほしいのです。