雨水 | 围棋有必胜策略吗？

围棋一直被视为对弈棋类游戏中最为复杂的一种。围棋的战术和策略被视为艺术，不仅具有高度的智慧，也蕴含着哲理。然而，AlphaGo 的出现永远地改变了围棋。AI 不但可以通过学习人类的所有棋谱来得到人类的智慧，甚至还可以通过自我训练的方式从零成为大师。如今，棋手的训练已经出现了仿照 AI 的趋势，一项智力上的艺术逐渐变成了模仿和记忆，失去了原本的意义。

在围棋界，人类已经无法匹敌 AI，但无论是人类还是 AI，下棋的时候都只能做出很有限的几步思考。棋手思考能力的局限造就了瞬息万变的棋局，围棋的魅力也正因此而生。然而，对于两个全知全能的上帝玩家来说，围棋或许是非常无聊的，他在刚开始下棋的时候就预知了自己的结局。难道围棋的结局真的是注定的吗？上帝真的可以让自己始终立于不败之地，或者知道自己永远不可能获胜吗？

1913年，数学家和逻辑学家策梅洛（Zermelo）证明了一个定理，回答了上面的问题。具体来说，不论是什么样的游戏，只要有限步内停止，实行回合制（你一步，我一步），对弈双方都知道所有的信息，那么有且仅有以下三种可能：

1. 先手玩家存在必胜策略

2. 后手玩家存在必胜策略

3. 双方的最优策略将会导向平局

使用数理逻辑可以轻松地给出定理的证明：用 x_{i} 和 y_{i} 来分别表示第 i 步的时候先手和后手玩家的策略，设 W 表示游戏结局为先手玩家不败。我们先考虑一个在第二步先手下完就会结束的游戏。先手玩家有必胜策略可以这样去描述：第一步先手可以这样走，使得不管第一步后手是怎么走的，第二步的时候先手都有一个策略使得她不输，用逻辑符号来写就是

而对应地，后手玩家必胜的表述就是

这两个命题正好互为否定关系！因此根据排中律[1]，如果先手玩家没有不败策略，那么后手玩家一定有必胜策略。对于一般局数的对弈来说，证明是类似的。

回到围棋的问题，策梅洛定理表明了对于全知全能的上帝来说，围棋的双方中，总有一方能够立于不败之地，因此，游戏的结局在开始的时候就注定了。策梅洛定理描述了一个博弈论问题，解答的方式却使用了数理逻辑，又提供了对 AI 的一个有趣的思考。然而，对于不完全信息的游戏以及多人游戏，策梅洛定理并不成立，斗地主就是一个典型的例子。人类或许更加享受这样的游戏，毕竟，运气也是实力的一部分。

[1] 排中律的一种表述是：如果命题 p 的否定（即 \neg p）不是真的，那么命题 p 一定是真的。