二人対戦のプレイヤ強さを数値化したい

ゲームなどにおける二人対戦のプレイヤ強さの数値化手法について紹介します. ここでは導出などは行わずあくまで紹介に止めます. ・Ingo Rating Syatem シンプルで西ドイツで長く使われてきた. ・ECF Rating System こちらもシンプルなレーティングシステム.弱いときから始めている人がレーティングをあげるのは難しいため、何らかの救済措置が必要となる. ・Elo Rating Syatem(イロレーティング) 最も使用されるレーティング手法.レーティングの差分がそのユーザの勝率を示す.大きい値の方が強い. ・Glicko Rating System(グリコレーティング) Elo Rating Systemにおいてレーティングがインフレしてしまう問題を改善.またレーティングの信頼性も算出可能で,どれくらいの幅を持ったレーティングかが計算可能.一部の団体やゲームにて採用されている.Glicko2も開発されている.最後のプレイからの時間も考慮. ・True Skill MicrosoftがXBoxで採用しているレーティング.特許、商標を出しているため、使用にはライセンス許諾が必要.複数人やチーム対戦などにも対応したアルゴリズムになっている.

Ingoのレーティングはかなりシンプルなものになっている. 全員のレーティングの平均を求めて、(50% - プレイヤーの勝率) * Xポイント分の計算をして更新する.Xは適宜決める.

$$R = R_{average}-X \times (50 - \frac{N_{win}}{N_{total}}) $$

$$\begin{eqnarray} \left\{ \begin{array}{l} R = R_{enemy} - 50 + 100(win) \\ R = R_{enemy} - 50 + 0(lose) \end{array} \right.\end{eqnarray}$$

ECFは統計的な背景を考慮せずに算出するレーティングアルゴリズム. 非常にシンプルで、勝った場合は50増えて、負けた場合は50失う. ただし、プレイヤ間で40以上の差があると勝ってもレーティングが下がってしまうので、そのようなことはしないように注意.

Elo Ratingは様々な場面で使われる最も有名なレーティングアルゴリズム.チェスのレーティングのために開発され、二人組の競技にて計算することを想定している. 各ユーザの強さ(その日のパフォーマンスを含めて)を正規分布で近似できることを前提としている. レーティングの差分を計算することで相手に対する勝率を計算することができるのが特徴. 算出も更新も用意なアルゴリズムとなっている.

Elo Ratingを実際に適用した試合結果等についてまとめている動画は数多くあるので、どのような使われ方をしているかは右のリンク参照願います.

$$\begin{eqnarray} \left\{ \begin{array}{l} E_a = \frac{1}{1+10^{(R_b-R_a)/400}} \\ E_b = \frac{1}{1+10^{(R_a-R_b)/400}} \end{array} \right.\end{eqnarray}$$

$$R_{a_{new}} = R_a + K(S_A-E_a) $$

余談だが、Facebookのマークザッカーバーグが作成していたFacemashのランキングアルゴリズムはElo Ratingによるものらしい

Glicko Rating SystemはEloを改善したアルゴリズムになっており、採用実績も多い. 改善点は、 ・インフレしないような工夫 ・レーティングの信頼性を算出(前回プレイしてから時間が立っている等) を行っている.

詳しいGlicko Ratingの算出方法は右を参照

True Skillは複数人やチームでの対戦などにも適用することのできるレーティング手法. 各人のプレイヤの強さは正規分布で近似できることを前提としており(Eloも同じ)、 それらのパラメータを求める(分布を推定する)のが主な作業. 分布をモデル化してそれらをつなぎ合わせたファクターグラフを作成、そこから試合の結果を反映して各人の分布の更新を行います.

True Skillについては公式の説明をしているページ、よくある質問に対する答えなどを用意していますので、参考にしてください

Microsoftは近年True Skillの改良版True Skill2を発表しており, True Skillにゲーム内で得られる情報を付加してさらにレーティングの精度を高める工夫が行われている.