SpawELO - LANパーティー向けの小規模無料マッチメイキングシステム
(blog.spawek.com)- 16年間続いている友人たちの LANパーティー で、毎回Dota 2のチームを手作業で決めるのが難しくなったため、チーム選択を自動化するSpawELOが作られた
- 実力差と流動的な参加人数のため、手動ドラフトでは 似たチームの繰り返し や奇数人数時の不均衡が頻繁に起きていた
- 最初の実装では35件の過去試合と Eloレーティング を使い、チームごとの合計スコアが最も近い組み合わせを探し、その後は試合結果を繰り返し反映してスコアを補正した
- 勝率予測モデルに切り替えた後は、L2損失 と逆伝播でプレイヤーEloを調整したが、すべての勝利を100%として扱うと過去試合を記憶してしまう過学習が発生した
- 最終的な方式では、試合結果を75%または95%の 確率的な勝利 として扱うことで過学習を減らし、4v5のような奇数人数構成でも使えるチームマッチングを目指している
LANパーティーで明らかになったチーム選択の問題
- 友人グループは過去 16年間、毎年少なくとも1回LANパーティーを開いており、通常は4〜5日間続き、ピーク時には約12人が参加する
- 主なゲームはDota 2で、Counter-Strike、Wolfenstein: Enemy Territory、Warcraft 3、Blobby Volley なども一緒に遊ぶ
- 参加者は到着時間も退出時間も異なり、途中で子どもの世話に行く人もいるため、毎回同じメンバーでゲームが進むわけではない
- Dota 2は通常 5v5 で1試合約40分かかり、4v5のような不均衡な試合は一方的になりやすい
- グループ内にはDota 2を定期的にプレイしている人と、LANパーティーのときだけ遊ぶ人が混在しており、実力差 が大きい
手動ドラフトの限界
- 従来の方式では、たいてい最も上手い人か、逆に最も経験の少ない2人がリーダーとなり、校庭でチームを選ぶように交互にメンバーを指名していた
- 指名順は、最初のリーダーが1人、2人目のリーダーが2人、再び最初のリーダーが2人ずつ選び、最後に各リーダーが1人ずつ選ぶ方式だった
- 先に選ぶ側の利点を減らすための変形ルールである
- 実力差が大きいため、結果として似たような、あるいは同じチームが頻繁に作られ、毎回ドラフトする面白さも薄れていた
- 手動でのチーム選びは時間がかかって面倒で、誰もリーダー役をやりたがらないという問題もあった
- 人数が合わないときは特に チームの不均衡 が大きくなった
最初の実装: 過去試合とElo合計
- 前回のLANパーティーでチーム選択への不満が高まったため、急いで自動化コードを書いた
- まず35件の過去試合データを集めて Colab に入れ、各試合には勝利チームと敗北チームのプレイヤー一覧を含めた
- 基本アイデアは、Elo rating でプレイヤーのスコアを計算することだった
- すべてのプレイヤーは1000点から始まる
- 勝てば点数を得て、負ければ点数を失う
- 2人のプレイヤーのElo差だけで勝率を計算する
- 最初の単純な実装では、勝ったプレイヤーに20点を加え、負けたプレイヤーから20点を引く方式だった
- チーム編成は、要求されたプレイヤーの組み合わせをすべて調べたうえで、チームElo合計 の差が最も小さい組み合わせを選ぶ方式で生成した
- 例では8人を2チームに分け、一方が4100点、もう一方が4080点と計算された
反復計算で改善したEloモデル
- 35試合を1回なぞるだけではデータ活用が不十分だと考え、過去試合データを何度も繰り返し処理した
- 改善版のElo更新は、単純に±20点を適用するのではなく、より強い相手に勝てばより多くの点を得て、より強い相手に負けた場合は失う点が少なくなる仕組みである
- 例として、1260点のSpawekが900点のGoovieに勝っても4.47点しか得ない
- 900点のStatusが1100点のDragonに勝つと30.38点を得る
- 個人対個人ではなくチーム単位で計算していたため、勝利チームと敗北チームの チームElo合計 を使い、更新点はチームメンバーに均等配分した
- この方式はLANパーティー中にも使われ、各ゲームの後に新しいデータを追加して、残りのパーティー期間中のチームを再生成できた
- ときどき明らかに不均衡なマッチが生成された場合は、予想勝者を入れた「偽の試合」をデータに追加してからチームを再生成した
勝率予測モデルに変えた第2の改善
- 次の改善では、Eloを単なる点数表ではなく、チーム勝率を予測する モデル として扱った
- モデルは各プレイヤーのEloを保持し、2チームの
SUM(Elo)を比較して勝利確率を計算する - 全試合データには単純な L2損失 を適用した
- 勝利チームElo合計と敗北チームElo合計を計算する
- 勝利確率を計算する
- 実際の確率と予測確率の差を二乗して損失に加える
- 学習には backpropagation を使った
- 順伝播で予測勝率を計算する
- 損失と勝率関数の導関数を使って、各プレイヤーEloが損失に与える影響を計算する
LEARNING_RATE = 10_000.0,ITERATIONS = 10001でElo値を更新する
- この方式は損失の削減には成功したが、Elo値は収束しなかった
過学習を減らした確率的な試合結果
- ML的なモデルでは、過去試合の実際の勝率をすべて1.0、つまり 100%勝利 として扱っていたため、過学習が発生した
- モデルが各試合を一般化せずに記憶してしまい、一部の試合では予測勝率が0.999994567526197のように1に極めて近くなった
- 目標は過去結果をそのまま符号化することではなく、良いチームを編成することなので、確定した勝敗ではなく確率的な結果を使うように変えた
- 過去の試合記録をさらに確認し、試合の性質を2種類に分けた
- 接戦だった試合は、勝利チームの実際の勝率を 75% に設定する
- 明らかに一方的だった試合は、勝利チームの実際の勝率を 95% に設定する
- 75%の勝率に必要なElo差は約200点で、100%の勝率に必要なElo差は約500点から無限大の範囲になるため、モデルはすべての試合を記憶しにくくなる
lossとbackpropagation関数でreal_probability = 1の代わりにreal_probability = game["win_probability"]を使うように変えたところ、損失は急速に下がり、プレイヤーEloも妥当な水準に収束した
奇数人数でも組めるラインナップ
- 新しいシステムでは、奇数人数 のチームでも勝率を予測してチームを作れる
- 2週間後に始まるLANパーティーの最初のラインナップ例は次のとおり
- team 1: Elo 2660
- team 2: Elo 2655
- 例のラインナップは一方が4人、もう一方が5人の構成である
- team 1: Spawek, Bixkog, Bania, Goovie
- team 2: Hypys, Muhah, J, Vifon, Status
1件のコメント
Hacker News のコメント
チームベースのゲームで Elo/TrueSkill ベースではない方式を使ったことがあるのか気になる
チームの Elo を合計または平均してマッチメイキングするのは、個人マッチメイキング用のモデルにチームマッチメイキングを無理やり押し込む場当たり的な対応のように感じる
また、A と B は一緒に組むと個人 Elo の合計より強いが、A と C は一緒に組むと弱くなる、といった チーム内の相性 情報をかなり失ってしまう
スポーツではチームが負けてもシーズン後にオールスターや MVP が出ることがあり、逆に優勝チームにいても中心選手ではない場合がある
チーム e スポーツは勝利にすべてが懸かっているため、リーグ全体でトップクラスのディフェンダー、アタッカー、サポートのようなプレイヤーの表現がうまく追跡されたり認められたりしない
多くのスポーツのように、ある程度 高度な指標 を追跡し反映すべきだ。プレイヤーは Elo そのものというより、1 試合あたりのアシスト、リバウンド、得点、打点、ヤード数のような値に近い
そうすれば、チームに得点がもっと必要なのか、守備がもっと必要なのかが見えやすくなるので、マッチメイキングも「勝者がもっと必要/敗者がもっと必要」より自然に合っていくはず
Elo の強みは、コストに対して得られる情報が大きいことにある。すべてを代表する 1 つの数値である点が核心だ
自然の美しい多様性を完璧に説明するものではないが、相手の実力について知るべきことの 70% を含む 最も効率的な抽象化 に近い
より多くの情報を含む 多次元のプレイヤースキルベクトル や埋め込み、そしてその上に載るより非線形なモデルがあるとよさそうだ
例えば多くのゲームではチームにたいていサポートプレイヤーが必要だが、1 つの数値だけではその情報をマッチメイキングに入れるには不十分だ
例えばテーブルサッカーではシングルスとダブルスの両方をするプレイヤーがいるが、優れたディフェンダー 2 人がチームになっても、各ポジションにより適した弱い相手に負けることがある
Counter-Strike、Apex、Overwatch、ある程度 Dota のようにチームが大きく支えられるゲームもそれぞれ違う。Counter-Strike では実力不足だったりヘッドセットを持っていなかったりする弱いチームメイト 1 人がゲーム全体を台無しにし得るが、Overwatch ではサポートクラスを選んで後方で休みつつ、残りのチームが勝つのを待つこともできる
ケミストリー もある。職場でも見られるように、特定の組み合わせでだけ生まれるシナジーや、単なるプレイスタイルの違いが結果を変えることがある
ビリヤードのように似て見える派生ゲームでも、あるプレイヤーは一つの種目で輝くが、別の種目ではうまくいかないこともある
Kaggle に評価システムのコンペがあった、あるいは今もあるようだ
https://www.kaggle.com/competitions/chess/discussion/107
Elo より性能の良い 評価システム はかなり多い
トーナメントには、チェスで人気があると理解している スイス式 が気に入っている
[1]: https://en.wikipedia.org/wiki/Swiss-system_tournament
スイス式は 6 ラウンドなら最大 40 人程度が適しているが、100 人以上を招待するには 2 敗失格の組み合わせを使う必要がある。そうでないとトーナメントが 1 週間はかかる
いちばん良い点はコストパフォーマンスが高いことだ。結果に関係なくトーナメント中ずっとプレイし続けられ、進むにつれて相手が自分のレベルに合っていくため、誰でも楽しく参加できる
何ラウンド必要かをどう決めるのかはよく分からないが、その細部が核心なのかも分からない
分析の部分を見ると、ノックアウトトーナメントと比較して、引き分けがないと仮定した場合、明確な優勝者を決めるのに必要なラウンド数はノックアウトと同じだ
スイス式には、誰も脱落させず、最終順位が優勝者だけでなく参加者全体の相対的な実力もある程度示すという利点がある
ただし、あるプレイヤーが大きくリードしすぎると最終ラウンド前にすでに優勝が確定することがあり、必ずしも劇的な結末で終わるわけではない
シャープレイ値 を試してみるのはどうだろう
ほとんど Wikipedia の導入部そのままだが、読んでもよく分からない。ここでいう協力ゲームの総余剰とは何なのか、AoE でチームが集めた木材の量のようなものなのか気になる
それを「配分」することがどう役に立つのかも分からないし、むしろゲーム結果であるべきではないかと思う。分かりやすく説明してもらえるとありがたい