とある格闘ゲームのレーティング対戦サイトを作った時にGlicko-2 Ratingについて触れたので備忘録としてメモしておきます。
Glicko-2 Ratingとは
プレイヤーの強さをレーティングという数値で表すためのアルゴリズムの 1 つです。他にもElo Ratingが有名ですね。
Glicko-2 Ratingは対戦ごとに3つのパラメータを変動させてレーティングを決定します。
・$r : rating,$ 強さの指標となるレーティングの値です。一般的に初期値は1500であるとされています。
・$RD : Deviation,$ レーティングのブレを表します。$r \pm 2RD$ が95%信頼区間とされます。
・$\sigma : Volatility,$ 変動率と呼ばれます。プレイヤーの戦績の安定度合いを表します。大きいほど不安定です。
入出力で考えると
$[r, RD, \sigma]$ → 処理 → $[r', RD', \sigma']$
という話ですね。シンプル。
仕組み
Glicko-2の詳しい歴史はWikipedia辺りに任せるとして、早速実際の処理がどうなっているかを見てみましょう。今回実装するにあたり
を参考にさせていただきました。
Step.0：事前準備
初期 $r$ と $RD$ を決めます。また $\sigma'$の導出に必要なパラメータとして$\tau ( 0.3 \leq \tau \leq 1.2 )$を定めます。一般には0.5が採用され、小さいほどレーティングの変動が落ち着きます。
一例として、初期値を $r = 1500, RD = 350, \sigma = 0.06 $ とします。
Step.1：スケールの落とし込み
$\mu = (r - 1500)/173.7178$
$\phi = \frac{RD}{173.7178}$
$\sigma$ は変更しません。
プログラム上ではこの $\mu, \phi, \sigma$ を変化させることになります。
Step.2：下準備となる v, Δ の導出
$v^{-1} = {\sum_{j=1}^{m} g(\phi_{j})^2 E(\mu, \mu_j, \phi_j)[1 - E(\mu, \mu_j, \phi_j)]}$
$\Delta = v \sum_{j=1}^{m}g(\phi_j)[s_j - E(\mu, \mu_j, \phi_j)]$
$g(\phi) = \frac{1}{\sqrt{1 + \frac{3{\phi^2}}{\pi^2}}}$
$E(\mu, \mu_j, \phi_j) = \frac{1}{1 + exp(-g(\phi_j)(\mu - \mu_j))}$
（Qiita君中括弧対応してない…）
$s$ は実際の勝敗（勝ちなら1，引き分けなら0.5，負けなら0）を示し、ここにおける $\mu_j, \phi_j, s_j$ は $j$ 番目の対戦相手の $\mu, \phi, s$ を表しています。
式は難しくなりましたが所詮計算式なのでプログラムで表現するのは難しくありません。数学系のライブラリをインポートして書いていきましょう。
Step.3：新しいσ(=σ')の導出
このステップは計算式のみでは対応できなくなりますが難しい動きはしないため、じっくり追っていきましょう。
先に簡単に説明しておくと、ある計算式を繰り返し行いながら収束させ、その時点の値がσの導出に用いられます。ループさせて条件分岐ですね。かんたん。
まず収束の基準となる値である $\epsilon$ を定めます。よく$10^{-6}$が採用されるようです。
次に関数 $f(x)$ を定義します。
$f(x) = \frac{e^x(\Delta^2 - \phi^2 - v - e^x)}{2(\phi^2 + v + e^x)} - \frac{x - a}{\tau}$
なお $a = ln(\sigma^2)$ とします。lnは底がネイピア数の自然対数のことですね。
この $f(x)$ は引数 $x$ を取る関数として準備しておきましょう。
次に、定数 $A, B$ を定めます。
$ A = a = ln(\sigma^2)$
$ B = ln(\Delta - \phi - v) $
$B$ について、 $\Delta - \phi - v \leq 0$ となる場合があります。対数関数の定義域は0より大きいことが条件ですから、代わりに次の方法で $B$ を求めます。
k = 1
WHILE f(a-k*tau) < 0
k = k+1
END WHILE
B = a-k*tau
まだ続きます。
$f_A = f(A), f_B = f(B)$ を準備しておき、次の処理を行います。
WHILE abs(B - A) > epsilon //収束していないなら
C = A + (A - B)*f_A/(f_B - f_A)
f_C = f(C)
IF f_B*f_C < 0 THEN
A = B
f_A = f_B
ELSE
f_A = f_A/2
ENDIF
B = C
f_B = f_C
ENDWHILE
Whileループ終了時つまり $|B - A| \leq \epsilon$ ならば
$ \sigma' = e^{\frac{A}{2}} $
とします。これでようやく新しい $\sigma'$ を求めることができました。
Step.4：φ', μ'の導出
ここまでくると後は簡単です。
$\phi_{s} = \sqrt{\phi^2 + \sigma'^2}$
$\phi' = \frac{1}{\sqrt{\phi^{-2}_{s} + v^{-1}}}$
$\mu' = \mu + \frac{\phi'^2\Delta}{v}$
計算式だけですね。結果を代入して終わりです。
Step.5：スケールを戻す
最後にスケールを戻して終了です。お疲れさまでした。
$r' = 173.7178\mu' + 1500$
$RD' = 173.7178\phi'$
Note：シーズンの不参加を考慮する
レーティング戦はシーズン・ピリオドという形で一定期間の間で行われるものです。シーズンごとにレーティングをリセットしない手法を取る場合は、「１シーズン不参加だった場合の処理」を追加します。といっても、$r, \sigma $ は変更せず、$RD$ の元となる$\phi'$のみ次の式で導出します。
$ \phi' = \phi_{s} = \sqrt{\phi^2 + \sigma^2}$
実装にあたって
レーティングプログラムとして使うためにはもうひと手間加えます。
始めに流れとして $[r, RD, \sigma]$ → 処理 → $[r', RD', \sigma']$ と書きましたがこのままでは情報が足りません。そう、相手側の対戦時の $r, RD$ と勝敗の結果が必要です。対戦ログをデータとして記録する際には [ 勝敗，対戦相手の当時の $r$，対戦相手の当時の $RD$ ] を入れることをお忘れなく。
実際のプログラムでは次のようにすると良いでしょう。
・$(r, RD, \sigma)$ をまとめて管理・操作できるようにする。クラスにするのが手っ取り早いかも。
・レーティングの計算を行う関数の入力は $[r, RD, \sigma, matches]$ とし、$matches : list[result, r_{opponent}, RD_{opponent}]$ とする。これで必要十分な情報を関数に与えることができます。$r_{opponent}, RD_{opponent}$ に現在の情報を適用しないようご注意を。