博弈论

原理

公平组合游戏

公平组合游戏，又称ICG，需要满足：

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

NIM博弈属于公平组合游戏，但是城建类的棋类游戏，比如围棋，就不是ICG。

NIM游戏

给定N堆物品，第i堆物品有A[i]个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。
我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： NIM博弈先手必胜，当且仅当:

$A[1] \^ A[2] \^ ... \^ A[n] != 0$

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

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

SG函数

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

$SG(x) = mex({SG(y_1), SG(y_2), ..., SG(y_k)})$

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

有向图游戏的和

设G1, G2, …, Gm 是m个有向图游戏。定义有向图游戏G，它的行动规则是任选某个有向图游戏Gi，并在Gi上行动一步。G被称为有向图游戏G1, G2, …, Gm的和。
有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：

$SG(G) = SG(G_1) \^ SG(G_2) \^ ... \^ SG(G_m)$

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

模板

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010;

int s[N], f[M];
int n, m;

//SG函数，一般使用记忆化搜索的方法来实现
int sg(int x)
{
    if (f[x] != -1) return f[x];

    unordered_set<int> S;

    for (int i = 0; i < n; i ++ ) 
        if (x >= s[i])
            S.insert(sg(x - s[i]));

    for (int i = 0; ; i ++ )
        if (!S.count(i))
            return f[x] = i;
}

int main()
{
    memset(f, -1, sizeof f);

    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> s[i];
    cin >> m;

    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if (res) puts("Yes");
    else puts("No");

    return 0;
}

例题

AW.893 集合-Nim游戏（简单）

AW.894 拆分-Nim游戏（简单）

博弈论

博弈论

原理