什么！？围棋竟然必然会被破解！——策梅洛(Zermelo)定理

前段时间，Google的围棋AI——Alpha Go击败李世石，标志着人工智能技术进入了新的时代。

公认的最复杂的棋类运动，围棋，如今也已经被AI所“破解”。

之所以围棋曾经被认为是“AI不能解决”的，是因为围棋相较于国际象棋等其他棋类，其变化之丰富，已经超出了人类目前最强力的计算机的枚举能力。

Google的AI能击败人类顶尖选手，是因为它采用了深度神经网络等一系列的算法，这里我们不做介绍。

那么仅仅从数学上来说，围棋是否是可以被完全“破解”的呢？

换句话说，围棋中是否存在一方(先手或后手)有必胜策略？

这里就需要博弈论中的重要定理：策梅洛(Zermelo)定理出场了。

我们首先来看策梅洛定理的一个弱化形式

• 定理1：

如果在一个游戏(双方交替地在某个棋盘上进行操作)中，游戏的胜利与否与运气成分无关，并且游戏一定能在N步以内决出胜负(这里的N是某个确定的正整数)，那么先手和后手中必有一方有必胜策略。

比如说中国象棋

中国象棋的胜利条件可以规定为吃掉对方的将(帅)，因此与运气成分无关。
(实际上它只与棋盘当前的状态有关)

由于中国象棋的棋盘大小和棋子数目都是有限的，那么棋子的排列只有有限种，而规则限制了相同的局面不能重复出现三次以上，因此有限步之内必然能决出胜负。

也就是说，在中国象棋中，必有一方有必胜策略，只是我们目前还并不知道这个策略是什么而已。

对于围棋而言，如果我们要求相同的局面不能重复出现，而现行的规则下不会出现平手，基于同样的理由我们可以知道围棋能在有限步内决出胜负。

因此在局面不能重复的前提下，围棋中也有一方必胜。

这个定理的证明出奇的简单，我们只需要用到数学归纳法：

我们把先手称作甲，后手称作乙

N=1时命题是显然成立

因为假设保证了在甲走一步之后游戏就决出了胜负，那么胜利与否完全取决于甲怎么走

假设命题对N-1成立

现在我们考虑N时的情况

在甲走一步后，就得到了一个之多在N-1步内结束的新的游戏

根据归纳假设，新游戏要么先手必胜，要么后手必胜

如果无论甲怎么走，得到的游戏都是先手必胜，那么原来的游戏甲必败，因为新的游戏里乙变成了先手

如果存在一种走法，使得新游戏后手必胜，那么原来的游戏先手必胜，因为新的游戏中甲变成了后手

因此，命题对所有正整数N成立

QED

怎么样，是不是对此大吃一惊呢？

不过这个定理只保证了必胜策略的存在性，它无法告诉我们任何关于具体怎么才能必胜的信息。

如果想要找到必胜策略，我们或许只能将所有可能的情况一一枚举，而这是我们现在的计算能力所做不到的。

我们不必因此对棋类运动灰心，毕竟下棋重在与对手博弈的过程。

 

至于完整版本的策梅洛定理，咕咕咕咕咕咕咕咕咕咕咕