策梅洛定理：游戏开始时，结局就定了！博弈论与纳什均衡（一）

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

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

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

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

我们假设有一个非常简单的游戏，先手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个格子上轮流放棋子，所以每个格子有黑白空三种可能，整个围棋棋盘上的状态数上限是3³⁶¹=1.7×10¹⁷²，去掉一些重复和对称，围棋的状态复杂度大约是10¹⁷²量级。

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

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

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