我正在为一个虚拟城市商业游戏(Urbien.com)开发一个锦标赛模型,希望能得到一些算法建议以下是场景和当前的“基本”实现:
脚本
条目是成对的决斗风格,比如在原始facemash或pixoto.com上。
“玩家”是一个法官,他得到一个决斗对流,必须为每对选择一个赢家。
锦标赛永不结束,人们可以随时提交新的参赛作品,并根据当天的数据选择当天/周/月/千年的获奖者。
需要解决的问题
评分算法-如何评分参赛者和如何调整他们的评分后,每场比赛?
配对算法-如何选择下一对来喂球员?
当前解决方案
评分算法-目前在国际象棋和其他比赛中使用的ELO评分系统。
配对算法-我们当前的算法识别两个必要条件:
对目前为止决斗次数较少的条目进行更多决斗
以更高的概率匹配具有相似评级的人
鉴于:
N=参赛总人数
D=到目前为止所有玩家在比赛中的决斗总数
到目前为止X玩家有多少次决斗
要选择玩家x和y进行决斗,我们首先选择具有概率的玩家x:
p(x)=(1-(Dx/D))/N
然后按以下方式选择玩家y:
按等级对玩家进行排序
在排序列表中的索引jIdx处选择播放器j的概率为:
p(j)=…
0,如果(j==x)
n*r^abs(jidx-xidx)否则
其中0基本上,从x到任意方向的概率形成了一个几何级数,标准化后它们相加为1。
关注
将决斗的信息价值最大化——将最低评级的条目与最高评级条目配对,不太可能给你提供任何有用的信息。
速度-我们不想做大量的计算只是为了选择一对另一种选择是使用类似瑞士配对系统的东西,一次配对所有条目,而不是一次选择一个新的决斗。这有缺点(?)在给定的时间范围内提交的所有参赛作品将经历大致相同的决斗,这可能是可取的,也可能是不可取的。
均衡-Pixoto的ImageDuel算法检测条目何时不太可能进一步提高它们的评分,并从那时起减少它们的决斗。这种检测的好处值得商榷。一方面,如果您“暂停”了一半的条目,则可以节省计算时间。另一方面,有固定收视率的条目可能是新条目的完美匹配,以建立新条目的收视率。
条目数-如果只有几个条目数,比如10个,也许应该使用更简单的算法。
输赢-玩家的输赢率如何影响下一对,如果有的话?
存储-如何存储每个条目和锦标赛本身?当前存储:
参赛项目:决斗到目前为止,胜负,评分
比赛:到目前为止的决斗,参赛者

最佳答案

而不是投掷ELO和特设概率公式,你可以使用基于最大似然法的标准方法。
最大似然法是一种参数估计方法,它的工作原理是这样的(例)。每个参赛者(选手)都被分配一个参数s[i](1

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

这是logistic曲线(见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的选手,然后选择那些比赛年龄为t1,t2,…,时间调整的比赛次数(e^-t1+e^-t2+…)的选手很低。最好的办法是计算出全球两名球员之间的胜负的总影响,然后选择那些对收视率有最大预期影响的比赛,但这可能需要大量的计算。
你不需要一直运行最大似然估计/全局优化算法,你可以每天运行一次,作为批处理运行,并使用第二天的结果来匹配人们。时间调整后的匹配质量可以实时更新。
在算法方面,你可以根据他们的S参数对最大似然进行排序,所以很容易找到相等的力量球员。

关于algorithm - 开放式锦标赛配对算法,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/10513029/

10-16 07:11