博弈论
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 Turning游戏 例子
二维空间的Coin Turning游戏 Nim复杂情况 方格游戏 练习
6. Green Hackenbush 竹竿
Green Hackenbush on tress
Green hackenbush 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根，至多拿走3根； （4） 轮流操作，从玩家1开始；
（5） 拿走最后一根薯条的玩家赢（不能继续的玩家输）。
我们怎么分析这个游戏呢？有某个玩家必胜的策略吗？你更希望成为玩家1还是玩家2？这是个好决策吗？
我们从最后的状态到初始状态来分析这个游戏。这种方法有时叫做向后归纳法。 如果只剩下1，2或3根薯条，那么接下来的玩家可以一次取完并且获得胜利。
假设现在剩下4根薯条。那么接下来的玩家一定会留下1，2或3根薯条，这时他的对手就赢了。所以4根薯条的状态对接下来（next）的玩家是败态，对前一位（previous）玩家是胜态。
如果剩下5，6或7根薯条，那么next玩家可以取4根从而得到胜利。
如果剩下8根薯条，next玩家一定会留下5，6或7根薯条，从而使得previous玩家获胜。
如此一来，我们希望能够使状态变为0，4，8，12，16从而获胜。现在我们来分析以下21根薯条的状态。因为21不能被4整除，所以先手获胜。唯一最佳的操作是先手拿走1根薯条，留下20根薯条（20根薯条是我们希望的状态）。
1.2什么是组合游戏？现在我们来给组合游戏一个更精确的定义。满足以下条件的游戏叫做组合游戏：
（1） 有两个玩家；
（2） 游戏的操作状态是一个有限的集合；
（3） 指定操作规则（操作规则是一样的则为impartial否则，为patizan）； （4） 双方轮流操作；
（5） 游戏在不能继续操作时结束。在normal play rule下，最后操作的玩家获胜；在
misere play rule下则相反。如果一个游戏无法停止，就叫做draw（纸牌）。但是一般情况下，我们会增加一条the Ending Condition规则防止draw的出现。
（6） 无论如何操作，游戏总是能在有限次操作后结束。
要注意的是这个定义省略的地方。随机的操作，比如掷骰子或发牌是不允许的。这些规则对应的游戏有双陆棋和美国扑克。组合游戏是一种既定的游戏：同时操作和暗操作是不允许的。这些规则对应的游戏有battleship和石头剪子布。在这些条件下，我们把注意力集中到公正的游戏上来，一般考虑normal play rule。
1.3 P态和N态。回到我们1.1节讲的tale-away 游戏，我们认为0，4，8，12，16…是Previous玩家获胜的状态，而1，2，3，5，6，7，9，10，11，…是Next玩家获胜的状态。前者我们把它叫做P状态，后者我们叫做N状态。在1.1节的take-away游戏中，P状态就是那些薯条的根数可以被4整除的状态。
在公平的组合游戏中，可以从终态通过利用下面的程序提供的归纳法，寻找到N态
和P态的规律。我们把无法继续操作的状态叫做终态。这个算法其实就是我们在1.1节中用到的算法。（关于中英文不同的标识方法，我自己的理解是，在操作前，我们需要的是N态——所以称为必胜点，然后把N态变为P态，那么我们就获胜了） Step 1：把所有终态标记为P态（必败点）； Step 2：把所有能够进入P态的状态标记为N态（必胜点）；
Step 3：如果从某个点开始的所有一步操作都只能进入N点（必胜点） ，则将该点标记为P点（必败点）；
Step 4：如果没有找到新的P点就停止，否则回到step2。
很容易看出，把状态变成P的玩家获胜。当状态是P状态时，我们的对手只能进入N态（3），这时你像（2）那样，又进入了P状态，最后由（1）知道，我们赢了。
下面是一些P态和N态的性质（公平的组合游戏里都有效，考虑normal play rule并排除draw的情况）：
特征性质。P态和N态可以由以下三条递归定义： （1） 所有终态都是P态；
（2） 每个N态都至少有一种办法变为P态；
（3） 从某个P态出发，无论怎样操作，都会进入N态。
在misere play rule下，只需要把第一条中终态标记为N态。
4.差集游戏。我们来考虑一类像1.1节里提到的take-away游戏一样的组合游戏。假设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态（至少存在一种方法使当前态变为P态）。但是2是一个P态，因为它只能变为1。那么5，6都是N态因为它们都能变为2。7也是一个P态，因为它只能变为6，4，3（都是N态）。
以此类推，我们可以得到P态集为P={0,2,7,9,14,16}，模7余0或2的非负整数集。N态集则是它的补集，N={1,3,4,5,6,8,10,11,12,13,15}. 如下表：
模式PNPNNNN不断循环…
如果有100根薯条，谁会赢呢？100模7余数是2，对应为P态，这就是说，先手必败，后手必胜。
1.5相关练习
1. 考虑misere版本的take-away游戏（1.1节）。给出P态集。 2. 概括take-away游戏：（a）假设薯条根数为n，S={1,2,3,4,5,6}，必胜的决
策是什么？P态集呢？（b）如果有31根薯条，你怎么获胜？ 3. 31游戏。(Geoffrey Mott-Smith(1954))从一副扑克牌中拿出每种花色的A，2，
3，4，5，6。这24张牌面朝上放在桌子上。两个人轮流把扑克翻过去，翻过去的数字总和将被计算作为游戏的进展。每张A被计算为1.首先把数字总和超过31的人失败。这很有点像我们讲过的31根薯条的游戏。但是这里有个条件限制。任意一张牌不能被抽出超过4次。
（a） 如果你是第一个操作的人，如果你用之前我们讲过的策略，如果
对手一直选择4会怎样？
（b） 然而，先手还是可以通过完美的操作必胜。怎么操作呢？ 4. 寻找以下S对应的P态集：
(a) S={1,3,5,7} (b) S={1,3,6}
(c) S={1,2,4,5,16…}=2的n次幂
(d) 在以上情况下，先手会获胜还是后手呢？
5. Empty and Divide.(Ferguson(1998))有两个箱子。开始时，一个箱子里有m
根薯条，另一个箱子里则有n根薯条。这种状态被表示为（m,n），m>0,n>0。两人轮流操作。每次操作包括：把一个箱子取空，把另一个箱子的薯条分到两个箱子里，使得每个箱子里的薯条根数至少为1。这儿有一个唯一的终态，即（1，1）。最后操作的人为胜。请找出所有P态。
6. Chomp!Fred发明了一种游戏。Schuh(1952)被David Gale(1974)从一种算法
形式中被独立地分出来。Gale的游戏版本包括从一个矩形木板（m*n）中移走一些正方形。两人轮流操作。拿走（1，1）正方形的人被判为输。Chomp的名字来自于把木板想象成巧克力棒，移走就变成了“吃掉”。但是（1，1）正方形这一块是有毒的，谁吃到它就失败了。
比方说，从一个8*3的巧克力上开始，假设第一个玩家从（6，2）的位置吃了6小块；然后第二个玩家从（2，3）的位置吃了4小块，如图：
（1，1） 位置表示有毒。
（a） 证明这是一个N态（找到一个必胜的办法）；
（b） 试着证明，当巧克力是一个矩形时，先手必胜。提示：也许把右
上角的巧克力移走就构成了胜局呢。
7. Dynamic subtraction.我们前面讲的差集游戏可以这样扩展：将玩家的差集
规则和前一位玩家的操作联系起来。很多早期的例子在Schuh(1968)的第十二章出现了。现在我们来看两个其它的例子（如果想知道一般情况，请查看Schwenk(1970)）。
（a） 有一堆n根的薯条。先手第一次可以拿走1~n-1根薯条。然后两人
轮流操作，每个玩家至少拿一根，至多拿前一位玩家所拿的根数。如果n=44，那么先手要怎么操作才能赢？n为多少时，后手必胜？
（b） Fibonacci Nim。（Whinihan(1963)）和(a)差不多的规则，只是每位
玩家可以最多一次拿前一位玩家所拿的两倍。这个游戏比(a)更为复杂，因为它建立在斐波拉契数上。下面给一个定理，使得我们更容易思考：
Zeckendorf’s Theorem.任意一个正整数都能被唯一地写成一些不相邻（当然也不相等）的斐波拉契数之和。例如，43=34+8+1是唯一的，虽然也有43=34+5+3+1，但是5，3是相邻的。如果n=43，先手怎么获胜呢？n为多少时，后手必胜？可以看看
http://www.math.ucla.edu/~tom/Games/fibonim.html。 8. SOS游戏。（28届美国数学奥林匹克周年赛，1999）一块木板由一行正方
形组成，初始化为空。玩家可以选择一块空正方形并在上面写上S或者是O。谁先写出连续的SOS谁就获胜。如果谁都不能写成，那么这个游戏就是一个draw。
(a) 假设n=4，且先手在第一块正方形上写了S。证明后手必胜。 (b) 证明当n=7时，先手必胜。 (c) 证明n=2000时，后手必胜。 (d) 如果n=14，谁会赢呢？
2. Nim游戏。
最有名的take-away游戏就是Nim游戏，如下所述进行。有三堆薯条，根数分别为x1,x2,x3。（可以假定为5，7，9；这样会很有趣）。两个玩家轮流操作。每次操作是选择其中一堆，拿走这一堆中的任意根数（可以把这一堆拿完）。谁拿走最后一根薯条就获胜。
2.1 初步的分析。这儿只有一个终态，即（0，0，0），它是一个P态。对Nim游戏来说，
拿完一堆并不是什么大事，你可以直接把整堆拿走。因此，所有（0，0，x），x>0的状态都是N态。想象一下两堆的情况。很容易发现如果两堆薯条的根数是一样的话，这就是一个P态。作为后手，你只需要看先手拿了多少根你就跟着在另一堆中拿一样的根数就可以了，这样一直到终态，你一定获胜。
如果3堆都是非空的，情况就更为复杂。显然，（1，1，1），（1，1，2），（1，1，3），（1，2，2）都是N态，因为它们都能被变为（1，1，0）或是（0，2，2）。于是可以推 出
（1，2，3）是一个P态。接着我们还能发现（1，4，5）和（2，4，6）也是P态。但是 这很难推广。（5，7，9）；（15，23，30）呢？
如果你按上述所说你能发现一个规律。但是为了节约我们的时间，我把方法说给你听。因为这个解答有些难以想到而且又包含了一个叫做nim-sum的东西，有根据的解答是不那么显然的。等一会，我们将用P态和N态的基本概念来给出有根据的证明。
2.2 Nim-Sum。两个非负整数的nim和是它们的2进制不进位加法（即按位异或）。
Nim和的性质：满足交换律和结合律。
具体证明nim游戏和按位异或运算关系的定理就是我们将要提到的C.L.Bouton定理。 定理1.状态（x1,x2,x3）在nim游戏中，当且仅当x1^x2^x3=0时它是一个P态。（例子略）
2.3 更多堆情况的nim游戏。我们发现1堆的nim游戏是微不足道的，2堆的是很容易的。
但是既然3堆的情况那么复杂，4堆的情况也许会更为复杂吧。非也。定理1其实对多堆的情况也适用！（x1,x2,x3,x4）是P态当且仅当x1^x2^x3^x4=0。以下我们将来证明有限堆时的情况。
2.4 Bouton定理的证明。设P表示nim和为0的状态集，N表示P的补集（nim和为正整数
的状态集）。我们来验证1.3节中提到的三条性质。
（1） 所有的终态都是P态。这是当然的啦。唯一的终态是任何一堆里都没有薯条，
即0^0^0…^0=0。
（2） 对每一种N态，都有一种办法使得它变为一种N态。现在我们来构造一次这样
的操作。现在注意当且状态下的nim和，尤其看到它的二进制表示的最左边的那个1。任意选择根数的二进制在这一位也有1的一堆，并把选择的这一堆的根数进行调整，使得二进制根数和每一列的1的个数都是偶数。（这是一定能做到的，且总的薯条根数在减少，因为与nim和最左边的1相同的位置上该堆的二进制数已经变为了0）这样一来，我们就成功地把一个N态变为了P态。
（3） 对于每一种P态，都只能进入一个N态。如果(x1,x2,…)是一个P状态且x1经
过操作后变为了x1’;x1’ 这三条特性保证了P的确是P态集。 有趣的是，从第（2）点我们看到，在nim游戏中，从N状态到P状态转换的次数和sum和最左边1的个数和（奇数）是相等的。特别地，胜者的操作次数是一个奇数。 2.5 Misere Nim。如果我们考虑misere play role，会怎么样呢？在任意的状态下，我们还 能找到谁会必胜，且给出一个简单的取胜办法吗？这初看起来很难，其实只要想一下，这个问题很简单。 这里给出Bouton对付misere情况的最佳方案。当还有至少两堆的薯条根数大于1时，你就像在normal情况下一样操作。当你的对手把情况变为只有一堆的薯条根数大于1时，你只需要把那堆薯条拿走并留下一根，你就能获胜了。 这是能做到的。因为你的完美方案在nim游戏中并不会让你只留下薯条根数大于等于1的一堆（因为nim和要=0）；而且你的对手不能把两堆都大于1根的薯条在一次操作内变为没有一堆大于1根。所以最后游戏最后会发展到只有一堆根数大于1的薯条，而且这时，一定是你来操作。 类似的分析在其它的博弈题里同样适用。但是一般说来，misere情况下的博弈比normal规则下的博弈要复杂得多。有些游戏的normal情况相当简单，可是在misere情况下却非常复杂。例如我们在第三章第四节将要提到的Kayles and Dawson’s chess。 2.6 相关练习 1.（a）略 （b）略 2.给出下列情况的必胜策略： （a）3堆，分别是12，19，27； （b）4堆，分别是13，17，19，23； （c）如果是在misere规则下，以上两种情况的必胜呢？ 3. Nimble.这个游戏是在一块由一行正方形组成的游戏板上进行的，正方形被依次标上序 号0，1，2，3，?有限个硬币被放在正方形上，一个正方形上可能放不止一个硬币。一次操作包括拿走一个硬币并把它放到左边的任意一个正方形上，可能移到一些硬币之前也可能移到一个已经有硬币的正方形上。两人轮流操作。当所有硬币都在正方形0上时，游戏结束。最后操作的玩家获胜。证明这其实就是nim游戏。下图的情况下，谁必胜？如果是先手必胜，请给出必胜策略。（hint:其实当然是先手必胜了） 4. Turning Turtle。另一类博弈，根据H.W.Lenstra所述，是在一行硬币上进行的，操作可以把一些硬币从正面翻转到背面或者从背面翻转到正面。看第五节的一些值得注意的定理。这儿有一个简单的例子叫做turning turtle。 一行有n个硬币的水平线被随机地摆出（随机是指它们是背面朝上还是正面朝上）。一次操作包括把一个硬币从正面翻转到背面；在必要时，也可以把这个硬币左边的一个硬币翻转过来。比如说下面这个n=13时的例子（H代表正面朝上，T代表背面朝上）： 一个可能的操作是，把第9个硬币翻转过来，顺便把第4个硬币翻转过来。 (a) 证明这个游戏在其实也是nim游戏的一个翻版。（hint:第n个位置的H可以用来表 示有n根的薯条） (b) 假设(a)是对的，请给出以上例子的必胜方案。 (c) 你可以在网上试一下这种类似的游戏，网址是： http://www.chlond.demon.co.uk/Coins.html。 5. Northcott’s Game。（这一段的英文好懂难译，建议看原题） （关于这一题我没有想明白） 6. Staircase Nim。（Sprague(1937)）一个n阶的楼梯，在某些阶上可能放有一些硬币。 用（x1,x2,?,xn）来表示各个阶上有的硬币数。一次操作包括从任意一层（记为j）阶上移动任意（至少为1至多全部拿走）个硬币到下一层阶（j-1）上。到达第0阶的硬币将从游戏中拿走。游戏在所有硬币达到0阶的时候结束。两人轮流操作且最后一次操作者胜。 证明（x1,x2,?,xn）是一个P态当且仅当（x1,x3,?xk）（即奇数阶状态）是nim游戏中的P态。 7. Moore’s Nim(k)。E.H.Moore于1910年提出了一般化的nim游戏和讲究的定理，名叫 Nim(k)。Nim(k)游戏和nim游戏基本相同，只是一次操作必须从k堆薯条里移走薯条（k是给定的且至少有一堆中要拿走1根）。K=1时，它就是nim游戏。 Moore的定理表示，状态（x1,x2,?,xn）是一个P态当且仅当x1到xn按位（二进制） 进行模(k+1)运算时的结果为0. （a） 考虑练习3的nimble游戏但是有一点点改动，即每次操作玩家可以移动1 或2个硬币到它的左边。注意这其实就是nim(k)游戏，k=2的情况。用Moore的定理证明练习3的状态是一个N态，并找到一个变为P态的办法。 （b） 证明Moore的定理。 （c） 考虑一下，misere版本的Nim(k)游戏的最佳方案。 （关于这一题，我已经给出了证明，需要的可以问一下） 3.图表游戏 我们现在来在有向图游戏上给出一个与组合游戏等价的描述。这包括第一章和第二章里面描述的游戏。这可以通过用有向图的节点表示状态，用有向图的边表示操作来实现。接下来我们将定义一个被叫做SG（Sprague-Grundy）的函数，它包含了除了P态和N态的更多信息。 3.1 有向图游戏。我们先给出有向图的数学定义。 Definition。有向图G可以表示为（X，F），X是一个非空节点（即状态）集；F是一个关于x（x∈X）的函数，它是X的一个子集。对于一个给定的x，F(x)表示从状态x出发可以到达的状态（叫做x的followers）。如果F(x)为空，则x是一个终态。 一个二人博弈可以在一张有向图上进行，从x0(初始状态)出发并遵循以下规定： （1） 玩家1从x0开始先操作； （2） 双方轮流操作； （3） 在x状态时，进行操作的玩家将它变换到一个状态y∈F(x)； （4） 在一个玩家操作前游戏已经到达终态则该玩家被判为输。 根据定义，图游戏会在无限次操作进行时无法停止。为了避免这种情况和其它问题的发生，我们现在考虑这样的图：无论从哪个x0状态出发，都有一个与x0相关的整数n，使得每条从x0出发的路的长度都小于等于n。这样的图叫做[Progressively Bounded]。如果X是有限集合，这意味着这张图中没有环（环是这样一种路，x0,x1,?,xm中x0=xm且m>3）。 例如，我们在1.1节曾经分析过的差集游戏，S={1,2,3}就是一个图游戏的代表。设X={0,1,?,n}是状态集。空堆是终态，故F(0)为空集。同样的，F(1)={0},F(2)={0,1};当2<=k<=n时，F(k)={k-3,k-2,k-1}。这样就把游戏定了下来。 图3.1 S={1,2,3}时差集游戏所对应的有向图 把这样的有向图画出来是十分有益的。点表示节点，线表示可以做的操作。箭头表示操作的方向。图3.1表示了有10根薯条时的有向图。 3.2 Sprague-Grundy（SG）函数。图表游戏可以通过P态和N态集来分析。也可以用SG函数来分析。 Definition。一个有向图（X,F）的Sprague-Grundy函数是这样一个定义在X上的g函数，值域属于非负整数集，满足： g(x)=min(n>=0:n≠g(y)对每一个y∈F(x)). （1） 总的来说，g(x)是不属于x后继的SG值的最小非负整数。如果我们定义minimal excludant(也叫做mex)为不属于该集合的最小非负整数，我们就能简单地写成： g(x)=mex{g(y):y∈F(x)}. (2) 注意g(x)是被递归定义的。也就是说，g(x)是根据x的所有可能后继的SG值来定义的。而且，这个递归是主动工作的。对于终态x来说，定义暗示了g(x)=0，因为F(x)为空。对于只能到达终态的状态x，g(x)=1。在下一节要讲的例子当中，我们将会发现g(x)用到了这样的归纳方法。这对所有的progressively bounded图都适用，并且能够证明，对所有这样的图SG函数都存在，是唯一而有限的。但是，其它的图要求更精细的技巧，这我们在3.4节中将会讲到。 如果给出一个图的SG函数，那么我们能够很容易地分析对应的有向图游戏。g(x)=0的状态是P态而其它的状态都是N态。必胜的办法是，在每一次操作时，把当前状态变为g(x)=0的状态。在1.3节中这能被很好地验证： （1） 如果x是一个终态，g(x)=0； （2） 如果状态x的g(x)=0，那么它的所有后继y的g(y)≠0； （3） 如果状态x的g(x)≠0，那么它至少有一个后继y使得g(y)=0。 故SG函数比P态集和N态集携带了更多的信息。这些额外信息能做什么呢？我们在第四章将会看到，SG函数使得我们能够分析图游戏的sum。 3.3 例子。 1.我们用图3.2来描述SG值的递归法（把SG值标在节点上）。这个方法能够容易地找到后继SG值都已知的状态x的SG值。反复应用第（1）条或（2）条来计算SG值，直到所有的SG值都被找到。 在计算之前，所有终态的SG值都被标记为0。这儿有4个终态，分别在图的左边和下方。接下来我们找所有后继都是终态的状态，即有a点，把它的SG值标记为1。 然后是b,c；它们的后继节点的SG值都已经被计算出来了。g(b)=2；g(c)=1。?以此类推，算出所有点的SG值。 2.差集游戏的S={1,2,3}时，SG值是怎样的呢？我们依照定义的方法，可以推出： 3.At-Least-Half。考虑一堆的游戏，每次操作你必须拿走至少当前根数的一半的薯条。唯一的终态是0。我们能够递归地计算SG函数： 我们发现，g(x)能够被表示成g(x)=min{k:2^k>x}。 事实上，这是一个很愚蠢的游戏。先手可以在第一次操作的时候拿走所有的薯条！计算SG函数有什么用呢？ 这个问题将在下一章内给出解答。如果这个游戏考虑的是n堆的情况而不是1堆的情况，那么这个游戏就不是那么简单了。下章要讲的定理将会告诉我们怎么把nim-addition和SG函数联系起来解决多堆的问题。 3.4 更一般化的SG函数。让我们暂时看一下当图不再是progressively bounded，或者含有环时的问题。 首先，假设progressively bounded条件放宽到progressively finite（每条路都是有限长的）。这个条件等价与我们说组合游戏（1.2节）时的条件（6）。图中仍然不允许出现环。 我们给一个例子，它是progressively finite而不是progressively bounded。这是一个progressively finite图，因为游戏将在有限次操作后结束；但是它不是progressively bounded图，因为并不是每一条路的长度在初始情况时都能够知道它们的上限。
