博弈论

Bash Game

巴什博弈：只有一堆n个物品，两个人轮流从这堆物品中取物，规定每次至少取一个，最多取m个。最后取光者得胜。

分析

先剖析题意——每次可以取1~m个，那存在如下几种情况：

  1. n%（m+1）==0，此时，无论先手取几个，后手都可以取i个使每轮是m+1个，最终先手必输。
  2. n%（m+1）!=0，此时先手先取n%（m+1）个，后手取k个，先手再取l个使k+l=m+1，最后一次即为先手取得。

例子

51Nod—1066 Bash游戏

NIm Game

Nim Game：m堆n个物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜

分析

所有物品数目二进制异或 为0，则先手必输
所有物品数目二进制异或不为0，则后手必输
从另一个角度思考这个问题，如果物品数量随机，那么每个数目的每一位上1或0概率相同，
如果有奇数个堆，那么1的个数为偶数或者奇数的概率相同，
如果有偶数个堆，那么1的个数为偶数的概率略大1/(m+1)，
也就是说异或结果的每一位为0或1的概率几乎差不多，而先手必输要求异或结果每一位都为0，其实输的概率很小

例子

51Nod—1069 Nim游戏

SG函数

当我们面对由n个游戏组合成的一个游戏时，只需对于每个游戏找出求它的每个局面的SG值的方法，就可以把这些SG值全部看成Nim的石子堆，然后依照找Nim的必胜策略的方法来找这个游戏的必胜策略了！（Nim其实就是n个从一堆中拿石子的游戏求SG的变型，总SG=n个sg的异或）。（very important）

解题模型：

  1. 把原游戏分解成多个独立的子游戏，则原游戏的SG函数值是它的所有子游戏的SG函数值的异或。

​ 即sg(G)=sg(G1)^sg(G2)^…^sg(Gn)。

  1. 分别考虑没一个子游戏，计算其SG值。

    SG值的计算方法：（重点）

  2. 可选步数为1~m的连续整数，直接取模即可，SG(x) = x % (m+1);

  3. 可选步数为任意步，SG(x) = x;

  4. 可选步数为一系列不连续的数，用模板计算。

模板一：打表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int MAX_DIG = 64;

//  SG打表
//  f[]:可以取走的石子个数
//  sg[]:0~n的SG函数值
//  hash[]:mex{}
int f[MAX_DIG];
int sg[MAX_DIG];
int hash[MAX_DIG];

void getSG(int n)
{
    memset(sg, 0, sizeof(sg));
    for (int i = 1; i <= n; i++){
        memset(hash, 0, sizeof(hash));
        for (int j = 1; f[j] <= i; j++){
            hash[sg[i - f[j]]] = 1;
        }
        for (int j = 0; j <= n; j++){    //  求mes{}中未出现的最小的非负整数
            if (hash[j] == 0){
                sg[i] = j;
                break;
            }
        }
    }
}

模板二：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int MAX_DIG = 64;

//  DFS
//  注意 S数组要按从小到大排序 SG函数要初始化为-1 对于每个集合只需初始化1遍
//  n是集合s的大小 S[i]是定义的特殊取法规则的数组
int s[MAX_DIG];
int sg[MAX_DIG * 100];
int n;

int SG_dfs(int x)
{
    if (sg[x] != -1){
        return sg[x];
    }
    bool vis[MAX_DIG];
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i < n; i++){
        if (x >= s[i]){
            SG_dfs(x - s[i]);
            vis[sg[x - s[i]]] = 1;
        }
    }
    int e;
    for (int i = 0; ; i++){
        if (!vis[i]){
            e = i;
            break;
        }
    }
    return sg[x] = e;
}

一般DFS只在打表解决不了的情况下用，首选打表预处理。

例子（打表）

51Nod—1714 B君的游戏