こんにちは!₍₍⁽⁽ฅ•ω•ฅ₎₎⁾⁾
今回はタイトルにある通り、ちょっぴり技術的で面白い実験(自画自賛)をしてみたので紹介します。
きっかけ
タイピング練習ソフトやサイトはいろいろあり、各練習ソフト、サイトにはほぼ必ずと言っていいほどランキングが存在します。
ランキングがあることで、自分の相対的な立ち位置はなんとなく把握することはできると思います。
しかし、レーティングといったように、自分の実力を表す数値を算出しているサイトはほとんどないと思われます。なので、ほぼ興味本位ですが、レーティングなるものを一度定義してみたかったのでやってみました。
ご注意
数式アレルギーの方は最後の「結果発表~」だけ読んでください。その方が楽しいかと思われます。
レーティングの定義
今回は対戦型ゲームで非常によく用いられている Elo(イロ)レーティングシステムを用いました。 文献は記事末尾に書いてある [1] になります。
Elo レーティングの仕組みについて簡単に解説します。
プレイヤー $i$ とプレイヤー $j$ が対戦することを考えます。プレイヤー $i$ の現在のレーティングを $r_i(\text{old})$ 、プレイヤー $j$ の現在のレーティングを $r_j(\text{old})$ と書くことにします。
まず、レーティングの更新式を書いてしまいますが、定数 $K$ と後で定義する $ S_{ij} $ 、 $\mu_{ij}$ を用いて、プレイヤー $i$ の新しいレーティング $r_i(\text{new})$ は、
$$r_i(\text{new}) = r_i(\text{old}) + K(S_{ij} - \mu_{ij})$$
と書くことができます。簡単に言えば、第1項が現在のレーティング、第2項が対戦による変動分(報酬)を表しています。
では、$S_{ij}$、$\mu_{ij}$、$K$ とは何かを説明していきます。
$S_{ij}$ は成績を表す値であり、
$$S_{ij} = \begin{cases} 1 & \text{プレイヤー}~i~\text{がプレイヤー}~j~\text{に勝った場合}\\ 0 & \text{プレイヤー}~i~\text{がプレイヤー}~j~\text{に負けた場合} \end{cases}$$
です。ちなみに、この定義に限らず、$S_{ij} + S_{ji} = 1$ を常に満たせばよいです(引き分けは $S_{ij} = S_{ji} = 1/2$ や得失点差で変えるなど)
$\mu_{ij}$ はプレイヤー $i$ がプレイヤー $j$ に対して獲得すると期待される成績(勝利確率)を表しており、ロジスティック関数において指数の底を $10$ にした形である
$$\mu_{ij} = \frac{1}{1 + 10^{-d_{ij} / \xi}}, ~~ d_{ij} = r_i(\text{old}) - r_j(\text{old})$$
が用いられます。$\xi$ はパラメータです。
これについて、ちょっと変形を行うと(old は長いので省略して書きますが)、
$$\mu_{ij} = \frac{10^{r_i / \xi}}{10^{r_i / \xi} + 10^{r_j / \xi}}, \mu_{ji} = \frac{10^{r_j / \xi}}{10^{r_i / \xi} + 10^{r_j / \xi}}$$
より
$$\frac{\mu_{ij}}{\mu_{ji}} = \frac{10^{r_i / \xi}}{10^{r_j / \xi}}$$
$$\mu_{ij} = \mu_{ji} \left( 10^{(r_i - r_j) / \xi} \right)$$
が導けます。
つまり、二人のレーティングが全く同じであれば勝率は五分五分、プレイヤー $i$ のレーティングの方が、プレイヤー $j$ のレーティングより $\xi$ ポイントだけ高ければ、プレイヤー $i$ がプレイヤー $j$ に勝てる確率は、プレイヤー $j$ がプレイヤー $i$ に勝てる確率より10倍大きいということが表されています。
このパラメータ $\xi$ は好きな値に設定することができ、レーティングシステムの調整をすることが可能となっています。よく $\xi = 400$ が用いられます。
また、対戦で勝ったときの報酬(新しいレーティングを計算する式の第2項である $K(S_{ij} - \mu_{ij})$)は、強いプレイヤーが弱いプレイヤーに勝つよりも、弱いプレイヤーが強いプレイヤーに勝つ方が報酬が大きくなるという仕組みになっています(計算してみてください)。
さて、最後に定数 $K$ ですが、これは $K$ 因子と呼ばれ、レーティングの変動をどれくらい大きくするかを決定するものになります。$K$ が大きいほど1試合で変動するレーティングが大きくなります。 ただし、大きすぎるとレーティングが不安定になり、小さすぎるとレーティングが変動しなさすぎることになります。
また、$K$ の大きさをその試合の重要性やプレイヤーのレベルによって試合ごとに変えることができるのもポイントです。例えば、親善試合は $K = 20$、通常の試合は $K=30$、国際的な試合では $K=40$などと変えることができます。
紹介した $\xi$ や $K$ 因子は、競技に応じて変更することができるため、レーティングシステム設計者の味付けができる部分であり、おもしろい部分でもあります。
ここまでが Elo レーティングの簡単な仕組みの説明でした。
使ったデータ
e-typing 第1029回 腕試しタイピング(2021/1/5~2021/1/12)ローマ字のランキングデータを取得しました。取得してくるのは結構大変で、1回分のデータしかとりませんでした。ちなみにこの回を選んだ理由は、自分の自己ベストが載っているからという利己的な理由と、「元気が出る言葉」がワードセットに選ばれていたので比較的打つ文字数が多く、スコア分布が比較的きれいになりそうと思ったからです。
さて、この回のスコア分布はこうなっております。
e-typing の情報によると、参加人数は 6382 人、平均スコアは 259.12 点だそうです。
なんとなく正規分布っぽい感じはしますね。細かいことを言うと、スコアは基本0以上の値になるので、確率密度関数において $x < 0$ の部分は使えませんが、今回は平均と標準偏差を出したいだけなので気にしないことにします。
この確率密度関数を積分すると総面積が1になるように調整してから正規分布でフィッティングしてみます。
思ったよりいい感じですね。
正規分布の形を決定するパラメータですが、 平均 $\mu = 259.21321$ 、標準偏差 σ $= 103.11068$ でありました。
e-typing が算出した平均スコアが 259.12 点であり、正規分布の平均とよく一致しています。 曲線もヒストグラムに結構よくあてはまっていますね。
この求めたパラメータはあとで利用します。
シミュレーション
やっと数学的な準備ができたのでシミュレーションをします。 詳しいことはソースコードにある程度書いてあるのでそちらを読んでいただければと思います。
まず、先ほどもとめた e-typing のスコアの正規分布に基づいて、そのスコアを出すプレイヤーを5500人ほど生成します。 つまり、平均 $\mu = 259.21321$、標準偏差 σ $= 103.11068$ の正規分布に従う乱数を生成します。 プレイヤーは毎回同じスコアを出すものと仮定します。スコアは基本は0以上であるため、負になった場合はそのスコアは使わないことにします。 また、普通に乱数を生成すると平均から大きく外れた範囲のプレイヤーは生成されない(=シミュレーションで変態パーが生成される確率がほぼゼロ)ので、1点から850点まで5点区切りで別途プレイヤーを生成します。 これで合計でおおよそ 5670 人ほどのプレイヤーが生成されます。
次にプレイヤーが勝利する確率についてです。プレイヤー $i$ がスコア $s_i$、プレイヤー $j$ がスコア $s_j$ を出すとき、プレイヤー $i$ がプレイヤー $j$ に勝利する確率 $P_{ij}$ を
$$P_{ij} = \frac{1}{1 + 10^{-(s_i - s_j)/100}}$$
で定義することにします。ここでの勝利確率は、仮にプレイヤー $i$ とプレイヤー $j$ がタイピングで1対1で戦う時に、e-typing のスコアの差がプレイヤー $i$ の方がプレイヤー $j$ より 100 ポイント高いとプレイヤー $i$ の方が10倍勝ちやすいということを表し、現在のレーティングには依存しないことに注意します。どちらが勝つかは 0 以上 1 未満の乱数を生成して決定します。プレイヤー $i$ が勝利した場合は $S_{ij} = 1, S_{ji} = 0$、プレイヤー $j$ が勝利した場合は $S_{ji} = 1, S_{ij} = 0$ となります。
現時点でのプレイヤー $i$ のレーティングが $r_i(\text{old})$、プレイヤー $j$ のレーティングが $r_j(\text{old})$ のとき、 $\mu_{ij}$ はプレイヤー $i$ がプレイヤー $j$ に対して獲得すると期待される成績(勝利確率)でしたから、
$$\mu_{ij} = \frac{1}{1 + 10^{-d_{ij} / 400}}, ~~ d_{ij} = r_i(\text{old}) - r_j(\text{old})$$
と表せます。この値と、実際の対戦結果 $S_{ij}$ を用いて、プレイヤー $i$ の新しいレーティング $r_i(\text{new})$ を、
$$r_i(\text{new}) = r_i(\text{old}) + K(S_{ij} - \mu_{ij})$$
で更新していきます。今回は $K = 50$ としました。
レーティングの初期値は全員 1200 と仮定します。この値は初期値であると同時に平均的なプレイヤーのレーティングを最終的に表すものでもあります。
対戦する相手についてですが、レーティングがあまりにもかけ離れ過ぎた人同士で対戦させるのは治安がよろしくなく、レーティングの変動計算においてもほぼ無意味なので、自分のレーティングより上で自分のレーティングに近い順に250人、自分のレーティングより下で自分のレーティングに近い順に250人の合計500人とだけ対戦させるようにしました。
結果発表~
最終的なレーティング分布はこうなりました。
レーティングの下限が 142、上限が 3491 であり、初期値 1200 付近が平均的と定義してあったので、その辺の人数が多いことがわかります。
さて、レーティングを出したところで、いよいよタイパーとしての実力を評価しましょう!
今回は、こちらの Codeforces のサイトを参考にランクを勝手につけてみました。
How to Interpret Contest Ratings - Codeforces
レーティングに応じてランクと色がつくシステムです。
今回のシミュレーションでは以下の結果となりました。 「元気が出る言葉」でやったときかそれに準ずるくらいの文字数を打つことになるお題で出したスコアでしか(おそらく)使えないことに注意してください。
レーティング | ランク | スコア |
---|---|---|
3000+ | Legendary Grandmaster | 726~ |
2700-2999 | International Grandmaster | 656~ |
2400-2699 | Grandmaster | 586~ |
2200-2399 | International Master | 526~ |
2000-2199 | Master | 476~ |
1800-1999 | Candidate Master | 428~ |
1600-1799 | Expert | 382~ |
1400-1599 | Specialist | 330~ |
1200-1399 | Apprentice | 270~ |
1000-1199 | Pupil | 203~ |
Up to 999 | Newbie | ~202 |
また、パーセンタイルとスコア、レーティングの関係は以下のようになりました(スコアは小数点以下四捨五入)。 最上位はなかなか推定が難しいのですが、それなりに参考になる数値かとは思われます。できるだけ Codeforces に近づけるように状況を設定しましたが、Codeforces で書かれているパーセンタイルとは異なります。もちろんですが、計算式自体が大きく違うのでこの数値を AtC〇der や T〇pcoder などに当てはめることはできません。
スコア | レーティング | パーセンタイル |
---|---|---|
818 | 3367 | 99.9%(上位0.1%) |
790 | 3270 | 99.8% |
761 | 3180 | 99.7% |
733 | 3019 | 99.6% |
705 | 2938 | 99.5%(上位0.5%) |
677 | 2827 | 99.4% |
648 | 2692 | 99.3% |
626 | 2598 | 99.2% |
602 | 2500 | 99.1% |
585 | 2392 | 99.0%(上位1%) |
526 | 2206 | 98.5% |
501 | 2082 | 98.0%(上位2%) |
480 | 2016 | 97.5% |
467 | 1964 | 97.0%(上位3%) |
435 | 1835 | 95.0%(上位5%) |
395 | 1659 | 90.0%(上位10%) |
369 | 1554 | 85.0% |
348 | 1476 | 80.0% |
331 | 1404 | 75.0%(上位25%) |
314 | 1354 | 70.0% |
287 | 1256 | 60.0% |
260 | 1171 | 50.0%(平均) |
234 | 1100 | 40.0% |
206 | 1011 | 30.0% |
174 | 902 | 20.0% |
129 | 741 | 10.0% |
どうでしたか?
筆者の白狐はこの回で 743 を出しており、今回のシミュレーションでは上位 0.4%、Legendary Grandmasterという結果になりました。
ツイッター上ではバケモノクラスのタイパーがたくさんいるので、なかなかわかりにくいですが、こうやって相対的に自分がどの辺に位置するのかわかるとおもしろいかもしれませんね!
おわりに
休日1日かけてモデル設計、コーディング、シミュレーション、ブログ執筆を行いました。 1日でやったので結構雑になっている部分もあるかもしれないですが、それなりにいいシミュレーションはできたかと思います。
一つだけ、終わりに注意書きですが、レーティングが高い=えらいわけじゃないということです。確かに、実力者であることは間違いないのですが、人を貶めるために実力を身に着ける人にはなってほしくないと切に願います。レーティングはあくまで相対的な実力評価だったり、同じくらいの実力の人を探すのに使ったり、目標設定に使ったりと有意義な使い方をしてほしいものです。
最後までお読みいただきありがとうございました~!
参考文献
- [1] レイティング・ランキングの数理 : No.1は誰か? / Amy N. Langville, Carl D. Meyer著 ; 岩野和生, 中村英史, 清水咲里訳
- [2] How to Interpret Contest Ratings - Codeforces