SMASH BANZUKE Season1の算出方法
大乱闘スマッシュブラザーズSpecialのトッププレイヤーのランキングを決定するためのアルゴリズム
ダブルイリミネーショントーナメントに複数参加したプレイヤーを評価するという前提で作成した
この記事はアルゴリズムの提案者であるとさかず(@smash_tskz)が主に執筆した
- 遅くなってごめんなさい
最終的なランキングはこちら
SMASH BANZUKE シーズン1 TOP51〜TOP100 #SMASH_BANZUKE #スマブラSP pic.twitter.com/9u8p6csaAC
— SMASH BANZUKE (@SmashBanzuke) 2023年4月26日
どんなプレイヤーが評価されるか
細かいことはどうでもいいのでどんな成績を残したプレイヤーが高い順位になるか知りたい人向けの説明
たくさんの大会に参加し，いい順位をたくさん取った人が高くなるランキングになっている
- 下振れてもランキングが下がることはないのでどんどん大会に参加するべし
ただし「良い順位は取っていないが大会にたくさん出た」という人はランクが高くならない仕組みになっているので，最上位に食い込むにはどこかで良い順位を取る必要がある
直接対決で強いプレイヤーに勝ってもランクそのものは上がらないので，トーナメント全体で良い順位を取ることが重要
- 特に期間内の戦績が良いプレイヤーたくさん参加している大会で上位の順位を取ることが重要
アルゴリズム概要
ざっと知りたい人向けの説明
Step 1: 直接対決の結果から各選手のレートを推定
Step 2: 各トーナメントで各プレイヤーが獲得したポイントをトーナメント参加プレイヤーの推定レートから計算
Step 3: 獲得したトーナメントのポイントに重みをつけて合計し，今シーズンで各プレイヤーが獲得したポイントを計算
Step 4: 今シーズンで獲得したポイントが高い順にSmash Banzukeのランキングを決定
アルゴリズム詳細
- 厳密にアルゴリズムを知りたい人向けの説明
Step 1: 直接対決の結果から各選手のレートを推定
各トーナメントで得られるポイントを決定するための準備として，各選手の「強さ」を直接対決の結果をもとに推定
ここで推定した強さの順位=ランキングではないことに注意
ここの強さをランキングに用いるといくつかの問題が発生する
集計対象だがトップレベルではないトーナメントに参加して勝者側のまま優勝したプレイヤーが最強判定される
- 今回のデータには存在しなかった
そうでなくても1回大会に参加してそれなりにいい結果を残したプレイヤーが過大評価される
- 勝者側ではなく敗者側を駆け抜けたプレイヤーのほうがポイントが多くなることがありうる
以降の数式では選手を表すIDを$i\in \mathbb{N}$で表す
Step 1-1: BTモデルのパラメータを計算
Bradley-Terryモデル(BTモデル)を用いて直接対決の結果から各選手の強さを表すパラメータ$b_i\in\mathbb{R}$を推定
BTモデルはスマメイトでも使われているレーティングシステムであるEloレーティングのベースとなっているモデル
- プレイヤー$1$がプレイヤー$2$に勝つ確率を$\dfrac{b_1}{b_1+b_2}$で表現する
- $b_i$の値は最尤推定により計算する
Eloと異なり時系列を考慮しない（Eloの場合は後半の結果が重要）のでシーズン制のランキングと相性が良い
Eloのように対戦回数が少ないだけの強者に負けて評価が下がることがない
今回のランキングは日本大会だけを考慮するので，Eloでは強い海外勢が1度参加して暴れた時に偶然トナメで当たった人の評価が落ちがち
オフ大会参加数が少ないオンライン勢の強者がふらっと参加したケースも同様
Eloよりも少ない対戦回数で強さを評価できる
ある程度の精度で強さが推定できる（トーナメント参加が1回で勝者側のまま優勝するケースは除く）
もちろん対戦回数は多い方が精度は高い
Step 1-2: Eloのレートに変換
Step 2で使うためにBTモデルのパラメータをEloのレートに変換
ここで変換した後のレートを修正前推定レート$e'_i$と呼ぶ
BTモデルとEloのレートには互換性があり厳密に変換できる
$e'_i=1500 + 400 \times \log_{10} b_i$
$e'_i$に対してレート調整を行ったレートを計算する
1位のレートは2500となるように平行移動
さらにレート1500未満のプレイヤーは全員レート1500に変更
修正前レート1位のプレイヤーのレートを$e'_1$とする
修正した後のレートを推定レート$e_i$と呼ぶ
$e_i = \text{max}\left(e'_i - (2500 - e'_1), 1500\right)$
ここでEloのレートは定数加算しても問題ないことに注意
レート1500未満をレート1500に変更するのはトーナメント参加数が少ない中堅未満の層が過小評価されることがわかったため
Step 2: 各トーナメントで各プレイヤーが獲得したポイントを計算
参加したトーナメント$τ$での順位と他のプレイヤーの推定レートをもとに，各プレイヤー$ i $のトーナメントポイント$ t^τ_i $を決定する
ここでは直接対決の結果は考慮しない
自分が参加したトーナメントに他のどのプレイヤーが参加していたかは考慮する
Step 2-1: 自分以外のプレイヤーを敗者側トーナメントに配置
各トーナメント$τ$について，Step 1で計算したレートが高い順に敗者側トーナメントの上から自分以外のプレイヤーを配置する
これを仮想トーナメントと呼ぶ
例えば自分以外の参加者のレートが上から2500, 2400, 2300, 2200, 2100, 2000, 1900だった場合仮想トーナメントは以下のようになる
GF : 2500
LF : 2400
LSF : 2300
LQF : 2200 or 2100
Losers Top 8 : 2000 or 1900
実際に獲得した順位とは無関係
レートが高いプレイヤーが下振れて早めに敗退した時，そのプレイヤーより高い順位を取った人がそのプレイヤーに当たっていないのに高いポイントをもらうのを防ぐため
レートが高いプレイヤーが「大会に参加することで他のプレイヤーのポイントを上げやすくしてしまう」リスクを下げる
Step 2-2: どこまで勝ち進んだかをもとにトーナメントポイントを計算
実際に自分が獲得した順位をもとに，仮想トーナメントを敗者側1回戦からそこまで勝ち上がったとする
仮想トーナメントにいて各ラウンド$k$で得られるポイントは以下の計算式で決定
各ラウンドに配置されている各プレイヤー$j$について直接対決ポイント$m_j\in\mathbb{R}$を計算
- $m_j$は「プレイヤー$j$に勝つことの一般的な凄さ」を表す
$m_j$は自分のレートが1500の時にプレイヤー$j$に勝つとEloでもらえるレートとする
$m_j=1 - \dfrac{1}{10^{(e_j-1500)/400}}$
- 係数の定数はランキングに影響しないので省略
そのラウンド$k$に配置されているプレイヤー全員の直接対決ポイントの平均をラウンドポイント$r_{k}\in\mathbb{R}$とする
ラウンド$k$で当たるプレイヤーの集合を$R_k\in\mathbb{N}^n$とする
$r_k = \dfrac{1}{|R_k|}\sum_{j\in R_k}m_j$
- これはそのラウンドに配置されているプレイヤーに一様な確率でランダムに対戦し勝利した時の期待値を表す
トーナメント$τ$全体で得られるポイントをトーナメントポイント$ t^τ_{i}\in\mathbb{R} $と呼ぶ
プレイヤー$i$が実際に勝利したラウンドまで$r^{k}$を合計する
プレイヤー$i$が実際に勝利したラウンドを$w_i\in\mathbb{N}$とする
$t^{τ}_{i} = \sum_{k=1}^{w_i}r_{k}$
- 負けた時に減るポイントは考慮しないことに注意
Step 3: トーナメントポイントを集計してプレイヤーポイントを計算
各プレイヤー$i$について，今シーズンで獲得したプレイヤーポイント$p_i\in\mathbb{R}$を計算する
プレイヤーポイントはトーナメントポイントに重みをつけて合計したものとする
- この計算式の意図は「議論 - 上振れと安定性の評価のバランス」にて後述
プレイヤー$i$のトーナメントポイントを高い順に並べ変えた数列を$(t^{1}_{i}, t^{2}_{i}, t^{3}_{i}, t^{4}_{i}, ...)$で表す
上位3件はそのまま加算
上位4件目以降は係数を$\dfrac{1}{2}$ずつ指数的に減衰させながら加算
$p_{i} = t^{1}_{i} + t^{2}_{i} + t^{3}_{i} + \dfrac{1}{2}t^{4}_{i} + \dfrac{1}{2^{2}}t^{5}_{i} + \dfrac{1}{2^{3}}t^{6}_{i} + \cdots + \dfrac{1}{2^{n-3}}t^{n}_{i}$
Step 4: プレイヤーポイントをもとにランキング決定
- プレイヤーポイント$p_i$が高い順にプレイヤーを並べたランキングをSmash Banzukeのランキングとする
備考:
ハイパーパラメータ
最高レート: 2500
最低レート: 1500
基準レート: 1500
固定加算数: 3
減衰係数: 0.5
BTモデルの訓練
LBFGSで最適化
最大1000イテレーション
セット数は考慮せず，そのラウンドの勝者が1勝（敗者が1敗）という数え方
DQの扱い
最初からDQしたかトーナメントの途中でDQしたかに関わらず集計対象からは除去される
- 「勝者側で数勝してDQ→他の大会に参加しない」という行動をとるとBTモデルが過大評価してしまうため
トーナメントポイントの集計時も途中でDQした場合は不参加判定になる
議論
直接対決の結果をランキングに反映するべきか
考え方にもよるが，本手法は意図的に直接対決の結果をランキングに反映していない
直接対決の結果をランキングに反映させることは以下の問題を引き起こす
「大会で高順位を狙う戦略」と「シーズンランキングで上位を狙う戦略」が一致しなくなる場合がある
- 勝者側をわざと負けて敗者側を走った方が点数が高くなるケースなど
直接対決の結果をランキングに反映することはダブルイリミネーショントーナメントと相性が悪い
下振れをしたプレイヤーの評価を下げるべきか
これも考え方によるが，本手法では下振れによるポイントの下方修正は意図的に行なっていない
- シーズンの途中の大会で上振れた時，それより後の大会の参加を控えることが戦略として有効になってしまうのを防ぐため
界隈の発展を考えると，シーズンランキングの影響で大会参加を控えさせるようなことは好ましくない
上振れと安定性の評価のバランス
「できるだけ多くの大会の結果を考慮すること」と，「たくさん大会に出たが上位をとっていない人を過大評価しないこと」の両立は難しい
下振れしたプレイヤーの評価を下げない場合はこの問題が顕著になる
従来手法と提案手法ではこれに対するアプローチが少し異なる
従来手法
他のランキング手法では「トーナメントポイントに相当する数値の上位$N$件を合算する」ことを行なっており$N$の変更でこのバランスを調整していることが多い
この方法の問題点は2つ
考慮できる大会数に限界がある
- 多くの大会を考慮すると$N$を大きくすることになるが，そうすると「ただ大会にたくさん出ただけの人」が過大評価されるのでどこかで妥協が必要
プレイヤーが大会に参加する目的が「ランキングを上げること」だとした場合を仮定すると，高いポイントを取ったプレイヤーはそれ以上大会に参加する意味がなくなってしまう可能性がある
その大会で1位をとってもプレイヤーポイントの増加が0であることが大会参加前にわかってしまう場合がある
小さな大会ではこの影響を受けやすい
提案手法
今回のランキングアルゴリズムでは，「上位$N$件は通常通り合算し，途中からは係数をかけて合算」することでそのバランス調整を行う
この方法は先に述べた問題点を改善している
全ての大会の成績を考慮しつつ，大会にたくさん出ただけでポイントが高くなることを防げる
減衰係数が$\frac{1}{2}$の場合，係数がかかる部分の影響は，係数がかからない1大会分の影響以下になる
$\sum^{\infty}_{k=1}\frac{1}{2^{k}}=1$
$t^{3}_{i} \geq t^{4}_{i} \geq\cdots\geq t^{n}_{i}$
よって $t^{3}_{i} \geq \dfrac{1}{2}t^{4}_{i} + \dfrac{1}{2^{2}}t^{5}_{i} + \dfrac{1}{2^{3}}t^{6}_{i} + \cdots + \dfrac{1}{2^{n-3}}t^{n}_{i}$
プレイヤーが大会に参加する目的が「ランキングを上げること」だとした場合を仮定しても，提案手法では集計対象ならどんな大会でも参加する意味が残る
- すでに良い成績を何度か収めているプレイヤーでも，大会に出れば必ずプレイヤーポイントが上昇する
ポイントの獲得しやすさの平等性
他のランキング手法では「どのプレイヤーでも同じ順位を取ったプレイヤーがもらえるポイントは同じ」という設計になっていることが多い
これは上位プレイヤーほど「自分が出ると大会の評価が上がりポイントが上げやすくなる」という現象を引き起こし平等ではない
- 例えばマイナーでレベルが高くない大会にMkLeoが急に参戦した場合，MkLeoが出ているので大会の評価はある程度高くなるかもしれないが，MkLeoにとっては他にレベルの高いプレイヤーが参加していないので簡単に1位が取れてしまう
この問題に対処するため，提案手法では各順位で得られるポイントを「自分以外の参加者の強さ」をもとに決定している
- 同じ順位でもプレイヤーによって得られるポイントが異なる
来季の計算方法について
- 来季は集計期間を半年にして計算する予定
- それに伴いハイパーパラメータとアルゴリズムの一部を調整する可能性がある
おわりに
- 質問や意見があればスマブラアナリスト窓のランキング論チャンネルまでどうぞ
