《组合博弈入门报告优秀PPT.ppt》由会员分享，可在线阅读，更多相关《组合博弈入门报告优秀PPT.ppt（38页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、ACM程序设计程序设计杭州电子科技高校刘春英acmhdu.edu4/14/20231今日，今日，你你 了吗？了吗？AC4/14/20232每周一星每周一星（9 9）：）：Hugo4/14/20233第十讲第十讲组合博弈入门组合博弈入门（Simple Game Theory）4/14/20234导引游戏导引游戏(1)(1)玩家：玩家：2 2人；人；(2)(2)道具：道具：2323张扑克牌；张扑克牌；(3)(3)规则：规则：游戏双方轮番取牌；游戏双方轮番取牌；每人每次仅限于取每人每次仅限于取1 1张、张、2 2张或张或3 3张牌；张牌；扑克牌取光，则游戏结束；扑克牌取光，则游戏结束；最终取牌的一方
2、为胜者。最终取牌的一方为胜者。4/14/20235基本思路？基本思路？请陈述自己的观点请陈述自己的观点4/14/20236第一部分第一部分简洁取子游戏简洁取子游戏（组合游戏的一种）（组合游戏的一种）4/14/20237什么是组合游戏什么是组合游戏(1)有两个玩家；(2)游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；(3)游戏双方轮番操作；(4)双方的每次操作必需符合游戏规定；(5)当一方不能将游戏接着进行的时候，游戏结束，同时，对方为获胜方；(6)无论如何操作，游戏总能在有限次操作后结束；4/14/20238概念概念:必败点和必胜点必败点和必胜点(P(P点点&N&N点点)n必败点必败
3、点(P(P点点):前一个选手(P Previous player)将取胜的位置称为必败点。n必胜点必胜点(N(N点点):下下一个选手(Next player)将取胜的位置称为必胜点。4/14/20239必败必败(必胜必胜)点属性点属性(1)(1)全部终结点是必败点（全部终结点是必败点（P P点）；点）；(2)(2)从任何必胜点（从任何必胜点（N N点）操作，至少有点）操作，至少有一种方法可以进入必败点（一种方法可以进入必败点（P P点）；点）；(3)(3)无论如何操作，无论如何操作，从必败点（从必败点（P P点）都点）都只能进入必胜点（只能进入必胜点（N N点）点）.4/14/202310取子
4、游戏算法实现取子游戏算法实现 步骤步骤1:1:将全部终结位置标记为必败点（将全部终结位置标记为必败点（P P点）点）；步骤步骤2:2:将全部一步操作能进入必败点（将全部一步操作能进入必败点（P P点）的位置标记为必胜点（点）的位置标记为必胜点（N N点）点）步骤步骤3:3:假如从某个点起先的全部一步操作假如从某个点起先的全部一步操作都只能进入必胜点（都只能进入必胜点（N N点）点），则将该点标，则将该点标记为必败点（记为必败点（P P点）点）；步骤步骤4:4:假如在步骤假如在步骤3 3未能找到新的必败（未能找到新的必败（P P点），则算法终止；否则，返回到步骤点），则算法终止；否则，返回到步骤
5、2 2。4/14/202311课内练习课内练习:nSubtraction Games:subtraction set S=1,3,4x:01234567891011121314Pos:PNPNNNNPNPNNNNP4/14/202312实战练习实战练习nkikis gamekikis game 4/14/202313其次部分其次部分NimNim游游戏戏4/14/202314NimNim游游戏简戏简介介(1)有两个玩家；(2)有三堆扑克牌（比如：可以分别是5，7，9张）；(3)游戏双方轮番操作；(4)玩家的每次操作是选择其中某一堆牌，然后从中取走随意张；(5)最终一次取牌的一方为获胜方；4/14
6、/2023154/14/202316初步分析初步分析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?4/14/202317引入概念引入概念：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）.4/14/202318定理一：定理一：对于nim游戏的某个位置
7、(x1,x2,x3),当且仅当它各部分的nim-sum等于0时（即x1x2x3=0），则当前位于必败点。定理一也适用于更多堆的状况定理一也适用于更多堆的状况4/14/202319定理一的证明定理一的证明 4/14/202320思索（思索（1）：）：n有了定理一，如何推断某个游戏有了定理一，如何推断某个游戏的先手是输还是赢？的先手是输还是赢？4/14/202321思索（思索（2）：）：n对于必胜点，如何推断有几种可对于必胜点，如何推断有几种可行的操作方案？行的操作方案？4/14/202322实例分析实例分析(HDOJ_1850)nBeing a Good Being a Good Boy in
8、Spring Boy in Spring FestivalFestival 4/14/202323第三部分第三部分Graph Games&Graph Games&Sprague-Grundy Sprague-Grundy FunctionFunction4/14/202324What 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
9、 F(x).(4)The player who is confronted with a terminal position at his turn,and thus cannot move,loses.4/14/202325Example about graph game:0,0,01,0,00,0,10,1,05,7,92,0,04/14/202326The Sprague-Grundy Function.Definition:The Sprague-Grundy function of a graph,(X,F),is a function,g,defined on X and taki
10、ng 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)4/14/202327Use ofthe Sprague-Grundy Function:P-positions:Positions x for which g(x)=0 N-positio
11、ns:Positions x for which g(x)0 4/14/202328Exercise: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.4/14/202329Question:What can the S-G value describe?4/14/202330Part 4:Sums of Combinatorial Games4/14/2
12、02331What is so-called“Sums of Combinatorial Games”?4/14/202332Theorem 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).4/14/202333Applications:Sums of three Subtraction Games.In the first game:m=3 and the pile has 9 chips.In the s
13、econd:m=5 and the pile has 10 chips.In the third:m=7 and the pile has 14c hips.g(9,10,14)=?4/14/202334附:参考源码(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;nintmai
14、n()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);4/14/202335课后练习n201003ACM程序设计在线作业（程序设计在线作业（10）博弈入门博弈入门 4/14/202336记住记住:n学习是快学习是快乐的乐的4/14/202337Welcome to HDOJWelcome to HDOJThank Thank You You 4/14/202338