博弈游戏中的数学必胜策略

女士们，先生们，老少爷们儿们！在下张大少。

数学家们热爱游戏。他们不仅能在看似忙于工作的同时享受乐趣，而且即使是最简单的游戏也可能需要巧妙的战术和策略才能获胜。这类问题正是用数学来解决的理想对象。

数学的一个分支，称为组合博弈论，大约在30年前发展起来，专门用于分析游戏。它提供了一种将游戏分解为更易于研究的较小部分的方法，然后利用一种特殊的代数将这些子游戏的值相加。如果说数学家们擅长一件事，那就是计数。

组合博弈论

尽管组合博弈论（CGT）功能强大，但它仅适用于满足某些条件的游戏。最重要的条件是：游戏有两名玩家，双方对游戏状态拥有完全信息，不存在随机因素（如掷骰子或洗牌），并且双方轮流行动（不允许跳过回合），最终无法行动的一方输掉游戏。因此，双陆棋、扑克、海战棋、大富翁和纸牌接龙等游戏无法用CGT来分析，因为它们在各种不同组合上不满足这些标准。

能够应用CGT的游戏都具有相同的本质：你通过确保自己能比对手多走至少一步来获胜。这类游戏的经典例子是我们小时候都玩过的，那就是……

《棋手》，作者：托马斯·埃金斯

二十一（取物游戏）

先回忆一下玩法，二十一游戏的玩法是：在两个参赛者之间放一堆共21枚硬币（或火柴棍，或其他任何小物件）。玩家轮流从堆中取走1枚、2枚或3枚硬币，目标是取走最后一枚硬币，从而让对手无法继续行动而输掉游戏。

事实证明，二十一是一个“先手必胜”的游戏——无论第二名玩家玩得多么好，先手玩家都拥有一种无解的策略。如果你先开始，你可以确保在对手回合时恰好剩下四枚硬币。对手最多能拿走其中三枚，然后你就可以取走剩下的硬币从而获胜。

研究组合博弈论的数学家花了大量时间分析一个与二十一非常相似的游戏，叫做尼姆游戏。尼姆游戏可以用任意多堆硬币来玩，两名选手被允许取走一整堆，或从同一堆中取任意数量的硬币。同样，胜者是取走最后一堆或最后一枚硬币、使得对手没有硬币剩下的人。事实上，二十一游戏是尼姆游戏的一个特例，相当于有七堆，每堆只有3枚硬币。

尼姆游戏

事实证明，尼姆游戏非常适合用组合博弈论（CGT）进行分析。尼姆游戏的目标是确保你总能走出一步，而对手在你之前就无法继续行动。那么，CGT所做的就是计算出双方玩家能够走出的最大步数，从而判断谁拥有额外的“多余步数”。尼姆游戏是一种所谓的“impartial game”（无偏博弈），因为双方使用相同的棋子，因此有相同的可选步数——这与国际象棋不同，国际象棋是一种“partisan game”（有偏博弈），意味着每个玩家拥有自己独有的棋子，只有自己才能移动它们。

在尼姆游戏中，双方玩家拥有相同数量的“额外步数”，唯一重要的是轮到谁走棋。例如，当只剩下一枚硬币时，接下来轮到谁走谁就获胜。第一名玩家取走最后一枚硬币后，对手就没有硬币可取了，因此输掉比赛。CGT有自己独特的方式来描述此类局面，并有一套自己的代数来计算出博弈的值。只剩一枚硬币的情形记作：

{ 0 | 0 } = *

由于CGT不知道下一步轮到谁，它给出的是在任意一方走棋后剩余的可走步数。花括号中的数字表示：在取走最后一枚硬币后，左边的玩家将没有剩余步数，右边的玩家也同样如此。因为尼姆游戏是无偏博弈，中间竖线左右两侧的数字总是相同的。该博弈的值写在等号后面。星号表示下一步走棋的一方获胜，这被称为模糊局面。二十一游戏从一开始就是一个模糊局面，因为先走的一方总能强行获胜。

然而，如果剩下两枚孤立的硬币，那么下一步走棋的一方将会输掉。这是因为无论左方还是右方先走，都只能留下一枚硬币。对方取走这枚硬币，从而赢得游戏。这种情况记作：

{1∣1}=0.

同样，左侧和右侧的数字告诉我们，在任意一方走完下一步之后剩余的可走步数，在这个例子中就是1。这里的值是0，因为下一步走棋的一方将会输掉游戏，因此“先手必败”的局面也被称为零局面。所有先手必败的局面都可以简化为游戏中没有硬币剩下的最终状态：

{ ∣ }=0.

一个稍微复杂一些的局面是剩下三枚硬币，排列为一堆两枚和旁边一枚孤立的硬币。先手玩家从两枚的那堆中取走上面一枚，第二名玩家随后从剩下的两枚孤立硬币中取走一枚，然后先手玩家取走最后一枚硬币获胜。因此，无论左方还是右方先走，都能获胜——这又是一个模糊局面：

{2∣2}=∗.

当然，先手玩家也可以一开始就取走那枚孤立的硬币，或者取走整堆两枚的硬币。这种在留下一枚或两枚剩余步数之间的选择，可以记为：

{1,2∣1,2}.

但在对手回合开始时，不必要地只留下一枚剩余步数是完全不理智的，因为对手会直接取走剩下的硬币从而赢得比赛。在CGT中，这种愚蠢的选择会被忽略，因为假定双方都是理智地在玩，并试图获胜。因此：

{1,2∣1,2}={2∣2}=∗.

正如第一个例子那样，这一局面简化为了 {0∣0}=∗，即第二名玩家走完后的局面。

A possible starting setup for Nim

尼姆游戏的一种可能初始布局

尼姆游戏中的一个模糊局面

有偏博弈——国际象棋

在有偏博弈中，两位玩家拥有的可选走法不同。此时花括号中的左侧数字和右侧数字不一定相同。如果左方有四步可行走法，而右方只有三步，那么左方就多出一步优势，无论谁先走，左方都会获胜。这种情况记为：

{4∣3}=1,

它可以简化为

{0∣ }=1。这被称为“正局面”，因为无论谁先走，左方都能赢。如果情况反过来，右方多出一步优势，那么该博弈就是“负局面”（按照惯例，博弈的值总是从左方的角度给出）。

国际象棋就是这样一种有偏博弈。既然我们理解了CGT的工作原理，就可以用它来分析棋局。不过严格来说，国际象棋作为一个整体并不符合CGT的分析条件。尽管双方对棋盘上的棋子有完全的信息，并且不存在随机因素，但CGT的应用还有一些更微妙的要求。一般而言，国际象棋的胜负并不取决于谁拥有更多的剩余步数，而是取决于谁将死对方。而CGT最适合那些“走一步通常是一种劣势”的游戏。然而在国际象棋中，拥有下一步走棋权几乎总是巨大的优势。事实上，一种为了平衡强弱选手而设计的让子方式，就是移除强手方某一匹马前的兵，并让弱手方在开局时连续走两步（这种让子方式称为“兵加两着”）。

国际象棋也比尼姆等游戏复杂得多，仅仅拥有比对手更多的剩余步数并不足以让你获胜——你仍然可能被将死。此外，国际象棋开局时棋子很多，而且关键是有一些非常强大的棋子，它们能在棋盘上大范围施加影响力；例如，后最多可以攻击18个格子。结果是，在游戏的大部分时间里，棋盘无法像尼姆中分开的几堆硬币那样分解成独立的组成部分。然而，在残局阶段，当大多数长距离棋子被兑掉之后，棋盘就可以分解为若干个子博弈。此时，下一步走棋可能不再是一种优势，而CGT就成了分析这种局面的完美工具。

《两位棋手肖像》，作者：奥诺雷·杜米埃

残局中的CGT

在残局的某些局面中，必须走棋的一方将会输掉。这与尼姆中的零局面相同，在国际象棋中，这些特殊情况被称为“相互逼走”。“Zugzwang”是一个德语词，意为“被迫移动”。右图所示的“Trébuchet”局面就是这样一个相互逼走的例子：

{ ∣ }=0.

一个“Trébuchet”局面

双方的小兵互相阻挡了对方的推进，因此接下来必须由某一方的王移动。然而，白王不能走到f4格，黑王也不能走到d5格，因为那样会导致王受到对方小兵的攻击。因此，必须先移动的王不得不从自己的小兵旁边退开，从而无法再保护它（国际象棋规则禁止双方的王相距一格之内）。此时对手就能吃掉这个小兵，并迫使自己的小兵前进到底线。根据规则，这个小兵可以升变为后，这一优势被认为是决定性的，从而确保后走的一方必胜。

{ 0 | 0 } = *.

如果在棋盘上增加一些额外的棋子，就可以将这一局面转化为一个模糊局面——先走的一方获胜：

{0∣0}=∗.

残局中的一个模糊局面

在此局面中，先走的一方可以将自己在a线上的小兵向前推一格。此时对方的小兵被阻塞，除了移动王之外别无选择。在这种情况下，游戏包含两个部分：a线小兵的局面值为∗，而Trébuchet局面的值为0。因此，整个游戏的总值为∗。

然而，如果白方的兵是在a2格而不是a3格，那么局面的值将变为正数：{0∣ }=1。此时白兵在游戏中尚未移动过，因此它在第一步可以选择前进一格或两格。正是这个选择给了白方一个多余的步数。如果黑方先走，白兵就前进一格，像之前那样挡住黑兵。但如果轮到白方先走，白兵可以一次前进两格直接形成阻塞，从而再次迫使黑方打破Trébuchet局面并输掉比赛。因此，无论谁先走，白方都能获胜。

残局中的一个正局面

不过，上述局面仍然相对简单。CGT真正发挥威力的时候，是当棋盘上有更多小兵，局面变得过于复杂以至于无法仅靠观察来轻易分析时。例如，左图所示的局面出自1929年Schweda与Sika之间的一盘对局。执白的Schweda正确判断出这是他的必胜局面。1960年，Euwe证明如果轮到黑方先走，黑方也能获胜。但即便Euwe曾担任两年世界冠军并拥有数学博士学位，他也无法清晰地解释为什么这个局面是先走的一方获胜。然而，在组合博弈论发展起来之后，这个分析就变得容易了。

Schweda vs Sika, 1929

关键在于将游戏分解为独立的组成部分，并计算出每个部分的值。位于e线和f线上的王与兵被锁定在另一种形式的Trébuchet局面中，正如我们所知，它的值为0。因此，另外两个子博弈构成了一个“后走者胜”的局面。

位于a线和b线上的小兵实际上处于相当复杂的局面：其中三个小兵拥有双步移动的选择，并且再过几步还会出现吃子的机会。不过，如果把这些数值加起来，结果发现这个a线和b线子博弈的值等于↑。这是一个新的符号，它所表达的意思是：这个局面是无穷小的正数——白方拥有非常微弱的优势。

第二个组成部分——h线上的两个小兵——的值更容易计算。在这里，黑方拥有双步移动的选择，而白方没有。如果轮到黑方走棋，黑兵前进两格，并在下一回合挡住白兵的推进。如果白方先走，黑方则只前进一格，随后同样很快挡住白兵。因此，黑方可以利用这个多余的步数，保证在该子博弈结束后轮到白方走棋。这个子博弈的值是↓，它表示一个略为负的数。

利用CGT的代数可以将↑和↓相加，结果发现这两个组成部分之和为一个模糊值。无论谁在棋盘上先走，都可以巧妙地安排，使得在这些小兵子博弈结束后轮到对方走棋。对方别无选择，只能移动自己的王，从而输掉Trébuchet局面，并很快输掉整盘棋。

因此，组合博弈论是分析某些类型游戏的非常强大的工具。简单的尼姆游戏很好地展示了这一技术的运作方式，但其真正的威力只有在应用于像国际象棋残局这样复杂得多的局面时才会显现出来。它甚至能解开一个困扰了75年之久的谜题——这个谜题曾难倒了一位拥有数学博士学位的国际象棋特级大师。

《棋手》，作者：托马斯·埃金斯

延伸阅读

1 Winning Ways For Your Mathematical Plays, Volume 1, 2nd edition, Berlekamp, Conway, Guy

2 Games of No Chance, Richard Nowakowski (ed.)

青山不改，绿水长流，在下告退。

转发随意，转载请联系张大少本尊。