组合博弈入门.pptVIP

组合博弈入门 蔡尚真 Tel:609787 什么是组合游戏—— 有两个玩家； 游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）； 游戏双方轮流操作； 双方的每次操作必须符合游戏规定； 当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方； 无论如何操作，游戏总能在有限次操作后结束； 组合博弈入门 巴什博奕（Bash Game） 威佐夫博奕（Wythoff Game） 尼姆博奕（Nimm Game） 巴什博奕（Bash Game） 只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。 威佐夫博奕（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 bk ,则同时从两堆中拿走 ak – a[b – ak]）个物体,变为奇异局势（ a[b – ak] , a[b – ak]+ b – ak）；如果a 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)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。 对于一个给定的有向无环图，定义关于图的每个顶点的Sprague-Garundy函数g如下：g(x)=mex{ g(y) | y是x的后继 }。 SG函数性质 所有的terminal position所对应的顶点，也就是没有出边的顶点，其SG值为0，因为它的后