衡量玩家技能是一个单独的话题,我不会给出任何想法。使用现有方案(例如 ELO 或 Microsoft 研究开发的公式http://en.wikipedia.org/wiki/TrueSkill或许多其他方案之一)我认为是一个很好的起点。
一旦你有了你的幻数,就会有很多考虑因素,比如你(和你的玩家)的偏好。虽然它不是用 C++ 编写的,但您可以在下面找到我的配对系统迷你原型(100 行 f# 代码,您可以在http://www.tryfsharp.org/Create上玩,无需下载任何工具)。
我的设计目标是:
- 让它运行得快(不要为了提高团队平衡而进行长时间的迭代),考虑到可能有 100000 名玩家,其中几百人在队列中,被分配到可能要开始的 50-100 场比赛,太科学是也许不是一个好主意。但我宁愿将其视为一个实验性框架,您可以将改进/想法放入其中的功能称为“ImproveTeams”。
- 不要尝试在给定时间跨多个新游戏进行优化。
- 尝试为玩家提供他们自己技能水平的游戏体验,而不是为团队配备绝对的新手和职业游戏玩家。
这个怎么运作:
- 池按玩家评分降序排列。
- 自上而下(最好的球员到更差的球员),球队通过简单地拼接前 2 个 N 来组装(N = 每支球队的球员数量)。这样做会导致 A 队总是比 B 队更好或同样强大。
- 使用团队 a、团队 b 和池的其余部分的信息调用 ImprovementTeams。ImprovementTeams 迭代两支球队,计算技能增量,然后根据它是正数还是负数,将两支球队阵列中相同位置的球员洗牌。
这同样适用于剩余在池中的玩家,在第一场比赛配对后,直到服务器容量(免费游戏槽)用完或玩家池为空。
缺点:糟糕的玩家等待时间更长,因为他们总是最后处理。一个简单的修改可以通过简单地在上面描述的自上而下工作的算法与自下而上工作的双重解决方案之间交替来改善这一点。
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