博弈论 By Thomas S.Ferguson /译者：xly 第一部分：公平的组合游戏 1. Take-Away游戏 1.1 一个简单的 Take-Away游戏 1.2 什么叫做组合游戏？ 1.3 P 态与 N 态 1.4 差集游戏 1.5 相关练习 2. Nim 游戏 初步分析 Nim-sum 多堆的 Nim 游戏 Bounton 理论的证明 Misere 版本的 Nim 游戏 相关练习 3. 图表游戏 有向图游戏 SG 函数 相关例题 一般图的 SG 函数 4. 组合游戏的和 n 个图表游戏的和 SG 定理 有关应用 Take-and-Break 游戏 相关练习 5. Coin Tu rning 游戏 例子 二维空间的 Coin Tu rning 游戏 Nim 复杂情况 方格游戏 练习 6. Green Hackenbu sh 竹竿 Green Hackenbu sh on tress Green hackenbu sh on general Rooted Graphs 练习 参考资料 第一部分：公平的组合游戏 1. take-away 游戏 组合游戏是一种两人游戏，给定足够的条件时，当一方无法继续操作时，游戏的胜负就出来了。这种游戏的胜负取决于一系列的状态，包括初始状态和正准备操作的玩家。游戏双方轮流操作，直到达到最终状态。最终状态的意思是，该状态已经不能被操作。这时，胜负已分。 这里介绍两本关于组合游戏的主要资料。一本是 J.H.Conway 写的 On Numbers and Games，学术出版社 1976 年出版。这本书介绍了很多关于这方面的基本思想，加快了今天这块领域的发展。更适合这堂课的另一本参考书，Berlekamp，Conway 和 Guy 写的winning ways for your mathematical plays，学术出版社 1982 年出版，是一套两册的平装本。这本书介绍了很多有趣的游戏，学数学的本科生可以理解它。这些理论可以分为两类，Impartial games 是指任意给定一个状态，对游戏双方而言将要采取的操作是一样的；而partizan games 是说，给定一个状态，游戏双方要采取的操作会有不同。比如国际象棋就是一种 partizan game。在第一部分中，我们只研究“公正的游戏”。关于公正的组合游戏入门可以参见 Richard K.Guy 写的 Fair Game（刊载于 1989 年 COMAP 数学探索系列）。我们从一个简单的例子开始。 1.1 一个简单的 Take-Away Game。下面是这个公正组合游戏的一些规则（从一堆薯条里拿走一些）： （1） 有两个玩家，我们分别把他们标记为 1 号和 2 号； （2） 桌上有一堆薯条，共 21 根； （3） 一次操作可以拿走 1，2，3 根薯条，必须至少拿走 1 ...
