The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

组合游戏总结——基本博弈问题

【概述】
  最近的几次比赛,博弈的题目一直不少,而且博弈问题是一块比较复杂、庞大的内容,因此在这里小结一下,希望能够帮自己理清一些思路,争取也多来几个系列,呵呵。

竞赛中出现的组合游戏问题一般都满足以下特征:
    1. 二人博弈游戏,每个人都采用对自己最有利的策略,并且是两个人轮流做出决策
    2. 在游戏中的任意时刻,每个玩家可选择的状态是固定的,没有随机成分
    3. 游戏在有限步数内结束,没有平局出现
  大部分的题目都满足上述条件,因此这里只讨论在上述条件范畴内的博弈问题。这类博弈问题,通常还有若干分类。一种是规定移动最后一步的游戏者获胜,这种规则叫做Normal Play Rule;另一种是规定移动最后一步的游戏者输,这种规则叫做Misere Play Rule,也称为Anti-SG游戏。此外,对于游戏的双方,如果二者博弈的规则相同,那么称为这类游戏是对等(impartial games)的;否则称为不平等游戏(partizan games )。当初WHU的那场比赛就是由于对于这个概念不是很清晰,导致看完题目之后就用SG定理来做,浪费了很多机时。实际上,解决不平等博弈问题的方法和普通的博弈问题(SG游戏)是有区别的,一般会采用动态规划或者surreal number。

【博弈基础知识】
  在SG游戏中,最为人熟知的是必胜必败态,也叫NP态理论。注意的是,P态对应的是先手必败态,N态对应的是先手必胜态。必胜必败态理论是:
  1. All terminal positions are P-positions
  2. From every N-position, there is at least one move to a P-position
  3. From every P-position, every move is to an N-position
  英文的表述非常简洁清晰,而且这个理论也很好理解,如果在当前状态的下一步可以走到必败态,那么当前玩家就可以走到那个状态,把必败态推给另一方;如果所有可达状态都是必胜态,那么当前玩家无论如何走,都会把必胜态让给对方。根据必胜必败态理论,我们可以递归的求出每个状态是N态还是P态。必胜必败态理论其实已经把博弈问题转化成了一个有向图,借助图这个模型来分析问题,使得问题变得形象了许多。需要注意的是,这种SG游戏对应的有向图是无环的,因为如果有环,那么游戏双方就可能在环上不停的转换状态,游戏不能在有限步终止,这样就不满足组合游戏的特征3了。
  然而在很多时候仅仅知道某个状态是必胜还是必败是不够的,因为如果存在多个组合游戏(比如经典的Nim),对应的状态集合非常大,无法直接利用必胜必败态理论求解,因此需要用到博弈论中一个很重要的工具:SG函数。
  某个状态的SG函数值定义为当前状态所有不可达的状态编号中最小的编号,其中终止态的SG函数值是0。有了这个工具,就引入一个非常强大的定理——SG分解定理:

  多个组合游戏的SG函数值是每个组合游戏的函数值的和。(这里的和定义为异或操作)
  
  SG分解定理的证明不是很难,其实和Nim的证明很像。根据这个定理,我们就知道为什么Nim的解法是异或所有的石子个数了,因为每堆石子的SG值就是石子的个数。SG分解定理告诉我们任何SG游戏都可以转化成Nim游戏来做。
  Nim中的一个变形就是拿走最后一块石子的人算输。通过修改SG的计算规则,可以得出相同的结论(因为当石子个数是1的时候SG值为0,因此要单独处理);当然也可以利用一个叫做SJ定理的方法来做,依然是要处理当所有堆的SG值不大于1的情况。

【博弈基本模型】
  除了Nim模型,很多模型都看似复杂,最后都划归到了Nim模型上,然后利用SG分解来做的。在证明两种模型等价的时候,可以通过计算SG值判断是否相同,或者通过判断必胜策略的走法将其转化为Nim。许多模型非常的神奇,其获胜策略又千差万别,因此无法一一列举,但是掌握一些经典模型是必须的,这样通过模型的转化可以简化问题的难度。
  经典模型1:Nim变种。包括:
    (1) 楼梯Nim。把奇数台阶的石子作为Nim,二者等价,因为必胜的策略是相同的。
    (2) 每次可以取k堆,这个是经典的Moore Nim。它是泛化的Nim游戏。
    (3) 两堆石子,每次可以取一堆或两堆,从两堆取得时候个数必须相同,谁先取完获胜。这个是著名的威佐夫博弈,跟黄金分割数有关,具体证明不是很清楚,但是用SG值打表可以找出规律。代码如下:
#include <cstdio>
#include 
<cmath>
#include 
<algorithm>
using namespace std;

int main()
{
    
const double k = (sqrt(5.0+ 1/ 2.0;
    
int a, b, t;

    
while (scanf("%d %d"&a, &b) == 2)
    {
        
if (a > b)
            swap(a, b);
        t 
= b - a;
        
if (a == (int)(t * k))
            puts(
"0");
        
else
            puts(
"1");
    }

    
return 0;
}

    (4) Subtraction Games。一种通用的Nim游戏,每次从可用状态集合中选择下一步的状态,有很多变形,核心思想还是计算SG函数值。
    (5) Take-and-Break Game。每次把局面分成多个Nim子游戏,利用SG分解定理求出对应的SG值。
  经典模型2:翻硬币游戏(Coin Turning Game)
    (1) 一维的翻硬币游戏,每次可以翻1个或两个。通过单独考虑每个可以翻的硬币发现,Coin Turning Game的SG值和Nim等价,因此两个模型等价。需要注意的是,许多翻硬币游戏根据题目的要求,一般编号从0开始。
    (2) 一维的翻硬币游戏,每次可以翻1个或两个,限定了翻第二枚硬币的范围,那么就和Subtraction Game等价了。
    (3) 一维的翻硬币游戏,每次可以翻1个、2个或3个,这个游戏叫做Mock Turtles,有一个神奇的规律,是Odious Number序列。
    (4) 高维的翻硬币游戏,需要用到Nim积和Tartan定理。
  翻硬币模型的变化更多,很多模型都有一些奇妙的规律,需要打表才能发现。
  经典模型3:删边游戏(Green Hackenbush)
    (1) 树的删边游戏:Colon原理证明这种模型和Nim依然是等价的,多个叉的SG值异或就是对应根节点的SG值。
    (2) 无向图删边游戏:利用Fursion定理收缩圈,然后就转换成树的删边游戏了,不过这个定理还不会证。

转自:http://www.cppblog.com/sdfond/archive/2010/02/06/107364.aspx



PS:最近做了好多博弈问题,但是总觉得还处在做一题,只会一题的状态,我想是时候系统的学习一下了。

posted on 2010-05-27 11:10 abilitytao 阅读(391) 评论(0)  编辑 收藏 引用


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