现在在棋类游戏这方面, AI 已经完胜人类. 即使是最复杂的围棋, 人类也败下阵来. 那么, 是否存在一种策略, 使得黑方或白方必胜呢. 如果这种策略存在, 那么棋类游戏还有其存在意义吗?

策梅洛 (Zermelo) 定理

在 1913 年, 策梅洛 (Zermelo) 证明了策梅洛定理, 定理表示在二人的有限游戏中，如果双方皆拥有完全的资讯, 并且运气因素并不牵涉在游戏中, 那先行或后行者当中必有一方有必胜/必不败的策略. 若运用至国际象棋, 则策梅洛定理表示 “要么黑方有必胜之策略、要么白方有必胜之策略、要么双方也有必不败之策略” .
策梅洛的论文于1913年以德文发表, 并被 Ulrich Schwalbe 和 Paul Walker 于1997年译为英文.
很明显棋类游戏符合上述 “有限游戏”, “拥有完全资讯”, “不包括运气因素” 的要求, 因此是存在必胜或不败的策略的.

证明

最让我惊奇的是这条定理的证明如此简单, 只需利用数学归纳法.
首先我们定义这个有限游戏的结局, 即黑方胜, 白方胜, 以及平局, 规定在游戏开始后第 m 步如果没有分出胜负则是平局.
我们先考虑差一步就可以得到结局的局面, 假设此时是黑方做出决策 (在这里黑方和白方是相对的, 不存在哪一方先手) 此时显然有三种互斥的结局.

  • 如果这一步可以获胜, 那么黑方有必胜策略, 白方必败.
  • 这一步怎么走都会败, 那么黑方必败, 白方有必胜策略.
  • 如果不胜也不败, 那么会平局, 则双方有不败策略.

假设第 n+1 步的局面要么有某方必胜策略, 要么有不败策略, 这里证明对于 n 步的局面也同样如此.
如果第 n 步是黑方做出决策, 那么有互斥的三种情况

  • 存在一种策略可以导向黑方必胜 (也就是第 n+1 步黑方必胜局面) 局面, 那么黑方有必胜策略.
  • 所有策略都会导向白方必胜 (也就是第 n+1 步白方必胜局面), 那么黑方必输, 白方有必胜策略.
  • 所有策略黑方都不败不胜 (也就是第 n+1 步双方不败局面), 那么双方必平局.

因此递推成立, 数学归纳法证明完成.

思考

虽然必然存在必胜或不败策略, 但是并不知道怎样的策略和哪方先手可以必胜、不败, 而且要找出这样的策略也应该是十分困难的, 所以棋类游戏仍然还有其意义. 而且就算找到了这样的 “完美策略” , 那么也不是人类能够掌握的 (时间, 空间复杂度太高).