组合博弈入门预习版

1、2022-2-271李悦乔2022-2-27组合博弈入门组合博弈入门（Simple Game Theory）2022-2-27一堆一堆多堆多堆P/NP/N分析分析( (通常方法通常方法) )第一部分 第二部分S-GS-G函数函数( (王道王道) )第三部分 第四部分2022-2-27简单取子游戏简单取子游戏（组合游戏的一种）（组合游戏的一种）2022-2-27(1) 有两个玩家；(2) 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；(3) 游戏双方轮流操作；(4) 双方的每次操作必须符合游戏规定；(5) 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；(6) 无论如何操

2、作，游戏总能在有限次操作后结束；2022-2-27有些地方叫必败点必胜点有些地方叫必败点必胜点P P点点 : :前一个选手(P Previous player)将取胜的位置称为必败点。 N N点点 : :下下一个选手(Next player)将取胜的位置称为必胜点。 2022-2-27(1) (1) 所有终结点是所有终结点是P P点；（如果不是，转点；（如果不是，转化之）化之）(2) (2) 从任何（从任何（N N点）操作，至少有一种方点）操作，至少有一种方法可以进入（法可以进入（P P点）；点）；(3)(3)无论如何操作，无论如何操作， 从（从（P P点）都只能进点）都只能进入（入（N N点

3、）点）. .2022-2-27步步骤骤1:1:将所有终结位置标记为（将所有终结位置标记为（P P点）；点）；步骤步骤2: 2: 将所有一步操作能进入（将所有一步操作能进入（P P点）的点）的位置标记为（位置标记为（N N点）点）步骤步骤3:3:如果从某个点开始的所有一步操作如果从某个点开始的所有一步操作都只能进入（都只能进入（N N点）点） ，则将该点标记为，则将该点标记为（P P点）点） ；步骤步骤4: 4: 如果在步骤如果在步骤3 3未能找到新的（未能找到新的（P P点），点），则算法终止；否则，返回到步骤则算法终止；否则，返回到步骤2 2。2022-2-27BraveGame(1846)

4、BraveGame(1846)CET-4(1847)CET-4(1847)kikis gamekikis game(2147)(2147)2022-2-27NimNim游戏游戏2022-2-27(1) 有两个玩家；(2) 有三堆扑克牌（比如：可以分别是 5，7，9张）；(3) 游戏双方轮流操作；(4) 玩家的每次操作是选择其中某一堆牌，然后从中取走任意张；(5) 最后一次取牌的一方为获胜方；2022-2-27(0, 0, 0) (0, 0, x) (0, 1, 1) (0, k, k) P-position P-position P-position N-position (14, 35, 4

5、6) ? 2022-2-27 定义定义: : 假设假设 (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）.2022-2-27 对于对于nimnim游戏的某个位置游戏的某个位置(x(x1 1,x,x2 2,x,x3 3),),当且仅当它各部分的当且仅当它各部分的nim-sumnim-sum等于等于0 0时（即时（即x x1 1 x x2 2 x x3 3=0=0），则当前），则当前位于（位于（P P点）。点）。定理一也

6、适用于更多堆的情况定理一也适用于更多堆的情况2022-2-27 2022-2-27有了定理一，如果判断某个游戏有了定理一，如果判断某个游戏的先手是输还是赢？的先手是输还是赢？2022-2-27对于必胜点，如何判断有几种可对于必胜点，如何判断有几种可行的操作方案？行的操作方案？2022-2-27Being a Being a Good Boy in Good Boy in Spring Spring FestivalFestival 2022-2-27Graph Game &Graph Game &S-GS-G函数函数2022-2-27(1) (1) 有向无环图有向无环图(2) (2) 玩家玩家

7、1 1先移动，起点是先移动，起点是x x0 0(3) (3) 两个玩家轮流移动两个玩家轮流移动(4) (4) 对于顶点对于顶点x, x, 玩家能够移动到的顶玩家能够移动到的顶点集记为点集记为F(x).F(x).(5) (5) 不能移动的玩家会输掉游戏不能移动的玩家会输掉游戏2022-2-270,0,01,0,00,0,10,1,05,7,92,0,02022-2-27首先定义首先定义mex(minimal excludant)mex(minimal excludant)运算，这是施加于一个集合的运运算，这是施加于一个集合的运算，表示最小的不属于这个集合算，表示最小的不属于这个集合的非负整数。例

8、如的非负整数。例如mex0,1,2,4=3mex0,1,2,4=3、 mex2,3,5=0 mex2,3,5=0、mex=0mex=0。2022-2-27定义定义: : 一个图的一个图的Sprague-Grundy函数(X,F)是定义在X上的非负函数g(x)，并且满足：g(x) = mexg(y) : yF(x)g(x) = mexg(y) : yF(x)2022-2-27P-点点: 即令即令 g(x) = 0 的的 x 点！点！N-点点: 即令即令 g(x) 0 的的 x 点！点！2022-2-27BraveGame(1846)BraveGame(1846)CET-4(1847)CET-4(

9、1847)kikis gamekikis game(2147)(2147)2022-2-27Sums of Combinatorial Games2022-2-272022-2-27假设游戏假设游戏 G Gi i的的SGSG函数是函数是g gi i, , i=1,n, i=1,n, 则则 G = GG = G1 1 + + G + + Gn n 的的 SGSG函数是函数是 g(xg(x1 1,x,xn n) = g) = g1 1(x(x1 1)g)gn n(x(xn n).).2022-2-27假设有三个取子游戏叠加假设有三个取子游戏叠加.第一个: 最多可取 3 子并且共有 9 子. 第二个

10、: 最多可取 5 子并且共有 10 子. 第三个: 最多可取 7 子并且共有 14 子. g(9, 10, 14) =?2022-2-27(HDOJ_1850) Being a Good Boy in Spring Festival (HDOJ_1536) S-Nim2022-2-27#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);

11、gft=1; for(i=0;i+) if(!gi) return i; int main() int n,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); else printf(W); printf(n); 2022-2-27 1517 A Multiplication Game 1079 Calendar Gam