(これは私がデザインしているゲームです) ゲームに 2 つのチームのプレイヤーがいるとします。各チームには4人のプレーヤーがいます。各プレーヤーにはランク (0 ～ 9) があり、0 は悪いプレーヤーを示し、9 は素晴らしいプレーヤーを示します。ゲームをプレイするのを待っているプレーヤーのキュー (またはリスト) があります (これは少数または非常に多数の可能性があります)。各チームの全体的なランクは、内の 4 人のプレーヤーの平均であるとしましょう。複数のオープン ゲームと、プレーヤーを配置できるチームがあります。
質問: チームの待機キュー/リストにプレーヤーを配置して、ゲーム内の各チームがゲーム全体でほぼ同じランクになるようにする優れたアルゴリズムは何ですか? (完璧である必要はありません)? また、プレイヤーはチームに配置されるまで 1 分以上待つ必要はありません (プレイヤーが非常に少ない場合は、より長くなる可能性があります) [配置が早ければ早いほど良い]
これは、チームの合計ランキングがどれだけ接近する必要があるかに完全に依存します。精度がそれほど重要でない場合は、次のような簡単なことを行うことができます。
これは、最もバランスの取れた結果を生成しない可能性がありますが、高速でシンプルなはずです。待機時間が最も長いプレーヤーを常に使用するため、待機時間は最小限に抑える必要があります。ステップ 2 は、実際には、計算する可能性の数を排除するための近道です。ステップ 2 がなければ、70 通りのチームの組み合わせが可能です (「8 人が 4 人を選ぶ」)。時間をかけずに 70 個すべてを計算して、適切な解を見つけることができるかもしれません。ヒント: 理想的なチーム スコアは (すべてのプレーヤーの合計 / 2) です。その特定のチーム スコアの組み合わせに出くわした場合は、停止できます。
必要に応じて、これをさらに洗練することができます。8 人の中で最高の組み合わせを見つけたら、2 つのチームのスコアを比較します。それらが離れすぎている場合 (何が「遠すぎる」かを定義する必要があります)、2 人のプレーヤーをランダムにキューの次の 2 人と置き換えて、もう一度やり直してください。プレイヤーの待機時間に基づいて、「遠すぎる」の定義をより寛大にすることもできます。
これとは少し異なるアプローチを取ることもできます。プレイヤーをランダムにチームにグループ分けし、ランキングが似ている 2 つのチームを探します (これは、1 つの数字を比較するのと同じくらい簡単です)。チームが一致を見つけることなく指定された時間経過したら、それらのプレーヤーをプールに戻して、新しいチームに再編成します。通常、多数のプレーヤーがキューに入っている場合 (つまり、既製のチームのプールが大きい場合)、これにより結果が早くなる可能性があります。
このアルゴリズムに時間をかける前に、プレーヤーのランキングを生成するアルゴリズムをよく見てください。人間のスキルと経験は、比較的大きな誤差がなければ 1 桁に要約できません。ここでの誤差がかなり大きくなる可能性が高い場合は、精度の低いチーム ビルディング アルゴリズムを使用する余裕があります (余分な精度は、プレーヤーのランキング システムの誤差によって無効になります)。
1 人でテーブルの作成を開始する必要があります。人物 A のランクが 8 で、別のプレイヤーがランク 4 でゲームに参加し、配置ガイドが 2 倍の場合、
プレイヤー A はテーブルを持っています プレイヤー A はランク 8 を持っています
プレーヤー B が部屋に入る プレーヤー B のランクは 6 と 10 の間にありませんか?
if (Brank < Arank - 2 || Brank > Arank + 2)
そうであれば、ランクはテーブルの制限内にないため、比較するランクとしてブランクを使用して新しいテーブルを開始する必要があります。
それが偽の場合、ランクはテーブルの宣言されたランクの +-2 であり、そのプレイヤーは参加できます。
どうしてもおしゃれになりたい場合は、テーブルを待っている人の数に基づいてランキングを宣言できます。
ロビーに 100 人がいる場合は、制限を +-2 にします。ロビーに 15 人がいる場合は、制限を +-4 にします。
まず第一に、これはプレイヤーのスキルをどのように測定するかによって異なります。それには複数の方法があり、それぞれに複数のプレーヤーの「平均スキル」の独自の尺度があります。
良いアプローチは、すでに開発されたシステムを採用することです。Elo レーティング ( http://en.wikipedia.org/wiki/Elo_rating_system ) は最近広く使用されていますが、単純な実装はうまく機能しないことを知っておいてください。複数のプレーヤーがいるチームで個々のプレーヤーのスキルを測定します。
そうは言っても、チームの評価がそのメンバーの評価の平均であるシステムがあるとします。また、プレイヤーのスキル レベルが均一に分布しているとします。最初の適切なアプローチは、同じゲームで同じスキル レベルのプレイヤーをグループ化することです。あるチームにレーティング 9 のプレイヤーが 2 人、レーティング 1 のプレイヤーが 2 人いて、もう一方のチームにレーティング 5 のプレイヤーが 4 人いるような試合は、良いものにはなりません。
そのため、スキル レベルが近いプレイヤーを、最大 8 人までの複数のグループにグループ化することから始めます。(プレーヤーは、これらの複数に存在する可能性があります)。これを行うには、スキル レベル 1 ～ 4 のプレーヤーのグループを作成し、別のグループを 2 ～ 5、3 ～ 6 などにします。これらのグループのいずれかに 8 人のプレーヤーがいる場合、それらを試合に編成し、チームを並べ替えることができます。それぞれがほぼ同じ平均を持つ方法。
ここで、プレイヤーの待機時間が長すぎるという問題があるため、スキル 4 のプレイヤーが 1 分以上待機した場合、スキル レベル 5 ～ 8 のプレイヤー グループに参加させることができます。グループは、キュー内のプレーヤーの数によって異なります。
プレーヤーランクの数が少ない場合は、それを中心にアルゴリズムを構築できます。ランクごとに1つずつ、合計10のキューがあります。各エントリがいつ挿入されたかを追跡して、最も長く待機しているランクiのプレーヤーが誰であるかを常に把握できるようにします（キューiの先頭を調べることにより）。
そこから、次のようにゲームを作成できます。
整数Tの4分割は、i + j + k + l = Tとなるような（i、j、k、l）です。
プレイヤーのスキルを測定することは別のトピックであり、私は何も考えません。既存のスキーム (例えば、ELO や Microsoft の研究で開発された公式http://en.wikipedia.org/wiki/TrueSkillや他の多くのスキームの 1 つ) を使用することは、良い出発点だと思います。
マジック ナンバーを取得したら、あなた (およびプレイヤー) の好みに関して、多くの考慮事項が入ります。これは C++ で書かれていませんが、以下にマッチメイキング システムのミニ プロトタイプを示します (100 行の f# コード、ツールをダウンロードせずにhttp://www.tryfsharp.org/Createで操作できます)。
私の設計目標は次のとおりです。
使い方：
最初のマッチがペアリングされた後、サーバーの容量 (無料のゲーム スロット) が使い果たされるか、プレイヤー プールが空になるまで、プールに残っているプレイヤーにも同じことが適用されます。
欠点: 悪いプレイヤーは常に最後に処理されるため、待ち時間が長くなります。上に示したアルゴリズムをトップダウンで動作させ、デュアル ソリューションをボトムアップで動作させるだけで、簡単な変更で改善できます。
type Rating = uint32
type RatingDiff = int32
type Player = { name : string; rating : Rating }
// tuple of: Candidate player in team a, Canditate players in team b, Remainder of pool
type WorkingSet = Player array * Player array * Player array
let pool : Player array =
[| { name = "Hugo"; rating = 1100u }
{ name = "Paul"; rating = 800u }
{ name = "Egon"; rating = 1800u }
{ name = "John"; rating = 1300u }
{ name = "Rob"; rating = 400u }
{ name = "Matt"; rating = 1254u }
{ name = "Bruce"; rating = 2400u }
{ name = "Chuck"; rating = 2286u }
{ name = "Chuck1"; rating = 2186u }
{ name = "Chuck2"; rating = 2860u }
{ name = "Chuck3"; rating = 1286u }
{ name = "Chuck4"; rating = 786u }
|]
let SortByRating (pool : Player array) : Player array =
pool
|> Array.sortWith
(fun (p1 : Player) (p2 : Player) ->
match (p1.rating,p2.rating) with
| (r1,r2) when r1 > r2 -> -1
| (r1,r2) when r1 < r2 -> 1
| _ -> 0
)
let evens n = 2 * n
let odds n = 2 * n + 1
// Note: Since the input is sorted by player level, obviously team A is always stronger or equal in strength to team B
let Split (n : int) (a : Player array) : WorkingSet =
let teamA : Player array = [| for i in 0 .. (n-1) -> a.[evens i] |]
let teamB : Player array = [| for i in 0 .. (n-1) -> a.[odds i] |]
let remainder = Array.sub a (2*n) ((Array.length a) - 2 * n)
( teamA, teamB, remainder )
// This is the function where teams get improved - can be as well a recursive function.
// Anyone is invited to provide alternate, better implementations!
let ImproveTeams (ws : WorkingSet) : WorkingSet =
let a,b,r = ws
let R2RD (r : Rating) : RatingDiff =
let r1 : RatingDiff = int32 r
r1
let UpdateScore (score : RatingDiff) (pa : Player) (pb : Player) : RatingDiff =
score + (R2RD pa.rating) - (R2RD pb.rating)
let improved : RatingDiff * Player array * Player array =
Array.fold2
(fun s pa pb ->
let score,teamA, teamB = s
let betterPlayer p1 p2 =
match (p1.rating,p2.rating) with
| (r1,r2) when r1 >= r2 -> p1
| _ -> p2
let worsePlayer p1 p2 =
match (p1.rating,p2.rating) with
| (r1,r2) when r1 >= r2 -> p2
| _ -> p1
let bp = betterPlayer pa pb
let wp = worsePlayer pa pb
match score with
| x when x > 0 -> (UpdateScore x wp bp, Array.append teamA [| wp |], Array.append teamB [| bp |])
| _ -> (UpdateScore score bp wp, Array.append teamA [| bp |], Array.append teamB [| wp |])
) (0, [||], [||]) a b
let ns,nta,ntb = improved
(nta, ntb,r)
let rec CreateTeams (maxPlayersPerTeam : int) (players : Player array) : WorkingSet =
let sortedPool = SortByRating players
match (Array.length sortedPool) with
| c when c >= (maxPlayersPerTeam * 2) ->
Split maxPlayersPerTeam sortedPool
|> ImproveTeams
| 0 -> ( [||], [||], [||] )
| _ -> CreateTeams (maxPlayersPerTeam-1) players
let ShowResult (result : WorkingSet) : unit =
let ShowPlayer p =
printf "%s - %d" p.name p.rating
let a,b,r = result
let Score (pl : Player array) : Rating =
Array.fold (fun s p -> s + p.rating) 0u pl
printfn "Team A\t\t\t| Team B"
Array.iter2
( fun pa pb ->
ShowPlayer pa
printf "\t\t\t| "
ShowPlayer pb
printfn ""
) a b
let sa = Score a
let sb = Score b
printfn "Score Team A: %d\t\t\t| Score Team B: %d" sa sb
printfn "Players still in pool: "
Array.iter
(fun p ->
ShowPlayer p
printfn ""
) r
CreateTeams 4 pool |> ShowResult