Halo のスキルとマッチングシステムについて書く①
まえがき
Halo Infinite があと半年後に出るらしい。Halo のマッチングとスキルシステムについてこれまで何度か調べて忘れてを繰り返していたが、Infinite が出たら再び興味が沸くと思うのでまとめておく。また、久々に Forum を見たらマッチングシステムに関する FAQ を Josh が１ヶ月前に作っており、MMR と CSR の関係性やマッチングシステムについてわかりやすくなったこともなんとなく書くきっかけになっている。ただし、MCC のシステムは 5 と根本的に異なるとあるため肝心の Infinite がどうなるかはわからない。特に CSR 側は刷新されてもおかしくないと思う。なんにせよ TrueSkill は技術的におもしろいので調べたことをまとめておこうと思う。
スキルとマッチングシステム
Halo におけるランクマッチはスキルを考慮して公平になるようにマッチングが組まれる。公平な試合とはどちらのチームも勝率が等しくなることをいう。しかし、1対1の対戦ならまだしも4対4や6人の個人戦では、参加者全員が等しいスキルを持つようにプレイヤーを集めるのは時間やプレイ人口の面から難しい。そのため、スキルをもとにそれぞれの勝敗を重み付けして公平となるようにしている。マッチングの公平性という大原則に関わることから、正確にプレイヤーのスキルを表すことが必要となり、そのスキル計算には TrueSkill というアルゴリズムが使われている。
スキル
一般的に言ってスキルはプレイヤーの上手さを定量化したものである。だが、上手さとひとことに言っても人によって想像するものは異なるだろう。勝率や命中率、キル数といった明確な数字以外に、判断力や立ち回りといった曖昧なもの、そしてそれらが複雑な因果関係を持ちゲームの勝敗をなしているため、うまさを一つの数字で表すことは難しい。Halo の根底にあるスキルシステム TrueSkill では、スキル（レート）をそのプレイヤーの未来のマッチの期待勝率として定義する。勘違いしやすいところは、このスキルはその時間までの単なる勝率ではなく、相手のスキルを考慮し、これから始まるマッチに対する期待勝率を表している点だ。そして、その未知のマッチの期待勝率に対して実際の結果が上回ったか下回ったかでスキルが上下する。例を3つ書く。
・同じスキルを持つプレイヤーと10戦するとき
TrueSkill では期待勝率50%になるため5勝5敗の場合スキルは上下しない。6勝4敗になった場合、現在のスキルの期待勝率を超える実力、すなわち現在のスキルより高いスキルを持っていると考えられるためスキルは上昇する。逆も然りでこのときは勝敗数にスキルが比例するためシンプルである。ただし、実際は１戦ごとにスキルは更新されていくためこの例より複雑になる。
・自分より低いスキルのプレイヤーと10戦する場合
TrueSkill によって自分の勝率が90%と計算されたとする。このとき、9勝1敗すると大量に勝っているにも関わらずスキルは上下しない。なぜなら、そのスキルを持つ自分が9勝するのは当然であり、より高いスキルを持っているならばもっと高い勝率を出せるはずだからである。この理由から10勝0敗したときのみスキルは上昇する。同様の理由で8勝2敗したときは下がる。今のスキルならば9勝するはずのマッチであるにも関わらず8勝しかできないということは、今のスキルより低いスキルを持つと証明されてしまうからである。
・自分より高いスキルのプレイヤーと10戦する場合
TrueSkill によって自分の勝率が10％と計算されたとする。このとき、1勝9敗するとスキルは上下しない。スキルにふさわしい実力、すなわち1勝9敗できているからである。2勝8敗すれば上がる。今のスキルであれば1勝であるべきところを2勝もしているからであり、実際にはプレイヤーは今のスキルが表す実力より上の実力＝高いスキルを持っている証明だからである。
2つ目と3つ目の例のように、勝っても負けても上下しないというシステムは一見すると不思議な挙動に感じる。TrueSkill は先に見た例のように、相手によっては10戦9勝や10戦1勝を叩き出してもスキルが上下しない場合がごく普通に存在する。これはひとえに TrueSkill がより現実的な意味での”実力”を示すよう考えられているからにほかならない。例えば Apex Legends のように勝てば上昇し負ければ下降するポイントシステムの場合、自分より格上の相手に対して10戦１勝しても10戦2勝してもポイントは下降の一途をたどる。しかし、いつもは1勝しかできないところを2勝できるようになったら実力は上がっていると考えていいはずだ。そのため TrueSkill は10戦2勝が彼我の実力差をもとにどれほど価値があるのかを相対評価し、スキルを増減させる仕組みになっている。
このような挙動はより現実的な意味の実力に即した数字になっていると個人的に感じる。だが、実際には不確実性を考慮した非直感的振る舞いや過程のブラックボックス化、 UX などから評判が悪いところも多く、正しさが受け入れられるとは限らない点にはなかなか考えさせられるものがある。ここからは TrueSkill の細かい中身について説明する。
TrueSkill
TrueSkill は2007年に Microsoft が提案したアルゴリズムである。Eloレーティングをオンラインゲーム用に複数人またはチーム戦で適用するのがモチベーションだったようだ。ちなみに NIPS2007 に採択されている。
TrueSkill はあくまでゲームのために作られており正確さだけでなく実用を含めた数々の設計思想が盛り込まれている。個人的に特におもしろかった点は、プレイヤーの特定の行動に直接的に関連しないようにする点である。論文中の例では回復回数が挙げられているが、ここは Apex など明示的なポイントルールがあるゲームと真っ向から対立する。先も述べたように正しさが評価されるとは限らないため、どのゲームがどのようなスキルシステムを採用しているかは、かなり興味深いトピックになると思う。実用の観点ではリリース直後から精度を高める必要があるため収束が早いことや、ハイパーパラメータの調整などを不必要とするような点が挙げられる。
思想はいろいろあれど、肝心な点は互いのスキルをもとに不確実性を含めた期待パフォーマンスを計算し、それを使った期待勝率を求める点である。スキルをベースとすることで彼我の実力差をモデルに落としこむ。そうした期待パフォーマンスから試合結果を予想し、実際の結果と比較してモデルパラメータを更新し、試合結果とスキルの分布を正確に推定できるようにしていく。端的に言うと TrueSkill は個人のスキルを確率変数とした生成モデルである。いつもの式を見たほうがはやい。
Skill, Result と、A はチームを表すが、TrueSkill2 ではそれを内包した match condition と呼ばれ、スキル以外で試合結果に結びつく要素をチームごとに示す。Halo5 は TrueSkill2 なので match condition として考えていい。事後確率は次の試合の事前確率として1戦ごとにスキルを更新していく。モデルの誤差は推定したチームのパフォーマンス差の周辺確率と、それと同じ分散と平均を持つガウス分布とのカルバック・ライブラー・ダイバージェンスである（正直怪しい）。実装ではグラフィカルモデルを使って各プレイヤーの事後周辺確率を最終的に求めていく。グラフィカルモデルのメッセージの詳細については別のブログに詳しいので、ここでは尤度がプレイヤーのどういった側面を考慮しているのかについて書く。
試合結果 r は各チームのプレイヤーのパフォーマンスの合計値 p の差分 d で定義する。引き分けを考慮している場合はマージンを取る。各プレイヤーのパフォーマンスはスキル s を中心としたガウス分布で仮定される。n はチーム数なところに注意。TrueSkill2 ではこれに加え、プレイヤーのプレイ時間による経験の多寡による補正、プリメイドによる補正、個人戦績を使ったパフォーマンスの確からしさを導入し、より細かくモデリングしている。
経験の多寡による補正
プレイ時間の多寡と実力は比例するはずだという仮定を反映するため、そのプレイリストの経験した試合数 e を μ のオフセットとし、その試合のスキルを暫定的に更新する（スキルの事後分布とは完全に異なるので注意）。ちなみに γ はスキル更新の増減幅を制御するハイパーパラメータ。これ TrueSkill の思想と矛盾してないかという疑問はある。
プリメイドによる補正
プリメイドによる勝率上昇を反映するため、パフォーマンス計算の際にプリメイドの数で μ をオフセットする。squadOffset の具体的計算式は載っていないが実際の統計出せるならあっさり決まると思う。ちなみに β はプリメイドとは関係なくパフォーマンスの不確実性を表すハイパーパラメータ。
個人戦績のモデリング
試合結果意外にもパフォーマンスから個人のキルデス数を推定し、パフォーマンスの精度を高める。c = {kill, death} とする。w, v はゲームモードにおけるキルデスの重要度を制御するハイパーパラメータ。perf_i^o は敵チームの平均パフォーマンス。
パフォーマンス合計と勝敗
各プレイヤーのパフォーマンスをその試合にいた時間の割合を重みにした線形和でチームの合計パフォーマンスとする。この差分で勝敗を決する。ただし、引き分けがあるマッチの場合はマージン ε を定義し、差分がマージン内にあるかどうかも判別する。
TrueSkill2 のその他の機能
今回は一つのノーマルな試合のみの計算について書いたが、実際のゲームでは途中抜けや他のゲームモードでの経験値なども結果に影響する。TrueSkill2 では途中抜けのペナルティがチームパフォーマンスの面でどういった影響を与えるかと、他のゲームモードでの経験値も考慮している。ここではやたら長くなるのと、途中抜けペナルティの理解がまだ危ういので一旦書かない。気分が向いたら書く。
このように計算された期待勝率計算モデルとスキルは、Halo や GoW でマッチングの公平性を担保するのに利用されている。しかし、プレイヤーがゲーム上で見ているレートは直接的にこのスキルの数字を示していない。つまり Halo5 の CSR は TrueSkill とは異なる。次回はそこの CSR と TrueSkill の関係性について書く。
参考
Herbrich, Ralf, Tom Minka, and Thore Graepel. "TrueSkill™: a Bayesian skill rating system." Advances in neural information processing systems. 2007.
Dangauthier, Pierre, et al. "Trueskill through time: Revisiting the history of chess." Advances in neural information processing systems. 2008.
Minka, Tom, Ryan Cleven, and Yordan Zaykov. "Trueskill 2: An improved bayesian skill rating system." Tech. Rep. (2018).
この記事が気に入ったらサポートをしてみませんか？