在线游戏的公平匹配

Question

大多数在线游戏任意组成团队.通常由用户决定,他们会选择带有空闲插槽的快速服务器.这种行为导致不公平的团队和人们愤怒退出.通过跟踪球员的静力学(或任何可以收集的静力学),你如何选择尽可能公平的球队？

Answer 1

现在比较着名的系统之一是微软的TrueSkill算法.

人们也试图让Elo系统适应团队配对,尽管它更适合1-v-1配对.

Answer 2

在我之前的回答之后,我意识到,如果你想要真正想要的话,你可以使用一个非常简单但有力的想法:Markov Chains.

使用马尔可夫链背后的直观想法是这样的:

1. 创建图G =(V,E)
2. 设V中的每个顶点代表一个实体
3. 设E中的每个边表示实体之间的转换概率.这意味着每个顶点的出度之和必须为1.
4. 在开始时(时间t = 0),为每个实体分配单位值1
5. 在每个时间步,通过3中定义的转移概率转换实体i,j.
6. 设t->无穷大,那么t =无穷大时每个实体的价值就是均衡(即向实体过渡的机会与从实体过渡的总机会相同.)

例如,这个想法已成功用于实现Google的页面排名算法.要描述如何使用它,请考虑以下事项:

1. V =玩家E =根据相对赢/输比率将玩家转变为玩家的概率
2. 每个玩家都是一个顶点.
3. 从玩家A到B的边缘(B不等于A)具有概率X/N,其中N是由A玩的游戏的总数,X是从B丢失的总游戏.从A到A添加边缘概率M/N,其中M是A赢得的游戏总数.
4. 在开始时为每个玩家分配技能等级1.
5. 使用幂方法找到由3中定义的概率构造的链接矩阵的主要特征向量.
6. 主导特征向量是每个玩家在t =无穷大时具有的技能量,即每个玩家在马尔可夫链达到平衡后具有的技能量.这是使用赢/输空间拓扑结构衡量每个玩家技能的非常有力的方法.

一些警告:直接应用这个有几个问题,最大的问题将是分离的网(这是你的马尔可夫链不会不可简化,所以权力方法将无法保证收敛.)幸运的是,谷歌已处理所有这些问题以及实现其页面排名算法时的更多问题以及所有剩余的问题就是如果你如此倾向于查找它们如何规避这些问题.