ACM程序设计程序设计杭州电子科技大学刘春英acmhdu.edu.cn9/1/20241周六月赛周六月赛，你你 了吗？了吗？准备好9/1/20242每周一星（每周一星（11）：荒古劳神圣体荒古劳神圣体9/1/20243第十第十二二讲讲组合博弈入门组合博弈入门（Simple Game Theory）9/1/20244导引游戏导引游戏(1) (1) 玩家：玩家：2 2人；人；(2) (2) 道具：道具：2323张扑克牌；张扑克牌；(3) (3) 规则：规则：n游戏双方轮流取牌；游戏双方轮流取牌；n每人每次仅限于取每人每次仅限于取1 1张、张、2 2张或张或3 3张牌；张牌；n扑克牌取光，则游戏结束；扑克牌取光，则游戏结束；n最后取牌的一方为胜者。最后取牌的一方为胜者。9/1/20245基本思路？基本思路？请陈述自己的观点请陈述自己的观点9/1/20246第一部分第一部分简单取子游戏简单取子游戏（组合游戏的一种）（组合游戏的一种）9/1/20247什么是组合游戏什么是组合游戏(1)有两个玩家；(2)游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；(3)游戏双方轮流操作；(4)双方的每次操作必须符合游戏规定；(5)当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；(6)无论如何操作，游戏总能在有限次操作后结束；9/1/20248概念概念: :必败点和必胜点必败点和必胜点(P(P点点 & N & N点点) )n必败点必败点(P(P点点) ) : :前一个选手(P Previous player)将取胜的位置称为必败点。 n必胜点必胜点(N(N点点) ) : :下下一个选手(Next player)将取胜的位置称为必胜点。 9/1/20249必败必败( (必胜必胜) )点属性点属性(1) (1) 所有终结点是必败点（所有终结点是必败点（P P点）；点）；(2) (2) 从任何必胜点（从任何必胜点（N N点）操作，至少有点）操作，至少有一种方法可以进入必败点（一种方法可以进入必败点（P P点）；点）；(3)(3)无论如何操作，无论如何操作， 从必败点（从必败点（P P点）都点）都只能进入必胜点（只能进入必胜点（N N点）点）. .9/1/202410取子游戏算法实现取子游戏算法实现步步骤骤1:1:将所有终结位置标记为必败点（将所有终结位置标记为必败点（P P点）；点）；步骤步骤2: 2: 将所有一步操作能进入必败点（将所有一步操作能进入必败点（P P点）的点）的位置标记为必胜点（位置标记为必胜点（N N点）点）步骤步骤3:3:如果从某个点开始的所有一步操作都只能如果从某个点开始的所有一步操作都只能进入必胜点（进入必胜点（N N点）点） ，则将该点标记为必败点，则将该点标记为必败点（P P点）点） ；步骤步骤4: 4: 如果在步骤如果在步骤3 3未能找到新的必败（未能找到新的必败（P P点），点），则算法终止；否则，返回到步骤则算法终止；否则，返回到步骤2 2。9/1/202411课内练习课内练习: :nSubtraction Games:subtraction set S = 1, 3, 4x:01234567891011121314Pos:PNPNNNNPNPNNNNP9/1/202412实战练习实战练习nkikis gamekikis game 9/1/202413第二部分第二部分NimNim游戏游戏9/1/202414NimNim游戏简介游戏简介(1)有两个玩家；(2)有三堆扑克牌（比如：可以分别是5，7，9张）；(3)游戏双方轮流操作；(4)玩家的每次操作是选择其中某一堆牌，然后从中取走任意张；(5)最后一次取牌的一方为获胜方；9/1/2024159/1/202416初步分析初步分析n(0, 0, 0) n(0, 0, x) n(0, 1, 1) n(0, k, k) nP-position nP-position nP-position nN-position n(14, 35, 46) n? 9/1/202417引入概念引入概念：Nim-SumNim-Sumn定义定义: : 假设假设 (xm x0)2 和和(ym y0)2 的的nim-sum是是(zm z0)2,则我们表示成则我们表示成 (xm x0)2 (ym y0)2 = (zm z0)2, 这里这里，zk = xk + yk (mod 2)（k=0m）.9/1/202418定理一：定理一： 对于对于nimnim游戏的某个位置游戏的某个位置(x(x1 1,x,x2 2,x,x3 3),),当当且仅当它各部分的且仅当它各部分的nim-sumnim-sum等于等于0 0时（即时（即x x1 1x x2 2x x3 3=0=0），则当前位于必败点。），则当前位于必败点。定理一也适用于更多堆的情况定理一也适用于更多堆的情况9/1/202419定理一的证明定理一的证明 9/1/202420思考（思考（1）：）：n有了定理一，如何判断某个游戏有了定理一，如何判断某个游戏的先手是输还是赢？的先手是输还是赢？9/1/202421思考（思考（2）：）：n对于必胜点，如何判断有几种可对于必胜点，如何判断有几种可行的操作方案？行的操作方案？9/1/202422实例分析实例分析(HDOJ_1850)nBeing a Good Being a Good Boy in Spring Boy in Spring FestivalFestival 9/1/202423第三部分第三部分Graph Games &Graph Games &Sprague-Grundy Sprague-Grundy FunctionFunction9/1/202424What is the graph game ?(1) Player I moves first, starting at x0.(2) Players alternate moves.(3) At position x, the player whose turn it is to move chooses a position y F(x).(4) The player who is confronted with a terminal position at his turn, and thus cannot move, loses.9/1/202425Example about graph game:0,0,01,0,00,0,10,1,05,7,92,0,09/1/202426The Sprague-Grundy Function.Definition: The Sprague-Grundy function of a graph, (X,F), is a function, g, defined on X and taking non-negative integer values, such thatg(x) =minn 0 : ng(y) for y F(x). (1)In words, g(x) the smallest non-negative integer not found among the Sprague-Grundy values of the followers of x.g(x) =mexg(y) : y F(x). (2)9/1/202427Use ofthe Sprague-Grundy Function:P-positions: Positions x for which g(x) = 0 N-positions: Positions x for which g(x) 0 9/1/202428Exercise:nWhat is the SG-value of the subtraction game with subtraction set S = 1, 2, 3?x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14. . .g(x) 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2. . .9/1/202429Question:What can the S-G value describe?9/1/202430Part 4:Sums of Combinatorial Games9/1/202431What is so-called “Sums of Combinatorial Games”?9/1/202432Theorem 2.If gi is the Sprague-Grundy function of Gi , i = 1, . . . , n, then G = G1 + + Gn has Sprague-Grundy function g(x1, . . . , xn) = g1(x1) gn(xn).9/1/202433Applications:Sums of three Subtraction Games.In the first game: m = 3 and the pile has 9 chips. In the second: m = 5 and the pile has 10 chips. In the third:m = 7 and the pile has 14c hips.g(9, 10, 14) =?9/1/202434附:参考源码(HDOJ-1536)n#include#include#includeusingnamespacestd;intk,a100,f10001;intmex(intp)inti,t;boolg101=0;for(i=0;ik;i+)t=p-ai;if(t0)break;if(ft=-1)ft=mex(t);gft=1;for(i=0;i+)if(!gi)returni;nintmain()intn,i,m,t,s;while(scanf(%d,&k),k)for(i=0;ik;i+)scanf(%d,&ai);sort(a,a+k);memset(f,-1,sizeof(f);f0=0;scanf(%d,&n);while(n-)scanf(%d,&m);s=0;while(m-)scanf(%d,&t);if(ft=-1)ft=mex(t);s=sft;if(s=0)printf(L);elseprintf(W);printf(n);9/1/202435课后练习n201403ACM程序设计作业（程序设计作业（12） 刘春英老师刘春英老师9/1/202436原来原来n学习学习也可以也可以很很快乐快乐9/1/202437Welcome to HDOJWelcome to HDOJThank Thank You You 9/1/202438