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

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

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

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

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

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

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

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

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

  • 定理1:

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

比如说中国象棋

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

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

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

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

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

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

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

N=1时命题是显然成立

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

假设命题对N-1成立

现在我们考虑N时的情况

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

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

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

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

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

QED

怎么样,是不是对此大吃一惊呢?

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

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

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

 

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

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注