(lecture_11)组合博弈入门.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,ACM,程序设计,杭州电子科技大学 刘春英,acm,3/5/2026,1,今天，,你,了吗？,AC,3/5/2026,2,每周一星,（,10,）：,Lin2144,3/5/2026,3,第十一讲,组合博弈入门,（,Simple,G,ame,T,heory,）,3/5/2026,4,导引游戏,(1),玩家：,2,人；,(2),道具：,23,张扑克牌；,(3),规则：,游戏双方轮流取牌；,每人每次仅限于取,1,张、,2,张或,3,张牌；,扑克牌取光，则游戏结束；,最后取牌的一方为胜者。,3/5/2026,5,基本思路？,请陈述自己的观点,3/5/2026,6,第一部分,简单取子游戏,（组合游戏的一种）,3/5/2026,7,什么是组合游戏,有两个玩家；,游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；,游戏双方轮流操作；,双方的每次操作必须符合游戏规定；,当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；,无论如何操作，游戏总能在有限次操作后结束；,3/5/2026,8,概念,:,必败点和必胜点,(P,点,&N,点,),必败点,(P,点,),:,前一个选手,(,P,revious player),将取胜的位置称为必败点。,必胜点,(N,点,),:,下,一个选手,(Next player),将取胜的位置称为必胜点。,3/5/2026,9,必败,(,必胜,),点属性,(1),所有终结点是必败点（,P,点）；,(2),从任何必胜点（,N,点）操作，至少有一种方法可以进入必败点（,P,点）；,(3),无论如何操作，从必败点（,P,点）都只能进入必胜点（,N,点）,.,3/5/2026,10,取子游戏算法实现,步,骤,1:,将所有终结位置标记为必败点（,P,点）；,步骤,2:,将所有一步操作能进入必败点（,P,点）的位置标记为必胜点（,N,点）,步骤,3:,如果从某个点开始的所有一步操作都只能进入必胜点（,N,点），则将该点标记为必败点（,P,点）；,步骤,4:,如果在步骤,3,未能找到新的必败（,P,点），则算法终止；否则，返回到步骤,2,。,3/5/2026,11,课内练习,:,Subtraction Games:,subtraction set S=1,3,4,x,:,0 1,2 3 4,5 6 7 8,9 10 11 12 13 14,Pos,:,P N P N N N N P N P,N,N,N,N,P,3/5/2026,12,实战练习,kikis game,3/5/2026,13,第二部分,Nim,游戏,3/5/2026,14,Nim,游戏简介,有两个玩家；,有三堆扑克牌（比如：可以分别是,5,，,7,，,9,张）；,游戏双方轮流操作；,玩家的每次操作是选择其中某一堆牌，然后从中取走任意张；,最后一次取牌的一方为获胜方；,3/5/2026,15,3/5/2026,16,初步分析,(0,0,0),(0,0,x),(0,1,1),(0,k,k),P-position,P-position,P-position,N-position,(14,35,46),?,3/5/2026,17,引入概念,：,Nim-Sum,定义,:,假设,(x,m,x0),2,和,(y,m,y,0,),2,的,nim-sum,是,(z,m,z,0,),2,则我们表示成,(x,m,x,0,),2,(y,m,y,0,),2,=(z,m,z,0,),2,这里,，,z,k,=x,k,+y,k,(mod 2),（,k=0,m,）,.,3/5/2026,18,定理一：,对于,nim,游戏的某个位置,(x,1,x,2,x,3,),当且仅当它各部分的,nim-sum,等于,0,时（即,x,1,x,2,x,3,=0,），则当前位于必败点。,定理一也适用于更多堆的情况,3/5/2026,19,定理一的证明,3/5/2026,20,思考（,1,）：,有了定理一，如果判断某个游戏的先手是输还是赢？,3/5/2026,21,思考（,2,）：,对于必胜点，如何判断有几种可行的操作方案？,3/5/2026,22,实例分析,(HDOJ_,1850,),Being a Good Boy in Spring Festival,3/5/2026,23,第三部分,Graph Games&,Sprague-Grundy Function,3/5/2026,24,What 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.,3/5/2026,25,Example about graph game:,0,0,0,1,0,0,0,0,1,0,1,0,5,7,9,2,0,0,3/5/2026,26,The 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 that,g(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),3/5/2026,27,Use of,the Sprague-Grundy Function:,P-positions:Positions x for which g(x)=0,N-positions:Positions x for which g(x)0,3/5/2026,28,Exercise:,What 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,.,3/5/2026,29,Question:,What can the S-G value describe?,3/5/2026,30,Part 4:,Sums of,Combinatorial Games,3/5/2026,31,What,is so-called“Sums of Combinatorial Games”?,3/5/2026,32,Theorem 2.,If g,i,is the Sprague-Grundy function of G,i,i,=1,.,n,then,G,=,G,1,+,+,G,n,has Sprague-Grundy function,g,(,x,1,.,x,n,)=,g,1(,x,1,),gn,(,x,n,),.,3/5/2026,33,Applications:,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)=?,3/5/2026,34,附,:,参考源码,(HDOJ-1536),#include#include#includeusing namespace std;int k,a100,f10001;int mex(int p)int i,t;bool g101=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)return i;,int main()int n,i,m,t,s;while(scanf(%d,3/5/2026,35,课后练习,2008ACM,ProgrammingExercise(12,)_,博弈入门,1517 A Multiplication Game,1079 Calendar Game,2147 kikis game,1404 Digital Deletions,1536,S-Nim,1729,Stone Game,1730 Northcott Game,1760 A New Tetris Game,1809,A New Tetris Game(2),1524,A Chess Game,3/5/2026,36,记住,:,学习是快乐的,3/5/2026,37,Welcome to HDOJ,Thank,You,3/5/2026,38,