algorithm - 开放式锦标赛配对算法

Question

我正在为虚拟城市商业游戏 ( 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，如果(j==x) n*r^abs(jIdx - xIdx) 否则

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

基本上，x 的任一方向上的概率形成一个几何级数，经过标准化后，它们的总和为 1。

担忧

• 最大限度地提高决斗的信息值(value) - 将评分最低的条目与评分最高的条目配对不太可能为您提供任何有用的信息。
• 速度 - 我们不想仅仅为了选择一对而进行大量计算。一种替代方法是使用瑞士配对系统之类的系统，将所有条目一次配对，而不是一次选择一个新的决斗。这有一个缺点(？)，即在给定时间范围内提交的所有参赛作品将经历大致相同数量的决斗，这可能是理想的，也可能是不理想的。
• Equilibrium - Pixoto 的 ImageDuel 算法会检测条目何时不太可能进一步提高其评级，并从此减少对决。这种检测的好处是有争议的。一方面，如果“暂停”一半的条目，则可以节省计算量。另一方面，已建立评级的条目可能与新条目完美匹配，从而建立新手的评级。
• 条目数 - 如果只有几个条目，例如 10 个，也许应该使用更简单的算法。
• 胜利/失败 - 玩家的胜利/失败比率如何影响下一个配对(如果有的话)？
• 存储 - 存储每个条目和锦标赛本身的哪些内容？当前存储: 锦标赛报名:到目前为止 # 场决斗，# 胜，# 负，评分 锦标赛:目前已进行 # 场决斗，# 名参赛者

Answer 1

您可以使用基于最大似然法的标准方法，而不是使用 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

然后你找到使产品值(value)最大化的参数 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(...) 公式来计算任何 future 比赛的输赢概率。为了配对参赛者，您可以对 P(...) 值接近 0.5 的参赛者进行配对，然后优先选择那些耗时调整的比赛次数(e^-t1 + e^-t2 + ... 之和)的参赛者。 ) 对于比赛年龄 t1, t2, ... 较低。 最好的事情是计算全局两名玩家之间的胜利或失败的总影响，然后选择那些对收视率具有最大预期影响的比赛，但是可能需要大量计算。

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

在算法方面，您可以根据玩家的s参数对最大似然运行后的玩家进行排序，因此很容易快速找到实力相当的玩家。