基于MCMC方法的中国象棋等级分系统模型分析 梁久阳学号：5130309025班级：F1324001邮箱：liangjiuyang@sjtu.edu.cn 谭明 学号：5132409001班级：F1324001邮箱：tanming@sjtu.edu.cn 2014-6-19 Abstract 中国象棋等级分制度是我们判断一名职业象棋大师水平的重要依据。本文使用MCMC方法 模拟中国象棋大师赛的比赛结果，进而对各象棋职业选手等级分变化以及年终排名做出合理 的估计。 关键词：等级分系统随机模拟MCMC 1问题背景 1.1中国象棋 中国象棋(Chinese Chess)在中国有着悠久的历史，属于二人对抗性游戏的一种。由于用 具简单，趣味性强，成为流行极为广泛的棋艺活动。是我国正式开展的78个体育项目之一。在 中国古代，象棋被列为士大夫们的修身之艺，现在则被视为怡神益智的一种有益的活动。在棋 战中，人们可以从攻与防、虚与实、整体与局部等复杂关系的变化中悟出某种哲理。象棋是中 华民族的传统文化，不仅在国内深受群众喜爱，而且流传国外。 同篮球、足球一样，象棋同样属于一项体育运动，棋手亦按技术水平划分等级。棋手等级 标准，是根据比赛名次来确定，不像田径运动那样，规定跑多少秒，跳多少米，更具客观性。 因为一次比赛的成绩难免有某种误差。所以棋手等级属于粗线条的分类，而且同等级的各项幅 差相当大，例如中国男子个人赛第二名与第十六名都是大师.显然两名之间的棋艺水平有一定 的差距.即使对于同一个大师，在各次比赛中名次有升降，但棋手等级称号反映不出来。因此， 需要换取一种方法，能够细致地、动态地用数值反映一名棋手当前的棋艺水平，这就是棋手等 级分制度，是由美国埃洛教授创立的。它得到了世界国际象棋联合会的确认，70年代起采用埃 洛理论计算国际比赛中的棋手等级分，取得了良好效果。 1.2中国实行等级分制度的简记 假定某棋手在一局比赛前的等级分为R,按照埃洛理论预测次局得分为We,而比赛结束时 实际得分为W,则此棋手赛后等级分R按下式计算： R1=Ro +K(W-We) 其中放大倍数K为正值，W查表可得，详见下文。从上式得知：当实得局分高手预测局分时， 既棋手下得比较好，则等级分上升。当实得局分等于预测局分时，棋手发挥正常，等级分不变。 当实得局分低于预测局分时，棋手下得不好，等级分下降.原本无等级分的男棋手，第一次参 加全国比赛时，先给与等级分最低值R0=1500,等级分一经达到2400的棋手，以后即使再降， 1
ƒuMCMCê{•Iñ⁄ ?©X⁄ .©¤ ˘» Æ“µ5130309025 Å?µF1324001 eáµliangjiuyang@sjtu.edu.cn ² Æ“µ5132409001 Å?µF1324001 eáµtanming@sjtu.edu.cn 2014-6-19 Abstract •Iñ⁄ ?©õ›¥·Ç‰ò¶Öíñ⁄åìY²áù‚" ©¶^MCMCê{ [•Iñ⁄åìm'm(Jß? Èàñ⁄Öí¿Ã ?©Cz±9c™¸¶â—‹n O" 'Öcµ ?©X⁄ ëÅ [ MCMC 1 ØKµ 1.1 •Iñ⁄ •Iñ⁄£Chinese Chess§3•IkXa»{§ß·u<È|5iZò´"du^ ‰{¸ßõ5rߧè614è2ç⁄²¹ƒ"¥·I™m–78áNòë8Éò"3 •Iìßñ⁄è¨åÅÇ? ɲßy3K¿è¶ Ãúò´kùƒ"3⁄ ‘•ß<Çå±lÙÜì!JÜ¢!Nܤ‹ E,'XCz•×—,´Ûn"ñ⁄¥ • u¨xD⁄©zßÿ=3IS …+ØUOß Ö6DI " ”;•!v•òßñ⁄”·uòëNò$ƒß⁄ýUE‚Y²y© ?"⁄à ? IOߥä‚'m¶g5(½ßÿîXª$ƒ@ß5½ı¶ßaıíßç‰ê*5" œ èòg'm§1Jùk,´ÿ "§±⁄à ?·uoÇ^©aß Ö” ?àëà Éåß~X•IIfá<m1¶Ü1õ8¶—¥åì©w,¸¶Ém ⁄²Y²kò ½ ©=¶Èu”òáåìß3àg'm•¶gk,¸ß⁄à ?°“áNÿ—5"œdß IáÜò´ê{ßU [ó/!ƒ/^ÍäáNò¶⁄Ãc⁄²Y²ß˘“ ¥⁄à ?©õ›ß¥d{ID‚«M·"ß .ISñ⁄È‹¨(@ß70cìÂÊ^D ‚nÿOéIS'm•⁄à ?©ß ˚–J" 1.2 •I¢1 ?©õ›{P b½,⁄Ã3ò¤'mc ?©èR0ßUÏD‚nÿ˝ˇg¤©èWeß 'm(Âû ¢S©èW,Kd⁄Ãm ?©R1Ue™Oéµ R1 = R0 + K(W − We) Ÿ•òåÍKèäßWeLåßçÑe©"l˛™µ¢¤©pÃ˝ˇ¤©ûß Q⁄Ãe'–ßK ?©˛,"¢¤© u˝ˇ¤©ûß⁄Ãuû~ß ?©ÿC" ¢¤ ©$u˝ˇ¤©ûß⁄Ãeÿ–ß ?©e¸© à ?©I⁄Ãß1ògÎ \ I'mûßkâÜ ?©Å$äR0 = 1500ß ?©ò²à2400⁄Ãß±=¶2¸ß 1
也永远确定K=10。关于W值的确定，与对局双方等级分之差值D有关，若赛前双方等级分 相等时，即双方棋力相等，预测结果和棋，各得半分。 D=0.We=0.5 当甲方等级分高于乙方200时，根据统计表明，甲方胜率为四分之三，乙方胜率为四分之一，故 得到如下关系： D=200,We=0.75 D=-200.We=0.25 实用上，如从曲线上对应D查找到We的近似值，用数据表显示出来，如下图表Table?,这样， 我们就可以根据D查找到We,再计算出等级分值。 Table1:We的数据表 D We D We W。 H L H L HL 0-3 0.500.50122-1290.670.33279-2900.840.16 4-10 0.510.49130-1370.680.32291-302 0.850.15 11-17 0.520.48 138-1450.690.31 303-315 0.860.14 18-25 0.530.47146-1530.700.30316-3280.870.13 26-32 0.540.46154-1620.710.29329-3440.880.12 33-39 0.55 0.45 163-170 0.720.28345-357 0.89 0.11 40-460.560.44 171-1790.730.27358-3740.900.10 47-53 0.570.43 180-1880.740.26375-3910.910.09 54-61 0.580.42189-1970.750.25392-4110.920.08 62-68 0.59 0.41 198-2060.76 0.24 412-432 0.93 0.07 69-76 0.600.40207-2150.770.23433-4560.940.06 77-83 0.610.39216-2250.780.22 457-4840.950.05 84-91 0.620.38 226-2350.790.21485-571 0.960.04 92-980.630.37 236-2450.800.20518-5590.970.03 99-1060.640.36246-2560.810.19560-6190.980.02 107-1130.650.35257-2670.820.18620-7340.990.01 114-1210.660.34 268-2780.830.17 >734 1.000.00 注1.数据表的H表示高分棋手的预测局分，L表示低分棋手的预测局分，二者相差D=高分棋手 的等级分-低分棋手的等级分。 K的算法是： 如高分棋手胜低分棋手，将根据高分棋手的等级分。 如低分棋手胜或和高分棋手，将根据低分棋手的等级分。 值计算方法如下Table??, 2
è[(½K = 10" 'uWeä(½ßÜȤVê ?©É äDk'ßemcVê ?© É ûß=Vê⁄ÂÉ ß˝ˇ(J⁄⁄ßàå©" D = 0, We = 0.5 `ê ?©puØê200ûßä‚⁄OL²ß`êë«èo©ÉnßØêë«èo©Éòß Xe'Xµ D = 200, We = 0.75 D = −200, We = 0.25 ¢^˛ßXlDzÈADÈWeCqäß^Í‚Lw´—5ßXe„LTable ??ß˘ß ·Ç“å±ä‚DÈWeß2Oé— ?©ä" Table 1: WeÍ‚L D We D We D We H L H L H L 0-3 0.50 0.50 122-129 0.67 0.33 279-290 0.84 0.16 4-10 0.51 0.49 130-137 0.68 0.32 291-302 0.85 0.15 11-17 0.52 0.48 138-145 0.69 0.31 303-315 0.86 0.14 18-25 0.53 0.47 146-153 0.70 0.30 316-328 0.87 0.13 26-32 0.54 0.46 154-162 0.71 0.29 329-344 0.88 0.12 33-39 0.55 0.45 163-170 0.72 0.28 345-357 0.89 0.11 40-46 0.56 0.44 171-179 0.73 0.27 358-374 0.90 0.10 47-53 0.57 0.43 180-188 0.74 0.26 375-391 0.91 0.09 54-61 0.58 0.42 189-197 0.75 0.25 392-411 0.92 0.08 62-68 0.59 0.41 198-206 0.76 0.24 412-432 0.93 0.07 69-76 0.60 0.40 207-215 0.77 0.23 433-456 0.94 0.06 77-83 0.61 0.39 216-225 0.78 0.22 457-484 0.95 0.05 84-91 0.62 0.38 226-235 0.79 0.21 485-571 0.96 0.04 92-98 0.63 0.37 236-245 0.80 0.20 518-559 0.97 0.03 99-106 0.64 0.36 246-256 0.81 0.19 560-619 0.98 0.02 107-113 0.65 0.35 257-267 0.82 0.18 620-734 0.99 0.01 114-121 0.66 0.34 268-278 0.83 0.17 >734 1.00 0.00 5 1. Í‚L H L´p©⁄Ã˝ˇ¤©, L L´$©⁄Ã˝ˇ¤©ßˆÉ D=p©⁄à ?©-$©⁄à ?©" Ké{¥µ Xp©⁄Ãë$©⁄ÃßÚä‚p©⁄à ?©" X$©⁄Ãë½⁄p©⁄ÃßÚä‚$©⁄à ?©" KäOéê{XeTable ??ß 2
Table2:K值计算方法 棋手等级分 K <1500 55 1500-1799 40 1800-2099 25 ≥2100 10 2MCMC算法 2.1 Metropolis-Hastings算法 Metropolis-Hastings算法是一种非常通用的构造马氏链的方法。这个方法从t=0开始， 取Xo)=xo),其中xo)是从某个初始分布g中随机抽取的样本使得满足f(xo)>0。给 定X因=x),下面的算法用于产生X+1)。 1.由某提案密度g(z(o)产生一个候选值X*。 2.计算Metropolis-Hastings比率R(z(),X*),其中 R(u,v）= f(v)g(ulv) f(u)g(ulv) 注意(x(),X*)总是有定义的，因为只有f(x)>0且g(x*x()>0时才有 X米=x米 3.根据下式抽取X(+1): X(t+1) X*,以概率minR(x(),X*)=1 x),否则 4.增加t,返回第1步。 我们将第步迭代称作产生X()=x()的过程。 通过Metropolis-Hastings算法构造得到的链满足马氏性，因为X(t+i)仅依赖于Xe)。而是否是非 周期不可约的则取决于提案分布的选取，需要自己去检验是否满足这些条件。如果满足了，那 么这样生成的链具有唯一的极限平稳分布。 3基于MCMC算法的中国象棋等级分系统的变化模拟 作为中国最高级别的象棋组织，中国象棋协会每年都会进行一次等级分评定，由此来确定 本年度象棋职业选手的年终排名，为下一年各中国象棋甲级联赛参赛队选拔队员提供最富权威 性的数据参考。而在所有比赛结束之前，人们往往对预测年终前四名的人选和他们的排序乐此 不疲。我们要做的，便是利用算法更加准确的估计本年度中国象棋届的“BIG4”。 作为本年度的压轴大戏，中国象棋大师赛将邀请截止到赛前全国等级分前8的选手参加比 赛，这次比赛结束后，每名选手最终的年终排名便会出炉。对于即时排名前四的选手而言，这 3
Table 2: KäOéê{ ⁄à ?© K < 1500 55 1500 − 1799 40 1800 − 2099 25 > 2100 10 2 MCMCé{ 2.1 Metropolis-Hastings é{ Metropolis-Hastings é{¥ò´ö~œ^EͺÛê{"˘áê{lt = 0m©ß X(0) = x (0)ߟ•x (0)¥l,á–©©Ÿg•ëŃ ¶˜v f(x (0)) > 0" â ½X(t) = x (t)ße°é{^u)X(t+1)" 1. d,JYó›g(·|x (0)))òáˇ¿äX>" 2. OéMetropolis-Hastings'«R(x (t) , X>)ߟ• R(u, v) = f(v)g(u|v) f(u)g(u|v) 5øR(x (t) , X>)o¥k½¬ßœèêkf(x (t) ) > 0Ög(x >|x (t) ) > 0û‚k X> = x > 3. ä‚e™ƒX(t+1)µ X(t+1) = ( X> ß±V«min R(x (t) , X>) = 1 x (t) ߃K 4. O\tßà£11⁄" ·ÇÚ1t⁄Sì°ä)X(t) = x (t)Lß" œLMetropolis-Hastingsé{EÛ˜vͺ5ßœèX(t+1)=ù6uX(t)" ¥ƒ¥ö ±œÿåK˚uJY©Ÿ¿ßIágCu¥ƒ˜v ˘ ^á"XJ˜v ß@ o˘)§Û‰kçò4Ų©Ÿ" 3 ƒuMCMCé{•Iñ⁄ ?©X⁄Cz [ äè•IÅp?Oñ⁄|Ñß•Iñ⁄¨zc—¨?1òg ?©µ½ßdd5(½ c›ñ⁄Öí¿Ãc™¸¶ßèeòcà•Iñ⁄`?ÈmÎmË¿oË J¯ÅL% 5 Í‚Î" 3§k'm(ÂÉcß<Ç È˝ˇc™co¶<¿⁄¶Ç¸SWd ÿò"·ÇáâßB¥|^é{ç\O(O c›•Iñ⁄3/BIG 40" äè c›ÿ¶åZß•Iñ⁄åìmÚû émc I ?©c8¿ÃÎ\' mߢg'm(Âßz¶¿ÃÅ™c™¸¶B¨—¨"Èu=û¸¶co¿Ã Ûߢ 3
次比赛是一次很好的抢占榜首的机会：对于排名在四到八名的选手而言，这次比赛是他们最好 也是最后的抢分机会，能否挤进前四在此一搏。因此，这场比赛每年都会聚焦起全中国象棋爱 好者们的目光。 3.1比赛规则 比赛共有八名选手参加，采用单败淘汰制，根据抽签决定比赛顺序。具体的抽签方法为： 第一轮由所有人打乱顺序随机抽取自己的对手，共4场比赛；第二轮由第一场比赛的胜者对第四 场比赛的胜者，第二场比赛的胜者对第三场比赛的胜者，共两场比赛：第三轮决出最后的冠军。 比赛共进行三站，每站都会进行三轮比赛直至决出一个冠军。每名选手获得的等级分由上文中 给出的公式进行计算后得出。 3.2选手数据 上一年度，进入年终总决赛的共有王天一、许银川、赵鑫鑫、汪洋、谢靖、孙勇征、郑惟 桐、洪智等8位棋手。比赛前，各位选手的即时等级分如下Tble?: Table3:2014年上半年中国象棋男子棋手等级分排行榜(8人) 序号 姓名 单位 称号 等级分 1 王天一 北京 特 2665 2许银川 广东 特 2663 3赵鑫鑫 浙江 特 2634 4汪洋 湖北 特 2630 5谢靖 上海 特 2618 6孙勇征 上海 特 2597 7郑惟桐 四川 大 2589 8洪智 湖北 特 2588 经过我们对这八名选手之前互相比赛结果的分析，得到了他们互相之间比赛的平均胜率如 FTable ??Table ??Table ??Table ??Table ??Table ??Table ??Table ?? Table4:王天一PK其他7人情况 对手姓名 总PK 胜率 胜局 和局 负局 许银川 15 33.3% 0 10 5 赵鑫鑫 16 53.1% 3 11 2 汪洋 16 65.6% 6 3 谢靖 18 61.1% 5 12 1 孙勇征 23 67.4% 10 11 2 郑惟桐 17 55.9% 5 9 3 洪智 25 58.0% > 15 3 4
g 'm¥ògÈ–s”íƒÅ¨¶Èu¸¶3ol¶¿Ã Ûߢg'm¥¶ÇÅ– è¥Ås©Å¨ßUƒ@?co3dò»"œdߢ|'mzc—¨‡Â •Iñ⁄ O –ˆÇ81" 3.1 'm5K 'mkl¶¿ÃÎ\ßÊ^¸}=õß䂃\˚½'m^S"‰Nƒ\ê{èµ 1ò”d§k<ãœ^SëŃgCÈÃß4|'m¶1”d1ò|'mëˆÈ1o |'mëˆß1|'mëˆÈ1n|'mëˆß¸|'m¶1n”˚—Å)" 'm?1n’ßz’—¨?1n”'mÜñ˚—òá)"z¶¿Ãº ?©d ˛©• â—˙™?1Oé—" 3.2 ¿ÃÍ‚ ˛òc›ß?\c™o˚mk Uò!N’A!Îcc!! ½!ö]!xé –!ˆú 8†⁄Ã"'mcßà†¿Ã=û ?©XeTable ??µ Table 3: 2014c˛åc•Iñ⁄If⁄à ?©¸1í£8<§ S“ 6¶ ¸† °“ ?© 1 Uò Æ A 2665 2 N’A 2¿ A 2663 3 Îcc ˙Ù A 2634 4 A 2630 5 ½ ˛° A 2618 6 ö] ˛° A 2597 7 xé– oA å 2589 8 ˆú A 2588 ²L·ÇÈ˘l¶¿ÃÉcpÉ'm(J©¤ß ¶ÇpÉÉm'm²˛ë«X eTable ??ßTable ??ßTable ??ßTable ??ß Table ??ßTable ??ßTable ??ßTable ??µ Table 4: UòPKŸ¶7<ú¹ ÈÃ6¶ oPK ë« ë¤ ⁄¤ K¤ N’A 15 33.3% 0 10 5 Îcc 16 53.1% 3 11 2 16 65.6% 8 5 3 ½ 18 61.1% 5 12 1 ö] 23 67.4% 10 11 2 xé– 17 55.9% 5 9 3 ˆú 25 58.0% 7 15 3 4
Table5:许银川PK其他7人情况 对手姓名 总PK 胜率 胜局 和局 负局 王天一 15 66.7% 10 0 赵鑫鑫 36 54.2% 7 25 4 汪洋 28 60.7% P 18 2 谢靖 15 63.3% 4 11 0 孙勇征 29 55.2% 6 20 3 郑惟桐 10 65.0% 3 7 0 洪智 55 58.2% 18 28 9 Table6:赵鑫鑫PK其他7人情况 对手姓名 总PK 胜率 胜局 和局 负局 王天一 16 46.9% 3 11 3 许银川 36 45.8% 4 25 7 汪洋 32 48.4% 5 21 6 谢靖 22 59.1% 6 14 2 孙勇征 26 44.2% 3 17 6 郑惟桐 P 68.8% x 1 洪智 36 50% 8 20 8 Table7:汪洋PK其他7人情况 对手姓名 总PK 胜率 胜局 和局 负局 王天一 16 34.4% 3 5 8 许银川 28 39.3% 2 18 8 赵鑫鑫 25 51.6% 6 21 5 谢靖 25 50.0% 5 15 5 孙勇征 22 54.5% 4 16 2 郑惟桐 9 50.0% 2 5 2 洪智 21 54.8% 6 11 4 Table8:谢靖PK其他7人情况 对手姓名 总PK 胜率 胜局 和局 负局 王天一 18 38.9% 12 5 许银川 15 36.7% 0 11 4 赵鑫鑫 22 40.9% 2 14 6 汪洋 25 50.0% 5 15 5 孙勇征 14 42.9% 3 6 5 郑惟桐 5 50.0% 0 5 0 洪智 18 52.8% 3 13 2 5
Table 5: N’APKŸ¶7<ú¹ ÈÃ6¶ oPK ë« ë¤ ⁄¤ K¤ Uò 15 66.7% 5 10 0 Îcc 36 54.2% 7 25 4 28 60.7% 8 18 2 ½ 15 63.3% 4 11 0 ö] 29 55.2% 6 20 3 xé– 10 65.0% 3 7 0 ˆú 55 58.2% 18 28 9 Table 6: ÎccPKŸ¶7<ú¹ ÈÃ6¶ oPK ë« ë¤ ⁄¤ K¤ Uò 16 46.9% 2 11 3 N’A 36 45.8% 4 25 7 32 48.4% 5 21 6 ½ 22 59.1% 6 14 2 ö] 26 44.2% 3 17 6 xé– 8 68.8% 4 3 1 ˆú 36 50% 8 20 8 Table 7: PKŸ¶7<ú¹ ÈÃ6¶ oPK ë« ë¤ ⁄¤ K¤ Uò 16 34.4% 3 5 8 N’A 28 39.3% 2 18 8 Îcc 25 51.6% 6 21 5 ½ 25 50.0% 5 15 5 ö] 22 54.5% 4 16 2 xé– 9 50.0% 2 5 2 ˆú 21 54.8% 6 11 4 Table 8: ½PKŸ¶7<ú¹ ÈÃ6¶ oPK ë« ë¤ ⁄¤ K¤ Uò 18 38.9% 1 12 5 N’A 15 36.7% 0 11 4 Îcc 22 40.9% 2 14 6 25 50.0% 5 15 5 ö] 14 42.9% 3 6 5 xé– 5 50.0% 0 5 0 ˆú 18 52.8% 3 13 2 5