组合博弈入门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;,
