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参数对最大似然跑完后的选手进行排序，所以很容易快速找到实力相当的选手。