1948 年，在普林斯顿数学楼的公共休息室里，教授和学生们下午常在这里下国际象棋和围棋，约翰·纳什拿出了一种新游戏。棋盘是一个菱形，铺满了像蜂巢一样的六边形格子。红、蓝两位棋手轮流在空格上落子，每次一枚。棋子落下后永不移动。红方要用一串红子连接上下两条边；蓝方要用一串蓝子连接左右两条边。

同学们把这种游戏叫做"纳什"。他并不知道，丹麦人皮特·海恩早在 1942 年就发明了它，取名 Polygon。1952 年，帕克兄弟公司以一个流传至今的名字推出了它：海克斯（Hex）。

7×7 的海克斯棋盘。红方获胜：一串用黄色标出的红色格子连接了上下两边。
7×7 的海克斯棋盘。红方获胜：一串用黄色标出的红色格子连接了上下两边。Euler’s Eyes 绘图

永远不会平局

第一个令人惊讶的性质：在海克斯棋中，下满的棋盘总有一位胜者。不可能把所有格子填满而谁都没有连成。

直觉是这样的：要阻止红方从上连到下，蓝方需要一道从一边切到另一边的"屏障"。而一道从一边通到另一边的蓝色屏障，恰恰就是一串获胜的蓝色链条。如果红方没有赢，那是因为蓝方挡住了它，而挡住就是赢。

这依赖于格子是六边形。在国际象棋那样的正方形棋盘上，两个格子可以只在角上相接，两条不同颜色的路径可以沿对角线交叉，谁也连不成。而在六边形中，每个顶点处恰好有三个格子相遇，这样的交叉是不可能的。1979 年，数学家大卫·盖尔证明，海克斯棋没有平局这一事实与布劳威尔不动点定理等价，而纳什在博弈均衡中用到的正是这类结果。

策略窃取

第二个性质更奇怪。纳什证明了先手有必胜策略：只要下得完美，他总能赢。但证明并没有说这个策略是什么。这个论证叫做策略窃取，过程如下：

  1. 游戏是有限的，并且没有平局。所以两位棋手中必有一位有必胜策略：一套规则，告诉他在每种局面下怎么走，并保证无论对方怎么防守都能获胜。
  2. 用反证法，假设拥有必胜策略的是后手。
  3. 那么先手可以把它"偷"过来。他随便走第一步，然后假装自己是后手，无视那枚多出来的棋子，按照后手的必胜策略下棋。
  4. 如果某一刻策略要求下在那枚多余棋子所在的格子，他就随便下在别的格子上，这枚新棋子成为新的多余棋子。
  5. 在海克斯棋中，盘面上多一枚子永远不会吃亏。所以先手按照偷来的策略下棋，一定获胜。
  6. 但这与"后手有必胜策略"的假设矛盾。因此拥有必胜策略的是先手。
$$\boxed{\text{在海克斯棋中，先手总能获胜。}}$$

这是一个存在性证明：它保证策略存在，却不把它展示出来。对于不超过 9×9 的棋盘，计算机已经找到了明确的必胜策略。对于标准的 11×11 棋盘，没有人知道它是什么。

练习：在 1×1 和 2×2 的海克斯棋盘上，先手怎样获胜？

在 1×1 的棋盘上，唯一的格子同时接触四条边：先手第一步就赢了。在 2×2 的棋盘上，如果红方先走，制胜的一步是菱形两个钝角处的格子之一：每个这样的格子都与另一行的两个格子相邻，而蓝方只能占住其中一个。下一步，红方就连成了链。

练习：策略窃取论证适用于井字棋吗？国际象棋呢？

在井字棋中，多一枚子同样不会吃亏，论证表明后手不可能有必胜策略。但井字棋可以平局，而且在完美对弈下确实是平局：论证只保证先手不会输。在国际象棋中，论证一开始就失效了：多一枚子可能吃亏，因为有时候必须走棋反而是劣势，即所谓"楚茨文格"（zugzwang）。

来源： David Gale，“The game of Hex and the Brouwer fixed-point theorem”，The American Mathematical Monthly 86（1979）· Martin Gardner，“The game of Hex”，收于 Hexaflexagons and Other Mathematical Diversions（Chicago，1988）· Sylvia Nasar，A Beautiful Mind（Simon & Schuster，1998），第 11 章。

约翰·纳什的全部主题 · ← 约翰·纳什的一生 · 纳什均衡：谁也无法单独改善 →

图片来源.