找回密码
 欢迎注册
查看: 12221|回复: 2

[提问] 淘汰赛设计问题

[复制链接]
发表于 2016-7-1 15:41:27 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
本帖最后由 BeerRabbit 于 2016-7-1 15:42 编辑

要举办一场象棋赛。假定每场比赛都只有胜负之分,没有平局;采用单败淘汰赛制,所以,对于给定的2^n个选手,可以有n轮比赛,第n轮即冠军争夺赛。
已知:每个选手对其他各个选手的经验胜率(这个数据通过对历史数据的统计得出,在数学处理上可以看做是本次大赛的严格胜率),比如用P(i,j)(i≠j)表示选手i对选手j的胜率。
问题:给出一个分组方案,使得各个选手的夺冠概率分布最合理。
补充:关于问题中的“胜率分布最合理”,可以有很多开放的衡量标准,比如:
(1)方差最小;
(2)熵最大;
(3)其他……

PS:如果使用穷举方法,从(2^n)!/2^(2^n-1)个分组方案中进行筛选,理论上是可行的,但是耗时有点吃不消……因此,需要一个优化方法,这个方法是什么?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-7-24 16:04:47 | 显示全部楼层
“已知:每个选手对其他各个选手的经验胜率”

这其实是一张$N\times N$的表格,记录了任意两位棋手对弈的胜负概率。

如果以这张表格作为此问题的输入数据,那么这是一个$NP$完全问题,

即不存在关于$N$的多项式时间复杂度的算法,对于任意的输入数据都能求出正确答案。

因此楼主不用煞费心机寻找又高效又能得出准确结果的算法了。

#####

实际上 ,并不是任意一张胜率表都是合理的。

每一位象棋、围棋等棋类选手,我们通常用一个数值来衡量他的“棋力”。

以围棋为例,这个数值称为"Elo"。围棋选手的世界排名就是根据"Elo"的大小进行排名的(参见 http://www.goratings.org 表格的最后一列)

每$400$点Elo就等于一个数量级,

即Elo为$3600$的选手与Elo为$3200$的选手对战,前者的胜率约为$90%$;

Elo为$3200$的选手与Elo为$2800$的选手对战,前者的胜率也是约为$90%$;

而Elo为$3600$的选手与Elo为$2800$的选手对战,前者的胜率约为$99%$。

有了Elo值作为度量,那么

知道了$A$大概率赢$B$以及$B$大概率赢$C$,就可以推出$A$会以更大概率赢$C$。

而如果$C$也大概率赢$A$就不合情理了。

也就是具有传递性的胜率表才是合理的。

#####

那么“合理的胜率分布”就应该是选手的夺冠概率与$10$的${Elo}/400$次方成正比。

为了达成这一分布,通常会把已知Elo很高的选手(种子选手)分在不同的分组,避免他们过早地撞上。

例如,一共有$16$名选手,他们的Elo都已知,从高到低排序后得到第$1$、第$2$、……、第$16$,那么合理的分组就是

{[(1,9),(5,13)],[(3,11),(7,15)]},{[(2,10),(6,14)],[(4,12),(8,16)]},

以确保各路高手能顺利晋级,避免过早被其他高手撞下去。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2016-7-24 16:16:53 | 显示全部楼层
为什么不是
{[(1,16),(8,9)],[(4,13),(5,12)]},{[(2,15),(7,10)],[(3,14),(6,11)]}

评分

参与人数 1贡献 +3 收起 理由
KeyTo9_Fans + 3 对哦,这样更好呢,强者被刷下去的概率更低.

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-28 20:02 , Processed in 0.056719 second(s), 17 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表