対戦ゲームのレーティングシステムについて
(筆者は統計や機械学習の素人なので間違いの指摘等歓迎です．)
はじめに
対戦ゲームにはプレイヤーの実力を測るためのレーティングシステムが導入されていることが多い．自分の知っているゲームだとスプラトゥーン，ポケットモンスター(のオンライン対戦)，マリオカートなど．
この三つのゲームのレートの中で，実はマリオカートのレートは少し種類が違う．スプラトゥーンやポケットモンスターのレートは「やればやるほど上がる」ものではないのだが，マリオカート(当記事では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に採択されるのよくない？
ともかく，普段ゲームでなんとなく見ていたレートは意外と科学的に面白い．読者も面白く思ってくれたら幸いです．
参考
この記事の数学的な部分はほとんど以下の記事を自分用に再構成して日本語にしたものである．
Temtem対戦初心者がダイヤに行った記録
11月中盤くらいにTemtemという素晴しいゲームのランクマッチに潜り始め先日ダイヤランク(レート1200)に到達できたのでその記録。始めたのが11月中盤と言っても、スプラ3に忙しかったり体調を崩したりしていて、11月は3日しか潜ってないし、12月も5日くらいしか潜ってないのでまぁまぁ良いペースで達成できたんじゃないでしょうか。
11月(シーズン1)
ランクマを始める前に、どんなテムが強いかなーと公式Wikiを見たり、自分でチームを作ろうとしたりしていた。しかし一回も対人戦をしたことがないので当たり前だけど感覚がわからないし、Showdown実装前で育成の手間もあったので既成のチームを使おうと思った。
そこでYouTubeを見ていたらseaKseaさん(当時のIGNはtemconさんだった)という方が初心者向けアグロチームを紹介していたので、それを使ってみることにした。
www.youtube.comこの動画の何が良いかというと、とにかく解説が豊富なこと。ピックバンの方針や、初手の選び方などを説明してくれているし、試合中に自分の思考を言葉にしてくれていて、わかりやすい。(英語だけど。)
ということでこのデジタル+炎+自然アグロを育てて早速ランクマへ。
記念すべき初めての認定戦の結果は6勝4敗でレート1096くらいだった。意外と勝てたなという印象。で、認定戦だけしてこの日は終わり。とにかくマイクロウェーブびゅんびゅんしてた。あとは火傷を入れてダメージを減らす意識をしたり、相手の裏を見て「相手のこのテムを倒すために自分のこのテムは取っておこう」と考えたりして戦っていた。
次の日あたりにも軽くランクマに潜ると、たしか1150くらいまでは行けたけど、そこで1100-1150くらいまでを彷徨う感じになったので、これが実力かなと思い終了。とらわれ状態なのに入れ替えようとしてターンを無駄にしてしまうなど、沼プが多かった。
で、そこからはランクマに潜っていなかったが、最終日の直前に某フレンドさんに「1200目指しましょう」と言われたのでやってみることにした。
最終日、出だしは順調ですぐ1190くらいまで行けたのだけど、そこからまた下がったり上がったりを繰り返す。1100-1140くらいまではそんなに相手が強くないなという印象だったけど、そこから上がきつかった。
とくに、トゥルカン+ティラナクの並びが大量発生していて、そこに速い水テムが加わるとこちらのチームはめっぽうきつかった。正直これはチーム単位で無理なのではと思い、夜中にウィプランを投入したりしたけど、体力の限界を感じたので諦めた。
何回か1190台には行って最高で1196だったのでマッチング運ではいけたかもしれないけど、流行りの構築に勝てなかったということでまぁ厳しい。ミノトール+ロールダーはそこまできつくはなかったけど。
ちなみに、この日seaKseaさんにマッチングして、見事に負けたけど、向こうからゲーム内メッセージをいただいた。チャット機能のあるゲームをあまりやってこなかったのもあって感動した。
12月(シーズン2)
前シーズンの雪辱を果たすぞ！と思いきや、なんとマイクロウェーブが仕様変更されシナジーが電気タイプに。パーティ崩壊。なんでや。
そこで先ほどのseaKseaさんが配信でデジタル+電気チームを使っていて、これなら似た感覚で使えそうと思いそのチームで認定戦に挑戦。
認定戦と同時に、なぜか慣れない生配信などということをしてしまい、時間切れ等の沼プを連発する。結果は4勝6敗でゴールド1-1。むずい。
その後、テム界の某うさぎちゃんから「このチームどうですか」と、razofinさんという方の炎統一(ほぼ)チームを紹介される(Y66GT)。前シーズンのチームと被っているテムも多く、使いやすそうだったので使ってみることに。
認定戦のデジタル+電気チームと比べて勝率よく勝てた。試合を録画して視聴者と見る配信もした。いろいろアドバイスをもらえて助かった。とくにレイドボスとの戦い方のアドバイスが参考になった。しかもなんとチームの生みの親であるrazofinさんも配信に来てくれたので、すかさず「水がいっぱいいるチームがきついんですけどどうすればいいですかね〜」みたいなことを英語で聞いたりした。速い水をバンするとのこと。ありがたや。
しかしゴールド2あたりで少し伸びが悪くなる。これはいかんと思い、炎パにきついテムの素早さや覚える技を公式Wikiで確認した。たとえば「シーズマンチが大地技を打つのはだいたい2ターン目以降」のようなことを最初はまったく把握していなかったのだけど、そういうのが分かるだけでもだいぶ変わる。
ということで再度ランクマへ。そこそこ順調に進み、ゴールド2-2から一日でダイヤへ。きた〜〜〜。
炎パの感想
強い。ヘルファイヤ強いし色交換クロメオンもおもしろい。ティラナクの威圧感と合わせてタイプ相性を切り替えるオシャレプレイもやりたかったけど、多分一回しかその機会はなかった。
あとバルヘルムの逆転力が高かった。ダイヤ戦最後のフィニッシャーもバルヘルム。かっこいい。バルヘルムしゅきしゅきぴっぴ〜〜〜
ウカマの選出率が私は低かったからもうだいたい統一パ。統一パなのに強くてすごい。ウィプラン・オセアーラ・プラティマスみたいな速い水が二体以上いるときつかったけど、それでも勝てたこともあった。見せ合いの段階で無理じゃねって思ったのに勝てて、やりがいがあっておもしろい。
Temtem対人戦の感想
めっちゃ楽しい。自分はピックバンがとくに好き。ポケモンだとかカードゲームだとかって初手の情報が非公開がちじゃないですか。ポケモンは選出択があるし、MtGみたいなカードゲームは相手の手札はわからないし自分の手札もランダム。(まぁカードゲーム詳しくないけど。)
Temtemのピックバンだと、相手の各テムの育成内容まではわからないものの、どのテムがいるかはわかった状態でお互い選出を進めて、最終的な相手の選出まで見えている。公開情報が比較的多い状態で戦うほうがゲームとして好きなのかもしれない。
あと乱数がないのも自分は好きかもしれない。択はあるけど、ポケモンと比べると少ない気がするし、択負けの損失もポケモンより小さいことが多い気がする。5vs5であることと、弱点を突かれてもワンパンされることが多くはないという性質が択負けの損失を小さくしている印象がある。ガチ勢じゃないのでわからんけど。
自分は使っていないけど、コントロール系のチームも面白そう。状態変化が交代しても続くから、じわじわ盤面をコントロールしていくっていうことができるのが良い。グランパーがTurbo Choreographyと催眠をしてくるチームに負けたときは、負けたのに面白かったし感動した。
ということで、これからもっと上を目指すぞ〜。
(念のために書いておくと、ポケモンをdisる意図はありません。)
