Codeforcesのレーティング計算の仕組み

Codeforcesのパフォーマンスって計算できるんだろうか、という話が挙がる機会が多いので、レーティング計算について調べた内容をまとめます。

情報源

公式な情報源はこれです。

Open Codeforces Rating System [updated on October 2015] - Codeforces

5年前に公開されたソースコードへのリンクもありますが、CF-Predictorのコードと少し違う点があり、時期を考えるとCF-Predictorのほうが正確そうなので、そちらを読んでいます。

CF-rating-prediction/RatingCalculatorTeam.java at e91f85dca8362c2c2b8e70289bf5e2afada6a1a9 · WslF/CF-rating-prediction · GitHub

この記事は2020年6月時点でのCF-Predictorのコードを元にしています。

アウトライン

レーティング計算のアウトラインは以下のようになっています。ここでの「参加者」や「順位」はratedな参加者を対象にしたものを指します。

各参加者に対して、以下のようにレーティング変動値を計算する。
1. 本人と他の参加者のコンテスト前のレーティングから、そのコンテストにおける本人の seed （後述）を計算する。
2. 本人がコンテストで取った順位とseedの相乗平均を取る。これを AverageRank と呼ぶ。
3. seedの計算の逆を用いて、「レーティングいくつならseedとAverageRankが一致していたのか」を計算する。これを expR と呼ぶ。
4. expRとコンテスト前のレーティングの相加平均を 新レーティング（の調整前の値） とする。これによりレーティング変動値を計算する。ただし変動値は $\lbrack -300, 700\rbrack$ の範囲に収める。
レーティングのインフレ/デフレを抑制するため、レーティング変動値の合計がおよそになるように調整する。
1. まず全員のレーティング変動値合計が $0$ になるように一様な値を加算する。
2. その後、コンテスト参加者 $n$ 人のうちトップ $4\sqrt{n}$ 人について、その中でのレーティング変動値合計が $0$ になるように一様な値を加算する。ただしこのときに加算される値は $\lbrack -10, 0\rbrack$ の範囲に収める。

これに加えて2020年5月ごろ以降は、あくまで「表示上の」補正として参加回数が6回未満の人のレーティングには参加回数に応じたマイナス補正が掛かっています（リンク）。

seedとは

イロレーティングに基づいて計算された「順位の期待値」とでも呼ぶべき値です。

イロレーティングは1対1での対戦における勝利/敗北確率を定義しています。ある参加者（本人）がレーティング $a$ であるとき、レーティングが $b_{i}$ である他の参加者に敗北する確率がそれぞれ計算されます。これを自分以外の参加者の $b_{i}$ 全てについて計算して和を取り、1を足したものがseedです。

seedの値は $a$ の増加に対して単調減少なので、逆算する際には二分探索が用いられています。競プロは競プロの役に立つ。

各コンテストにおける各参加者のseedはCF-Predictorで閲覧できます。

いわゆる25％説について

レーティング計算において、最近のコンテストの成績の重みが25％を占めているという話があります。これは、

AverageRankを計算するのに、現レーティングからのseed値と実際の順位の相乗平均を
expRを計算するのに、現レーティングとexpRの相加平均を

用いていることに由来しています。何かと何かが $1:3$ の割合で混合されている訳ではないので注意が必要です。

いわゆるパフォーマンスについて

AtCoderではパフォーマンスという値がレーティング計算の途中結果として生成され、ユーザーにも公開されています。「このコンテスト（と参加者集団）でこの順位を取ったらパフォーマンスはこの値」というのが自分のレーティングに依存せずに計算されるため、コンテスト1回ごとの出来栄えをレーティングの尺度で測るために重宝されています。

AtCoderではCodeforcesと異なり、本人がコンテストで取った順位から直接「レーティングいくつならseedと実際の順位が一致していたのか」に相当する値InnerPerfを求めています。これにコンテスト毎に設定されている上限を付けたものがパフォーマンスです。なので本人のレーティングの影響が混入していません。

一方でCodeforcesでは早い段階で本人のレーティングが計算に混入してしまうため、レーティング変動からパフォーマンスに対応する値を取ることは難しいと考えます。Codeforcesのレーティング計算とは関係なく、AtCoderと同様に取った順位を直接用いてseedの逆計算を行えばそれっぽい値は出ると思いますが、そのためには全参加者のレーティング情報が必要です。

実用上は、「CF-Predictorを見て自分の順位とseedの値が近い人のPrevious ratingを見る」くらいが良いのではないかと個人的には思っています。もしPrevious ratingから計算されるseedと同順位を取った場合、ゼロサム調整前のレーティング変動値が $0$ になるはずだからです。これは「あるパフォーマンスを無限回取り続けるとそのレーティングに収束する」という挙動にある程度合っています。