博弈进阶

储备知识：
　　贾志豪：《组合游戏略述——浅谈SG游戏的若干拓展及变形》

http://wenku.baidu.com/view/25540742a8956bec0975e3a8.html

　　王晓珂：《解析一类组合游戏》

　　核心策略：归纳，分解，转化组合游戏

以下题目如阶梯般一步步揭开博弈神秘的面纱~^~，也是对博弈由浅入深的一步步学习之路

从Nim小博弈开始：尼姆博弈

取石子游戏即著名的 nim 游戏，游戏规则如下：
  桌子上有 N 堆石子，游戏者轮流取石子。
  每次只能从一堆中取出任意数目的石子，但不能不取。
  取走最后一个石子者胜。
这道题每一堆石子的 SG 函数值很显然为该堆石子的数目，根据 SG 函数的特点，最后所有
堆石子的 SG 函数的和
    SG=SG1^SG2……SGn
最后，先手胜当且仅当该值不为 0。

尼姆博弈介绍

　　1.理解SG函数，熟悉异或xor(^）操作

　　　　题目：hdu2176:取(m堆)石子游戏

#include<stdio.h>
int a[210000];
int main()
{
    int m,ans;
    int i;
    while(scanf("%d",&m)!=EOF&&m)
    {
        ans=0;
        for(i=0;i<m;i++)
        {
            scanf("%d",&a[i]);
            ans^=a[i];
        }
        if(ans)
        {
            printf("Yes
");
            //printf("#%d
",ans);
            for(i=0;i<m;i++)
            {
                int tmp=ans^a[i];//^tmp之后会为0
                if(a[i]>=tmp)
                {
                    printf("%d %d
",a[i],tmp);
                }
            }
        }
        else printf("No
");
    }
    return 0;
}

View Code

　　　　结论：sg[x]==0,当且仅当x为必败状态（SG，与Anti-SG游戏区别）。

　　2.Anti-SG 游戏和 SJ 定理

　　　 [定义]（anti-nim 游戏）

　　　　 桌子上有 N 堆石子，游戏者轮流取石子。
　　　　 每次只能从一堆中取出任意数目的石子，但不能不取。
　　　　 取走最后一个石子者败。
　　　　[结论]
　　　　先手必胜当且仅当：
　　　　（1）所有堆的石子数都为 1 且游戏的 SG 值为 0；
　　　　（2）有些堆的石子数大于 1 且游戏的 SG 值不为 0。

　　　　题目：hdu 1907： John

#include<stdio.h>
int main()
{
    int t,n,x,flag,ans;
    int i,j;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        flag=1;
        ans=0;
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            ans^=x;
            if(x>1)flag=0;
        }
        if((flag&&!ans)||(ans&&!flag))printf("John
");
        else printf("Brother
");
    }
    return 0;
}

View Code

一般的Anti-SG游戏：

　　　　[定义]
　　　　 Anti-SG 游戏规定，决策集合为空的游戏者赢。
　　　　 Anti-SG 其他规则与 SG 游戏相同。
　　　　[定理]（SJ 定理）
　　　　对于任意一个 Anti-SG 游戏，如果我们规定当局面中所有的单一游
　　　　戏的 SG 值为 0 时，游戏结束，则先手必胜当且仅当：　　　　　　

　　　　（1）游戏的 SG 函数不为 0 且游戏中某个单一游戏的 SG 函数大于 1；

　　　　（2）游戏的 SG 函数为 0 且游戏中没有单一游戏的 SG 函数大于 1。

几种组合游戏模型的转化：

　　1.Cutting Edges游戏（树）

　　规则如下：

　　　　 给出一个有 N 个点的树，有一个点作为树的根节点。　　　

　　　　 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。

　　　　 谁无路可走谁输。
　　我们有如下定理：
　　　　叶子节点的 SG 值为 0；中间节点的 SG 值为它的所有子节点的 SG 值加 1 后的异或和。

　　练习：hdu 3590 PP and QQ 题解

　　树中加边形成环的情况：

　　题目大意：
　　　　 有 N 个局部联通的图。
　　　　 Harry 和 Sally 轮流从图中删边，删去一条边后，不与根节点相
　　　　　　连的部分将被移走。Sally 为先手。
　　　　 图是通过从基础树中加一些边得到的。
　　　　 所有形成的环保证不共用边，且只与基础树有一个公共点。
　　　　 谁无路可走谁输

　　解决办法（奇偶去环）：

　　　 （1）对于长度为奇数的环，去掉其中任意一个边之后，剩下的

　　两个链长度同奇偶，抑或之后的 SG 值不可能为奇数，所
　　以它的 SG 值为 1；
　　　　（2）对于长度为偶数的环，去掉其中任意一个边之后，剩下的
　　两个链长度异奇偶，抑或之后的 SG 值不可能为 0，所以它
　　的 SG 值为 0；

　　练习 POJ 3710 Christmas Game 题解

　　2.无向图的删边游戏

　　无向图的删边游戏：

　　　　 一个无相联通图，有一个点作为图的根。
　　　　 游戏者轮流从图中删去边，删去一条边后，不与根节点相连的部
　　　　　　分将被移走。
　　　　 谁无路可走谁输。

　　一个著名的定理——Fusion Principle。

　　[定理]
　　　　我们可以对无向图做如下改动：将图中的任意一个偶环缩成一个新
　　　　点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全
　　　　部改为与新点相连。这样的改动不会影响图的 SG 值。

　　3.翻硬币游戏

　　一般的翻硬币游戏的规则是这样的：

　　　　 N 枚硬币排成一排，有的正面朝上，有的反面朝上。我们从左开
　　　　始对硬币按 1 到 N 编号。
　　　　 游戏者根据某些约束翻硬币（如：每次只能翻一或两枚，或者每
　　　　次只能翻连续的几枚），但他所翻动的硬币中，最右边的必须是
　　　　从正面翻到反面。
　　　　 谁不能翻谁输。
　　这样的结论：局面的 SG 值为局面中每个正面朝上的棋子单一存在
　　时的 SG 值的异或和。

　　$$补充翻硬币游戏约束条件￥￥

　　4.Every-SG游戏

　　　　何为Every-SG游戏？？？

　　　　有N个单一游戏，游戏者轮流进行决策；

　　　　游戏者的决策必须满足：

　　　　对于所有还没有结束的单一游戏，游戏者必须对该单一游戏进行一步操作；

　　　　无路可走者输

　　贪心策略：

　　　　对于某一个单一游戏，如果当前是先手必胜局，

　　　　那么先手不会放弃游戏的胜利！！！那么，

　　　　游戏者需要做的，就是让自己可以取得胜利的游戏尽可能长的玩下去，

　　　　让自己不能取得胜利的游戏尽可能短的玩下去！！！

　　解决方法：

　　　　对于SG值为0的点，我们需要知道最少几步能将游戏带入终止状态；

　　　　对于SG值不为0的点，我们需要知道最多几步游戏会被带入终止状态；

　　　　以上两个值，我们都用step来表示

　　结论：

　　　　先手必胜当且仅当step值最大的单一游戏为先手必胜游戏

　　思考：

　　　　step值最大的既有先手必胜游戏，又有先手必败游戏时，是否意味着平局？？？