2

我正在为虚拟城市商业游戏 ( Urbien.com ) 开发锦标赛模型，并希望获得一些算法建议。这是场景和当前的“基本”实现：

设想

  • 参赛作品以决斗风格配对，就像在原始的 Facemash 或 Pixoto.com 上一样。
  • “玩家”是一名裁判，他得到一系列决斗对，并且必须为每一对选择一个获胜者。
  • 比赛永无止境，人们可以随时提交新的参赛作品，并根据该日期的数据选择日/周/月/千年的获胜者。

需要解决的问题

  • 评分算法 - 如何对锦标赛参赛作品进行评分以及如何在每场比赛后调整其评分？
  • 配对算法 - 如何选择下一对来喂玩家？

当前解决方案

  • 评分算法 - 目前在国际象棋和其他锦标赛中使用的 Elo 评分系统。
  • 配对算法——我们当前的算法承认两个必要条件：
    1. 对迄今为止决斗次数较少的条目给予更多的决斗
    2. 以更高的概率匹配具有相似评分的人

给定：
N = 锦标赛中的参赛
总数 D = 迄今为止所有玩家在锦标赛中进行的决斗总数
Dx = 玩家 x 到目前为止进行了多少决斗

为了选择玩家 x 和 y 进行决斗，我们首先选择玩家 x 的概率：

p(x) = (1 - (Dx / D)) / N

然后按照以下方式选择玩家 y： 按等级对玩家进行排序 让在排序列表中的索引 jIdx 处选择玩家 j 的概率为： p(j) = ... 0, if (j == x) n*r^ abs(jIdx - xIdx) 否则

其中 0 < r < 1 是要选择的系数，n 是归一化因子。

基本上，从 x 的任一方向的概率形成一个几何级数，归一化，因此它们总和为 1。

关注点

  • 最大化决斗的信息价值 - 将评分最低的条目与评分最高的条目配对不太可能为您提供任何有用的信息。
  • 速度——我们不想为了选择一对而进行大量的计算。一种替代方法是使用类似瑞士配对系统的系统，一次配对所有参赛作品，而不是一次选择一个新的决斗。这有一个缺点 (?)，即在给定时间范围内提交的所有参赛作品将经历大致相同数量的决斗，这可能是可取的，也可能不是可取的。
  • Equilibrium - Pixoto 的 ImageDuel 算法会检测条目何时不太可能进一步提高其评分，并从那时起减少他们的决斗。这种检测的好处是有争议的。一方面，如果你“暂停”一半的条目，你可以节省计算量。另一方面，具有既定评级的条目可能是新条目的完美匹配，以建立新手的评级。
  • 条目数 - 如果只有几个条目，比如 10 个，也许应该使用更简单的算法。
  • 赢/输 - 如果有的话，玩家的赢/输比如何影响下一次配对？
  • 存储 - 每个条目和锦标赛本身要存储什么？当前存储： 锦标赛条目：到目前为止 # 次决斗，# 胜，# 负，评级 锦标赛：到目前为止 # 次决斗，# 项
4

1 回答 1

4

您可以使用基于最大似然法的标准方法，而不是使用 ELO 和临时概率公式。

最大似然法是一种参数估计方法，它的工作原理是这样的（示例）。每个参赛者（玩家）都被分配了一个参数 s[i]（1 <= i <= N，其中 N 是参赛者的总数），用于衡量该玩家的力量或技能。您选择一个公式，将两个玩家的优势映射为第一个玩家获胜的概率。例如，

P(i, j) = 1/(1 + exp(s[j] - s[i]))

这是逻辑曲线（参见http://en.wikipedia.org/wiki/Sigmoid_function）。当您有一个显示用户之间实际结果的表格时，您可以使用全局优化（例如梯度下降）来找到那些使实际观察到的匹配结果的概率最大化的强度参数 s[1] .. s[N]。例如，如果您有三个参赛者并观察到两个结果：

  • 玩家 1 战胜了玩家 2
  • 玩家 2 战胜了玩家 3

然后你会找到最大化产品价值的参数 s[1], s[2], s[3]

 P(1, 2) * P(2, 3)

顺便说一句，最大化可能更容易

 log P(1, 2) + log P(2, 3)

请注意，如果您使用逻辑曲线之类的东西，那么只有强度参数的差异才重要，因此您需要将值锚定在某处，例如任意选择

 s[1] = 0

为了让最近的比赛“权重”更多，您可以根据他们的年龄调整比赛结果的重要性。如果 t 测量自匹配发生以来的时间（以某些时间单位），您可以最大化总和的值（使用示例）

 e^-t log P(1, 2) + e^-t' log P(2, 3)

其中 t 和 t' 是比赛 1-2 和 2-3 的年龄，因此最近发生的比赛权重更大。

这种方法的有趣之处在于，当强度参数有值时，可以立即使用 P(...) 公式来计算任何未来比赛的赢/输概率。要配对参赛者，您可以配对 P(...) 值接近 0.5 的参赛者，然后选择那些经过时间调整的比赛次数（e^-t1 + e^-t2 + ... ) 匹配年龄 t1, t2, ... 是低的。最好的办法是计算全球两名球员之间输赢的总影响，然后选择那些对收视率有最大预期影响的比赛，但这可能需要大量计算。

您不需要一直运行最大似然估计/全局优化算法；您可以将它作为批处理运行，例如每天运行一次，并使用第二天的结果将人们匹配在一起。无论如何，时间调整的匹配质量都可以实时更新。

在算法方面，您可以根据他们的 s 参数对最大似然运行后的球员进行排序，因此非常容易快速找到同等实力的球员。

于 2012-05-10T05:57:30.240 回答