组合博弈入门

n
一、巴什博奕(Bash Game)
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
思想:n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者如何先取s个必胜。什么时候情况特殊?


二、.威佐夫博奕(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
奇异局势有如下三条性质:
     1、任何自然数都包含在一个且仅有一个奇异局势中。 由于ak是未在前面出现过的最小自然数,所以有ak > ak-1 ,而 bk= ak + k > ak-1 + k-1 = bk-1 > ak-1 。所以性质1。成立。
    2、任意操作都可将奇异局势变为非奇异局势。
    3、采用适当的方法,可以将非奇异局势变为奇异局势。
   
     假设面对的局势是(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点).

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,因为它的后继集合是空集。然后对于一个g(x)=0的顶点x,它的所有后继y都满足g(y)!=0。对于一个g(x)!=0的顶点,必定存在一个后继y满足g(y)=0。
         那么当g(x)=0时的点其实就是必败点,否则为必胜点。

posted on 2012-03-07 18:29 煙雨默嘫 阅读(222) 评论(0)  编辑 收藏 引用 所属分类: 博弈


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年3月>
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

公告

  • 默默的大神
  • 常用链接

    留言簿

    随笔分类

    随笔档案

    文章档案

    相册

    最新随笔

    搜索

    积分与排名

    最新评论

    阅读排行榜

    评论排行榜