新浪网

策梅洛定理:游戏开始时,结局就固定了!博弈论与纳什均衡(一)

李永乐老师

关注

确定不再关注此人吗

各位同学们大家好!我是李永乐老师。

之前我做了两个系列节目:《漫谈相对论》和《从亚里士多德到牛顿的宇宙》,我想,第三个系列节目就换换口味,讲讲数学的一个小分支,在经济学上又很有用的学问——博弈论吧。

我在北大读书时,学过一点经济学,但是没有系统学习过博弈论这门课。今天所讲的都是我个人对博弈论的理解,如果有不准确的地方,欢迎大家批评指正。在这个系列中,我把之前零零散散讲过的博弈论内容进行了总结(所以,这是一个炒冷饭的内容),希望大家喜欢我的讲述。

“弈”这个字,原本意思是下棋。请问各位同学,你会下棋吗?你下棋输过吗?如果我说,围棋也好,象棋也好,其实都是有必胜法的,你们相信吗?

我们假设有一个非常简单的游戏,先手A和后手B各做一次决策(选择上路或者下路),根据二人决策的结果,游戏的胜负如下。通过这个表格,你能知道游戏的结果是谁获胜吗?

也许有同学认为:A的赢面大一些,因为A有2种可能会赢,而B只有一种可能会赢。事实并非如此。这盘棋的结果一定是和棋(除非有一方实在脑子不太好用,才会输掉)。

我们可以画一个游戏树来解释:

我们看:如果先手A选择上方,游戏进入到一个由进行B进行决策的分支,这叫做一个子游戏。在这个子游戏中,B选上方就A获胜,B选下方就B获胜,B要选择对自己有利的,所以他一定选择下方。这个子游戏的结局是固定的,就是B获胜。

如果先手A选择下方,游戏进入到另一个由B做决策的子游戏中,这时B选上方就A获胜,B选下方就和棋,B要选择对自己有利的,所以这个子游戏的结局一定是和棋。

我们再来考虑A:若A走上方,进入子游戏1,一定B获胜;A走下方,进入子游戏2,一定和棋。A也要选择对自己有利的,所以A选择下方。最终的游戏就是和棋。

如果游戏复杂一些,也不过是分支变多,长度变长,但是只要我们从最后端的子游戏开始,一层层倒推,就一定能推算出在最优策略下,游戏到底是先手胜,还是后手胜,还是和棋,这种胜负是不可避免的。

其实,象棋也好,围棋也好,它们与我刚才举的例子没有本质不同,只是复杂度高得多。而且,由于制定了一些胜负以及和棋规则,下棋的步骤也是有限的。

理论上讲,我们是可以画出围棋的游戏树的,如果我们遍历了所有情况,就能知道围棋结局到底是先手必胜,还是后手必胜,或者一定是和棋了。只是,这个过程过于复杂。

以围棋为例。围棋在19x19=361个格子上轮流放棋子,所以每个格子有黑白空三种可能,整个围棋棋盘上的状态数上限是3361=1.7×10^172,去掉一些重复和对称,围棋的状态复杂度大约是10^172量级。

要知道:宇宙中的原子个数只有大约10^72个,就算用宇宙中的一个原子代表一个围棋局面,穷尽宇宙中所有的原子,也不能表示出围棋所有的棋局局面。

围棋的游戏树就更难画了。因为围棋可以提子,有了空白的地方可以继续下,所以并不一定是填满了棋盘就结束。不过,我们可以估计游戏树的总层数和每一层的平均分支。根据统计和计算:一盘围棋的平均手数是150手,每一手的平均分支数是250种,所以整个围棋的游戏树复杂度大约是250^150≈10^360

理论上讲,如果我们遍历了所有10^360种情况,就能知道围棋结局到底是先手必胜,还是后手必胜,或者一定是和棋了。但是,这个计算量实在太大了。之前世界上最快的计算机富岳每秒最高可以计算100亿亿次浮点运算,假如1次浮点运算就能算出一条路径,那么算完所有围棋游戏的可能情况,需要10^342秒,而宇宙的年龄只有138亿年,大约只等于10^17秒。

虽然我们无法计算出这个最优策略,但是显然,这个最优策略一定是存在的。

不仅仅是围棋,所有的明棋都是这样,只不过复杂度不同而已。

1913年,数学家策梅洛证明:对于一个两人的完全信息游戏,一定存在一个策略,要么先手一定获胜,要么后手一定获胜,要么双方一定平局,这就是泽梅洛定理。

策梅洛

策梅洛定理告诉我们:假设双方都是棋类大师,对游戏树了如指掌,这时候他们一定会采用统一的策略,让游戏向固定的方向发展,最终的结局也是固定的。

因为,任何一个人单方面的改变决策,都会对自己不利。正如我们刚才举例的那个小游戏,如果A改变决策,将会让B获胜;如果B改变决策,将会让A获胜,双方都为了自己的利益考虑,一定会出现A选择下路,B也选择下路的情况,最后游戏就一定是和棋。

实际上,在许多的博弈过程,都和下棋很像,参与博弈的几方能采取的策略都是有限的。在1950年,著名的数学家约翰纳什证明了一个更加普遍的结论:

只要参与博弈的几方策略都是有限的,那么就一定存在一种平衡状态,大家都会采用这种平衡策略,而没有单方面改变策略的动力。这种平衡状态就叫做纳什均衡。这个规律就叫做纳什定理。

刚才举的下棋的例子,最优策略就是纳什均衡,策梅洛定理其实是纳什定理的一个例子。在我们所处的世界中,无论是政治还是经济,都充满了博弈论和纳什均衡的例子。你想了解更多吗?关注我,下一回继续带大家漫谈博弈论。

特别声明:以上文章内容仅代表作者本人观点,不代表 新浪网观点或立场。如有关于作品内容、版权或其它问题请于作品发布后的30日内与 新浪网联系。
加载中...