Messy

博弈论二日游

发表于 |

这是2017-07-05到2017-07-06的做题记录。

涵盖威佐夫博弈、Nim博弈、SG函数及其各种应用。

POJ 2348 威佐夫博弈

题意：两个数n, m。玩家从较大的数中减去较小的数的若干倍，要求减去后得到的数为非负数。双方轮流进行这个操作，直到某一方将其中一个数减到0，该玩家获得胜利。

题解：

假设m为较大数，令$m=kn+b,b=2$的时候，$(n,m)$是可以选择进入$(n,b)$或者$(n, n+b)$的，而这两个状态里必然有一个先手必败态，所以$k>=2$时，$(n,m)$为先手必胜态。

所以我们只要考虑$k=1$的情况，这种情况只有一个状态可以转移，并且转移后胜负状态必然改变。所以我们可以一直进行这个操作，直到出现$k>=2$的情况，原状态的胜负取决于转移到这个状态需要的次数的奇偶。

例如对于状态$(4,7)$，我们暂时无法判断其状态，但是它只能转移到$(3,4)$，$(3,4)$又只能转移到$(1,3)$，根据前面的推理，$(1,3)$是一个先手必胜态，故$(3,4)$为先手必败态，$(4,7)$先手必胜。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool check(ll a, ll b){
    if (a > b) swap(a, b);
    if (a == 0) return false;
    if (b >= a * 2) return true;
    return !check(a, b - a);
}
int main(){
    ll n, m;
    while (cin >> n >> m) {
        if (n + m == 0) return false;
        ll g = __gcd(n, m);
        n /= g;
        m /= g;
        if (check(n, m)) {
            cout << "Stan wins" << endl;
        } else {
            cout << "Ollie wins" << endl;
        }
    }
}

这题还有一个神奇的结论：当两数之比大于$\frac{\sqrt{5}+1}{2}$（黄金比例）时，先手必胜，否则先手必败。

这个结论可以这么理解：对于状态$(n_1,m_1)$，$m_1=p_1n_1,1\frac{\sqrt{5}+1}{2}$时，$p_2$小于这个数。

阶梯博弈

阶梯博弈的模型是这样的：在从低到高标号为1-N的阶梯上，每级阶梯都放有一定数量的石头，双方轮流进行的操作是选取任意一级阶梯i，取i上任意数量（不为0）的石子，放到阶梯i-1上，最后不能进行这个操作的判输。阶梯1上的石子可以放到地上（可视为阶梯0）。

将所有阶梯分为两部分：奇数标号的阶梯和偶数标号的阶梯。如果把偶数阶梯当做一个容器，限制双方只取奇数阶梯上的石头，那么这个问题就是一个Nim博弈问题。那如果我取奇数阶梯i，对方取了偶数阶梯j上的k个石子该怎么办呢？我们可以猥琐地模仿对方的走法，取j-1上的k个石子放到阶梯j-2上，那么再轮到对面取的时候，局面和上一次相同。所以这个问题就完全转化为了Nim博弈，石子数是阶梯博弈上奇数级阶梯上的石子数。为什么是奇数阶梯而不是偶数阶梯？因为取偶数阶梯不一定会有j-2这个阶梯（当j=1时），并且最后的胜负状态也不一样。

POJ 1704

这题可以很简单的转化成阶梯博弈的模型。把两个棋子之间的空格数视为阶梯上的石子数。阶梯1应是最后两个棋子之间的空格数。

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
int a[10010];
int b[10010];
int main(){
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        a[0] = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        n++;
        sort(a, a + n);
        for (int i = 1; i < n; ++i) {
            b[i-1] = a[i] - a[i-1] - 1;
        }
        int ans = 0;
        for (int i = n-2; i >= 0; i -= 2) {
            ans ^= b[i];
        }
        if (ans) {
            cout << "Georgia will win" << endl;
        } else {
            cout << "Bob will win" << endl;
        }
    }
}

HDU 3389

编号1-N的箱子，给出每个箱子里的卡片数量。双方轮流进行的操作是：在箱子A中取若干卡片（不为0）放入B中，满足$B<A, (A+B) mod 2=1, (A+B)mod 3=0$。不能取则判输。

首先枚举前几个编号的箱子能移动到哪些位置。发现如下规律：

  • 1，3，4号箱子不能再移动
  • 编号模6余数为0，2，5的箱子移动奇数步到1，3，4箱子（我们把这些箱子成为X类）。否则移动偶数步（称为Y类箱子）。
  • X类箱子下一步必然移动到Y类箱子，反之亦然。

利用这个规律，我们可以想出如下的猥琐走法：先手移动X类箱子，如果对方移动了X类箱子的卡片，我们也移动X类箱子；如果对方移动Y类箱子的卡片，我们模仿对方的移动方法，将它移动到的X箱子中相同数量的卡片移动到Y类箱子，这样对方将面临与上次相同的局面。这就是一个阶梯博弈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(){
    int T;
    cin >> T;
    for (int Cas = 1; Cas <= T; ++Cas) {
        printf("Case %d: " , Cas);
        int n, t, p;
        cin >> n;
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            cin >> p;
            t = i % 6;
            if (t == 2 || t == 5 || t == 0) {
                ans ^= p;
            }
        }
        if (ans) {
            cout << "Alice" << endl;
        } else {
            cout << "Bob" << endl;
        }
        
    }
}

Anti-SG POJ 3480

Anti-SG指的是最后不能进行合法操作的为胜者的游戏。这道题用到了SJ定理：先手必胜当且仅当满足以下条件之一：

  1. 游戏的 SG 函数不为 0，且游戏中某个单一游戏的 SG 函数大于 1。
  2. 游戏的 SG 函数为 0，且游戏中没有单一游戏的 SG 函数大于 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(){
    int m, t;
    cin >> t;
    while (t--) {
        int n, x;
        cin >> n;
        m = 0;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            cin >> x;
            ans ^= x;
            m = max(m, x);
        }
        if (m <= 1 && ans == 0) {
            cout << "John" << endl;
        } else if (m > 1 && ans) {
            cout << "John" << endl;
        } else {
            cout << "Brother" << endl;
        }
        
    }
}

Every-SG

Every-SG 游戏规定，对于还没有结束的单一游戏，游戏者必须对该游戏进行一步决策；其余和普通SG相同。

我们的方案是，让必胜的单一游戏尽可能长地玩下去，让必败的游戏尽可能短地玩下去。所以这是一个涉及到长短的游戏，需要记录每个状态的step值。下列公式中，u是v的后继。
$$
step(v)=\left{
\begin{aligned}
0 & , & end \
max(step(u))+1& ,& SG(v)>0,SG(u)=0 \
min(step(u))+1 & , & SG(v)=0
\end{aligned}
\right.
$$
对于整个局面来说，先手必胜当且仅当所有的单一游戏步数最大的为奇数（别的单一游戏先于它结束）。

HDU 3595

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
32
33
34
35
36
int sg[MAXN][MAXN], step[MAXN][MAXN];
int initSG(int x, int y) {
    if (x > y) swap(x, y);
    if (sg[x][y] != -1) return sg[x][y];
    if (x == 0) {
        return step[x][y] = sg[x][y] = 0;
    }
    int tx = y % x;
    int ty = x;
    int flag = initSG(tx, ty);
    step[x][y] = step[tx][ty] + 1;
    if (y / x == 1) {
        return sg[x][y] = flag ^ 1;
    } else {
        if (flag) step[x][y]++;
        return sg[x][y] = 1;
    }
}
int main(){
    memset(sg, -1, sizeof(sg));
    memset(step, 0, sizeof(step));
    int n, ans, x, y;
    while (~scanf("%d",&n)) {
        ans = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d%d", &x, &y);
            if (x > y) swap(x,y);
            initSG(x, y);
            ans = max(ans, step[x][y]);
        }
        if (ans % 2) cout << "MM" << endl;
        else cout << "GG" << endl;
    }
}

翻硬币游戏

游戏规则：

N枚硬币排成一排，有的正面朝上，有的反面朝上。从左到右编号为1-N。

游戏者将要根据某些约束翻硬币，但他所翻硬币中，最右的硬币是由正到反的。不能操作者判输。

此类游戏的结论：局面的SG值为每个正面朝上的棋子单一存在时的SG值的亦或和。

HDU 3537

这题对于单一棋子的SG的确定有着很玄学的推理过程。（打表+找规律+归纳）

一篇比较好的博客：http://blog.csdn.net/acm_cxlove/article/details/7854181

然而还是看得很头疼。。我的代码就不贴了

树的删边游戏

游戏规则：

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

定理：

叶子节点的SG值为0；中间节点的SG值为它的所有子节点的SG值加1后的异或和。

证明过程很精彩，参见贾志豪论文。

HDU 3094

就是这样一个删边游戏。

1
2
3
4
5
6
7
8
9
10
11
vector<int> G[MAXN];
int getSG(int u, int pre){
    int ret = 0;
    for (int i = 0; i < G[u].size(); ++i){
        if (G[u][i] != pre) {
            ret ^= (getSG(G[u][i], u) + 1);
        }
    }
    return ret;
}