玩不够的数学2:当数学遇上游戏
上QQ阅读APP看书,第一时间看更新

海量计算

无论是利用数学还是计算机分析一个游戏都是繁重的工作。最近,许多研究扑克游戏的团队为了获得进展而引入了关键的新方法,尤其是一种可以计算不同游戏规则下最优策略的方法,它成形至今还不到十年。

这个方法叫CFR算法,CFR是Counterfactual Regret Minimization的缩写,意为“反事实遗憾最小化”。它的主要想法是让程序与自身对局,然后根据模拟对局的胜负改变在每个决策点进行不同选择的概率。自2007年被引入之后,这种算法开始研究决策点越来越多的游戏。在2012年,人们终于能处理拥有3.8×1010种局面的简化扑克游戏,为计算现实中HULHE扑克游戏打开了一扇大门——HULHE扑克的局面数目是上述数目的大约10000倍。

正如证明16个提示数字不可能保证9×9数独有唯一解(见第6章)所需的计算一样,计算HULHE扑克的局面也达到了现在可行技术的可能极限。要确定几乎完美的策略,迈克尔·鲍林的团队在一个拥有200台机器的网络上进行了计算,其中每台机器拥有32 GB(32千兆字节,每个字节8比特)的内存,还有一个1TB(太字节)的硬盘。整个游戏被分成了110565个子游戏。CFR算法的每次迭代需要61分钟,计算所需的1579次迭代在这组设备上一共运行了两个月,整个计算量相当于一台单核计算机运行了900年。

职业玩家提出了几个关于这个游戏的问题,比如说,在某些情况下虚张声势有没有意义?这些问题都可以通过查看计算结果来解决。于是,即使是职业玩家,也能从这样的研究中得到宝贵的信息。

在计算完成之后,名为Cepheus的最优策略很快就能被应用到实战中。

为了了解研究人员的工作,我们再来看看含有随机性的不完全信息游戏中的最优策略到底是什么。想要理解这类游戏,就要进行一些分析,也就是约翰·冯·诺依曼与奥斯卡·莫根施特恩在1944年合著的《博弈论与经济行为》(Theory of Games and Economic Behavior)一书中讲述的那类分析。经过约翰·纳什(他为此获得了1994年的诺贝尔经济学奖)等人的完善之后,博弈论在合适的情况下能用来定义和计算最优的概率性策略,也叫作混合策略。我们首先来看看“石头、剪刀、布”这个游戏:两位玩家都在同一时刻选择石头、剪刀或者布。石头能赢剪刀,布能打败石头,而剪刀能胜过布(见第5页)。对于玩家来说,玩这个游戏的最优策略肯定不是一直选石头(或者剪刀,又或者布),因为如果这样的话,那么觉察到这个策略的对手就能赢下每一盘:他会一直选择出布(或者相应地出石头或剪刀)。计算表明(在这里考虑对称性,大大简化了计算),玩家的最优策略是随机以1/3的概率出剪刀,以1/3的概率出石头,以1/3的概率出布。在这个策略下,你的对手永远不可能打败你。如果他也采取相同策略,且不计统计波动的话,那么结果就是势均力敌。

举一个更接近HULHE扑克的例子,即只有三张牌的AKQ扑克游戏。

3.三张牌的AKQ扑克的最优策略

仅有三张牌的AKQ扑克证明了,虚张声势有时是有用的,这并不是心理策略,而是博弈论的结果。在这种三张牌的扑克中有两位玩家(A和B),三张牌分别记作1号、2号和3号,相当于扑克中的Q、K和A(见下页图),这也是扑克名称的由来。3号牌能赢2号牌和1号牌,而2号牌能赢1号牌。在牌局开始时,每位玩家都下注1欧元,这就构成了2欧元的彩池。然后给每位玩家发一张牌,而玩家查看各自的牌,玩家A决定是否加注1欧元。如果玩家A不加注,那么玩家B就赢得了彩池(也就赢了1欧元)。如果玩家A加注,那么就轮到玩家B决定是否加注另外1欧元。如果玩家B不加注,那么玩家A就赢得了彩池(也就赢了1欧元)。如果玩家B加注,那么现在彩池里就有4欧元,然后玩家们亮出底牌,谁的牌更大,谁就赢得彩池。

游戏的分析

玩家A(还有玩家B)要做的唯一决定,就是根据自己的底牌决定是否加注。对于A来说,有三种情况,取决于他接到的牌是1号、2号还是3号。对于B来说,同样有三种情况。所有可能的局面就是:

有些决定是显然的。在的情况下,A会选择加注(因为他肯定赢);在的情况下,B不会加注(因为他肯定输);在的情况下,B会选择加注(因为他肯定赢);在的情况下,玩家A或许应该加注。实际上,在A加注的情况下,如果B拿着1号牌,则B不会加注,而A就赢1欧元;如果B拿着3号牌,那么B会加注,A会输掉2欧元。于是,A平均每次输掉1/2欧元;如果A不加注,那么每次会输1欧元,比1/2欧元要输得多。

现在剩下两种需要分析的情况。在的情况下,玩家A应不应该加注来虚张声势?而在的情况下,玩家B应不应该冒着输2欧元的危险来加注?这两个问题没有确定的答案,它们的解答需要用到冯·诺伊曼的混合策略:A和B都应该选择以某个概率加注。设为A在情况下选择加注的最优概率,为B在情况下选择加注的最优概率。博弈论告诉我们,在A和B的最优策略中,的值对应着一个“纳什均衡”,即这样一种情况:

如果A改变策略(也就是的值),那么玩家B可以调整自己的策略(也就是的值),使得A的收益减少(换句话说,A改变策略也没有得益);

将A和B交换,也满足上面的条件。

计算最优策略

要计算“纳什均衡”,我们考虑在的值固定时,A和B的平均收益(见下表)。

举个例子,我们来解释一下这个式子,它对应的是在A拿着1号牌而B拿着2号牌时A的收益。如果A虚张声势,而B跟注的话(概率是),那么A就输掉2欧元(这就是的来源);如果A虚张声势,而B没有跟注的话(概率是),A就赢了1欧元(就是这么来的);如果A没有虚张声势(概率是),那么A会输掉一欧元(对应这一项)。

A的平均收益作为的函数(假设发牌是公平的),可以通过将所有可能对局中的收益加起来再除以6(因为每种对局发生的可能性相等)得到。

我们得到:

A的收益的收益

通过计算,只需要检查那些A的收益对和对的导数都为零的点,就能得到给出A和B最优策略的纳什均衡。在这样的点上,如果A改变的值,那么B可以调整的值来提高收益,反过来说也一样。如果两位玩家谨慎行事的话,那么他们都没有动机去改变自己的选择(A的话是,B的话是)。

导数的计算给出的是:

(A的收益)/,所以

(B的收益)/,所以

在这个点上,,而A的收益=,这就说明在这种微型扑克中,谁先叫牌(也就是A),谁就会平均每局输掉1/9欧元。

关于这种微型扑克的更多细节,可以参看比尔·陈和杰罗德·安肯曼在2013年由出版社Micro-Application发行的书《高等扑克数学》(Poker Maths Sup)。

随机性似乎在扑克游戏中扮演了重要的角色,有时我们也会认为没有“优秀”的玩家,只有“运气好”的玩家。擅长玩扑克的人却持相反的观点:聪明的玩法是存在的。然而也有别的玩法,如果坚持足够多局的话,那么你肯定会输。在某些禁止纯粹博彩游戏的国家中,这样的讨论对于是否允许在线扑克游戏有着实实在在的重要影响。法国的法律是这样定义博彩的:“博彩即需要付款的游戏,其中为了赢取游戏所需的运气成分要远大于技巧成分以及综合智慧的成分。”法国的多项司法判决将扑克归入了博彩的范畴。但在2013年,图卢兹法院做出了相反的判决。最终,法国最高法院果断介入,仍将扑克认定为博彩。

但法国最高法院搞错了,多项科学研究表明,技术和智慧在扑克游戏中有着重要的地位。美国芝加哥大学的史蒂文·莱维特和托马斯·迈尔斯针对这个问题进行了一项决定性的研究(见参考文献)。