讲义组合游戏论

1、论（1）Zhou Yuan组合by Zhou YuanOutlineCh.1 简单组合Ch.2 Nimby Zhou YuanCh.1 简单组合的组合（two-game） 两人双方知道所有信息（perfect information）没有随机事件（no chance moves） 确定的结果（a win-or-losee）by Zhou Yuan示例如下 有两个者：I和II桌上有21个石子每个人可以从桌子上拿走1, 2, 3个石子 I开始，两人轮流取石子 拿走最后一个石子的者获胜若参加后手必胜者都足够聪明，判断先手还是by Zhou Yuan组合称为组合：抽象定义(Combinatorial

2、Game)如下 有两个参与者 有一个很多可能的状态的集合（一般是有限集） 若两个人移动规则都一样，则称为公平的（Impartial），这是的主要情况 两个者交替移动 某个玩家不能移动时结束一般的：最后一个移动的玩家是胜者相反的（最后一个移动的玩家失败）也是一种规则在有限回合内一定结束by Zhou Yuan取石子的状态：桌子上：递推解法的石子数 0个，1个，2个，21个判断每一个状态先手必胜(N)/先手必败(P)先手必胜iff.某个后继状态先手必败先手必败iff.任何后继状态先手必胜没有后继的状态先手必败：0先手必败012345678910resultPNNNPNNNPNNby Zhou Yu

3、an构造必胜策略对于任何一个先手必胜(N)状态后继状态中，必有一个先手必败(P)状态选择这个状态，先手就可以保证必胜by Zhou Yuan观察：的平衡构造必胜策略时，始终将败局面留给一方看来：石子数n是4的倍数就是平衡点 预定的胜利者总是要平衡 预定到失败者面对平衡点，只能打破平衡，直平衡的主导权在胜利者，终止局面一定是平衡点问题在于：寻找的平衡点by Zhou Yuan)练在取石子的石子中，双方只能取走如下数目 1, 3, 5, 7 1, 3, 6 1, 2, 4, 8, 16, 2的整次幂那么哪些状态是先手必胜的？by Zhou Yuan练习(2)有两堆非空石子，一堆m个，一堆n个用(m

4、, n)表示这样的一个状态双方移动规则选择扔掉一堆石子把另一堆石子分成两堆（每堆非空）唯一的结束状态(1, 1)，最后移动这胜利求所有的先手必胜状态by Zhou Yuan练习(3)在一个棋盘上的双方移动规则：棋盘就是状态选择一个方格（不能是左下角的）移走这个方格和其右上方的所有方格不能移动者失败一个先手必胜的状态矩形棋盘：先手必胜by Zhou Yuan练习(4)一列n方格，初始都是空的双方轮流选择一个空方格写上S或者O第一个完成一个SOS的玩家胜利可能有平局证明n=4, 第一个人在第一个方格写下一个S, 则后者可以获胜n=7时先手必胜，n=2000时先手必败n=14时结果如何？by Zho

5、u YuanCh.2 Nim规则（两人） 桌上有很多堆石子，第i堆石子有xi个者轮流选择一堆石子，从中拿走至少一粒（最多将这一堆取完） 所有石子取完时，最后一个移动的玩家胜利by Zhou Yuan简要分析只有一堆非空石子：先手必胜（直接取完）有两堆非空石子 平衡点：两堆石子相同:(1,1), (2,2), (3,3) 先手从某一堆中拿走一定量石子打破平衡后手可以从另一堆中取走同样多石子终止状态(0,0)也属于平衡点：先手必败因此在上述平衡点先手必败其他非平衡状态都可以到达某个平衡状态先手必胜平衡by Zhou YuanNim和定义两个非负整数的Nim和定义为它们二进制形式的异或和例交换律结合

6、律by Zhou YuanNim和(contd)=求证：证明： 于是元by Zhou Yuan定理1：Boutons TheoremNim中一个局面是先手必败当且仅当每一堆石子的Nim和是0如4堆石子时，条件为证明思路为每一个胜局面找到一个必败的后继局面证明必败局面的后继都是胜局面（或无后继）by Zhou Yuan证明为胜局面找一个必败后继局面：构造胜局面：Nim和大于0在Nim和的竖式中找到最高的非0位选择一堆石子：其二进制在该位上是1可以让这堆石子变少使得Nim和为0：败局面11110111000110101010100011101111by Zhou Yuan证明(contd)Nim和是0的败局面 唯一的终止局面，每一堆石子都是0其他局面的每一个后继局面反若在第一堆石子中取走一些，Nim和仍为0，于是后继局面的Nim和不为0：胜局面by Zhou Yuan练习(5)一个一维棋盘，从左到右0,1,2,3,棋盘上有一些硬币:一个方格上可以有多个双方轮流移动 选择一枚硬币，将它移至左边的任意一个方格所有硬币都到0号位最后移动者胜利结束by Zhou Yuan练习(6)著名的Turning Turtles一列n个Turtles，头朝上(H)/尾朝上(T)双方轮流移动，最后移动者胜利选择一个H改为T同时还能选择左边的任何一个Turtle