DDOSvoid's Blog

博弈论

发表于 更新于 分类于
本文字数： 4.3k 阅读时长 ≈ 4 分钟

简介

ICG游戏

  1. 游戏有两个人参与，二者轮流做出决策。且这两个人的决策都对自己最有利
  2. 当有一人无法做出决策时游戏结束，无法做出决策的人输。无论二者如何做出决策，游戏可以在有限步内结束
  3. 游戏中的同一个状态不可能多次抵达。且游戏不会有平局出现。任意一个游戏者在某一确定状态可以作出的决策集合只与当前的状态有关，而与游戏者无关

一下讨论和出现的游戏非特殊说明均为 $ICG$ 游戏

一些名词的定义

必败态：无法移动到其他状态的状态或所有移动都进入必胜态的状态

必胜态：能移动到必败态的状态

游戏图：将状态看做点，一个状态能够到达另一个状态则视为两个状态之间有一条有向边

子游戏：每位玩家在每个回合只能从若干 $ICG$ 游戏中选择一个进行操作，当所有子游戏都无法进行操作时，当前玩家输掉游戏，不同的子游戏之间没有影响

局面：当前所有子游戏的总和

SG函数

简介

我们首先定义 $mex$ 运算，$mex(S)$ 表示最小的不属于集合 $S$ 的非负整数

首先我们定义 $mex$ 运算，$mex(S)$ 表示最小的不属于集合 $S$ 的非负整数

对于状态 $u$，$sg(u)=mex\lbrace sg(v)| u\rightarrow v\rbrace$

我们称 $sg(u)=0$ 的状态 $u$ 为必败态

如果 $u$ 不能到达任何状态，则 $\lbrace sg(v)|u\rightarrow v\rbrace=\emptyset$，则 $sg(u)=0$

否则说明 $u$ 所能到达的所有状态 $v$，都有 $sg(v)\neq 0$，则表明无论先手如何选择，后手都可以进入一个 $sg$ 为 0 的状态，进过有限次操作，先手必败

那么如果 $sg(u)\neq 0$，我们称状态 $u$ 为必胜态

SG定理

当前局面的 $SG$ 为所有子游戏的 $SG$ 的异或

如何用SG函数解决问题

经典博弈模型

巴什博弈

规则：两个人在玩游戏，有 $n$ 个石子，每人可以随便拿 $1\sim m$ 个石子，不能拿的人为败者，问先手是否有必胜策略

分析：

如果只有 $1\sim m$ 个石子，显然先手可以直接一次拿完，所以先手必胜

如果有 $m+1$ 个石子，那么不论先手那多少个石子，后手都可以一次拿完

如果有 $m+2\sim 2m$ 个石子，先手可以第一次拿到剩下 $m+1$，因为 $m+1$ 是一个必败态，所以先手必胜

不难发现，如果石子数 $s$ 为 $m+1$ 的倍数，先手必败

否则先手必胜

巴什博弈拓展

规则：两个人在玩游戏，有 $n$ 个石子，每人可以随便拿 $l\sim r$ 个石子，不能拿的人为败者，问先手是否有必胜策略

分析：令 $n\equiv k\bmod (a+b)$

如果 $k=0$，后手必胜，因为无论先手怎么拿，后手都可以使局面重新变回 $k=0$ 的情况

如果 $k\in[1,l)$，后手必胜，因为无论先手怎么拿，后手都可以使 $k$ 不会改变

如果 $k\in[l,r]$，先手必胜，因为先手第一次取 $k$ 个就能来到必败态

如果 $k\in(r,l+r)$，先手必胜，因为先手可以控制取的石子使得 $k$ 变成 $[1,l)$，这是一个必败态

Nim游戏

规则：初始有 $n$ 堆石子，每堆有 $a_i$ 个，两人轮流取石子，第一个不能取的人输，每个人只能在一堆中取至少一个，至多把整堆取完

分析：

能够发现每堆石子之间没有影响，所以每堆石子都是一个子游戏

我们首先考虑分析单个子游戏的 $sg$ 值，不妨令 $sg(x)$ 表示有 $x$ 个石子的 $sg$ 值

首先能够得到 $sg(0)=0$，那么 $sg(1) = 1$，因为 $1$ 个石子只能到达 $0$ 石子的状态

然后能够得到 $sg(2)=2$，依次类推可以得到 $sg(x)=x$

也就是说如果 $\bigoplus_{i=1}^na_i=0$，则先手必败，否则先手必胜

Nim游戏变形一

规则：与 $Nim$ 不同的是，对于一堆石子，如果我们取过 $x$ 个石子，那么就不能再取 $x$

分析：

注意到如果我们每次都拿最少的直到不能拿为止，那么我们能够得到一堆石子的最多操作次数

然后我们能够注意到一到这些步都能做到，那么它的 $sg$ 就是最多操作次数

Nim游戏变形二 阶梯Nim

规则：有 $n$ 堆石子依次摆好，每次可以进行以下两种操作中的一种，拿走第一堆的若干个石子，在第 $i$ 堆石子中拿出若干个石子放入第 $i-1$ 堆，注意到某堆石子数变成 $0$ 时并不会移除这堆，这也说明初始局面可能存在某一堆石子的个数为 $0$

分析：

如果双方都只动奇数位置的石子，那么就相当于两人在玩 $nim$ 游戏

那么在 $nim$ 游戏先手必胜的情况下，如果后手动偶数堆的石子，那么先手可以再将其移走继续 $nim$ 游戏，所以此时仍然先手必胜，反之亦然

所以结论就是奇数堆的石子的异或和为 $0$ 先手必败，反之先手必胜

树上删边游戏

规则：给定一棵有根树，每次操作可以选择一条边，将这条边删掉，只保留与根节点相连的部分，不能操作者输

分析：

首先给出答案

1
2
3
4
5
6
7
8
int dfs(int u, int fa) {
    int s = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        s ^= dfs(v, u) + 1; 
    }
    return s;
}

显然一条有 $n+1$ 个点的链的 $sg$ 值为 $n$

我们考虑一棵 $sg$ 值为 $n$ 的树 $H_1$ 和一条有 $n+1$ 个点的链有什么关系

不妨猜想将根的某一棵子树 $H$ 转换为一条 $sg$ 值相同的链是不会对这棵树造成影响的

那么我们考虑从叶子节点开始将所有子树都变成链

考虑只有一个分叉点的时候，这是一个简单的 $nim$ 游戏，然后我们能够意识到多个分叉点时也是简单的 $nim$ 游戏，只需要将 $sg$ 值异或起来即可

我们考虑推广一下这种合并方式

对于任意两棵 $sg$ 值相同的树 $H_1,H_2$，我们考虑将其解到同一棵树的同一个节点上，所得到的新树的 $sg$ 相同

不妨设这两棵树为 $G_1,G_2$，我们考虑证明 $sg(G_1)~xor~sg(G_2)=0$，如果先手操作 $H_1$ 或 $H_2$ 中的边，那么我们只需要操作另一颗树使得 $sg$ 仍然相同，如果先手操作原图中的点，那么我们做同样的操作即可

翻硬币游戏

规则：$n$ 枚硬币硬币排成一排，有的正面朝上，有的反面朝上，游戏者可以根据某些约束翻转硬币，但他所翻的硬币中，最右边的一定是从正面翻到反面

结论：局面的 $sg$ 值为局面中每个正面朝上的棋子单一存在时的 $sg$ 值的异或和

欧几里得游戏

规则：给出两个数 $a,b$，两人轮流操作，每次操作都可以将较大的数减去较小的数的正整数倍，不能使数小于零，不能操作的人输

分析：

可以将其转换为有 $n$ 堆石子，每次只能取第一堆石子

游戏的 $sg$ 值计算如下

1
2
3
int sg = a[n];
for (int i = n - 1; i; --i)
    sg = a[i] - (sg >= a[i]);

至于原因，我大概写一下（因为我也是猜的

首先对于第一堆之后的石子，我们不妨设其 $sg$ 值为 $y$，那么我们就能把后面一大堆石子替换成一堆有 $y$ 个石子，不妨设第一堆石子有 $x$ 个（正确性存疑

我们考虑暴力计算 $(x,y)$ 的 $sg$ 值，我们有 $sg(x,y)=mex\lbrace sg(x-1,y),sg(x-2,y),\cdots,sg(1,y),sg(y)\rbrace$

注意到如果 $sg(y)=y$，那么如果 $y>=x$，那么容易得到 $sg(x,y)=x-1$

如果 $y<x$，那么 $sg(x,y)=x$，那么 $sg$ 值的计算就如上式，我们倒着合并即可

接下来我们考虑一种特殊情况，$a_i$ 不降

容易得到 $sg$ 应为 $a_1-((cnt_{a_1}-[a_n=a_1])\bmod 2)$，其中 $cnt_{a_1}$ 表示等于 $a_1$ 的数量

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest A. Adrien and Austin

规则：有 $n$ 个石子排成一排，每个人可以取 $[1,k]$ 个石子，要求取出的石子必须连续

分析：

能够发现，如果先手能够将石子分成两部分，且这两部分石子相同，那么先手就能模仿后手的操作从而必胜

所以先手必胜的条件是 $k\ge 2$ ，或者 $k=1$ 且 $n$ 为奇数

例题

维持稳态

  1. 简要题意：给定一个正整数 $n$，每次操作可以减掉 $n$ 的一个不是 $1$ 和 $n$ 的因子，不能操作的人输，求是否先手必胜

    $n\le 10^9$

    简要题解：我们分三种情况讨论：

    1. $n$ 是奇数
    2. $n$ 是偶数但不是 $2$ 的幂
    3. $n$ 是 $2$ 的幂

    第一种情况，$n$ 是奇数，所以 $n$ 的因子 $d$ 也一定是奇数，因为我们一定有 $d|(n-d)$，所以 $n-d$ 一定不是 $2$ 的幂，所以第一种情况只能转化到第二种情况

    第二种情况，由于 $n$ 是偶数且不是 $2$​ 的幂，所以一定存在一个奇因子，所以一定能转化到第一种情况，由于第一种情况最终是必败态，所以第二种情况一定是必胜态

    第三种情况，当 $n$ 是 $2$ 的幂时，我们要么减掉 $\frac n 2$ 维持第三种情况，要么转换到第二种情况，但是第二种情况是必胜态，所以我们只能维持第三种情况，容易得到当 $n$ 是 $2$ 的偶数幂时必胜，奇数幂必败

    CF 1537D Deleting Divisors

CF 1397D Stoned Game

Luogu P1290 欧几里德的游戏

CF 786A Berzerk 再必胜和必败的基础上添加另一个状态平局

2018-2019 ACM-ICPC, Asia Nanjing Regional Contest A Adrien and Austin

The 16th Heilongjiang Provincial Collegiate Programming Contest I ICU4C 可以转换成阶梯 $nim$

2021杭电多校2 C I love playing games 直接 $dp$ 计算先手必胜/必败

  1. 简要题意：给 $n$ 堆石子，每次操作可以 $n$ 堆石子中取若干个石子或者将一堆石子数大于等于 $2$ 的石子分成两堆石子

    $n\le 10^6$

    简要题解：最经典的 $multi-sg$，但是并没有什么有用的结论，所以我们直接打表找规律即可，能够得到

    hdu 3032 Nim or not Nim?

Anti-Sg

简介

大概就是进行完最后一步操作的人失败

SJ定理

先手必胜当且仅当：

  1. 游戏的 $sg$ 值不为 $0$ 且至少一个游戏的 $sg$ 值大于 $1$
  2. 游戏的 $sg$ 值为 0 且没有任何一个游戏的 $sg$ 值大于 1

Multi-Sg

简介

一个单一游戏的后继可以为多个单一游戏

例题

  1. 直接计算 $sg$

    CF 850C Arpa and a game with Mojtaba