开发者社区> 云栖号资讯小哥> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 云栖号资讯:【点击查看更多行业资讯】在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来! 博弈论是一门很庞大的学科,它算是数学的一个分支,也和运筹学甚至是经济学有关。虽然它严格说起来并不是算法领域的内容,但是有不少关于博弈论有趣的算法和问题。
+关注继续查看

云栖号资讯:【点击查看更多行业资讯
在这里您可以找到不同行业的第一手的上云资讯,还在等什么,快来!


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

今天我们来聊聊博弈论当中最简单的巴什博奕(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

总结

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

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

【云栖号在线课堂】每天都有产品技术专家分享!
课程地址:https://yqh.aliyun.com/live

立即加入社群,与专家面对面,及时了解课程最新动态!
【云栖号在线课堂 社群】https://c.tb.cn/F3.Z8gvnK

原文发布时间:2020-06-13
本文作者:承志
本文来自:“掘金”,了解相关信息可以关注“掘金”

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
再学一道算法题: 食物链(带权并查集)
再学一道算法题: 食物链(带权并查集)
0 0
再学一道算法题: 寻找大富翁
再学一道算法题: 寻找大富翁
0 0
再学一道算法题: 最大子列和问题
再学一道算法题: 最大子列和问题
0 0
再学一道算法题: 井字棋
再学一道算法题: 井字棋
0 0
算法学习之路|害死人不偿命的(3n+1)猜想(15)
对任何一个自然数n,如果它是偶数,那么把它砍掉一半;如果它是奇数,那么把(3n+1)砍掉一半。。。
925 0
+关注
云栖号资讯小哥
云栖号小编在此 ^o^
文章
问答
文章排行榜
最热
最新
相关电子书
更多
考察数据科学家支持向量机(SVM)知识的25道题,快来测测吧
立即下载
数据+算法定义新世界
立即下载
大数据可视化与自然之美
立即下载