组合博弈入门ppt课件.ppt
17页
组合博弈入门组合博弈入门蔡尚真Tel:609787 什么是组合游戏——(1)有两个玩家；有两个玩家；(2)游戏的操作状态是一个有限的集合（比如：游戏的操作状态是一个有限的集合（比如：限定大小的棋盘）；限定大小的棋盘）；(3)游戏双方轮流操作；游戏双方轮流操作；(4)双方的每次操作必须符合游戏规定；双方的每次操作必须符合游戏规定；(5)当一方不能将游戏继续进行的时候，游戏当一方不能将游戏继续进行的时候，游戏结束，同时，对方为获胜方；结束，同时，对方为获胜方；(6)无论如何操作，游戏总能在有限次操作后无论如何操作，游戏总能在有限次操作后结束；结束； 组合博弈入门组合博弈入门n n巴什博奕（Bash Game）n n威佐夫博奕（Wythoff Game）n n尼姆博奕（Nimm Game） 巴什博奕（巴什博奕（Bash Game）） 只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个最后取光者得胜思想：n=（m+1）r+s，（r为任意自然数，s≤m)，那么先取者如何先取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））n n奇异局势有如下三条性质：奇异局势有如下三条性质： 1 1、任何自然数都包含在一个且仅有一个奇异局、任何自然数都包含在一个且仅有一个奇异局势中 由于由于akak是未在前面出现过的最小自然数，是未在前面出现过的最小自然数，所以有所以有akak > ak-1 > ak-1 ，而，而 bkbk= = akak + k > ak-1 + k-1 = bk- + k > ak-1 + k-1 = bk-1 > ak-1 1 > ak-1 。
所以性质所以性质1 1 2 2、任意操作都可将奇异局势变为非奇异局势任意操作都可将奇异局势变为非奇异局势 3 3、采用适当的方法，可以将非奇异局势变为奇异、采用适当的方法，可以将非奇异局势变为奇异局势 威佐夫博奕（威佐夫博奕（Wythoff Game）） 假设面对的局势是（假设面对的局势是（a,ba,b），若），若 b = ab = a，则同时，则同时从两堆中取走从两堆中取走 a a 个物体，就变为了奇异局势（个物体，就变为了奇异局势（0 0，，0 0）；如果）；如果a = a = akak ，，b > b > bkbk，那么，取走，那么，取走b – b – bkbk个物个物体，即变为奇异局势；如果体，即变为奇异局势；如果 a = a = akak ，， b < b < bkbk , ,则则同时从两堆中拿走同时从两堆中拿走 akak – – a[ba[b – – akak] ]）个物体）个物体, ,变为变为奇异局势（奇异局势（ a[ba[b – – akak] , ] , a[ba[b – – akak]+ b – ]+ b – akak）；如果）；如果a > a > akak ，，b= b= akak + k, + k,则从第一堆中拿走多余的数量则从第一堆中拿走多余的数量a a – – akak 即可；如果即可；如果a < a < akak ，，b= b= akak + k, + k,分两种情况，分两种情况，第一种，第一种，a=a=aj aj （（j < kj < k））, ,从第二堆里面拿走从第二堆里面拿走 b – b – bjbj 即可；第二种，即可；第二种，a=a=bjbj （（j < kj < k））, ,从第二堆里面拿走从第二堆里面拿走 b – b – aj aj 即可。
即可 尼姆博奕（尼姆博奕（Nimm Game）） 有三堆各若干个物品，两个人轮流从某一堆取任意多的物品，规定每次至少取一个，多者不限，最后取光者得胜思考：各个数之间二进制异或非零必胜？ 概念:必败点和必胜点(P点 & N点)n n必败点必败点(P(P点点) ) : :前一个选手(Previous player)将取胜的位置称为必败点通俗说就是先手必败点 n n必胜点必胜点(N(N点点) ) : :下下一个选手(Next player)将取胜的位置称为必胜点 必败(必胜)点属性(1) (1) 所有终结点是必败点（所有终结点是必败点（P P点）；点）；(2) (2) 从任何必胜点（从任何必胜点（N N点）操作，至少有点）操作，至少有一种方法可以进入必败点（一种方法可以进入必败点（P P点）；点）；(3)(3)无论如何操作，无论如何操作， 从必败点（从必败点（P P点）都点）都只能进入必胜点（只能进入必胜点（N N点）点）. . 练习:能取的集合 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… SG函数的提出函数的提出 现在我们来研究一个看上去似乎更为一般的现在我们来研究一个看上去似乎更为一般的游戏：给定一个有向无环图和一个起始顶点上的游戏：给定一个有向无环图和一个起始顶点上的一枚棋子，两名选手交替的将这枚棋子沿有向边一枚棋子，两名选手交替的将这枚棋子沿有向边进行移动，无法移动者判负。
事实上，这个游戏进行移动，无法移动者判负事实上，这个游戏可以认为是所有可以认为是所有Impartial Combinatorial GamesImpartial Combinatorial Games的的抽象模型也就是说，任何一个抽象模型也就是说，任何一个ICGICG都可以通过都可以通过把每个局面看成一个顶点，对每个局面和它的子把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个局面连一条有向边来抽象成这个“ “有向图游戏有向图游戏” ”下面我们就在有向无环图的顶点上定义下面我们就在有向无环图的顶点上定义Sprague-Sprague-GarundyGarundy函数函数 SG函数基础函数基础n n首先定义mex(minimal excludant)运算，这是施加于一个集合的运算，表示最小的不属于这个集合的非负整数例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0n n对于一个给定的有向无环图，定义关于图的每个顶点的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时的点其实就是必败点，否则为必胜点 多堆或多子游戏多堆或多子游戏n nSG+尼姆博奕n n各堆各自用SG，再用尼姆博弈n nhdu1848 nn// //使用求解使用求解SGSG来求解来求解nn#include <#include
