组合博弈入门

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   知识库   博问   管理


<2024年11月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

导航

统计

公告

  • 默默的大神

    • 常用链接

    留言簿

    随笔分类

    随笔档案

    文章档案

    相册

    最新随笔

    搜索

    积分与排名

    最新评论

    阅读排行榜

    评论排行榜