巴什游戏(Bash Game)

裸题：HDU 1846 Brave Game

题目链接：https://vjudge.net/problem/HDU-1846

题意：有 $n$ 颗石子，甲先取，乙后取，每次可以拿 $1 \sim m$ 颗石子，轮流拿下去，拿到最后一颗的人获胜。

思路：动态规划。时间复杂度为 $10^2 \times 10^3 \times 10^3 = 10^8$ ，本题数据不是很强，可以通过。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 1010;
int f[N];

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        
        memset(f, 0, sizeof f);
        
        for(int i = 1; i <= m; i++) f[i] = 1;
        
        for(int i = m + 1; i <= n; i++)
        {
            int t = 1;
            for(int j = 1; j <= m; j++) t &= f[i - j];
            // 如果有一个是必败态，那么这个状态就是必胜态
            // 如果全是必胜态，那么这个状态就是必败态
            f[i] = (t == 1 ? 0 : 1);
        }
        
        if(f[n])    puts("first");
        else    puts("second");
    }
    
    return 0;
}

上面动态规划的求解过程非常直观，但时间复杂度略高，所以，我们选择将 $n=23,m=2$ 的结果打印出来，看看有没有什么规律。

image.png

可以发现，如果 $n$ 是 $3$ 的倍数，则后手获胜；否则，先手获胜。

这个规律怎么解释呢？先来看两种简单的情况：

当 $n \leq m$ 时，由于一次最少拿 $1$ 个、最多拿 $m$ 个，甲可以一次拿完，先手赢。
当 $n=m+1$ 时，无论甲拿走多少个（ $1 \sim m$ 个），剩下的都多于 $1$ 个、少于等于 $m$ 个，乙都能一次拿走剩余的石子，后手取胜。

上面两种情况可以扩展为以下两种情况：

如果 $n \% (m+1)=0$ ，即 $n$ 是 $m+1$ 的整数倍，那么不管甲拿多少，例如 $k$ 个，乙都拿 $m+1-k$ 个，使得剩下的永远是 $m+1$ 的整数倍，直到最后的 $m+1$ 个，所以后拿的乙一定赢。
如果 $n \% (m＋1)!=0$ ，即 $n$ 不是 $m+1$ 的整数倍，还有余数 $r$ ，那么甲拿走 $r$ 个，剩下的是 $m+1$ 的倍数，这样就转移到了情况1，相当于甲、乙互换，结果是甲赢。

在这个拿石子的游戏里，对于后拿的乙来说是很不利的，只有在 $n \% (m+1)=0$ 的情况下乙才能赢，在其他情况下都是甲赢。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, m;
        cin >> n >> m;
        if(n % (m + 1) == 0)    puts("second");
        else    puts("first");
    }
    
    return 0;
}

本题是最经典也是最简单的巴什游戏，在编程时可以用动态规划，也可以直接按周期性变化规律做求余计算。但是，如果遇到更复杂的游戏，将很难分析。有一种高级的分析方法，即Sprague-Grundy函数，是该类问题的通用方法。

Sprague-Grundy函数

首先介绍一些概念：

公平组合游戏(Impartial Combinatorial Game, ICG)

若一个游戏满足：

由两名玩家交替行动；
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
不能行动的玩家判负；

则称该游戏为一个公平组合游戏。

常见的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 $2$ 和条件 $3$ 。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

设 $S$ 表示一个非负整数集合。定义 $mex(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：
$mex(S) = min\left\{ x \right\},\ x属于自然数且x不属于S$

SG函数

在有向图游戏中，对于每个节点 $x$ ，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1, y_2, …, y_k$ ，定义 $SG(x)$ 为 $x$ 的后继节点 $y_1, y_2, …, y_k$ 的 SG 函数值构成的集合再执行 mex 运算的结果，即：

$SG(x) = mex(\left\{SG(y_1),\ SG(y_2),\ …,\ SG(y_k)\right\})$

特别地，整个有向图游戏 $G$ 的 SG 函数值被定义为有向图游戏起点 $s$ 的 SG 函数值，即 $SG(G) = SG(s)$ 。

有向图游戏的和

设 $G_1, G_2, …, G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$ ，它的行动规则是任选某个有向图游戏 $G_i$ ，并在 $G_i$ 上行动一步。 $G$ 被称为有向图游戏 $G_1, G_2, …, G_m$ 的和。

有向图游戏的和的 SG 函数值等于它包含的各个子游戏 SG 函数值的异或和，即：

$SG(G) = SG(G_1) \oplus SG(G_2) \oplus … \oplus SG(G_m)$

定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于0。

有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于0。

至此，相关概念就介绍完了，接着，我们尝试用SG函数求解HDU 1846的巴什游戏。

AC代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>

using namespace std;
const int N = 1010;
int sg[N], s[N];

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n, m;
        cin >> n >> m;
        
        memset(sg, 0, sizeof sg);
        
        for(int i = 1; i <= n; i++)
        {
            memset(s, 0, sizeof s);
            
            // 把i的后继结点放到集合s中
            for(int j = 1; j <= m && i - j >= 0; j++)   s[sg[i - j]] = 1;
            
            // 计算sg[i]
            for(int j = 0; j <= n; j++)
            {
                if(!s[j])
                {
                    sg[i] = j;
                    break;
                }
            }
        }
        
        if(sg[n])   puts("first");
        else    puts("second");
    }
    
    return 0;
}

巴什游戏与SG函数

巴什游戏与SG函数

巴什游戏(Bash Game)

Sprague-Grundy函数