対戦ゲームのレーティングシステムについて
(筆者は統計や機械学習の素人なので間違いの指摘等歓迎です．)
はじめに
対戦ゲームにはプレイヤーの実力を測るためのレーティングシステムが導入されていることが多い．自分の知っているゲームだとスプラトゥーン，ポケットモンスター(のオンライン対戦)，マリオカートなど．
この三つのゲームのレートの中で，実はマリオカートのレートは少し種類が違う．スプラトゥーンやポケットモンスターのレートは「やればやるほど上がる」ものではないのだが，マリオカート(当記事では8DXを指すとする)のレートは実力がすごく高いわけではなくとも時間をかければ上がっていくシステムになっている．
それでは本当の実力が測れないということで，マリオカートガチ勢は「ラウンジ」と呼ばれる非公式システムを使い，そこではdiscordに戦績を入力することで独自のレートが計算される．自分はラウンジとは無縁のエンジョイプレイヤーなので詳細は分からないのだが，ちゃんと実力が反映されたレートになっているらしい．
それでは，その「実力が反映されるレート」とはどういうものなのか？
大雑把には「相手プレイヤーのレートが自分より高いほど，勝ったときにもらえるレートも大きく，逆に相手のレートが自分より低いほど，負けたときに下がるレートも大きい」という共通認識はあると思うが，具体的にどう計算されるのかは知らない人が多いと思う．
対戦ゲームでよく採用されているのはイロレーティングと呼ばれるレーティングシステムや，その派生型である．実際，スプラトゥーン2ではイロレーティングの派生であるグリコレーティングが使われていたらしく(解析班情報)(スプラ3のことはわからない)，マリオカートのラウンジでは，自分が調べた限りイロレーティングのようなものを採用しているらしかった．スマッシュブラザーズSPは世界戦闘力という名前で，自分の下の実力のプレイヤーが何人いるかをゲーム内に表示しているが，その「実力」を測っているのもイロレーティングらしい．
(ちなみに，最近自分がハマっているポケモンライクの海外ゲー "Temtem" でもイロレーティングの派生が採用されているぞ．)
ということでここではイロレーティングの数学的詳細について見ていこうと思う．
イロレーティングの理論
まず，イロレーティングシステムにおけるレートの更新を見てみよう．プレイヤー A と B が対戦しているものとして，それぞれの現在のレートを $R_A$, $R_B$ とする．勝負の結果， A が得たスコアを $S_A$ とする．スコアはゲームによってさまざまな定義の仕方ができるが，ここでは A が勝ったら $S_A=1$，負けたら $S_A = 0$ としよう．また，$K$ を正の定数とする．
このとき A の新しいレート $R_A'$ は以下である．
$$ R_A' = R_A + K(S_A - (\text{A の期待スコア})) $$
「A の期待スコア」は独自に定義される用語で，ここでは A が B に勝つ確率を意味する．定義は以下である．
$$ \text{A の期待スコア} = \frac{1}{1+10^{(R_B-R_A)/400}} $$
つまり、勝ったときのレートは $1-\text{(勝率)}$ の定数倍増えるし，負けたときは勝率の定数倍減る．
期待スコアの右辺は $R_A$ を変数としたときロジスティック関数と呼ばれ，0 から 1 までの開区間に値を取る．
この式を見ると，B のレート $R_B$ が A のレート $R_A$ より高いほど分母が大きくなり，A の期待スコア(つまり勝率)は低くなることがわかる．
また，$R_A'$ の式に戻ると，A が勝った場合，$S_A - (\text{A の期待スコア})$ は A の勝率が低いほど大きくなるので， A のレートの更新は大きくなる．
つまり，「自分よりレートが高い相手に勝つほどもらえる更新が大きい」といった要件が達成されている．
また，期待スコアはレートの差のみを使って定義されているので，もしたとえば A のレートが 1000, B が 1100, C が 1200 などというようにレート差が均等な場合，A が B に勝つ確率と，B が C に勝つ確率は同じということになる．
しかし，「期待スコア」は勝率を意味すると言ったが，本当に勝率を表しているのか？
結論から言うと，レートの更新は機械学習や統計学等で言うところの勾配降下法ととても似たことをしている．(より厳密には，確率的勾配降下法．)
レートというパラメータを勾配降下法により学習させ，期待スコアがちゃんと勝率を表すようにさせるのである．
(余談：前述したTemtemではイロレーティングを独自に変形した形でレートを計算しているらしく，おそらくスプラトゥーン3でもそうだ．これによってレートと勝率の関係が破れ，たとえばもしかするとたくさんレート戦に潜れるプレイヤーが多かれ少なかれ得をするシステムになっている可能性はある．)
確率的勾配降下法との関係を見ていこう．
ここからは，プレイヤーは $N$ 人いるものとし，プレイヤー1，プレイヤー2，…と呼ぶことにする．
プレイヤー $i$ とプレイヤー $j$ の対戦を $(0, \dots, 0, 1, 0, \dots, 0, -1, 0, \dots 0)^T$ のように，$i$ 番目が 1，$j$ 番目が -1，他が 0 となる $N$ 次元ベクトルを使って表す．このベクトルを $x_{(ij)}$ と書く．
$y=1$ のとき $i$ の勝ち，$y=0$ のとき $i$ の負けとして，対戦の結果を $(x_{(ij)}, y)$ というペアで表現する．
このとき $i$ 対 $j$ の結果が $y=1$ である確率は以下のように式変形できる．(ベイズの定理)
$$P(y=1\mid x_{(ij)}) = \frac{P(x_{(ij)}\mid y=1)P(y=1)}{P(x_{(ij)}\mid y=1)P(y=1)+P(x_{(ij)}\mid y=0)P(y=0)}$$
さらに変形して，以下の形にできる．
$$\frac{1}{1+\frac{P(x_{(ij)}\mid y=0)P(y=0)}{P(x_{(ij)}\mid y=1)P(y=1)}}$$
ここで $a =\log \frac{P(x_{(ij)}\mid y=1)P(y=1)}{P(x_{(ij)}\mid y=0)P(y=0)}$ とおくと，上の式は
$$\frac{1}{1+e^{-a}}$$
となり，期待スコアの定義に似ている式が出てきた．この式は $a$ を変数とするときシグモイド関数と呼ばれ，$S(a)$ と書く．(latexの\sigmaがなぜか出ない．なんで？)
また，$\frac{P(x_{(ij)}\mid y=1)P(y=1)}{P(x_{(ij)}\mid y=0)P(y=0)}$ はオッズと呼ばれる．ギャンブルなどで聞く言葉だろう．
オッズを，パラメータ $w_i$, $w_j$ を使って $w_i - w_j$ の形で近似することを考える．$N$ 人のプレイヤーに対する $w_1,w_2,\dots$ たちをまとめてベクトル $w$ で表す．(重みベクトルと呼ぶ．)
こうすると $w_i - w_j$ は $w^Tx_{(ij)}$ のように内積で書ける．
まとめると，
$$P(y=1\mid x_{(ij)},w) =S(w^Tx_{(ij)})$$
という式が作れる．
行なわれたすべての試合の結果のデータ(つまり $(x_{(ij)},y)$ の集まり)を $D$ と書きその要素を $(x_1,y_1)\dots, (x_K,y_K)$ とすると
$$P(D\mid w) = \prod_{k=1}^K S(w^Tx_k)^{y_k}(1-S(w^Tx_k))^{1-y_k}$$
となる．この全体データの確率を最大化するように $w$ を学習させていく．
これを最大化するということは，-log をつけて
$$-\log P(D\mid w) = -\sum_{k=1}^Ky_k\log S(w^Tx_k) + (1-y_k)\log (1-S(w^Tx_k))$$
を最小化することと同値である．この式を $E(w)$ と書く．
これの偏微分は
$$\frac{\partial}{\partial w_i}E(w) = \sum_{k=1}^K (S(w^Tx_k) - y_k)(x_k)_i $$
と計算できる．ここで，$(x_k)_i$ はベクトル $x_k$ の $i$ 番目の要素を指す．
勾配降下法は，この微分を使って
$$w' = w - \alpha\nabla E(w)$$
という式で $w$ を何度も更新していくことで，$E(w)$ を最小にするような $w$ を見付けるという手法である．($\alpha$ は定数．)
しかし $\nabla E(w)$ の中の総和を毎回すべて計算するのはコストが高い場合があるので，一回の更新では総和の中の項を一つだけランダムに選び，$\nabla E(w)$ の代わりに使うという手法もある．それが確率的勾配降下法である．
つまり，
$$w' = w - \alpha (S(w^T x_k) - y_k)x_k$$
が一回の更新の式となる．第 $i$ 成分に注目すると，
$$w_i' = w_i - \alpha (S(w^Tx_k) - y_k)(x_k)_i$$
となる．$x_k$ がプレイヤー $i$ 対プレイヤー $j$ の試合を指す場合，$(x_k)_i=1$ なのでこれは
$$w_i' = w_i + \alpha(y_k - S(w_i - w_j))$$
と書き直せる．実はこの式，記事の最初に与えたレートの更新の式とほとんど同じである．($S$ の定義と期待スコアの定義を見比べると，定数の分のみが違う．)
そういうわけで，これがイロレーティングの更新と確率的勾配降下法の関係であり，イロレーティングがそれらしく機能する理由の一つである．
その他のレーティングシステム
記事のはじめにスプラトゥーン2はグリコレーティングというイロレーティング派生を使っていると書いた．より厳密にはグリコ2レーティングと呼ばれるもので，これはレートのみではなくそのレートの不安定度も合わせて計算する．
たとえば，二人のプレイヤーが同じレートを持っていたとしても，片方が直近に何試合もこなしていて，もう片方が1年くらいゲームをしないままストップしたレートである場合，後者のレートはより不確かであり，その事実も計算に考慮しようというアイデアである．
また，イロレーティングやグリコレーティングはチェスのような1対1のゲームについて考えられたものであり，スプラトゥーンのように4対4で一人一人がレートを持っているという状況は想定されていない．(4人が固定チームで，チームごとに一つのレートが与えられるのなら問題ない．)
多人数ゲーム向けのレートとして，Microsoftが考案したTrueSkillというシステムがある．HaloやGears of WarといったMicrosftのゲームに使われているらしいが，特許を取得しておりMicrosoftのゲーム以外はライセンスを得ない限り使用が許可されていない．
ちなみにTrueSkillはAIのトップ国際カンファレンスであるNeurIPSに論文が採択されている．ゲームに関する研究でNeurIPSに採択されるのよくない？
ともかく，普段ゲームでなんとなく見ていたレートは意外と科学的に面白い．読者も面白く思ってくれたら幸いです．
参考
この記事の数学的な部分はほとんど以下の記事を自分用に再構成して日本語にしたものである．
