邯郸论文组

#数学系炉石专业毕业论文# 第二章 最优打法

炉石传说2018-12-17 06:45:40

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




第二章 最优打法

玩游戏我们总会面临各种抉择,是上怪好还是解场好?是过牌好还是赌收割机好?是趴下好还是冲锋好?到底哪种抉择才是最好的?这就涉及到一个问题:是否存在最优打法?


有人经常斩钉截铁地说存在唯一的最优打法,我不知道他有没有仔细想过这个问题。我大概觉得这个问题的答案是存在最优打法但是不唯一,也可能不对,我先这么说着,下面慢慢证明,如果发现不对,我再回头过来改。而且我估计这个问题会是我的系列里最难说明的,除非我狠下心打算证明炉石的确就是个运气游戏,但是本篇并不涉及任何高深的数学问题,不会像上一篇一样那么难懂。


我没查过任何文献,不知道专业的或者业余的对此有过什么研究,但这是一个很有趣也很有意义的问题,我脚趾头想想肯定有人研究过,所以如有雷同,别算我学术不端。不过有的话也肯定写的比我的好百倍千倍,所以也必然不屑说我抄袭。


这里我们需要定义一下什么是最优打法,这就得看你玩游戏的目的是什么?是用牧师恶心死对面用战士疲劳死对面用盗贼爆对面的牌还是别的。这里我们只考虑你的游戏目的是获胜,赢!上传说、打12胜、拿冠军你都要赢,所以最优打法就是让你以最大概率获胜的打法。当然如果你看完这篇文章仔细想想,把最优打法换成爆对面最多的牌的打法时答案也是一样的。


由于涉及到概率,我们显然需要如下的假设:我们对游戏的伪随机数一无所知(假设一) 我想这个假设对99.999%的玩家都是成立的。接下来的证明是显然的,由于玩家的打法是有限的,这是因为游戏会在60回合内结束,而玩家资源又是有限的(注1 写完后想想这里有问题,我们下面再提),有限集当然可以取到上确界,但是又不一定是唯一的,证完了。


如果文章写到这里肯定会有无数的人喷我了,不让我答辩通过,那我得找个解决办法,多拿点东西糊弄糊弄大家,证明我花了大量的心血来写这些,我决定把最优打法找出来给大家看。


由于炉石这个游戏还是挺复杂的,我们一步步来实现算法。


1st,我们假设游戏中没有换牌过程,没有任何包含随机性的卡牌和英雄技能(说的就是你萨满),没有可以重洗牌库的牌,然后再假设玩家知道双方所有的手牌和牌库信息,也就是下张摸啥下下张摸啥都是知道的(这里的知道指的是a知道b的牌库信息 b知道a知道b的牌库信息,a知道b知道a知道b的牌库信息,以此类推……也就是说双方的牌库信息是公共知识,不同于共有知识。例如我直播打天梯,对手窥屏,那么他就知道我的手牌,我自然知道我的手牌,但是我不知道他知道我的手牌,他也不知道我知道不知道他知道我的手牌,于是我的手牌就是共有知识但不是公共知识。(这里只是普及一下逻辑学概念,有兴趣的可以去看看红蓝眼悖论)


为了寻找最优打法,我们只需要把所有情况列出来,a在第一回合可能有若干种选择,每种选择下b可以作出若干种选择,如果在某个回合一个选手有取胜打法时,我们不再考虑其他打法,因为这肯定是最优的打法,依次类推,最后得到一个树状图,树的末端部分是a获胜,部分是b获胜,如果我们倒推,如果a有可以不让b获胜的选择,那么a肯定去选让b获胜的打法,这就是简单的序贯博弈,下图就是一个例子,因为说的可能不清楚,希望可以帮助大家理解。



用蓝色标记的才是ab会选择的打法,也就是最优打法。在上面的例子中,用蓝色标记的连通的路径就是最后会出现的打法,显然最优打法并不唯一。


由于本人图论的学习只到高中数学竞赛的水平,很多用词方法都不好,请见谅。


注意,在这个游戏里,一旦牌库洗好,只要双方都足够聪明,那么胜负已定,但是能否做到足够聪明呢? 这就涉及到计算量的问题。比如围棋和国际象棋计算量就非常大,所以这两个游戏可以流传,因为至今都没有研究透。如果按照我前面的算法,那么我们的计算量也会很大,但是应该可以证明若干引理,证明一些打法明显不会更好,可以大大简化计算量(比如空过往往都不是好的选择), 所以这样的游戏肯定是不会流行的。


2nd,我们把炉石中的随机性考虑进来,仍然假设明牌,不会导致牌库重洗的牌,没有换牌过程。


现在的游戏过程将充满不确定性,当一个玩家打出25仔后局面将充满各种可能,那到底怎么样的打法才是最优的呢?其实跟1st中的做法是一样的,但是打出一张随机性牌后,当出现各种不同的节点(场景) 他们是以一定概率发生的,这里涉及到概率计算是建立在我们对伪随机不知情的假设之下,这些节点都是以一定概率发生的,用乘法原理就可以得到节点的分叉下的概率,再用1st中的方法,每个人肯定选择让自己以更高概率获胜的打法,当概率相同时,可以同为最优打法,这样我们最后又会得到最后的牌局过程。


3rd 现在我们把明牌的条件去掉,卡牌游戏几乎都不是明牌的,这个会使情况更复杂。而且炉石不同于扑克和麻将,后两者在游戏中出现的牌是固定的,所以高手都是可以算出来其他人手上有什么牌,使得看似暗牌实则明牌,而且扑克更是没有抓牌过程 手牌是固定的那些。


为了说明这个问题,我们引进贝叶斯统计里的一个概念:先验分布。也就是说你原先就有一个分布的假设,再根据得到的数据可以得到一个后验分布再来进行你的估计。举例说来,如果你在天梯遇到一个骑士,你可能认为这个骑士80%是佛祖骑,10%是鱼人骑,5%是中速骑,4%是神恩骑,1%是宇宙骑。当对面打出一张奥秘守护者时你才断定它是佛祖骑,然后它挂了一个奥秘,你会认为37.5%是挡刀,31.8%是复仇,18.6%是救赎,6.3%是争强好胜,5.7%是忏悔,0.1%是审判或者以眼还眼,这是先验分布。然后你变脸a了一下什么都没发生,那就不会是挡刀了,你就觉得62.4%是复仇,24.5%是救赎,7.2%是争强好胜,5.9%是忏悔,这就是后验分布。你对很多东西都有一个先验知识,对面手牌是怎样的分布、牌库里的牌是什么样的分布、传送门给的卡也有等等……对面出张牌进行一个操作,甚至是一个犹豫都会改变你的认知。然后有一个后验知识,它也是你下一个调整判断的先验知识,有了上面的假设或者说是基础,我们还需要假设对于对手的先验后验知识调整一无所知(假设二),那么3rd完全转化成2nd,只是确定的牌转化成了随机的牌,使用相同的方法就可以得到最优打法。


这里有个问题,也就是注1提到的问题,如果我再看下面的说明4你就会发现,由于时间是连续的,对方的操作已经不再是一个有限集,这个问题在真人上特别突出,所以我们必须假设(假设三)玩家的后验知识只与对面选择的打法有关,这个假设其实也是合理的,特别是计算机层面上,如果双方玩家足够理性和机智(这还得是公共知识),不考虑他们打牌需要的思考时间,那么必将不会被对手在几秒后打出牌,点了什么牌所迷惑。但是玩家并不一定足够聪明,即使如此这也不会是公共知识,所以我们下面进行的几点讨论说明是有意义的。


但是我们这里忽略了对于先验后验知识的进一步讨论,怎么样的先验后验知识才是更优的呢?首先,事先情报收集影响先验知识的质量。比如你比赛遇到你的好友就很容易知道他会带什么,因为他可能就会那么两个职业,但是遇到朝神就不知道他会带什么因为他什么都不会。而对于后验知识,我认为这是一个人炉石水平的重要组成部分,在不同的后验知识下最优打法可能截然不同,故而水平高的后验分布更接近真实分布,打法就更佳,表现出来胜率就更高。那是否存在最优的后验分布呢?我还没仔细想过这个问题,因为这会非常复杂,因为玩家可能通过较差的打法(这个说法有待商榷 只是为了说明下假设二的必要性)强行改变对手的后验知识,从而导致游戏进入一个完全不同的走向,反败为胜,这样最佳后验知识就变成一个笑话。


我们上面大部分是从计算机的角度来考虑,对于真实人为操作,我认为以下几点还需要说明:


1. 我们都知道换牌是影响后验知识的,例如当年术士最强时代流行的看对面换几张牌策略。 先看对面换牌,换的少的是动物园,换的多的是手牌术等等……对于这些常识其实是可以利用的,如我在比赛或者天梯玩手牌术时,一看手牌不错,立刻进行换牌,让对面误以为自己是动物园,导致对面有一个偏离更远的后验知识,这也是我引进假设二的重要原因。不然一个换牌过程就研究不清,充满尔虞我诈;


2. 严谨的说对于一张牌,起手留的和换上来的地位是不等的,刚摸的和在手上停了两回合的地位都是不等的,但是我不觉得有谁甚至在比赛时会去记录对手每一张手牌停留的回合数等等信息。对于自身来说,当你手上有两张一样的卡牌时,是用刚摸的还是滞留手上的,自带的还是衍生的,自己的还是盗取的,隐蔽的还是回收暴露的,都是值得思考的。因为这会导致对手不同的后验知识,而且我不觉得网上流传的打刚摸的那张有多佳;


3. 有时候你可以故意暴露手牌,好友对战时故意告诉对面我有130让对面只有三个格子,不停地用一张指向性的卡牌比划让对面防你的横扫埋葬虽然可能只是愤怒和缩小,这些都是会改变对手的后验知识的,这种故意暴露或者是无中生有有时候可以为你带来胜利;


4. 你的回合思考时间也是会改变对手后验分布的,正常而言打得快的说明手上抉择少,打的慢的可能可以花式解场或者有一定斩杀能力,所以在比赛时候故意烧绳或者故意打快也是有作用的;


5. 暂时想到这些,以后想到别的了我也是不会来补充的,留着当作看门心机,打比赛的我还是推荐多点心机,多发点表情干扰干扰对面。要斩杀了故意不打想想下局用什么顺便气气对面也是很不错的,毕竟我干过这种事情要给自己找借口,虽然代价是在贴吧被喷的******,如果只是打打天梯我想就算了,毕竟游戏只是玩玩而已吗。


6. 当我把这些发出去给大家看之后,我就更不会参加什么炉石比赛了,因为我的一些小花招变成了共有知识。经过我大量演算发现,这直接降低了我一大半的胜率,真是心疼我自己。


说了这么多最优打法,也说了怎么求,但是能不能求呢?答案肯定是不能。因为我们连输入过程都无法完成,对战过程千变万化,带的卡牌千奇百怪,要怎么才能把我们在各个不同的境地下的先验(后验)知识输入呢?不可能。甚至我们连自己都不知道自己假定的分布是什么,反而要从最终的打法去估计自己假定的分布,即使我们完成了输入过程也可能因为由于计算量太大而无法计算,毕竟一个回合的时间只有90s,所以当你写出最优打法的程序后可能计算机也只是一个每回合烧绳过的***(去贴吧看是啥)。


所以炉石的训练也是有必要的,你在玩一套卡组时你可以慢慢摸索出一种接近最优的打法,这也可以认为是最优打法的模拟求法,所以一个天天只玩防战的玩家一般来说比其他玩家更“精通”防战,即使他水平很菜。


看完上段的人肯定大呼上当,一个傻屌说了半天其实啥都没说。好吧,我想先举下面的例子,大概在2014年中段,一套脚本萨横扫天梯,固定的卡组,美服有人用这个脚本轻松上了传说,很不幸,我也输给过这个脚本,再提一句,是萨满,一个永远在崛起的职业,最终导致暴雪严打脚本,一堆账号被封停。


好了这个例子,我就底气十足了,因为我就是在讨论能不能写出一个能完成最优打法的脚本。 换言之,这个脚本比所有人水平都高都厉害,前面说了这是不能的,但是我们完全可以写出一个高水平的脚本,它的打法接近最优打法,要实现这个脚本有两种办法:一是简化我上面的求解过程,目的是降低计算量,例如不考虑对手手牌只顾场面,满费打牌等等;另一种是模仿高玩的打法,也就是上面说的最优打法的模拟求法。


所以,我们可以弄出一堆超高水平的脚本,然后……被暴雪封号。


于是 gtmd暴雪阉割了我的商机 。




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