Part I. Impartial Combinatorial Games
第一部分. 公平组合游戏
1. 拿走游戏。
组合游戏是两人游戏，具有完美的信息和没有机会移动，以及赢或输的结果。这样的游戏由一组位置确定，包括初始位置和轮到移动的玩家。游戏从一个位置移动到另一个位置，玩家通常轮流移动，直到达到终端位置。终端位置是没有移动可能的位置。然后宣布其中一名玩家为胜者，另一名为输者。
关于组合游戏的材料有两个主要参考文献。一个是研究书籍，《关于数字和游戏》（On Numbers and Games）由 J. H. Conway 著，Academic Press，1976 年出版。这本书介绍了该学科的许多基本思想，并导致了该领域迅速增长并持续至今。另一个更适合这门课程的参考文献是两卷本的书《赢得你的数学游戏方式》（Winning Ways for your mathematical plays）由 Berlekamp、Conway 和 Guy 著，Academic Press，1982 年出版，平装。这本书中描述了许多有趣的游戏，其中大部分对本科数学学生都很容易理解。这一理论可以分为两部分：公平游戏中任何给定位置的可用移动集对两个玩家都相同；党派游戏中每个玩家从给定位置都有不同的可能移动集。象棋或跳棋这样的游戏，其中一名玩家移动白色棋子，另一名玩家移动黑色棋子属于党派游戏。在第一部分中，我们仅处理公平游戏的理论。在 Richard K. Guy 的《公平游戏》（Fair Game）一书中给出了公平组合游戏的初步介绍，该书发表在 COMAP 数学探索系列中，1989 年。我们从一个简单的例子开始。
1.1 一个简单的拿走游戏。下面是一个非常简单的公平组合游戏规则，从一堆筹码中取出筹码。
(1) 有两个玩家。我们将它们标记为 I 和 II。
(2) 桌子中间有一堆 21 个筹码。
(3) 移动包括从堆中取出一、二或三个筹码。至少必须取出一个筹码，但不能超过三个。
(4) 玩家轮流移动，由玩家 I 开始。
(5) 取走最后一个筹码的玩家获胜。（最后一个移动的玩家获胜。如果你不能移动，则输掉。）
我们如何分析这个游戏？这个游戏中有一个玩家可以强迫获胜吗？你宁愿成为开始的玩家还是第二个行动的玩家？什么是好策略？
我们从结束向开始分析这个游戏。这种方法有时被称为向后归纳。
如果只剩下一、二或三个筹码，下一个移动的玩家将赢得游戏，只需取走所有筹码即可。
假设还剩下四个筹码。那么下一个移动的玩家必须在堆中留下一、二或三个筹码，他的对手将能够获胜。所以四个筹码剩余是下一个移动的玩家的损失，而是上一个玩家的胜利，即刚刚移动过的那个。
当剩下 5、6 或 7 个筹码时，下一个移动的玩家可以通过移动到剩下四个筹码的位置来获胜。
当剩下 8 个筹码时，下一个移动的玩家必须留下 5、6 或 7 个筹码，因此上一个玩家可以获胜。
我们看到，0、4、8、12、16 等位置的筹码是目标位置；我们希望进入它们。现在我们可以分析有 21 个筹码的游戏。
由于 21 不是 4 的倍数，所以第一个移动的玩家可以获胜。唯一的最佳移动是取走一个筹码并留下 20 个筹码，这是一个目标位置。
1.2 什么是组合游戏？我们现在更精确地定义组合游戏的概念。它是一种满足以下条件的游戏。
(1) 有两个玩家。
(2) 有一组可能的游戏位置，通常是有限的。
(3) 游戏规则为两个玩家和每个位置指定哪些移动到其他位置的移动是合法的。如果规则不区分玩家，即如果两个玩家从每个位置移动的选项相同，则游戏称为公平；否则，游戏称为党派。
(4) 玩家轮流移动。
(5) 当到达一个对于轮到移动的玩家没有移动可能的位置时，游戏结束。按照正常游戏规则，最后一个移动的玩家获胜。按照失误游戏规则，最后一个移动的玩家输掉。
如果游戏永远不会结束，则宣布平局。然而，我们几乎总是添加以下条件，称为结束条件。这消除了平局的可能性。
(6) 无论如何进行游戏，游戏都将在有限步内结束。
重要的是要注意这个定义中省略了什么。不允许随机移动，例如掷骰子或发牌。这排除了像双陆棋和扑克这样的游戏。组合游戏是一种完美信息游戏：不允许同时移动和隐藏移动。这排除了海战和剪刀-纸-石头。在有限步内不可能出现平局。这排除了井字游戏。在这些笔记中，我们将注意力集中在公平游戏上，通常遵循正常游戏规则。
1.3 P-位置、N-位置。回到第 1.1 节中拿走游戏，我们看到 0、4、8、12、16 等是上一个玩家（刚刚移动过的那个）获胜的位置，而 1、2、3、5、6、7、9、10、11 等是下一个移动的玩家获胜的位置。前者称为 P-位置，后者称为 N-位置。
P-位置就是那些筹码数量可被 4 整除的位置，在第 1.1 节中称为目标位置。
在公平组合游戏中，原则上可以通过（可能是超限的）归纳使用以下标记过程从终端位置开始找到哪些位置是 P-位置，哪些是 N-位置。我们说一个游戏中的位置是终端位置，如果从它开始没有移动可能。这个算法就是我们用来解决第 1.1 节中拿走游戏的方法。
步骤 1：将每个终端位置标记为 P-位置。
步骤 2：将每个可以在一步内到达标记为 P-位置的位置标记为 N-位置。
步骤 3：找到那些只能移动到标记为 N-位置的位置；将这样的位置标记为 P-位置。
步骤 4：如果在步骤 3 中没有发现新的 P-位置，则停止；否则返回步骤 2。
很容易看出，移动到 P-位置的策略获胜。从 P-位置，你的对手只能移动到 N-位置（3）。然后你可以移回 P-位置（2）。最终游戏结束于终端位置，由于这是一个 P-位置，所以你获胜（1）。
下面是一个对 P-位置和 N-位置的描述，它适用于满足结束条件的公平组合游戏，在正常游戏规则下。
特征性质。P-位置和 N-位置由以下三个语句递归定义。
(1) 所有终端位置都是 P-位置。
(2) 从每个 N-位置，至少有一步移动到 P-位置。
(3) 从每个 P-位置，每一步都是到 N-位置。
对于使用失误游戏规则的游戏，应将条件 (1) 替换为所有终端位置都是 N-位置的条件。
1.4 减法游戏。现在让我们考虑一类包含第 1.1 节中拿走游戏作为特殊情况的组合游戏。设 S 为一组正整数。减法游戏的减法集合 S 如下进行。从一堆大量筹码（比如说 n 个）中，两个玩家轮流移动。移动包括从堆中取出 s 个筹码，其中 s ∈ S。最后一个移动的玩家获胜。
第 1.1 节中的拿走游戏是减法集合 S = {1, 2, 3} 的减法游戏。在练习 1.2 中，要求你分析减法集合 S = {1, 2, 3, 4, 5, 6} 的减法游戏。
举例说明，让我们通过找到它的 P-位置来分析减法集合 S = {1, 3, 4} 的减法游戏。只有一个终端位置，即 0。然后 1、3 和 4 是 N-位置，因为它们可以移动到 0。但是 2 必须是一个 P-位置，因为从 2 的唯一合法移动是到 1，这是一个 N-位置。然后 5 和 6 必须是 N-位置，因为它们可以移动到 2。现在我们看到，7 必须是一个 P-位置，因为从 7 的唯一移动是到 6、4 或 3，所有这些都是 N-位置。
现在我们继续类似地进行：我们看到 8、10 和 11 是 N-位置，9 是 P-位置，12 和 13 是 N-位置，14 是 P-位置。这通过归纳扩展。我们发现 P-位置的集合是 P = {0, 2, 7, 9, 14, 16, . . .}，即除以 7 余数为 0 或 2 的非负整数集合。N-位置的集合是其补集，N = {1, 3, 4, 5, 6, 8, 10, 11, 12, 13, 15, . . .}。
x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 . . .
位置 P N P N N N N P N P N N N N P . . .
长度为7的P NP NNNN模式永远重复。
100个筹码的游戏中谁会赢，第一个玩家还是第二个玩家？P-位置是模数为7的数字等于0或2。由于100除以7的余数为2，100是一个P-位置；第二个移动的玩家可以通过最佳游戏获胜。
1.5 练习。
1. 考虑第1.1节中拿走游戏的失误版本，其中最后一个移动的玩家输掉。目标是迫使你的对手拿走最后一枚筹码。分析这个游戏。目标位置（P-位置）是什么？
2. 拓展拿走游戏：(a) 假设在一堆包含大量筹码的游戏中，每轮可以取走1到6个筹码。什么是获胜策略？P-位置是什么？(b) 如果最初有31个筹码在堆中，你的获胜举动是什么（如果有）？
3. 十三点游戏。（Geoffrey Mott-Smith (1954)）从一副牌中取出每种花色的A、2、3、4、5和6。这24张牌面朝上放在桌子上。玩家轮流翻牌，计算翻过来的牌的总和随着游戏进程而计算。每个A算作一点。首先使总和超过31点的玩家输掉。看起来这相当于在31个筹码的堆上玩前一个练习中的游戏。但是有一个问题。任何整数都不能选择超过四次。
(a) 如果你是第一个移动，并且如果你使用前一个练习中找到的策略，那么如果对手一直选择4会发生什么？
(b) 然而，第一个玩家可以通过最佳游戏获胜。怎么做？
4. 找到减法集合为以下减法游戏的P-位置集合
(a) S = {1,3,5,7}。
(b) S = {1,3,6}。
(c) S = {1,2,4,8,16,…} = 所有2的幂。
(d) 如果从100个筹码开始玩这些游戏，谁会赢，第一个玩家还是第二个玩家？
- 清空和分割。 （Ferguson (1998)）有两个盒子。最初，一个盒子里有 m 个筹码，另一个盒子里有 n 个筹码。这样的位置用 (m, n) 表示，其中 m > 0 和 n > 0。两个玩家轮流移动。移动包括清空其中一个盒子，并将另一个盒子的内容分成两个盒子，每个盒子至少有一个筹码。只有一个终端位置，即 (1, 1)。最后一个移动的玩家获胜。找到所有 P-位置。
- Chomp！Fred. Schuh (1952) 发明了一种算术形式的游戏，David Gale (1974) 独立发现了一种完全不同形式的游戏。Gale 的游戏版本涉及从矩形板上移除方块，比如说 m×n 的板。移动包括取走一个方块并移走它右边和上面的所有方块。玩家轮流移动，取走 (1, 1) 方块的人输掉。这个名字“Chomp”来自想象这个板是一块巧克力，移动涉及掰下一些角落的方块吃掉。不过 (1, 1) 方块是有毒的；咬它的玩家输掉。你可以在网上玩这个游戏
http://www.math.ucla.edu/˜tom/Games/chomp.html。
例如，从一个 8×3 的板开始，假设第一个玩家在 (6, 2) 处咬掉了 6 块，然后第二个玩家在 (2, 3) 处咬掉了 4 块，留下了以下板子，其中⊗表示有毒的部分。
- 清空和分割。 （Ferguson (1998)）有两个盒子。最初，一个盒子里有 m 个筹码，另一个盒子里有 n 个筹码。这样的位置用 (m, n) 表示，其中 m > 0 和 n > 0。两个玩家轮流移动。移动包括清空其中一个盒子，并将另一个盒子的内容分成两个盒子，每个盒子至少有一个筹码。只有一个终端位置，即 (1, 1)。最后一个移动的玩家获胜。找到所有 P-位置。
- Chomp！Fred. Schuh (1952) 发明了一种算术形式的游戏，David Gale (1974) 独立发现了一种完全不同形式的游戏。Gale 的游戏版本涉及从矩形板上移除方块，比如说 m×n 的板。移动包括取走一个方块并移走它右边和上面的所有方块。玩家轮流移动，取走 (1, 1) 方块的人输掉。这个名字“Chomp”来自想象这个板是一块巧克力，移动涉及掰下一些角落的方块吃掉。不过 (1, 1) 方块是有毒的；咬它的玩家输掉。你可以在网上玩这个游戏
http://www.math.ucla.edu/˜tom/Games/chomp.html。
例如，从一个 8×3 的板开始，假设第一个玩家在 (6, 2) 处咬掉了 6 块，然后第二个玩家在 (2, 3) 处咬掉了 4 块，留下了以下板子，其中⊗表示有毒的部分。
(a) 找到第一个玩家的获胜举动（它是唯一的），证明这个位置是 N-位置。
(b) 已知第一个玩家可以赢得所有矩形起始位置。尽管证明很巧妙，但并不难。然而，这是一个“存在性”证明。它表明第一个玩家有获胜策略，但并没有提示如何找到第一步！看看你能否找到证明。这里有一个提示：删除右上角是否构成获胜举动？
- 动态减法。可以通过让减法集合取决于对手的最后一步来扩大减法游戏的类别。第12章中出现了许多早期例子 Schuh (1968)。下面是另外两个例子。（对于泛化，请参见 Schwenk (1970)）。
(a) 有一堆 n 个筹码。第一个移动的玩家可以取走任意多的筹码，至少取走一枚筹码但不能取走整堆筹码。此后，玩家轮流移动，每个玩家都不能取走比他在前一次移动中取走的筹码更多的筹码。如果 n = 44，则第一个玩家的最佳举动是什么？对于哪些 n 值，第二个玩家可以获胜？
(b) 斐波那契 Nim。（Whinihan (1963)）与 (a) 中相同的规则，除了玩家最多可以取走他在前一次移动中取走筹码数量的两倍。
这个游戏的分析比部分 (a) 中的游戏更困难，并且依赖于以 Leonardo Pisano Fibonacci 命名的数字序列，可以定义为 F1 = 1、F2 = 2，Fn+1 = Fn + Fn−1（n ≥ 2）。斐波那契序列是：1、2、3、5、8、13、21、34、55、…。解决方案得益于 Zeckendorf 定理。每个正整数都可以唯一地写成不相邻的斐波那契数之和。
一个数字可以用多种方式写成斐波那契数之和，但只有一种方法可以将其写成不相邻的斐波那契数之和。因此，43=34+8+1 是唯一的写法，因为尽管 43=34+5+3+1，但 5 和 3 是邻居。如果 n = 43，则第一个玩家的最佳举动是什么？对于哪些 n 值，第二个玩家可以获胜？在 http://www.math.ucla.edu/˜tom/Games/fibonim.html 上尝试你的解决方案。
- SOS 游戏。（来自第28届美国数学奥林匹克，1999年）
棋盘由一排 n 个方格组成，最初为空。玩家轮流选择一个空格并在其中写入 S 或 O。首先在连续的方格中完成 SOS 的玩家赢得游戏。如果整个棋盘被填满而没有任何地方连续出现 SOS，则游戏为平局。
(a) 假设 n = 4，第一个玩家将 S 放在第一个方格中。证明第二个玩家可以获胜。
(b) 证明如果 n = 7，则第一个玩家可以赢得游戏。
(c) 证明如果 n = 2000，则第二个玩家可以赢得游戏。
(d) 如果 n = 14，谁（如果有人）赢得游戏？
