1400字制限

「その情報量は Twitter のなんと10倍... つまり人類はすべて平等に無価値ということだ」

1対1ゲームとランキングの決め方についての小考

トーナメントで準決勝に残ったやつを「ベスト4」というけど、あれって主に組み合わせの問題であって実力順のベスト4じゃないよな〜というのが昔からずっと気になっていた。FIFAランキングとかどうやって決めてんだろと思って調べたら「試合に勝つと3点、引き分けなら1点、ただしPKなら2点で……」とか細かく決まっていていまいち一般性がなさそう。というわけで、

「1対1で戦うゲームの戦績をもとに、各プレイヤーの実力ランキングを決めるアルゴリズム

を考えることにする。多分もう定番のがあるんだろうけど、最近読書ばかりで能動的に頭動かしてない気がするので自分で考える。

手っ取り早いモデルとして、各プレイヤーに1変数の実力があると仮定して、実力差 d に対し (1+tanh(d))/2 の確率で勝利することにする。実力差が3もあればほぼ勝負は揺るがない。

f:id:yubais:20190206172004p:plain

各プレイヤーの実力値は0〜5の乱数にする。名前は日本人の名字ランキングからとってくる。ABC……とか振るよりも覚えやすい。

f:id:yubais:20190206171716p:plain

各プレイヤーの実力値

ずいぶん極端なツートップ体制になってしまったが別にいい。

あとはこの8人にトーナメント戦を100回(700試合)やらせる。当然ながら優勝はほぼ佐藤か渡辺で、1〜2回くらいは高橋が優勝する。とはいえ重要なのは優勝者ではなく戦績。

{'佐藤': 39, '鈴木': 1}
{'佐藤': 51, '高橋': 2}
{'佐藤': 19, '田中': 0}
{'佐藤': 27, '伊藤': 0}
{'佐藤': 58, '渡辺': 38}
{'佐藤': 16, '山本': 0}
{'佐藤': 23, '中村': 0}
{'鈴木': 4, '高橋': 21}
{'鈴木': 19, '田中': 1}
{'鈴木': 16, '伊藤': 0}
{'鈴木': 0, '渡辺': 37}
{'鈴木': 13, '山本': 0}
{'鈴木': 20, '中村': 2}
{'高橋': 19, '田中': 2}
{'高橋': 18, '伊藤': 1}
{'高橋': 2, '渡辺': 41}
{'高橋': 16, '山本': 0}
{'高橋': 20, '中村': 0}
{'田中': 8, '伊藤': 5}
{'田中': 0, '渡辺': 22}
{'田中': 10, '山本': 2}
{'田中': 3, '中村': 14}
{'伊藤': 0, '渡辺': 16}
{'伊藤': 8, '山本': 6}
{'伊藤': 3, '中村': 9}
{'渡辺': 23, '山本': 0}
{'渡辺': 29, '中村': 0}
{'山本': 2, '中村': 14}

こんな具合になる。トーナメントは勝つほど試合数が増えるので佐藤vs渡辺がいちばん対戦数が多く、伊藤vs山本がいちばん少ない……と思ったらもっと少ないのもある。

あとは、この戦績をもとに(もとの実力値をカンニングせずに)「推定実力値」を出して、それをもとに順位を決めることにする。かっこいいアルゴリズムが思いつかなかったので、

  1. まず全員の推定実力値を0と仮定する。
  2. それに基づいて2人の戦績を予測する。
  3. 実際の戦績がより勝っている方の推定実力値を0.01上げて、負けてる方を0.01下げる。
  4. これを100回繰り返す。

という安直極まりない方法でやってみた。能動的に頭を動かすという話はどうなった。

f:id:yubais:20190206173627p:plain

意外ときれいに相関していて、戦績から本来の実力を推測することができた。ただ縦横でスケールが合っていない。同じシグモイド関数を使っているのに、推定実力値は実力差を過大に評価している。

これは試合数が少ないせいで全勝・全敗が発生していることが原因である模様(このアルゴリズムは全勝ならば実力差が無限大であると推定する)。あとでトーナメントの回数を10倍にしたらもっと綺麗な正方形になった。とはいえ今回知りたいのは実力値の絶対値ではなく順位なのでこれで十分だ。

方針がついたので今日はこれで満足。