2

(这是针对我正在设计的游戏)假设一个游戏中有两队玩家。每支球队将有4名球员。每个玩家都有一个等级(0-9),其中 0 表示一个糟糕的玩家,9 表示一个了不起的玩家。有一个等待玩游戏的玩家队列(或列表)(这可能是一个小数字或一个非常大的数字)。假设每支球队的总排名是其中 4 名球员的平均排名。有多个开放的比赛和球队可以放置一名球员。

问题:有什么好的算法可以将玩家置于团队的等待队列/列表中,以便游戏中的每个团队在游戏中具有或多或少相同的总体排名(不一定是完美的)?此外,球员不应该等待超过一分钟才能被安排在一个团队中(如果球员很少,可以更多)[他们被安排得越快越好]

4

5 回答 5

7

这完全取决于球队的综合排名需要有多接近。如果准确性不是那么重要,您可以执行以下简单操作:

  1. 将前八名球员从名单中删除。
  2. 将排名最高的球员放在 A 队,将第二高的球员放在 B 队
  3. 剩下六名球员,这意味着你还剩下 20 个球队组合。计算所有 20 并选择导致最接近团队分数的组合。

这应该是快速和简单的,尽管它可能不会产生最平衡的结果。等待时间应该最短,因为它总是使用等待时间最长的玩家。第 2 步确实是消除计算可能性数量的捷径。如果没有第 2 步,则有 70 种可能的团队组合(“8 选 4”)。您可能会发现您可以计算所有 70 个并找到一个好的解决方案,而不会占用太多时间。提示:理想的球队得分是(所有球员的总和/2)。如果您偶然发现与该特定团队得分的组合,您可以停下来。

如果您愿意,可以进一步细化此步骤。一旦你找到了八人中最好的对决,比较两支球队的得分。如果他们相距太远(你必须定义什么构成“太远”),用队列中的下两个玩家随机替换两个玩家,然后再试一次。你甚至可以根据玩家等待的时间来让“太远”的定义变得更宽松。

您也可以对此采取稍微不同的方法。将球员随机分组,然后寻找两个排名相似的球队(这变得像比较一个数字一样简单)。一旦一支球队在指定的时间内没有找到比赛,将这些球员放回池中以重新组成新球队。如果您通常有大量玩家排队(因此有更多的现成团队),那么这可能会更快地产生结果。

在你花太多时间在这个算法上之前,先好好看看生成玩家排名的算法。人的技能和经验不能用一个数字来概括而没有相对较大的误差范围。如果这里的误差可能相当大,那么您可以使用不太准确的团队建设算法(任何额外的准确性都会被玩家排名系统中的错误抵消)。

于 2012-06-12T01:45:14.003 回答
2

你应该开始用一个人来搭建桌子。如果 A 的等级为 8,而另一个玩家以 4 的等级加入游戏,而你的位置指南是 2,那么

玩家 A 有桌子 玩家 A 的等级为 8

玩家 B 进入房间 玩家 B 的排名不是在 6 到 10 之间吗?

if (Brank < Arank - 2 || Brank > Arank + 2)

如果这是真的,那么排名不在表格的限制范围内,您应该以 Brank 作为您比较的排名开始一个新表格。

如果这是错误的,那么排名是表声明排名的 +-2 并且该玩家可以加入。

如果你真的想看中,你可以根据等桌的人数来宣布排名。

如果大厅100人,则限制+- 2。如果大厅15人,则限制+- 4。(使游戏更加不平衡,但不会导致人们等待太久)。

于 2012-06-12T01:24:05.247 回答
2

首先,这取决于你如何衡量球员的技能。有多种方法可以做到这一点,每种方法都有自己的衡量多个玩家“平均技能”的方法。

一个好的方法是采用已经开发的系统,Elo 评级(http://en.wikipedia.org/wiki/Elo_rating_system)如今已被广泛使用,但要知道,如果你想要一个简单的实现不会很好地工作在有多名球员的球队中衡量个人球员的技能。

话虽如此,假设您有一个系统,其中团队的评分是其成员评分的平均值。另外,让我们假设玩家在技能水平之间均匀分布。一个好的第一种方法是在同一个游戏中将具有相同技能水平的玩家分组。一支球队有 2 名 9 分和 2 名 1 分球员,而另一支球队有 4 名 5 分球员的比赛不会是一场好比赛。

因此,开始将技能水平相近的玩家分组到多个最多 8 人的组中。(一名球员可能在其中不止一个)。您可以通过将技能级别为 1-4 的球员分组,另一个为 2-5、3-6 等的球员组来做到这一点。当这些组中的任何一个有 8 名球员时,您可以将他们安排成一场比赛,并将球队排序一种方式,每个人都有大约相同的平均值。

现在,存在玩家等待时间过长的问题,因此如果玩家等待超过 1 分钟,您可以让技能 4 的玩家加入技能等级 5-8 的玩家组,例如还要记住玩家所涵盖的技能范围组应随队列中的玩家数量而变化。

于 2012-06-12T01:35:34.583 回答
1

鉴于您的玩家等级数量有限,您可以围绕它构建您的算法。有10个队列,每个等级一个。跟踪每个条目的插入时间,以便您始终知道等待时间最长的排名 i 的玩家是谁(通过检查队列 i 的头部)。

从那里你可以形成一个游戏如下。

  1. 将等待时间最长的四个人组成一个团队。
  2. 得到他们排名的总T
  3. 遍历 T 的每个 4 分区,(i,j,k,l) - 检查队列 i,j,k,l 的头部并添加它们的等待时间,找到总共等待时间最长的四个人,总排名的 T. 将他们组成第二队并开始比赛。
  4. (如果在步骤 3 中没有找到,请等待(更好的匹配)或将搜索扩展到 [T-delta, T+delta](更公平的等待时间))

整数 T 的 4 分区是 (i,j,k,l),使得 i+j+k+l = T。

于 2012-06-12T02:15:51.470 回答
1

衡量玩家技能是一个单独的话题,我不会给出任何想法。使用现有方案(例如 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
于 2013-09-09T07:05:03.893 回答