组合博弈入门ppt课件.ppt
组合博弈入门,蔡尚真 Tel:609787,什么是组合游戏,有两个玩家； 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）； 游戏双方轮流操作； 双方的每次操作必须符合游戏规定； 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方； 无论如何操作，游戏总能在有限次操作后结束；,组合博弈入门,巴什博奕（Bash Game） 威佐夫博奕（Wythoff Game） 尼姆博奕（Nimm Game）,巴什博奕（Bash Game）,只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。,思想：n=（m+1）r+s，（r为任意自然数，sm)，那么先取者如何先取s个必胜。什么时候情况特殊？,威佐夫博奕（Wythoff Game）,有两堆各若干个物品，两个人轮流从某一堆或同时从两堆中取同样多的物品，规定每次至少取一个，多者不限，最后取光者得胜。,威佐夫博奕（Wythoff Game）,这种情况下是颇为复杂的。我们用（ak，bk）（ak bk ,k=0，1，2，,n)表示两堆物品的数量并称其为局势，如果甲面对（0，0），那么甲已经输了，这种局势我们称为奇异局势。前几个奇异局势是：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。可以看出,a0=b0=0,ak是未在前面出现过的最小自然数,而 bk= ak + k,威佐夫博奕（Wythoff Game）,奇异局势有如下三条性质： 1、任何自然数都包含在一个且仅有一个奇异局势中。 由于ak是未在前面出现过的最小自然数，所以有ak ak-1 ，而 bk= ak + k ak-1 + k-1 = bk-1 ak-1 。所以性质1。成立。 2、任意操作都可将奇异局势变为非奇异局势。 3、采用适当的方法，可以将非奇异局势变为奇异局势。,威佐夫博奕（Wythoff Game）,假设面对的局势是（a,b），若 b = a，则同时从两堆中取走 a 个物体，就变为了奇异局势（0，0）；如果a = ak ，b bk，那么，取走b bk个物体，即变为奇异局势；如果 a = ak ， b ak ，b= ak + k,则从第一堆中拿走多余的数量a ak 即可；如果a ak ，b= ak + k,分两种情况，第一种，a=aj （j k）,从第二堆里面拿走 b bj 即可；第二种，a=bj （j k）,从第二堆里面拿走 b aj 即可。,尼姆博奕（Nimm Game）,有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜。 思考：各个数之间二进制异或非零必胜？,概念:必败点和必胜点(P点 & N点),必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。通俗说就是先手必败点。 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。,必败(必胜)点属性,(1) 所有终结点是必败点（P点）； (2) 从任何必胜点（N点）操作，至少有一种方法可以进入必败点（P点）； (3)无论如何操作， 从必败点（P点）都只能进入必胜点（N点）.,练习:,能取的集合 S = 1, 3, 4,SG函数的提出,现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。事实上，这个游戏可以认为是所有Impartial Combinatorial Games的抽象模型。也就是说，任何一个ICG都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。下面我们就在有向无环图的顶点上定义Sprague-Garundy函数 。,SG函数基础,首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex0,1,2,4=3、mex2,3,5=0、mex=0。 对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex g(y) | y是x的后继 。,SG函数性质,所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后继集合是空集。然后对于一个g(x)=0的顶点x，它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点，必定存在一个后继y满足g(y)=0。 那么当g(x)=0时的点其实就是必败点，否则为必胜点。,多堆或多子游戏,SG+尼姆博奕 各堆各自用SG，再用尼姆博弈 hdu1848,/使用求解SG来求解 #include using namespace std; int aaa1000000; const int MAX=1010; int a21,SGMAX; void get2() int i; a0=1; a1=2; for(i=2;inmp,n+m+p) if (SGn=-1) SGn=getSG(n); if (SGm=-1) SGm=getSG(m); if (SGp=-1) SGp=getSG(p); flag=SGnSGmSGp; if(flag) printf(“Fibon“); else printf(“Naccin“); return 0; ,
