#数学系炉石专业毕业论文# 第三章 博弈论与最优卡组

作为一款处处体现着随机性的游戏,关于《炉石传说》中概率与随机的讨论从未停止过,曾经在赛中大放异彩的清华大学数学系博士“朝神”@张昭君该昵称已经被占用 日前为我们带来了关于如何从数学角度看待《炉石传说》的文章,一起来看看吧!



第三章 博弈论与最优卡组


这章我们讨论最优卡组,如果你想一拉到底看眼卡组的,对不起,我们这文章应该不会讨论任何的单卡取舍或卡组构建,因此你是抱着抄卡组的目的请出门向左72.8度(此数字经过严格推算)拐弯去论坛看各位大神主播天梯牛人吹逼,所以这样的标题是唬人的,俗称标题党。


上次的二刚发出来,就有水友跟我说,是不是下一篇应该写最优卡组了,其实我想一笑置之的,因为在天梯中,任何卡组都应该是50的胜率,当然这个说法需要一大堆的条件,但是当我跟很多人说起这个结论时,大家都无法理解。好吧,那我就写这个好了,反正我也不知道写什么。


很多人看了上面一段,肯定想啪啪啪给我两耳光(不要问我为什么俩耳光有三声啪),这朝神你不是瞎jb扯淡吗,谁都知道咆哮德奥秘骑天梯虎的一逼,你自己瞎组的乱七八糟的卡组天天被直播吊打。


这真是个有趣的问题,我也一直在想,为什么咆哮德奥秘骑胜率会高呢,是错觉吗? 我问了很多高玩(音调别弄错),说并不是,这我就纳闷了,希望下面简单的数学可以解开你我心中的困惑。


我们先给出下面的定理:


定理1:假设游戏中每个人的卡牌收集齐全、技术水平一样、精通所有卡组、打天梯的目的是为了获胜,那么最终会出现在天梯里的卡组胜率都是50%。


这里有很多的假设,我们也可以不要所有的限制,得到的是下面的定理。


定理2:任何两个选手对局,假设他们的水平不发生变化,那么最终每位选手都会有固定的胜率。


定理1其实是定理2对称的版本,这里我们只讨论定理1,因为它更有实际意义,虽然有很多限制,我们可以认为这些假设是合理的。


这里最关键的假设是以获胜为目的,所以像我这种玩家是不记录在内的,所幸的是这样的玩家是少数的,至少在天梯顶端是少数的。


技术水平一样我觉得也是靠谱的假设,毕竟天梯匹配机制会将俩个水平相近的玩家放在一起, 但是因为连胜奖励的存在,天梯并不会有一个可以稳定的5成胜率的环境,水平差的人可以慢慢把等级升上去,导致稍微厉害的人胜率慢慢提高,直至传说。但是由于时间跨度只有一个月,所以我们可以忽略的认为,在每个等级几乎都是5成胜率的环境,当然传说最顶端的除外。总而言之,对于大部分人来说,技术水平一样这个假设是接近成立的。


然后卡牌收集齐全和精通所有卡组的假设,这个其实无所谓,只要每个卡组有足够多的人会玩就可以,我认为是不会影响的,这个我们可以稍后做解释。


关于这些假设,我们在最后会有进一步的讨论,这里就先说到这里。


关于这俩个定理的证明,我以前是会证的,但是学的多忘的多,我是去看书再证一遍呢还是就这样过去了呢,我认为就这样过去就可以了,毕竟我是说说而已的,大家肯定不会当真。有兴趣的可以找本对策论的书看下,前两章就有矩阵博弈有纳什均衡解(这个纳什不是罚球时候喜欢使用黏性物质但没被联盟警告的同志)的证明。直接套用结论就是:矩阵博弈一定存在混合纳什均衡,再由对称性立马得到天梯上所有卡组的胜率应该是50。so easy,妈妈再也不用担心你的学习,可见对称性真是件好东西。之前我们算精灵龙被奥弹打死的概率就用了对称性,初等概率论不及格的赶快再去读读我写的第一章,求求大家不要再来问我这个问题了。


很多人会问,什么是矩阵博弈?好吧,我也给不出定义,大概就是双方收益可以写在一个矩阵里,这东西还是举例比较形象,一目了然。最著名的囚徒困境就是一个这样的例子,大家经常在论坛看到的职业之间胜率表也是,因为默认双方胜率和为1,所以可以只写一个数字。 为了研究这个问题,我找网易炉石盒子要过数据,但是那些数据不太好用,那种表格可以看作盒子用户VS非盒子用户,所以双方水平是有偏差的,这在计量经济学里是个很正常的问题叫选择性偏差,有详细数据的话可以近似得到一个对称的,也就是我们说的双方水平相同的,我好像最近在论坛也看到了,不过我并没有问过他们是怎么做的。


但是研究而论,真实数据和我瞎编的数据没有区别,反而我瞎编的数据更有意义,为什么呢?例如当牧师对所有职业胜率都不超过50时,傻子才会去用牧师,因为没有傻子用牧师,只打牧师有优势的盗贼就变成只有蠢驴会去用,依次类推,你会发现有脑子的人只可能用德骑猎。没错,当然这里我们忽略每个职业有不同形态这点,只是为了帮助大家理解这个问题,把职业换成卡组就OK了,这可以解释为什么很多乱七八糟的卡组不会存在于天梯中,因为它并没有优势对局或者优势的对局也不出现在天梯中,在这种情况下,天梯中的混合纳什均衡只可能是部分卡组的一个混合。


然而问题又来了,现实中大部分的卡组(找30张组个不可能打死人的卡组应该有的,算上英雄技能,术士应该能做到)都有优势对局,我直播玩过的20橙德鲁伊依然能慢慢上分,可见也是有优势对局的,永远在崛起的萨满也有优势对局(我始终觉得打脸萨不能算萨满) ,于是我们用上面那种慢慢刨的方法不能去掉他们,所以混合纳什均衡里应该有他们吗? 也就是说这种卡组应该出现在天梯里吗? 你也许在有生之年里有幸在传说段位里见过萨满(打脸萨不是萨满) 但你可见过20橙德? 注意我们前提是以赢为目的的。


下面是我随手举的一个简单例子,用Excel写的程序,在这个例子成功后,我原本想做一个九职业的,但是由于计算精度的问题,并没有成功。这个问题在四职业时候我也遇到了,但是有幸被我找到一个好的目标函数给解决了,但是九职业的我尝试了好久我都没有成功,不过从计算机给我的答案中,我目测这个九职业最后可以简化到四职业最多五职业,也就是说大概有一半的职业不该出现在天梯里。



在我们的例子中,只有骑德战猎四个职业,最前面的矩阵是假定的互相对阵的胜率,我看心情写的,当然也做到了每个职业都有优劣势对抗,最后求得均衡下只有骑德猎三个职业,每个职业都是50的胜率,如果我数学不是那么太差的话,这结果的数字应该是七分之一的猎 七分之二的德和七分之四的骑,数字居然这么好真是没有想到。战士虽然打猎人是优势,但是战士在这个环境下只有不到37多点的胜率,所以不会有战士出没,心疼战士。至于其他的数据是我给均衡一个扰动之后的结果,大家可以看看,有兴趣也可以自己去试试 或许你会有比我更高深更准确的理解


这里需要说明几点 :


第一,我们说过均衡一定存在,但不一定只有一个,所以会达到哪个均衡得看起点在哪,大家经常看到的什么周报什么环境很可能是因为外界因素的冲击导致均衡改变了,从一个均衡到了另一个均衡,事实上如果存在多个均衡时,我们并不好预测均衡会在哪里,因为玩家的偏好、新卡组的出现都会对环境造成影响,更不用说版本的更迭了;


第二,全是同一套牌的环境是不是均衡呢? 可以是,前提是这套牌天下无敌,但是炉石出来这么久,历史上并没有哪套牌强势到天下无敌,冰法奇迹贼亡语猎奴隶战都不是,这个很好理解,只要一套牌有弱势对局比如傻屌骑,那么这个环境下,大家都纷纷去用傻屌骑 然后也许冰法出来了……


第三,为什么会达到均衡?这是个好问题,证明就不证了,我希望可以说的明白点让大家理解这个过程。还拿我们刚才那个例子来说,比如天梯全是傻屌骑,但是总会有几个异类玩别的,玩玩德打不过,玩玩战士打不过,玩玩猎人打……过了。卧槽,猎人在这个环境好上分啊,这个消息会渐渐被玩家观察到,于是傻屌骑越来越少,猎人越来越多。注意,总有异类在尝试小德和战士,当骑士和猎人达到一定比例,啥比例呢?就是小德在这个比例下胜率到了50,OK,小德也开始大面积出现了,那为什么还没有战士呢?因为小德比战士更早达到这个要求,于是天梯现在就有猎人骑士小德了,但是只要没有达到均衡,就是有职业胜率超过50 ,这个职业的数量就会增多,有职业胜率低于50 这个职业数量就会减少,战士也许会在某段时间挤入环境,但是很快环境的移动导致战士胜率较低,又被踢出了环境,最终环境就慢慢变成了我们前面计算的那个均衡。到了这个均衡之后大家会发现,无论用什么卡组都没有区别了,只要不是战士,这就跟市场价格一个道理,因为那也是一种均衡。


如果大家理解了上面那些,你们肯定会像我一样发出疑问,为什么某些卡组在天梯就比另一些强势呢?(你以为我们跟你一样蠢啊 我们早就知道是因为下面这些原因吧啦吧啦)


解释1 :信仰! 所谓信仰,就是刚入坑的时候合不起什么卡导致只能玩一俩个职业,或者刚入门啥卡组简单好学玩哪个。这就是为什么有这么多信仰动物园信仰德信仰法(很多人不好意思带上机械俩字怕丢脸) ,最近才开始玩炉石的肯定有一堆信仰骑。前面开个玩笑别当真,我不能暴露我一个黑子的本能,主播为了培养固定观众也信仰xx卡组,我也很好奇每天玩n个小时一套卡组是种什么体验。扯远了,总而言之,就像上面的例子,明知战士不行,但是仍会有一批玩家会坚持在天梯使用战士得到一个不到40的胜率(40只是因为例子而已) 。


事实上你要0.4533977(一元三次方程x3+2x-1=0的实根)的胜率才可以保持你的天梯等级,这个胜率往上到50可以达到5级,再往上就可以传说。这点在下面会有更详细的说明,但实际上真实胜率并没有显示的那么高,因为每个玩家从比自己水平低的得到一个较高的胜率,直到遇到和自己水平相当的才停止升级,从而导致大部分玩家在胜率统计上显示的是大于50%的,我觉得可以管这个叫胜率膨胀。


信仰玩家的存在导致了第二度的胜率膨胀。表面上看,战士玩家的存在便宜了小德和骑士,却坑了猎人玩家,但是同样的道理,这个比例会慢慢调整,战士这块蛋糕会被三个职业瓜分, 结果就是这三个职业都获得一个相同的高于50%的胜率,但是如果战士这块蛋糕太大,被战士坑的猎人很可能牙口不好,咬不到这块蛋糕(蛋糕还能咬不到?),可怜的猎人也被迫从天梯职业沦为信仰职业,呜呼哀哉,所以信仰猎都去找信仰战算账吧,我好看戏。其实上面这一点(姑且叫做猎人的悲剧)我并没有从数据上举例论证,但以我的聪明才智,是有可能不对的,欢迎严(chi)谨(bao)好(cheng)学(zhe)的读者看完后去验证下。


这下我们可以强行解释一波,咆哮德奥秘骑动物园这些专门吊打各路黑科技各路信仰的卡组在天梯果断可以吃香又喝辣去,留其他卡组吹冷空气。


解释2:信仰!其实还是信仰问题。我要拿难民卡组上传说,我要拿冰法鱼人骑打排名!只是举例,我认为冰法和死鱼骑作为很好的康特(我不是因为不会拼才打中文 只是因为爱国)。卡组应该是天梯卡组不是信仰卡组。 OK,的确有那么一些水平还凑合的玩家可以做到,但我们前面提到了胜率膨胀,这些卡组很可能本身很low,所以我看到论坛里月末一大堆吹自己什么卡组很厉害上传说的,大家懂的。由于胜率膨胀原因,假如天梯正常胜率应该是55的,很多信仰玩家发现自己的卡组可以打到53,很厉害啊,能上分啊,满足了,错误的低估了天梯正常胜率,导致天梯还没有达到均衡,但由于这种惰性以及信息不易观测和传达的缓慢,便宜了平衡移动最初的获利者,而这些获利者往往就是大家所说的毒瘤。


解释3:随机和心理。在我这个系列的第一篇文章里讲过随机性,但是其实我只是想给大家介绍伪随机,并没有概率和随机什么事,遗憾的是在大量的评论里(大部分都是实话实说夸我的)我发现大部分人并没有看懂,还在扯纯随机什么的,真尼玛心痛(可见写的太烂)。也许有生之年我会重写这一段,好,随机就是一半一半但也并不是一半一半。假如一个信仰萨,坚信萨满很厉害,运气好,打了一大波连胜,然后慢慢稳定的一个48胜率,你会发现这位玩家很容易觉得这套萨满表现很好,特别是他在这套牌80胜率的时候还去发了个帖子。 这种玩家进一步导致了胜率膨胀,而这种收益很可能又是毒瘤卡组最先品尝。


解释4 :人感知的不敏感和懒惰,这也是我瞎扯的一个解释。每位玩家在进行游戏时,都会有点感觉,胜率大约是多少、卡组里什么卡好用什么卡不好用,这一步解场好还是打脸好等等。但是人的这种感知是不太准确的,这也是为什么人类在棋牌游戏中往往不敌人工智能的原因之一。所以我们有理由相信玩家在天梯中的反应会比较迟钝,或者比如菜鸡朝这样的 明知道一套牌不好,或者需要修改,但是懒得切换页面重新去组牌,种种原因导致在天梯中卡组的调整不够及时,这就会使得天梯原先占便宜的卡组往往能够持续的占便宜,而那些卡组往往就是毒瘤。


解释5 :5你妹,再扯下去就没头了,其实是懒得再写下去了,大概总结一下,天梯存在很多导致胜率膨胀的因素,但是由于各种原因,导致均衡并不容易达到,尤其是信仰玩家的存在,使得一些诸如咆哮德和动物园的胜率偏高也就是那些均衡形成前胜率可能较高的卡组 或者说天梯环境的均衡压根没有形成 这才使得一些卡组占了便宜。


但是纵观历史,咆哮德在gvg时期有过低迷,动物园在鬼父出来之前也几乎被淘汰,以后咆哮德削弱了也并不会是咆哮德奥秘骑和动物园胜率偏高。根据我们之前的臆想,我大约觉得有这样的猜想:


猜想1 :打当前版本弱势职业优势较大的卡组往往会有一个偏高的胜率。


拿这个猜想去用历史数据检验往往更符合一些,让我们再回过头看看我们一开始提出的定理。


定理1: 假设游戏中每个人的卡牌收集齐全,技术水平一样,精通所有卡组,打天梯的目的是为了获胜,那么最终会出现在天梯里的卡组胜率都是50%。


既然定理的结果如果不成立,那么肯定是有定理的条件不成立 所以让我们再回过头审视我们的条件:


卡牌收集齐全:这肯定不成立,但是天梯稍微上面一些,甚至说活跃的玩家,大概都能组个至少一两套较为成熟的卡组,我们在说明均衡如何形成的过程中也可以看到,只要每个卡组有足够多的玩家,那么就OK了,所以这个条件显然不会是问题所在。


技术水平一样:这肯定也不成立,而且问题很大,关于这点,我也想的不是很明白,我们之前说过,如果一个人的天梯等级在5级以下,那么他的胜率应该就是0.4533977,这样才能保证他的等级稳定。实际上,由于20级0星输了不掉星,理论上还要比这个低点,等级越低偏差就越大,又由于5级开始没有连胜奖励,实际上在靠近5级的等级,会比刚才那个数稍微高点,然后5级开始你需要大于50的胜率才能涨星,所以照理说 在一个随机匹配的环境中,会有大量的玩家被滞留在5级附近,但是天梯的匹配规则会导致一些问题 相同等级的玩家进行匹配,既然是相同等级,大家水平一样,自然都应该是0.5的胜率啊。我们前面就是这么解释我们的假设的,怎么理解0.45多点的那个数字呢? 就是你倒霉,会跟一定比例的比你高水平的玩家相遇,等他们上去了,不再与你匹配了,你的胜率就会提高,然后等级上涨,然后重新遇到比你厉害的,胜率再次回到0.45,所以没错,如果天梯不是一个月结算一次,而是永久的,那么,所有的玩家除了最差的那些都能打到至少5级,然后只要坚持不懈的打下去,每个人都能上传说,这是因为随机游走的性质。


说了这么多只是想说明,天梯匹配机制可以很大程度上保证将水平相近的玩家放在一起,并不完全,如果高水平和低水平使用的卡组分布相同时,这个并没有关系,对称性可以抵消一些(因为不会完全对称), 但是卡组分布相同值得商榷,因为你去问问天梯高玩会发现他们都会自称咆哮德动物园专家,但是控场萨蓝龙贼专家越少之又少,凭我自己的感觉,如今的环境德骑术充斥着天梯顶端,但是在奴隶战最强的年代,天梯上奴隶战并不多见,但是这个原因具体会怎么影响天梯胜率,我很难给出定论。


精通所有卡组:这更不可能成立,毕竟没人敢说自己精通所有卡组,但是就像我们前面说的,这个条件只是为了确保天梯上每个卡组有足够多的人玩,而这应该是成立的。


目的是为了获胜:好吧,我承认我不是,我是为了好玩。作为职业选手应该是,但是普通的天梯玩家呢? 我认为也不是。虽然他们很想要上传说,如果去斗鱼看看直播你会发现,技术主播的观众远远没有娱乐主播多,当然这个证据也是有选择性偏差这个问题在,但我觉得很能说明问题。这个也能印证我前面的猜想,天梯上存在大量的信仰玩家娱乐玩家,这些不该有弱势职业可能成全了毒瘤卡组的高胜率。


虽然我们前面讨论的是天梯,比赛其实也差不多,我暂时还没有想过征服赛制会带来的一些问题。但是把卡组捆绑起来后那就肯定没问题,每个选手的期望胜率其实都是5成,当前还得是我们之前的那些假设。


如果你注意数据你会发现,其实比赛中也好天梯中也好,每个职业的胜率其实都相差不会太厉害,起码都在4成和6成之间。


这篇文章就这样写到这吧,其实我自己也觉得写的不是很清楚,还请大家见谅,毕竟我这么笨,但是我好歹长得丑啊。陆陆续续前后写了有两个月,很多我觉得很好的想法没及时写下来,也算是一种遗憾吧,上面很多东西并没有数学上的理论基础,只是我的YY,何况并没有好的数据来供我研究,这为我的懒惰也提供了无可反驳的理由。所以前面的观点有对有错 也欢迎有想法的朋友提出来讨论讨论,对于那些久等的朋友们,说声抱歉,还会不会有四,应该会有的,但是不知道猴年马月了。不对,好像猴年马月是今年的某一月,那就不知道马年猴月吧。



点此阅读“第一章 概率与随机

点此阅读“第二章 最优打法