# 大会を跨いだランキング（レーティング）システムの提案

とさかず (@smahs_tskz) です．
現在小規模オフ大会をより楽しくするためのWebサービスを作成しています．
そこで用いるための大会を跨いだランキング（レーティング）システムを考案していました．
Smash Banzukeという日本ランキングを作成するという話を聞き，参考になるかもしれないと思ったのでWebサービスの公開より先にシステムの仕様を共有しておきます．

（以前書いた仕様をそのまま乗っけているので分かりづらかったり情報の過剰や不足があるかもしれませんが，何か質問があれば気軽にTwitterやスマブラアナリスト窓で聞いてください．）

## レーティングアルゴリズム

### プレイヤーの持つパラメータ

任意のプレイヤー $S$ は「基準レート $B_S\in\mathbb{R}$ 」と「獲得レートポイント $A_S \in \mathbb{R}$ 」の2つのパラメータを持つ．  
「推定レート $P_S\in\mathbb{R}$ 」は「基準レート」と「獲得レートポイント」の和とする．  
つまり $P_S = B_S + A_S$ である．

### 一度の大会で得られるポイント

ベースのアルゴリズムとしてElo Ratingを用いる．

* $B_S\in\mathbb{R}$: プレイヤー $S$ の**基準レート**
* $P_1,...,P_N\in\mathbb{R}$: プレイヤー $S$ **以外**の全参加者 $N$ 人の**推定レート**を降順に並べた値
* $f(X,Y):\mathbb{R}\times\mathbb{R}\rightarrow\mathbb{R}$: Elo Ratingにおいてレート $X$ のプレイヤーがレート $Y$ のプレイヤーに勝った時に得られるレートポイント（詳細は後述）

この時プレイヤー $S$ が1位を取った時に得られるレートポイント $G_1\in\mathbb{R}$ は以下の式で決定する．

$$ G_1=f(B_S, P_1) + \frac{1}{2}(f(B_S, P_2)+f(B_S, P_3)) + \frac{1}{4}(f(B_S, P_4)+f(B_S, P_5)+f(B_S, P_6)+f(B_S, P_7)) + ... + \frac{1}{2^k}\sum_{i=1}^{2^k}f(B_S, P_{i+2^k-1}) + ... $$

またプレイヤー $S$ が2位，3位，4位を取った時に得られるレートポイント $G_2,G_3，G_4\in\mathbb{R}$ は以下の式で決定する．

$$ G_2=\frac{1}{2}(f(B_S, P_2)+f(B_S, P_3)) + \frac{1}{4}(f(B_S, P_4)+f(B_S, P_5)+f(B_S, P_6)+f(B_S, P_7)) + ... + \frac{1}{2^k}\sum_{i=1}^{2^k}f(B_S, P_{i+2^k-1}) + ... $$

$$ G_3=\frac{1}{2}f(B_S, P_3) + \frac{1}{4}(f(B_S, P_4)+f(B_S, P_5)+f(B_S, P_6)+f(B_S, P_7)) + ... + \frac{1}{2^k}\sum_{i=1}^{2^k}f(B_S, P_{i+2^k-1}) + ... $$

$$ G_4=\frac{1}{4}(f(B_S, P_4)+f(B_S, P_5)+f(B_S, P_6)+f(B_S, P_7)) + ... + \frac{1}{2^k}\sum_{i=1}^{2^k}f(B_S, P_{i+2^k-1}) + ... $$

同様にしてプレイヤー $S$ が $n\in\mathbb{N}$ 位を取った時に得られるレートポイント $G_n$ は $P_n$ を含む項から先を足したものとする．

### 獲得レートポイントの決定

* $C_1, ... C_M$ : プレイヤー $S$ が過去に獲得した $M$ 個の大会でのレートポイントを降順に並べたもの

この時プレイヤー $S$ の獲得レートポイント $A_S$ は以下の式で決定する．

$$ A_S = C_1 + \frac{1}{2}(C_2 + C_3) + \frac{1}{4}(C_4 + C_5 + C_6 + C_7) + ... + \frac{1}{2^k}\sum_{i=1}^{2^k}C_{i+2^k-1} + ... $$

### 基準レートの更新と獲得レートポイントのリセット

獲得レートポイントが $100$ を超えた時基準レートを $100$ 増加させ，獲得レートポイントを $0$ に更新する．  
ただしこの処理は基準レートが $2200$ のプレイヤーには適用しない．  

### Elo Ratingでの獲得レート詳細

$f(X,Y)$ は以下の式で決定される．
ただし $\lambda\in\mathbb{R}$ は調整できる定数で，今のところ $\lambda=30$ を予定している（主催者やプレイヤーの評判次第で調整する予定）．

$$ f(X,Y) = \lambda (1-\frac{1}{10^{(Y-X)/400}+1}) $$

### 累計獲得ポイント

基準レートや獲得レートポイントのリセットに関係なく，今まで獲得したレートポイントの合計を累計獲得ポイントとする．

## 段位分け

基準レート100ごとに段位を名付ける．何かかっこいい名前あれば募集．

### ±表記

同一段位内のランク分けを行う．
暫定では獲得レートポイントが0〜29はマイナス，30〜59は無印，60〜99はプラスの表記をつける．

## 初期基準レートの決定方法

### スマメイト最高レートによる決定方法

* スマメイト最高レート1600〜2200までをそのまま初期基準レートに適用する

### クマメイトVIP段位による決定方法

* スマメイト1600未満はクマメイトの段位から推定する
* 詳しい基準は要調査/要調整

### オフ大会成績による決定方法

* 要調査/要調整
* 初スマと同様の基準(n人規模で上位m%以上)をいくつか設けると良いはず
* 制限付きと非制限付きで分ける必要あり
* いくつかレベルの高い有名な大会はそれ用で分ける

## 飛び級制度

一つの大会で200レートポイント以上獲得した場合は獲得したポイントに応じて飛び級で段位を昇格できるようにする．

## レーティングアルゴリズムの設計意図と解釈

### 必要な性質

* 参加者数が多いほど得られるポイントが多い
* 強いプレイヤーが多いほど得られるポイントが多い
* ポイントの差から勝率が推定できる
  * スマメイトのレートとの結び付けをするために必要
* 具体的なマッチ情報を使わずに決定できる
  * ダブルエリミネーショントーナメントでは具体的なマッチ情報で獲得レートポイントを決めると「レートポイントの最大化の戦略」と「純粋に勝利を求めること」が一致しないことがあるため
  * レート戦やトーナメント等の対戦形式によらず得られるポイントを決定したい
* ランクが部分的に与えられることがあっても問題なく決定できる
  * トーナメント戦では完全な順位は決定できない
* 広義短調増加である
  * レート減少を恐れてプレイヤーが参加をオフ対戦会参加を渋ることを防ぐため

### 追加で得られた性質

* 参加者数に対して概ね対数的に得られるポイントが増加する
  * $G_1$ の計算式は全員の推定レートが等しい時 $\lambda \log_2 (N+1)$ で概算できる
  * $G_1$ の計算式は全員の推定レートが等しい時 $\lambda \log_2 (N+1)$ で概算できる
  * logは一階微分が正かつ二階微分が負であり性質が良い．
  * つまり人数や回数が多いほど増加するが，増加ペースは落ちていく
* 大会参加数に対して概ね対数的に得られるポイントが増加する
  * 同様に獲得レートポイントは各大会で得られたレートポイントが等しく $C\in\mathbb{R}$ であった時 $C\log_2 M$ で概算できる

### $G_1$ の計算式の解釈

$G_1$ の値は以下の状況でのElo Ratingに基づくレート変動値の期待値となる．

* プレイヤー $S$ 以外のプレイヤーについて，シード順位が推定レートポイントによって決定されている
* シード順位に基づいてシングルエリミネーショントーナメントを組み実施する
* プレイヤー $S$ 以外のプレイヤーについて，トーナメントの結果順位とシード順位+1が完全に一致していたとする
* トーナメント中の個別のマッチ結果をもとにレート変動値を計算する

つまり1位を取るプレイヤー $S$ は確率 $1$ で推定レート $P_1$ のプレイヤーと対戦し，
確率 $\frac{1}{2}$　（トーナメントの開始位置次第）で推定レート $P_2$ または $P_3$ のプレイヤーと対戦し...という構造になっている．

なお， $G_2$ 以降も同様に解釈できる．
ただし負けによるレート減少は考慮していない．

### 昇格の難易度

スマメイトでは同格に勝つとレートポイントが15得られる．
つまり最高レートを100増加させるには7連勝すれば良いと言える．
「事象を起こす確率=難易度」であるとすると，同格のみが出場している128人規模のシングルエリミネーショントーナメント（優勝まで7連勝が必要）で優勝することが同等の難易度であると言える．

この観点から考えても $G_1$ の式は理にかなっている．
$\lambda=30, N=128$ の時に $G_1 = 105$ となり，ちょうど昇格できる値になるためである．

複数回の結果による昇格では，意図的に2個目以降の大会結果に強い減衰をかけている．
これは小さな結果を積み重ねるだけで昇格できてしまう減少を防ぐためである．

そのため小規模大会のみで昇格を目指す場合は1度の優勝だけではなく複数回の入賞が必要となる．

例：

* $N=32$ の場合: 優勝1回，準優勝1回で昇格
* $N=24$ の場合: 優勝2回で昇格

小規模高頻度の大会では1度の参加のみで卒業すると参加者が減りやすいことを考えると妥当なラインだと思われる．

### レート変動値計算に自分の基準レートを使う理由

トーナメントの結果を出す順序によって得られるポイントが変わらないようにするため．

自分以外のレートは推定レートを使うことにしているが，これも基準レートの方が良い可能性もある．

### 同率順位の扱い

トーナメント方式で順位が決まった場合など同率順位のプレイヤーが存在する場合，Best xxの順位としてポイントを計算する．

例：3位のプレイヤーが2人いる場合→両名とも4位として処理