プレイヤの相対的スキルの決定

コンピュータゲーム、チェス、テニス、および任意の他の適した種類のゲームのようなゲームのプレイヤの相対的スキルの決定方法を提供したいという要望がある。我々の先願のベイジアンスコアリングシステムをXbox Live「商標」で実装しており、現在は商号TrueSkill「商標」の下で商用的に利用可能である。本発明では我々の以前の取り組みを基礎とし、処理時間を大幅に削減可能な新規の計算方法を使用する。更新したスキル確率の計算を複数のプレイヤから成る複数のチームの場合でも迅速に取得できるように、メッセージパッシング技術を適合させる。

【発明の詳細な説明】
【技術分野】
【0001】
本説明は一般に、コンピュータゲームまたは任意の他種類のゲームのようなゲームのプレイヤの相対的スキルを決定することに関する。より詳細には、ベイズ統計技術を用いてそれらのプレイヤが関与する複数のゲームの結果を踏まえてプレイヤをランク付けすることに関するが、これに限らない。
【背景技術】
【0002】
コンピュータゲーム、チェス、テニス、および任意の他種類のゲームのようなゲームのプレイヤの相対的スキルの決定方法を提供したいという要望がある。これを、相対的スキルの表示が可能な限り正確で、かつエンドユーザ(すなわち、ゲームプレイヤ)により理解および受け入れられるような方法で実現する必要がある。加えて、相対的なスキルを、多数のプレイヤが関与するゲームの場合でも、およびさらにそれぞれのチームが多数のメンバを有する多数のプレイヤチームの場合でも、迅速に決定する必要がある。これは、これらの状況では計算量が一般に大幅に増加するので特に問題である。プレイヤは人間のプレイヤまたはコンピュータプログラムであることができる。
【0003】
我々の先願特許である「特許文献1」では、ゲームの結果に基づいてプレイヤのスキルをランク付けする、またはプレイヤのスキルの表示を決定するシステムを説明している。スキルレベルを使用してゲーム環境におけるプレイヤの進捗および/または位置を追跡することができ、ならびに/もしくは将来のゲーム向けにプレイヤを互いと対戦させることができる。我々は、ベイズ統計技術を用いてプレイヤの相対的スキルの表示を決定するシステムを説明する。本発明は我々の以前の取り組みを基礎として拡張し、特に計算時間を削減可能な新規の計算方法を提供する。
【発明の開示】
【発明が解決しようとする課題】
【0004】
統計的アプローチを使用するゲーム向けのランク付けシステムが以前に提示されている。Arpad Eloが開発したELOランク付けシステムは、2プレイヤのゲームのみに対して適切である。しかしながら、対戦ごとに3人以上のプレイヤを有するゲームモードで動作するシステムを提供する必要がある。
【0005】
本発明は、ゲームのプレイヤの相対的スキルの表示の決定に対する改良した方法および装置の提供を図る。その方法および装置は、1つまたは複数の上述の問題を克服または少なくとも軽減する。
【0006】
【特許文献1】2005年1月24日出願、米国特許出願「Baysian Scoring」明細書
【非特許文献1】Press et al.,Numerical Recipes in C:the Art of Scientific Computing(2d.ed.),Cambridge,Cambridge University Press,ISBN−0−521−43108−5
【課題を解決するための手段】
【0007】
以下で、本開示の簡潔な要約を提示し、読者に基本的な理解を与える。本要約は本開示の広範的な概要ではなく、本発明の主要/重要な要素を特定せず、または本発明の範囲を区別しない。本要約の唯一の目的は、本明細書で開示したいくつかの概念を、後に提示するより詳細な説明に対する前置きとして簡潔な形で提示することである。その例は、ゲームの少なくとも第1のプレイヤおよび第2のプレイヤの相対的スキルの表示を、それらのプレイヤが関与する1つまたは複数の上記ゲームの結果に基づいて決定する方法を提供する。上記の方法は、
それぞれのプレイヤに対して、そのプレイヤのスキルに関する確率に関連付けた確率分布を記述する統計値にアクセスするステップ、
1つのゲームの結果に関する情報を受信するステップ、
ノードを備えるファクタグラフを形成するステップであって、そのグラフを上記の結果に関する受信情報を用いて形成し、上記ノードの少なくともいくつかを上記の統計値でインスタンス化するステップ、および
それぞれのプレイヤに関連付けた上記の統計値を、上記のファクタグラフ上のメッセージパッシング技術を用いて更新するステップ
から成るステップを備える。
【0008】
対応する装置を提供する。その装置は、ゲームの少なくとも第1のプレイヤおよび第2のプレイヤの相対的スキルの表示を、それらのプレイヤが関与する1つまたは複数の上記ゲームの結果に基づいて決定する。上記の装置は、
それぞれのプレイヤに対して、そのプレイヤのスキルに関する確率に関連付けた確率分布を記述する統計値にアクセスするよう配置した入力、
1つのゲームの結果に関する情報を受信するよう配置した入力、
ノードを備えるファクタグラフを形成する手段であって、そのグラフを上記の結果に関する受信情報を用いて形成し、上記ノードの少なくともいくつかを上記の統計値でインスタンス化する手段、および
それぞれのプレイヤに関連付けた上記の統計値を、上記のファクタグラフ上のメッセージパッシング技術を用いて更新するよう配置した1つまたは複数のプロセッサ
を備える。
【0009】
上記の統計値は、それぞれの確率分布を記述する少なくとも平均および分散を備えることが望ましい。
【0010】
上記の確率分布はガウス分布であることが望ましい。
【0011】
上記のファクタグラフは非巡回であることが望ましい。
【0012】
上記のファクタグラフは2種類のノードから成り、2部グラフであることが望ましい。
【0013】
上記のファクタグラフ上で適用したメッセージパッシング技術を配置して、ベイズ推論プロセスを十分に実施すると都合が良い。
【0014】
好適な例では、上記のファクタグラフは複数のノードグループを備え、それぞれのグループを特別なプレイヤに関連付け、そのそれぞれのグループは直列に接続したノードを備える。別の例では、上記のファクタグラフは複数の第2のノードグループを備え、それぞれの第2のグループをプレイヤチームに関連付ける。
【0015】
例において上記の方法はゲームの3人以上のプレイヤの相対的スキルの表示を決定する。
【0016】
いくつかの例では、ゲームの結果に関する情報はさらに、それぞれのプレイヤに対して、そのゲームへのそのプレイヤの参加時間の表示を備え、上記の統計値をその情報を基に更新する。
【0017】
いくつかの例では、ゲームの結果に関する情報は部分的なプレイヤランキングを備え、その部分的なランキングは、少なくとも1人のプレイヤに対するランクを備え、複数の他のプレイヤに対するランク情報は備えず、ランク付けしたプレイヤに関連付けたノードとランク付けしていないプレイヤの各々に関連付けたノードとの間のリンクを作成するように上記のファクタグラフを形成する。
【0018】
上記の例はコンピュータプログラムも含む。そのコンピュータプログラムは、そのプログラムをコンピュータ上で実行するときに任意の上記方法の全ステップを実行するよう適合させたコンピュータプログラムコード手段を備える。上記のコンピュータプログラムをコンピュータ可読媒体上で具現化することができる。
【0019】
上記の方法を、記憶媒体上で機械可読形態のソフトウェアにより実行することができる。そのソフトウェアは、上記の方法のステップを任意の適切な順序、または同時に実行できるように、並列プロセッサまたは直列プロセッサ上での実行に適していることができる。
【0020】
これは、ソフトウェアが貴重で別々に取引可能な商品であることを認めている。「ダム」または標準的なハードウェア上で実行またはそれらを制御するソフトウェアを網羅して、所望の機能を実行することを意図している(および従ってソフトウェアは本質的にレジスタ機能を定義し、従ってそれを標準的なハードウェアと結合する前でも、レジスタと称することができる)。同様な理由で、シリコンチップの設計、またはユニバーサルプログラマブルチップの構成に使用されるように、HDL(hardware description language)ソフトウェアのような、ハードウェア構成を「記述」または定義するソフトウェアを網羅して所望の機能を実行することも意図している。
【0021】
付随する特徴の多くは、付属図面と関連して考慮した以下の詳細な説明を参照することでより容易に理解され、より良く理解されるであろう。
【0022】
付属図面と照らし合わせて以下の詳細な説明を読むと、本発明はより良く理解されるであろう。
【0023】
付属図面では同じ参照番号を使用して同じ部分を指定する。
【発明を実施するための最良の形態】
【0024】
付属図面と関連して以下で与える詳細な説明は本例の説明として意図してあり、本例を構築または利用可能である唯一の形態を表すことは意図していない。本説明は、上記の例の機能、および上記の例を構築または操作するステップの順序を説明する。しかしながら、同一または等価な機能および順序を、異なる例により実現してもよい。
【0025】
我々の先願のベイジアンスコアリングシステムをXbox Live「商標」で実装しており、現在は商号TrueSkill「商標」の下で商用的に利用可能である。本発明は我々の以前の取り組みを基礎として拡張し、新規の計算方法を使用して処理時間を大幅に削減させることができる。現在利用可能なTrueSkillシステムの要約を与えて本発明の理解を支援する。
【0026】
ほとんどのゲームはその根源において、ゲームの目標が満たされたかどうかを判定する基準を有する。2人以上のプレイヤが関与する対戦(「マルチプレイヤ対戦」)の場合、これは対戦参加者のスキルをランク付けする方法を含むことがよくある。これにより、プレイヤ間の競争に、両者が個々の対戦に「勝利」するよう促し、彼らの全体のスキルレベルをより広範囲のコミュニティに理解および認識させることを促す。プレイヤは、自分の知っている人々と比較した自分のスキル、または自分がプレイしたことのない潜在的な相手と比較した自分のスキルを評価して、その結果面白い対戦を用意できることを望むかもしれない。参加プレイヤに対する勝利の可能性が非常に不均衡である場合、すなわち、勝利または敗北の可能性がない対戦のプレイを楽しむ人がほとんどいない場合、我々は対戦を「面白くない」と称する。反対に、任意の参加者が勝利する可能性が相対的に等価である対戦を「面白い」対戦とみなす。
【0027】
TrueSkillランキングシステムは、プレイヤのランク付けに対してベイズ推論と呼ばれる技術を使用するスキルベースのランキングシステムである。
【0028】
それぞれのプレイヤに対して単一の固定スキルを仮定するのではなく、上記のシステムは、その平均μおよび標準偏差σにより一意に記述されるベルカーブ確率分布(ガウス分布とも呼ばれる)を用いてその確率を特徴づける。例示的な確率分布を図1に示す。或る特定の範囲内にあるスキル確率分布曲線の領域は、プレイヤのスキルがその範囲にあるという確率に対応することに留意されたい。例えば、図1内の影領域は、プレイヤのスキルがレベル15から20の間にあるという確率を表す。システムがプレイヤのスキルに関してさらに学習すると、σはより小さく、そのプレイヤのスキルの範囲をより狭めるものとなる傾向がある。μおよびσの値の別の考え方は、それらを「平均的なプレイヤスキルの確率」およびそのスキルの調査に関連付けた「不確実性」と見なすことである。
【0029】
TrueSkillランキングシステムはガウス確率分布を使用してプレイヤのスキルを特徴づけるので、全ての平均的なスキル(すなわち、のμの値)は常にσの初期値の±4倍(より正確には99.99%の確率)の内部にある。
【0030】
TrueSkillランキングシステムは初期値1の不確実性を用いて全ての計算を行うことができる。なぜならば、μおよびσを、単純にそれらを掛け合わせることで任意の他の範囲に拡大できるからである。例えば、全ての計算を初期値3のμおよび初期値1のσで行うとする。プレイヤのスキルを50個の「レベル」のうち1つとして表現したい場合、殆ど全てのμがたまたまσの初期値の±3倍の内部にあるので、μおよびσに50/6=8.3を掛ける。
【0031】
意図は、σの値が同様だと仮定して2プレイヤのμ値の間の差分が大きくなれば、より高いμ値を有するプレイヤのゲームにおけるパフォーマンスがより良い可能性が高くなる。本原理はTrueSkillランキングシステムで当てはまる。しかし、これはより大きなμ値を有するプレイヤが常に勝利すると期待されることを意味するのではなく、そのプレイヤが勝利する可能性が、より小さなμ値を有するプレイヤが勝利する可能性よりも高いことを意味する。TrueSkillランキングシステムは、1つの対戦におけるパフォーマンスがプレイヤのスキルで変化すると仮定し、ゲームの結果(ゲームに参加する全てのプレイヤの相対的なランキング)がそのプレイヤのパフォーマンスにより決定されると仮定する。従って、TrueSkillランキングシステム内のプレイヤのスキルを、多数のゲームに対するプレイヤの平均的なパフォーマンスと考えることができる。スキルでのパフォーマンスの変化は、原則として、TrueSkillランキングシステムの構成可能なパラメータである。
【0032】
TrueSkillランキングシステムはμおよびσの更新の基礎をゲームの結果(全チームの相対的なランキング)のみに置く。TrueSkillランキングシステムは単純に、結果はプレイヤのスキルで変化するいくつかの未観測のパフォーマンスに起因すると仮定する。ポイントベースのゲームをプレイしていて、勝者が全ての他のプレイヤを10倍負かす場合、そのプレイヤの勝利は、そのプレイヤが1点だけ勝利した場合と変わらないスコアである。全ての対戦はシステムにそれぞれのプレイヤのスキル確率に関するさらなる情報を提供し、通常はσを押し下げる。
【0033】
新規ゲーム結果に対する全ての参加プレイヤの新規スキル確率を決定し始める前に、TrueSkillランキングシステムはそれぞれのプレイヤのスキルが、それぞれのプレイヤがプレイした現在と最後のゲームとの間で少々変化している可能性があると仮定する。上記の仮定を行う数学的な結果として、スキル不確実性σが少々増加することとなり、その量は原則として、TrueSkillランキングシステムの構成可能なパラメータである。TrueSkillシステムが長期に渡ってゲームのスキル向上を追跡することを可能とし、かつスキル不確実性σが決して零に減少しない(「モメンタムを維持する」)ことを保証するのはこのパラメータである。
【0034】
新規ゲーム結果に対する全ての参加プレイヤの新規スキル確率を決定するため、TrueSkillランキングシステムは、参加プレイヤの所与のスキルに対して観測したゲーム結果の確率を決定し、その確率に対し、対応するスキル確率の確率で重み付けする必要がある。これを、全ての可能なパフォーマンスを(その確率で重み付けして)平均化し、そのパフォーマンスからゲーム結果を導出することで行う。すなわち、最高パフォーマンスを有するプレイヤが勝者であり、2番目に高いパフォーマンスを有するプレイヤが第1の準優勝者である、等である。2人のプレイヤのパフォーマンスが非常に近い場合、TrueSkillランキングシステムはこれら2人のプレイヤ間の結果を引き分けと考える。TrueSkillランキングシステムによると、所与のリーグにおいて引き分けを定義するマージンが大きければ大きいほど、引き分けが発生する可能性が高くなる。このマージンのサイズはTrueSkillランキングシステムの構成可能なパラメータであり、ゲームモードに基づいて調整する。例えば、Project Gotham Racing3「商標」でのストリートレースは決して引き分けに終わらず(従って、上記のパラメータは0に設定される)、Perfect Dark Zero「商標」でのCapture−the−Flagゲームは簡単に引き分けに終わる可能性がある。
【0035】
(ベイズの法則に基づく)上記重み付け技術のおかげで、システムはゲームに参加する全てのプレイヤに対して新規スキル確率に到達する。これらのスキル確率はもはやガウス分布ではない。従って、TrueSkillランキングシステムは最良のガウス近似を決定する。結果として、所与のプレイヤのμ値はそのプレイヤが優位であったそれぞれの相手に対して増加し、そのプレイヤが敗北したそれぞれの相手に対して減少する。
【0036】
TrueSkillランキングシステム更新に対する最も単純なケースは、2人による対戦である。プレイヤA(アリス)とB(ボブ)がいて、それぞれのμおよびσの値はそれぞれ(μ、σ)および(μ、σ)であるとする。ゲームを終了すると、更新アルゴリズムは勝者(アリスまたはボブ)および敗者(ボブまたはアリス)を決定し、以下の更新式を適用する。
【0037】
【数1】

【0038】
【数2】

【0039】
【数3】

【0040】
【数4】

【0041】
【数5】

【0042】
これらの式において唯一未知であるのはβである。βはそれぞれのプレイヤの、スキルでのパフォーマンス分散である。さらに、εは、ゲームモードに依存する前述の引き分けマージンである。関数V(.,.)およびW(.,.)は以下で与える。
ゲームが勝利または敗北で終わる場合、
【0043】
【数6】

【0044】
【数7】

【0045】
またはゲームが引き分けで終わる場合
【0046】
【数8】

【0047】
【数9】

【0048】
である。ここで、記号NおよびΦはそれぞれ、ガウス分布関数の密度、およびガウス累積
分布関数を表す。記号tおよびαは単純にその関数に対する引数である。任意の適切な数値的方法または分析方法を使用して、「非特許文献1」で説明されるもののような関数を評価することができる。数値積分を用いて得たこれらの関数の、可変値ε/c記号に対するプロットを図2から5に与える。
【0049】
これらの更新式に関する2、3の所見がある。
【0050】
・ELOシステムと同様に、平均スキル更新式において勝者は平均スキルにv((μwinner−μloser)/c、ε/c)の倍数を加えたものを得、敗者は平均スキルからv((μwinner−μloser)/c、ε/c)の倍数を引いたものを得る。重みファクタは大まかに、不確実性の総和に対する勝者/敗者の不確実性に比例する(2βはスキルでのパフォーマンス変化による不確実性であり、
【0051】
【数10】

【0052】
は真のスキルに関する不確実性である)。従って、平均スキルに対するTrueSkillランキングシステムの更新式は零和になるとは保証されないことに留意されたい。
【0053】
・両方のプレイヤの不確実性は(勝利/敗北/引き分けに関わらず)、ファクタ
【0054】
【数11】

【0055】
だけ減少することになる。再度、高い不確実性を有するプレイヤは大幅な減少を被る。
【0056】
・平均スキルにおける変化、v(μwinner−μloser)/c,ε/c)、および不確実性における減少ファクタ
【0057】
【数12】

【0058】
は、ゲームの結果が驚くべきものでなかった場合は零に近い。
【0059】
勝利/敗北 勝者が全体の不確実性に対して非常に大きな平均スキルを有した場合(従って、(μwinner−μloser)>ε)、勝利しても勝者に追加の平均スキルポイントを与えることはできず、またはどの不確実性も除去することができない。ゲームの結果が驚くべきものであった場合はその反対が真である。すなわち、勝者がより小さな平均スキルを有した場合((μwinner−μloser)<ε)、μwinner−μloserに比例する平均ポイントを勝者に追加するか、または敗者から差し引く。
【0060】
引き分け 両方のプレイヤが予め同様な平均スキルを有した場合(従って、|μwinner−μloser|<ε)、両方のプレイヤは既に十分に接近しており、平均スキルポイント更新を行う必要はない。従って、不確実性は軽減されない。しかしながら、ゲームの前にTrueSkillランキングシステムにより一方のプレイヤの方が非常に強いと考えられた場合(例えば、μwinner−μloser)>ε)、そのプレイヤの平均スキルを減少させ、他のプレイヤの平均スキルを増加させて、実質的にその2つの平均スキルを接近させる。
【0061】
チーム対戦の場合、チームのスキルはプレイヤのスキルの関数であると仮定する。好適な実施形態では、この関数は和である。そのアルゴリズムは2チームのスキルの和を決定し、上の2つの式を使用する。この場合、
【0062】
【数13】

【0063】
および
【0064】
【数14】

【0065】
はそれぞれ、勝者チームおよび敗者チームの平均スキルおよびスキル分散である。
【0066】
3チーム以上に対する更新式では数値積分が必要である。この場合、TrueSkillランキングシステムは隣接するランク上の全チーム間で、すなわち、1番対2番のチーム、2番のチーム対3番のチーム、等で2チーム更新式を繰り返す。VおよびW関数に必要な数値積分の結果、3チーム以上に対して計算の複雑性は立方的に増加する。本発明では、メッセージパッシング技術でファクタグラフを用いてこれを解決するよう取り組み、多チームの状況で必要な計算を削減する。
【0067】
図6を参照する。ゲームのプレイヤの相対的スキルの表示を決定する我々の方法の例を説明する。その方法は、それぞれのプレイヤに対して、確率分布を記述する統計値(図6の囲み60を参照)にアクセスすることを含む。その確率分布はそれ自身、そのプレイヤのスキルに関する我々の確率を記述する。好適な実施形態では、我々は1次元ガウス分布を使用してスキルの確率を表す。例えば、図1は上述したガウス分布の例を示す。ガウス分布を使用することで我々は、上述のように上記の分布を2つの統計値、平均および標準偏差により一意に記述できるという利点を実現する。加えて、2つのガウスランダム変数の和はそれ自身、我々の計算を簡略化可能とするガウスランダム変数である。しかしながら、スキルの確率を表すためにガウス分布を使用することは本質的ではない。
【0068】
プレイヤが前にプレイしたことがある場合、および我々がそのプレイヤに対するスキル情報を格納したことがある場合、その情報にアクセスする。新規プレイヤの場合、我々は関連するデフォルトの統計値、例えば初期値3のμおよび初期値1のσでのデフォルトの確率分布を使用する。任意の適切なデフォルトの確率分布が使用される。
【0069】
ゲーム結果に関する情報を取得し(図6の囲み65を参照)、これを使用してファクタグラフ(囲み61を参照)を統計値とともに形成する。ファクタグラフは特定のプレイヤに関連付けたノードを備え、それらのノードを任意のチームおよびゲームの結果を基に順序付けする。ファクタグラフのノードの一部を、アクセスした統計情報(囲み62を参照)でインスタンス化する。次いでメッセージパッシングをファクタグラフ上で実施して、ベイズ推論を用いてその統計値を更新する(囲み63を参照)。結果の更新統計値はプレイヤの相対的スキルの我々の確率を記述し(囲み64を参照)、そのプロセスをさらなるゲームに対して繰り返すことができる。
【0070】
ファクタグラフの形成プロセスに関するさらなる詳細を、図7を参照して与える。ファクタグラフはリンク71で接続したノード70を備える。ノードは可変ノード(円)またはファクタノード(長方形)のいずれかである。可変ノードは記憶位置を表し、ファクタノードは計算ユニットを表す。ファクタノードは、後述の計算規則に従ってそれらの隣接する可変ノードに対して情報を読み書きする。
【0071】
それぞれのプレイヤを、特定のゲームにおけるそのプレイヤのスキルおよびパフォーマンスに関連する一連のノードに接続した、そのプレイヤのスキルに対する可変ノードで表す。図7において、これらのノードをそれぞれのプレイヤに対して1つの列で示し、同一チーム上のプレイヤは隣接する列内にノードを有する。図7に示す例では4つのチームを表してあり、勝利したチームが1人のプレイヤを有し、そのページの左側の列72で表す。第2位のチーム73は3人のプレイヤを備え、第3位のチーム74は2人のプレイヤを備え、最下位のチーム75は4人のプレイヤを備える。
【0072】
図7に示すように、ファクタグラフは非巡回であることが好ましい。ファクタグラフは2種類のノード、可変ノードおよびファクタノードを備え、2部グラフであることが望ましい。
【0073】
図の上端にあるファクタノード(行76)は、データベースまたは他のストアにアクセスしてそれぞれのプレイヤに対する確率分布を得る関数である(または新規プレイヤの場合はデフォルトの確率分布を使用する)。これらの計算ユニットは、プレイヤのスキル確率分布を記述するパラメータを、対応する可変ノードに送り込む。例えば、ガウス分布の場合は、それぞれの可変ノードに格納される2つのパラメータ(2つの浮動小数点数)があるであろう。可変ノードの次の行、すなわち、上端のリーフノードに直列して接続させた円形ノード77はプレイヤスキルを表す。これらのノードはそれぞれ、関連するプレイヤに対する確率分布を記述する統計値を格納する。ファクタノードの次の行は計算ユニット78である。計算ユニット78は、本例では、プレイヤスキルにノイズを加えたものを基にプレイヤパフォーマンスを計算する。すなわち、分散パラメータを増加させることでユニット77のスキル確率分布を修正し、結果を、プレイヤパフォーマンスを表す可変ノード79の行に格納する。これは決定性計算であるが、根底のランダム変数にノイズを加えるものとして考えることができる。
【0074】
個々のプレイヤパフォーマンスと対照的にチームパフォーマンスの表現を得るため、列を図7に示すように結合する。例えば第2位のチームの場合、このチームは3人のプレイヤを有する。このチームのパフォーマンスを3人のプレイヤのパフォーマンスの和と捉え、これを行80内の長方形ノードで示す。その計算結果を行81内の円形ノードに格納する。従って行81内には、プレイヤ毎に1つのノードではなくチーム毎に1つのノードがある。ガウス分布を使用する場合、総和プロセスの結果もガウス分布である。
【0075】
図7に示す好適な実施形態では、ノイズをそれぞれの個々のプレイヤに追加し、次いでプレイヤパフォーマンスを結合してチームパフォーマンスを形成する。しかしながら、これは本質的ではない。プレイヤスキルを最初に結合してチームスキルを得て、次いでノイズをチームスキルに追加してチームパフォーマンスを得ることも可能である。ノイズを個々のプレイヤパフォーマンスおよび/または結合したチームパフォーマンスに追加することができる。
【0076】
チームパフォーマンスの差分を行82内のノードで表し、示すようにそれぞれをチームパフォーマンス層81内の或る特定のノード間の差分として計算する。ゲームの結果がチームの全体の順序を与える場合、その順序内の連続するチーム間の差分を計算する。チーム間で引き分けの場合、引き分けたチームをそれらの間の任意の順序で配置し、差分をその順序における連続するチーム間で計算する。例えば図7において、ここでのゲーム結果が、中間の2つのチーム73、74が引き分けたようなものであった場合、それらの2チームを表すノードを入れ替えて等しく妥当なファクタグラフを生成することができる。行83内の円形ノードはチームパフォーマンスの差分計算の結果を表す。ガウス分布を使用する場合、差分プロセスの結果もガウス分布である。
【0077】
グラフ内の下端ノードは、チームパフォーマンスの差分が引き分けマージンεよりも大きく(引き分けなしの場合)、または絶対値での引き分けマージン未満である(引き分けの場合)よう促す計算プロセスを表すファクタノードである。これを図8に関してより詳細に説明する。
【0078】
図8は、例えば図7の行83にあるノードで利用可能なチームパフォーマンスの差分に対する確率分布の例を表すガウス分布(実線の曲線91で示す)を示す。このガウス分布を、インジケータ関数により図8内の点線90により示すものに変換する。このインジケータ関数はチームパフォーマンスの差分が引き分けマージンより大きくなるよう促す。ガウス分布91はネガティブ領域92に伸びる裾を有し、その変換によりネガティブ領域において非常に小さい裾のみを有するガウス分布90を生成する。変換したガウス分布は初期分布91より狭い。すなわち、より小さな偏差を有し、その平均も高い。
【0079】
メッセージパッシングのプロセスは、隣接する可変ノードからの分布パラメータを用いた計算ノード(図7の四角形ノード)に関連付けた計算の実行、および隣接する可変ノードの1つ(図7の円形ノード)に結果を渡すことを備える。結果を渡す方向(処理スケジュールとも称する)をさらに詳細に説明する。
【0080】
処理スケジュールを3段階、すなわち、前処理、連鎖処理、および後処理に分割することが好ましい。前処理スケジュールの例を図9に示す。上端のファクタノード(行76)から開始して、スキル分布をデータベースから取得するか、またはデフォルト値に設定し、計算はチームパフォーマンスの行(行81)に到達するまでそれぞれの列に沿って下方に進む。後処理スケジュールは前処理スケジュールの逆であるが、行77内のプレイヤスキルで停止する。
【0081】
前処理の1ステップの後、連鎖処理スケジュールを、確率分布の変化が止まるまで繰り返す。連鎖スケジュールの例を、点線矢印を用いて図8に示す。その連鎖スケジュールの例は、パフォーマンス確率分布を、全てのパフォーマンスの差分が下端のファクタノードが課す条件を満たすまでチーム間で往復して渡す。後処理段階はパフォーマンス分布を上方に渡して新規のプレイヤスキルを取得する。処理スケジュール内のそれぞれの矢印は自明でない計算を表し、それらの計算の詳細を以下で与える。図7で与える例では、全てのファクタノード(四角形の計算ノード)は、それらを最後のインジケータ関数ノード(順序ファクタノードと称する)を除いて正確に計算できるので、厳密なファクタノードである。順序ファクタノードは順序制約を実装し、これらのノードに対して関連する更新式は真のファクタ‐変数メッセージがもはやガウス分布でないので厳密ではない。
【0082】
メッセージパッシングプロセスにおいて矢印に沿った計算の実行に使用する一般的な更新式を提示する。我々は、示したガウス分布で使用するためのそれらの一般的な更新式を調整する。
【0083】
ガウスメッセージでのファクタノード更新
図10のファクタグラフを考える。
【0084】
メッセージmf→xおよび限界pを更新したいとする。すると、一般的な更新式は次のようになる。
【0085】
【数15】

【0086】
【数16】

【0087】
【数17】

【0088】
【数18】

【0089】
ここで、MM[・]は、引数と同じモーメントを有するガウスファミリー(Gaussian family)内の分布を返し、右辺の全ての量を分布になるように正規化する。次式で、我々はガウス分布の指数表現を使用する。すなわち、
【0090】
【数19】

【0091】
である。
【0092】
この密度は標準密度に対して次の関係を有する。
【0093】
【数20】

【0094】
、あるいは
【0095】
【数21】

【0096】
厳密なファクタノードの場合、更新式を以下の表で与える。
【0097】
【表1】

【0098】
順序ファクタノードの場合、更新式を次の表で与える。
【0099】
【表1】

【0100】
上の表で設計した更新式において、aは重みを表し、好適な例では1に設定する。重みが1ではない状況の例を、部分的プレイという小見出し以下で議論する。また、更新式において、vおよびwは次式で与える関数v(.,.)およびw(.,.)に対応する。
ゲームが勝利または敗北で終わる場合、
【0101】
【数22】

【0102】
【数23】

【0103】
ゲームが引き分けで終わる場合
【0104】
【数24】

【0105】
【数25】

【0106】
これらの式は、メッセージパッシングを用いずにTrueSkillの以前の実装においてガウス分布およびガウス累積分布を数値近似することで決定した。
【0107】
図9に示す例では、連鎖スケジュールの間のメッセージパッシングは、順序ファクタノード更新式表の第1行の更新式を用いて、行84内のノードから層83内のノードへの順序ファクタノード更新を含む。引き分けの場合、チームパフォーマンス差分の係数は、潜在的な引き分け値ε以下に制限され、順序ファクタノード更新式表の第2行の更新式を使用する。
【0108】
厳密なファクタノードの場合、計算ノード(四角形ノード)から1つの可変ノード(円形ノード)へのメッセージパッシングに対して、厳密なファクタノード更新式表の第1行の更新式を使用する。計算ノードから2つの可変ノードへのメッセージパッシングの場合、表の第2または第3の行の更新式を必要に応じて使用する。計算ノードから3つの可変ノードへのメッセージパッシングの場合、表の第4または第5の行の更新式を必要に応じて使用する。
【0109】
部分的プレイ
部分的プレイの場合、1人または複数人のプレイヤはゲーム継続時間より少ない時間だけゲームに参加する。プレイヤのスキルレベルに関する我々の確率の更新においてこれを考慮するため、上述の更新式における値aである重み付けを使用する。それぞれのプレイヤがゲームに参加する時間に関する情報を使用すると、プレイヤに対して適切な重み値を設定することが可能である。
【0110】
例えば、それぞれ2人のプレイヤを有する2つのチームから成るゲームにおいて、第1のチームの第1のプレイヤは全体のゲーム時間のうち75%しか参加していないことも可能である。この場合、対応する値は残りの他の3人のプレイヤに対する1.0と比較して0.75となるであろう。
【0111】
部分的ランキング
ゲームの結果、全てのプレイヤ(またはチーム)より1つ以上少ないランクのみが生じる場合、ファクタグラフの構造を修正することでこれを考慮することができる。例えば、モータレーシングゲームでは、第1、第2および第3の参加者のランクのみを知ることができ、任意の他のプレイヤはランクされない。あるいは、勝者を知ることはできるが、他のプレイヤにはランクが提供されない。この場合、我々は、特定の例として図19に示すようにファクタグラフの構造を修正する。
【0112】
図19は、勝者および第2位のチームは既知だが残りの2チーム190、191のランクは未知である場合を示す。ファクタグラフは、チームパフォーマンスの差分をチーム190と191との間ではなく第2位のチームとチーム191との間で計算することを除いて、図7と同じである。従って、ファクタグラフは既知のランクのチームに関連付けたノードと未知のランクのチームの各々に関連付けたチームとの間のリンクを備える。図19の例では、これらは行82内のノードΔおよびΔの各々に接続した行81内のノードtpに対応する。
【0113】
任意の適切な装置を使用して本明細書で説明した方法を実装することができる。例えば、図20はゲームの少なくとも第1のプレイヤおよび第2のプレイヤの相対的スキルの表示を、それらのプレイヤを含む1つまたは複数の上記ゲームの結果に基づいて決定する装置の概略図である。上記の装置は、
・それぞれのプレイヤに対して、そのプレイヤのスキルに関する確率に関連付けた確率分布を記述する統計値200にアクセスするよう配置した入力206、
・1つのゲームの結果201に関する情報を受信するよう配置した入力207、
・ノードを備えるファクタグラフを形成する手段203であって、そのグラフを上記の結果に関する受信情報を用いて形成し、上記ノードの少なくともいくつかを上記の統計値でインスタンス化する手段203、および
・それぞれのプレイヤに関連付けた上記の統計値を、上記のファクタグラフ上のメッセージパッシング技術を用いて更新するよう配置した1つまたは複数のプロセッサ204
を備える。
【0114】
当業者は、プログラム命令の格納に利用する記憶装置をネットワークに渡って分散できることを理解するであろう。例えば、リモートコンピュータは説明したプロセスの例をソフトウェアとして格納することができる。ローカルまたは端末コンピュータはリモートコンピュータにアクセスすることができ、ソフトウェアの一部または全部をダウンロードしてプログラムを実行することができる。あるいは、ローカルコンピュータはソフトウェア部分を必要に応じてダウンロードすることができ、またはいくつかのソフトウェア命令をローカル端末で実行して、いくつかをリモートコンピュータ(またはコンピュータネットワーク)で実行することができる。当業者は、当業者に公知である従来技術を利用することで、ソフトウェア命令の全部または一部をDSP、プログラマブルロジックアレイ、等のような専用回路により実行できることも理解するであろう。
【0115】
本明細書で説明した相対的スキルレベルの計算での使用に適合させたメッセージパッシング技術の使用は、分散処理に特に適合する。これは、ファクタグラフ内の任意の特定のファクタノードに関連付けた処理を所与のプロセッサで実行でき、その結果がグラフ内の他のノードに関連付けた計算を実行する別の独立したプロセッサに渡されるからである。それらの独立したプロセッサを、任意の適切な型の通信ネットワーク上で接続することができ、または互いに統合することができる。
【0116】
当業者に明らかなように、本明細書で与えた任意の範囲または装置の値を、求めた効果を失わずに拡張または変更することができる。
【0117】
本明細書で説明した方法のステップを必要に応じて任意の適切な順序、または同時に実行することができる。
【0118】
当然のことながら、好適な実施形態の上の説明は例として与えたに過ぎず、様々な修正を当業者により行うことができる。
【図面の簡単な説明】
【0119】
【図1】スキルの確率を表すために用いるガウス分布の例の図である。
【図2】ゲームが勝ち負けで終了する場合の、様々な引き分けマージンεの値に対する関数Vをプロットした図である。
【図3】ゲームが勝ち負けで終了する場合の、様々な引き分けマージンεの値に対する関数Wをプロットした図である。
【図4】ゲームが引き分けで終了する場合の、様々な引き分けマージンεの値に対する関数Vをプロットした図である。
【図5】ゲームが引き分けで終了する場合の、様々な引き分けマージンεの値に対する関数Wをプロットした図である。
【図6】ゲームのプレイヤの相対的スキルの表示を決定する方法のフロー図である。
【図7】4チームを有するゲームに対するファクタグラフの例の図である。
【図8】ファクタグラフ内の順序ノードに関連付けたプロセスの適用前後のガウス確率分布を示す図である。
【図9】スケジューリングを示す矢印を有する、図7のファクタグラフを示す図である。
【図10】ファクタグラフの例の図である。
【図11】ファクタグラフの例の図である。
【図12】ファクタグラフの例の図である。
【図13】ファクタグラフの例の図である。
【図14】ファクタグラフの例の図である。
【図15】ファクタグラフの例の図である。
【図16】ファクタグラフの例の図である。
【図17】ファクタグラフの例の図である。
【図18】ファクタグラフの例の図である。
【図19】部分的ランキングに対して修正した、図7のファクタグラフを示す図である。
【図20】ゲームのプレイヤの相対的スキルの表示を決定する装置の概略図である。

【特許請求の範囲】
【請求項1】
ゲームの少なくとも第1のプレイヤおよび第2のプレイヤの相対的スキルの表示を、それらのプレイヤが関与する1つまたは複数の前記ゲームの結果に基づいて決定する方法であって、
(1)それぞれのプレイヤに対して、そのプレイヤのスキルに関する確率に関連付けた確率分布を記述する統計値にアクセスするステップと、
(2)前記ゲームの1つの結果に関する情報を受信するステップと、
(3)ノードを備えるファクタグラフを形成するステップであって、前記グラフを前記結果に関する前記受信情報を用いて形成し、前記ノードの少なくともいくつかを前記統計値でインスタンス化するステップと、
(4)それぞれのプレイヤに関連付けた前記統計値を、前記ファクタグラフ上のメッセージパッシング技術を用いて更新するステップと
を備えることを特徴とする方法。
【請求項2】
前記統計値はそれぞれの確率分布を記述する少なくとも平均および分散を備えることを特徴とする請求項1に記載の方法。
【請求項3】
前記確率分布はガウス分布であることを特徴とする請求項1または2に記載の方法。
【請求項4】
前記ファクタグラフは非巡回であることを特徴とする任意の先行請求項に記載の方法。
【請求項5】
前記ファクタグラフに適用した前記メッセージパッシング技術を配置して、ベイズ推論プロセスを実行することを特徴とする任意の先行請求項に記載の方法。
【請求項6】
前記ファクタグラフは複数のノードグループを備え、それぞれのグループを特定のプレイヤに関連付け、前記のそれぞれのグループは直列に接続したノードを備えることを特徴とする任意の先行請求項に記載の方法。
【請求項7】
前記ファクタグループは複数の第2のノードグループを備え、それぞれの第2のグループをプレイヤチームに関連付けることを特徴とする任意の先行請求項に記載の方法。
【請求項8】
前記ノードグループを端で接続し、前記接続順序は前記ゲーム結果を反映することを特徴とする請求項6または7に記載の方法。
【請求項9】
前記ノードグループをさらに、前記プレイヤが参加しているチームを基に前記ファクタグラフ内で順序付けすることを特徴とする請求項8に記載の方法。
【請求項10】
3人以上のプレイヤが関与するゲームからプレイヤの前記相対的スキルの表示を決定することを特徴とする任意の先行請求項に記載の方法。
【請求項11】
前記ゲーム結果に関する情報は、それぞれのプレイヤに対して、前記ゲームにそのプレイヤが参加した時間の表示をさらに備え、前記統計値を前記情報を基に更新することを特徴とする任意の先行請求項に記載の方法。
【請求項12】
前記ゲーム結果に関する情報はプレイヤの部分的ランキングを備え、前記部分的ランキングは、複数の他のプレイヤと比較して少なくとも1人のプレイヤに対する順序情報を備え、前記複数の他のプレイヤの順序情報は備えず、前記ファクタグラフを、前記の少なくとも1人のプレイヤに関連付けたノードと前記の他のプレイヤの各々に関連付けたノードとの間でリンクが作成されるように形成することを特徴とする任意の先行請求項に記載の方法。
【請求項13】
コンピュータ上での実行時に任意の先行請求項の全ステップを実行するよう適合させたコンピュータプログラムコード手段を備えることを特徴とするコンピュータプログラム。
【請求項14】
コンピュータ可読媒体上に具現化されることを特徴とする請求項13に記載のコンピュータプログラム。
【請求項15】
ゲームの少なくとも第1のプレイヤおよび第2のプレイヤの相対的スキルの表示を、それらのプレイヤが関与する1つまたは複数の前記ゲームの結果に基づいて決定する装置であって、
(1)それぞれのプレイヤに対して、そのプレイヤのスキルに関する確率に関連付けた確率分布を記述する統計値にアクセスするよう配置した入力と、
(2)前記ゲームの1つの結果に関する情報を受信するよう配置した入力と、
(3)ノードを備えるファクタグラフを形成する手段であって、前記グラフを前記結果に関する前記受信情報を用いて形成し、また前記ノードの少なくともいくつかを前記統計値でインスタンス化する手段と、
(4)それぞれのプレイヤに関連付けた前記統計値を、前記ファクタグラフ上のメッセージパッシング技術を用いて更新するよう配置した1つまたは複数のプロセッサと
を備えることを特徴とする装置。
【請求項16】
前記ファクタグラフは非巡回であることを特徴とする請求項15に記載の装置。
【請求項17】
前記ファクタグラフに適用した前記メッセージパッシング技術を配置して、ベイズ推論プロセスを実行することを特徴とする請求項15および16のいずれかに記載の装置。
【請求項18】
前記ファクタグラフは複数のノードグループを備え、それぞれのグループを特定のプレイヤに関連付け、前記のそれぞれのグループは直列に接続したノードを備えることを特徴とする請求項15から17のいずれかに記載の装置。
【請求項19】
前記ファクタグラフは複数のノードグループを備え、それぞれのグループをプレイヤチームに関連付けることを特徴とする請求項15から18のいずれかに記載の装置。
【請求項20】
前記ノードグループを端で接続し、結果生じる順序は前記ゲーム結果を反映することを特徴とする請求項18または19に記載の装置。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate


【公表番号】特表2009−525807(P2009−525807A)
【公表日】平成21年7月16日(2009.7.16)
【国際特許分類】
【出願番号】特願2008−554242(P2008−554242)
【出願日】平成19年1月16日(2007.1.16)
【国際出願番号】PCT/US2007/001096
【国際公開番号】WO2007/094909
【国際公開日】平成19年8月23日(2007.8.23)
【出願人】(500046438)マイクロソフト コーポレーション (3,165)
【Fターム(参考)】