只用一行代码就能搞定,博弈论究竟是什么神仙算法?

本文始发于个人公众号:TechFlow,原创不易,求个关注

今天是算法与数据结构专题的第24篇文章,我们一起来聊聊有趣的博弈论问题。

博弈论是一门很庞大的学科,它算是数学的一个分支,也和运筹学甚至是经济学有关。虽然它严格说起来并不是算法领域的内容,但是有不少关于博弈论有趣的算法和问题。关于博弈的相关理论从很早就已经有了雏形,但是正式构建理论成为一门学科是从计算机之父冯诺依曼开始的。从这点上来说也和计算机有点关系。

今天我们来聊聊博弈论当中最简单的巴什博奕(Bash Game)。

说到巴什博奕就不能不提报数问题,它实在是太经典了,以至于我觉得你很有可能也听说过。题目是这样的,说是A和B两个人一起玩一个报数游戏,两个人轮流报数,每次最少报一个数,最多报5个数,第一个报到100的人获胜。如果你是先手的A,应该采取什么策略?

如果之前没有思考过这个问题或者是了解过博弈论的话,估计你可能会觉得这个问题很复杂,也很困难,应该没有什么好的办法。因为两个人每次都可以做好几种选择,每一种选择又会带来不同的选择,这样依次交错会带来大量的可能性。在这种情况下,似乎很难想出一个算法来解决问题。

报到100看不出来,我们缩小一下,如果报到6的人获胜呢?是不是就很明显了,先手的A不论采取什么策略都一定输。因为它不论报几个数,B都可以直接报到6。

既然报6个数的时候A一定必输,那么可以推导得到报的数如果是6的倍数A都一定必输。假设它在某一轮当中报了i,对方只要报6-i就行了。这样重复若干次之后最后一定会剩下6,那么就回到了上面说的最简单的情况。

假设我们开发出了一个state函数可以计算某个状态先手是必胜还是必败,我们用1表示先手必胜,0表示必败。那么显然state(0) = 0,state(6) = 0。由于不论先手在每一轮当中报几,后手都可以控制报一个和它加起来等于6的数,所以可以得到state(n) = state(n-6)。于是,我们可以推导出state(6n) = 0。

由于先手每次可以报1-5个数,当他面临一个6n+k的局面的时候,只要k不等于0。那么他就报k个数,就可以让局面转化成6n的必败局面给B。所以可以知道,除了6n的局面之外的所有局面都是先手必胜的

我们用代码实现的话就只有一行:

def win_or_lose(n):
    return n % 0 != 0

博弈论的精髓在于对问题的分析,体现在代码上就是思维比较复杂,但是代码极为精简。

报数这个问题比较直观,所以找找规律仔细想想也是可以猜出答案来的。但如果我们包装一下,可能就不一样了。

这题源自HDU1847,题面是两个人打牌,一共有n张牌,双方轮流抓牌。规定每人每次抓牌的数量必须是2的幂,最后抓完排的人获胜。假设两人都是极端聪明,请问最后会是谁获胜。

假设两个人极端聪明,这是博弈论问题的前提,也就是说两个人都会采取最优策略。没有这个前提,就无法使用博弈论进行分析了,因为它就不再是单纯的数学问题了。

和上面的题目相比,这题变得复杂了。因为每个人采取的策略数量变了,之前是严格限制了只有5种可能,现在则变成了无数种。但其实这里使用了障眼法,藏了一个trick。

我们首先把2的幂都列出来,从2的0次方开始,分别是1, 2, 4, 8…。看到这个1和2不知道大家有没有什么想法,其实如果你稍微了解一点数论的话就会知道,2的幂一定不能被3整除。也就是说2的幂模3的结果只会有两种,也就是1或者是2。所以这道题其实和上面一题是一样的, 我们拿2的几次幂不重要,重要的是拿的数模3之后余下的几。

state(0) = 0,因为对方已经拿完了。那么state(1) = state(2) = 1,只剩一张或者两张牌的时候可以一次全拿完。state(3) = 0,因为无法一次拿完。我们推广可以得到state(3n) = 0。也就是3的倍数对于先手是必败的。由于我们刚才说了,2的幂模3一定是1或者是2。所以可以得到,对于先手来说,只要面临的状态不是3的倍数,就一定必胜。因为他一定可以找到一个2的幂,使得拿完之后留下3的倍数给对方。

分析完了之后,代码又只有一行:

def win_or_lose(n):
    return n % 3 != 0

巴什博奕的问题很简单,一旦摸清楚了套路之后,这一系列类似的问题都手到擒来。但是要注意的是,面临巴什博奕的问题,我们不能只是简单地理解成是凑成一个数,或者是找到一个必胜或者必败的策略。而是要从状态的角度去分析它,究竟什么样的状态是必胜或者是必败的,状态之间又存在什么样的转移关系。

从这点上来看似乎又有点动态规划的意思,但不一样的是动态规划算法解决的都是边界有限的问题。而博弈论当中有的时候策略或者是状态可能是无限的,但是两者的确有相通的部分。巴什博奕只是博弈论算法当中最简单的算法,后面我们还会继续研究其他更复杂一些的博弈论问题。

如果喜欢本文,可以的话,请点个关注,给我一点鼓励,也方便获取更多文章。

本文使用 mdnice 排版

https://juejin.im/post/5ee4543ef265da76e125a1a4

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论