博弈论基础 – 整合

概述

博弈论,可以定义为两人或多人面对一定的规则约束下,根据所掌握的信息,同时或先后,一次或多次地,从各自允许的行为中选择最优策略,通常要使自身收益最大化。

囚徒困境

两名罪犯A, B分开囚禁在两个房间内,互相之间不能交流。

每名罪犯可以检举对方犯罪,也可以保持沉默。

  • 若A检举B,且B沉默,则B被判20年。
  • 若B检举A,且A沉默,则A被判20年。
  • 若A,B都检举对方,同时被判8年。
  • 若A,B都沉默,同时被判1年。
A/BA检举A沉默
B检举8/810/0
B沉默0/101/1

博弈:对于每个个体来讲都要是最优的。

P1288 取数游戏Ⅱ

$\rm{Description}$

取数游戏。给出一个环,每条边都有为负边权,所有边中至少有一个 $0$.

将一枚硬币放在环的一个节点上,两个玩家以这个放硬币的节点为起点开始游戏,轮流进行操作,操作方案如下:

  1. 选择当前硬币连出的两条边中的一条,要求这条边的权值为正;
  2. 将选取的这条边的权值,减少到任意一个,小于原本权值的非负整数;
  3. 将硬币移动到选取边的另一侧。

如果轮到一个玩家,硬币的两条边权都是 $0$,那么输掉游戏,比如:

P1288配图

$\rm{Solution}$

显然每次操作,把边权直接变为 $0$ 最优。

所以分别看起点的两端,如果它们的其中一个到第一个 $0$ 的距离为奇数,那么先手胜,反之后手胜。

巴什博奕

$\rm{Description}$

有 $n$ 个物品,A, B两人轮流从物品中拿走一部分,每次至少拿 $1$ 个,最多拿 $?$ 个,拿走最后一个的人获胜。是否有必胜策略,若有,则求出策略。

$\rm{Solution}$

可以想到,当物品的总量 $n=(m+1)r+s$ 时,A先拿走 $s$ 个物品,之后每次若B取走 $k$ 个,则 A对应的取走 $m+1-k$ 个,这样A显然能够取得胜利。

若物品总量为 $n=(m+1)r$ ,此时B用同样的策略即可,B必胜。

$\rm{Code}$

#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    if(n % (m + 1) == 0) {
        cout << "后手胜" << endl;
    } else {
        cout << "先手胜" << endl;
    }
    return 0;
}

威佐夫博弈

$\rm{Description}$

有两堆,若干个物品,两个人轮流从某一堆或从两堆中取同样多的物品,规定每次最少拿走一个,最多不限制,最后拿光的人获胜。

$\rm{Analysis}$

A表示先手玩家,B表示后手玩家,当前是A进行操作。为了判断 A 是否有必胜策略,可以这样分析:

  • 用有序数对 $(a, b)$ 表示两堆物品的数量状态;
  • $(0, 0)$ 是 $A$ 的必败策略,因为此时 $A$ 已输;
  • 若局面能够移动到 $B$ 无必胜策略的局面,那么这个局面是 $A$ 的必胜态
  • 若局面无论怎么移动,都会变成 $B$ 的必胜太,那么这个局面是 $A$ 的必败态

通过枚举,可以发现 $A$ 的必败态有:

$$
(0, 0),(1, 2),(3, 5),(4, 7),(6, 10),(8, 13),(9, 15),(11, 18),(12, 20)\ldots
$$

用有序数对序列$(a_0, b_0),(a_1, b_1),(a_2, b_2)\ldots$表示上面的必败态,可以看出,满足:$a_0=b_0=0$ 且 $b_i=a_i+i$,$a_i$ 是之前没有出现过的最小自然数。

$\rm{Demonstrate}$

前置命题: $a_{n+1}$ 是前 $n$ 组必败态中没有出现过的最小正整数。

证明命题: $\forall n, b_n=a_n+n$.

考虑归纳证明。若前 $k$ 个必败态分别为 $(a_1, a_1+1), (a_2, a_2+2), \cdots, (a_k, a_k+k)$,下证:第 $k+1$ 个必败态为 $(a_{k+1}, a_{k+1}+k+1)$.

从这个必败态出发,一共可能走向三类状态:从第一堆拿走,从第二堆拿走,或者两堆同时拿走,只需证明这三类都是必胜态。

情况一:从第一堆拿走一些。

因为任意一个比 $a_{k+1}$ 小的数都在之前的必胜态中出现过,第一堆变少之后,只需要把第二堆拿到第一堆对应的必败态。所以对于出现的新的状态,都可以直接指向必败态。

情况二:从第二堆拿走一些。

  1. 拿完之后第二堆仍然大于第一堆。此时可以表示成 $(a_{k+1}, a_{k+1}+m), (m < k+1)$,那么两堆同时拿掉一些之后,变成 $(a_m, a_m + m)$
  2. 拿完之后第二堆小于第一堆,设其拿成了 $(a_{k+1}, m)$,则 $m < a_{k+1}$ 一定属于之前的一个必败态,将第一堆拿到第二堆对应的必败态即可。

情况三:两堆同时拿走一些。

设拿完之后的状态是 $(m, m+k+1)$。因为 $m<a_{k+1}$,所以第一堆一定属于之前的一个必败态,将第二堆拿到第一堆对应的必败态即可。

所以现在已经得到了数列关系式 $b_n=a_n+n$.

$\rm{Attribute}$

在这个问题中,我们称必败态为奇异局势,记为 $(a_k, b_k)$ 那么有如下性质:

1. 任何自然数都包含在一个且仅一个奇异局势中

因为 $a_k$ 是之前没有出现过最小自然数,所以所有自然数都会被包含到奇异局势当中。

由于 $a_k > a_{k-1}$,所以 $b_k=a_k+k > a_{k-1}+k > a_{k-1}+k-1 = b_{k-1} > a_{k-1}$。整理后,有 $b_k > b_{k-1} > a_{k-1}$,所以不存在自然数被两个奇异局势包含。

2. 任意操作都可以将奇异局势变为非奇异局势

也就是说,必败态的后继一定都是必胜态

对于奇异局势 $(a_k, b_k)$,如果只改变其中一个数,那么由性质$1$,不可能是另一个奇异局势;

如果同时改变两个数,那么这两个数的差不变,由于 $b_k=a_k+k$,对于一个差值,只可能对应一个奇异局势,所以变化后也不可能是另一个奇异局势。

3. 可以将非奇异局势变为奇异局势

根据奇异局势满足 $b_k=a_k+k$,可以分类讨论进行证明。

具体地,对于任意的局势 $(a, b)$,

若 $a=b$,那么同时取走 $a$ 个物品即可变为 $(0, 0)$;

若 $a$ 是一个奇异局势中的 $a_k$,且 $b > b_k$,那么从 $b$ 堆中取出 $b-b_k$个物品,变为 $(a_k, b_k)$.

若 $a$ 是一个奇异局势中的 $a_k$,且 $b<b_k$,那么从两堆中同时拿走 $a-a_{b-a}$ 个物品。

若 $a$ 不属于任何一个奇异局势中,那么 $b$ 一定是一个奇异局势中的 $b_k=a_k+k$,此时有两种情况:

如果 $a>a_k$,从第一堆中拿走多余的 $a-a_k$.

如果 $a<a_k$,如果 $a=a_j (j < k)$,就从第二堆中拿走 $b-b_j$;如果 $a=b_j(j < k)$,就从第二堆里面拿走 $b-a_j$.

$\rm{Conclusion}$

快速判断局势 $(a, b)$ 是否是奇异局势的方法。

Beatty定理

设 $a, b$ 是正无理数,且 $\frac{1}{a}+\frac{1}{b}=1$,记 $P=\lfloor{na}\rfloor, Q=\lfloor{nb}\rfloor$,$n$ 为任意正整数。

那么 $P\cap Q=\emptyset$ 且 $P\cup Q=N^{*}$.

也就是说:取两个正无理数 $\frac{1}{\alpha}+\frac{1}{\beta}=1$,构造两个数列 $a_n=\lfloor\alpha n\rfloor$ 和 $b_n=\lfloor\beta n\rfloor$,那么两个数列单调递增,并且每个正整数在两个数列当中出现且仅出现一次。

推导

发现奇异局势和 Beatty 定理的条件很像,考虑计算出 $\alpha$ 和 $\beta$.

两个数列 $a_n$ 和 $b_n$ 就是奇异局势中的 $(a_n, b_n)$.

$a_n+n=\lfloor{\alpha\cdot n}\rfloor+n=\lfloor{(\alpha+1)\cdot n}\rfloor=\lfloor{\beta\cdot n}\rfloor$.

所以 $\alpha+1=\beta$

所以 $\frac{1}{\alpha}+\frac{1}{\beta}=\frac{1}{\alpha}+\frac{1}{\alpha+1}=1$.

解得 $\alpha=\frac{\sqrt{5}+1}{2}$.

所以 $a_n=\lfloor\frac{\sqrt{5}+1}{2}n\rfloor$,$b_n=\lfloor(\frac{\sqrt{5}+1}{2}+1)n\rfloor=\lfloor\frac{3+\sqrt{5}}{2}n\rfloor=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

所以根据 Beatty 定理,奇异局势的通项公式为:$a_n=\lfloor(\frac{\sqrt{5}+1}{2})n\rfloor$,$b_n=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

而 $\frac{\sqrt{5}+1}{2}$ 是黄金比,所以威佐夫博弈的奇异局势与黄金比相关。

判断方法

根据奇异局势的性质,对于需要判断的局势 $(a, b), (a < b)$,设 $k=”b-a$,可以计算出” $a_k$ 和 $b_k$,直接和 $a,b$ 进行比较即可。

威佐夫博弈

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
bool eq(double a, double b) {
	if(abs(a - b) < 1e-4) return true;
	else return false;
}
int main() {
	double a, b; cin >> a >> b;
	if(a > b) swap(a, b);
	double t = (1.0 + sqrt(5.0)) / 2.0;
	double k = b - a;
	if(eq(floor(k * t), a) && eq(floor(k * t * t), b)) {
		cout << 0 << endl;
	} else {
		cout << 1 << endl;
	}
	return 0;
}

必胜必败分析

概念

更明确的定义概念:

必胜点(N)

先手必胜点。

必败点(P)

先手必败点。

性质

所有终结点都是必败点;

从必胜点出发,存在一种方法能够进入必败点;

从必败点出发,无论如何都只能进入必败点。

算法

设计一种算法来分析,一个局面是先手必胜还是先手必败。

  1. 将终结点标为必败点;
  2. 将所有一步操作进入必败点的位置标为必胜点;
  3. 如果从某一个点开始,一步操作后只能进入必胜点,那么标记为必败点;
  4. 重复步骤2, 3.

记忆化搜索的过程,可以画出博弈树

例子

描述

一个 $4$ 行 $3$ 列的矩阵,有一个小球放在左上角。两个人依次移动小球,每次只能:

  • 向右移动一格;
  • 向下移动一格;
  • 向右下移动一格。

最后无路可走的人输。两人按最优策略,问谁必胜。

解析

直接用 $4$ 行 $3$ 列的矩阵表示必胜必败情况。用*表示情况不确定,P表示必败,N表示必胜。

首先标记最终的点是必败点:

***
***
***
**P

之后推第四行。第四行的所有点,只能往右走,所以:

***
***
***
PNP

再看第三行。$(3, 3)$ 可以往下走到必败,所以是必胜点。$(3, 2)$ 可以往右下走到必败,所以是必胜点,$(3, 1)$ 同理,所以:

***
***
NNN
PNP

同样的,可以算出最后两行:

NNN
PNP
NNN
PNP

所以,先手必胜。

代码实现

两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。分析必胜必败。

bool win[1001], vis[1001];//win[i]表示剩余i个物品时的必胜必败情况
void init() {
    win[0]=false;
    vis[0]=true;
}
void dfs(int x){
    if(vis[x]){
        return;
    }
    if(x>=1){
        dfs(x-1);
    }
    if(x>=3){
        dfs(x-3);
    }
    if(x>=4){
        dfs(x-4);
    }
    win[x]=false;
    if(x>=1&&!win[x-1]){
        win[x]=true;
    }
    if(x>=3&&!win[x-3]){
        win[x]=true;
    }
    if(x>=4&&!win[x-4]){
        win[x]=true;
    }
    vis[x]=true;
    return;
}

SG函数

组合博弈游戏

组合博弈游戏是这样一种博弈游戏:

  • 有两个游戏者
  • 有一个有限的游戏状态集
  • 游戏规则规定了在每一个状态可以到达的后继状态集。如果在任意状态,双方的走步集合是相同的,那么这个游戏是公平的,否则是不公平的。比如象棋是不公平的,因为每个玩家只能移动自己的棋子。
  • 两个人轮流操作
  • 一般情况下,当一方无法操作时,无法操作者输,游戏结束。

我是真找不到别的定义了……

对于任意一个公平的组合博弈游戏(ICG),我们将每个可能的局面当成图论当中的一个点。

在这个图中的连边规则是:把局面向这个局面经过操作后可能得到的所有局面连边,构成一个有向图。如果这个游戏对于任意的局面 $A$,都不能通过一些操作,回到这个局面 $A$,那么构成的图是一个有向无环图(DAG)。

SG函数

定义一个 $mex$ 函数,表示对于一个集合,不属于该集合的最小非负整数。比如 $mex\{0, 1, 2, 4\}=3$.

还是在这个博弈游戏中:两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。

我们对每个状态进行分级,终结态的级别是 $0$. 如果一个状态能够变为 $0$ ~ $n-1$ 级的状态,那么这个状态是 $n$ 级状态。

状态 $1$ 能够变成 $0$ 级状态,称它为 $1$ 级状态;

状态 $2$ 只能变成 $1$ 级,不能变成 $0$ 级,所以它的级别为 $0$;

状态 $3$ 可以变为 $0$ 级,级别为 $1$;

状态 $4$ 可以变为 $0,1$ 级,级别为 $2$;

状态 $5$ 可以变为 $0,1,2$ 级,级别为 $3$.

在博弈游戏当中,SG函数定义为:$\operatorname{sg}(x)=mex\{\operatorname{sg}(y)\mid y$ 是 $x$ 的后继$\}$,也就是上面所说的状态等级。

对于一个ICG来说,状态 $x$ 是必败态,当且仅当 $\operatorname{sg}(x)=0$.

例子

两个人从一堆 $n$ 个物品中轮流取物品,每次取 $1, 3, 4$ 个物品,最后没法取的人输。

$\operatorname{sg}(0)=mex(\emptyset)$,

$\operatorname{sg}(1)=mex\{\operatorname{sg}(0)\}=mex\{0\}=1$,

$\operatorname{sg}(5)=mex\{\operatorname{sg}(4), \operatorname{sg}(2), \operatorname{sg}(1)\}=3$.

Nim的石子游戏

$\rm{Description}$

给定数列 $n_1, n_2, \cdots, n_k$,表示有 $k$ 堆物品,第 $i$ 堆物品的数量为 $n_i$。

两人轮流从中取物品,规则:每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。

对于给定的数列,判断先手是否必胜,若必胜,输出第一次应该在哪堆取多少物品。

$\rm{Solution}$

必胜必败分析

先手必胜,当且仅当 $n_1\oplus n_2\oplus\cdots\oplus n_k\neq 0$。

对于其他 nim游戏 ,假设状态表示为 $(a_1, a_2, \cdots,a_n)$,那么先手必胜,当且仅当 $\operatorname{sg}(a_1)\oplus \operatorname{sg}(a_2)\oplus\cdots\oplus \operatorname{sg}(a_n)$,证明BFS。

本题中 $\operatorname{sg}(i)=i$,所以有上面的结论。

证明

设 $s=n_1\oplus n_2\oplus\cdots\oplus n_k$.

也就是证明:

  1. 当 $s \neq 0$ 时,存在一种取法,使得 $s=0$.
  2. 当 $s=0$ 时,无论怎么取物品,$s$ 都不等于 $0$.

命题一

因为 $s\neq 0$,根据异或的定义,存在一堆物品 $i$,满足 $n_i\oplus s < n_i$ ,那么就从第 $i$ 堆取走 $n_i-(n_i\oplus s)$,剩下
$n_i\oplus s$ 个物品。

此时,$s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_k\oplus s=s\oplus s=0$.

所以命题一成立。

命题二

反证法。若否,则 $s=0$ 时,存在一种取物品的方法使得 $s_{\rm{new}}=0$.

设取走第 $i$ 堆的若干物品,第 $i$ 堆剩余 $n_i’$ 个物品。

所以 $s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_i’\oplus\cdots\oplus n_k=0=s$.

把 $s$ 的定义式代入,得到 $n_i=n_i’$,产生矛盾。

所以命题二成立。

找方案的方法

利用命题一。找到一堆 $i$,满足 $n_i\oplus s < n_i$,将这一堆拿走 $n_i-(n_i\oplus s)$ 个物品,使得新的异或和为 $0$,满足题意。

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000008;
int T, n;
int a[MAXN];
int main() {
    scanf("%d", &n);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        res ^= a[i];
    }
    if(res == 0) {
        cout << "lose" << endl;
    } else {
    	for(int i = 1; i <= n; i++) {
    		if((res ^ a[i]) < a[i]) {
    			cout << a[i] - (res ^ a[i]) << " " << i << endl;
    			a[i] = res ^ a[i];
    			break;
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    return 0;
}

P2148 [SDOI2009]E&D

$\rm{Description}$

有 $2n$ 堆石子,编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$,归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.

定义分割操作:

  1. 任取一堆石子,不妨为第 $i$ 堆,将其全移走;
  2. 从和第 $i$ 堆同一组的石子中,取出若干正整数个石子,放到第 $i$ 堆的位置上。操作后,两堆石子数都要大于 $0$。

给定状态,问先手是否有必胜策略。

$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.

$\rm{Solution}$

定义

$f(x)$ 为 $x$ 的二进制末尾首个 $0$ 的出现位置(标号从 $0$ 开始)。比如 $f(5)=(101)_2=1$.

$\operatorname{sg}(x, y)$ 为一组分别有 $x+1, y+1$ 个石子的 $\operatorname{sg}$ 值。

$S_z$ 表示满足 $x+y+1=z$ 的 $\operatorname{sg}(x, y)$ 构成的自然数集合。$s_0=\emptyset$.

引理

  1. 终止局面的 $\operatorname{sg}$ 值为 $0$,即 $\operatorname{sg}(0, 0)=0$.
  2. $\operatorname{sg}(x, y)=mex($ 所有后继的 $\operatorname{sg}$ 值 $)=mex(S_x\cup s_y)$.

结论

  1. $S_z$ 等同于 $z$ 二进制下 $1$ 的位置集合。比如 $s_5=(101)_2={0, 2}$.
  2. $\operatorname{sg}(x, y)=f(x\mid y)$. 比如 $sg(1, 4)=f(5)=1$.

证明

考虑归纳证明。逐步放大 $z$,证明对于任意的 $z$,结论 $1$ 成立,且对于任意的 $x+y=z$,结论 $2$ 成立。

根据引理 $1$,结论 $2$ 在 $z=0$ 时正确。

假设已经证明结论 $2$ 在 $z-1$ 正确,考虑 $S_z$ 包含元素 $p$ 的条件。

由 $S_z$ 的定义,需要 $x+y=z-1$,由结论 $2$,需要 $f(x\mid y)=p$.

因此,$(x\mid y)$ 的二进制第 $p$ 位是 $0$,$0\sim p-1$ 位都是 $1$. 所以 $x+y$ 的 $0\sim p-1$ 位都是 $1$,第 $p$ 位是 $0$.

又因为 $x+y+1=z$,所以当包含元素 $p$ 时,无论如何,二进制下 $z$ 的第 $p$ 位总为 $1$.

所以,当且仅当 $z$ 的二进制第 $p$ 位为 $1$ 时,$S_z$ 包含元素 $p$,结论 $1$ 得证。

因为结论 $1$ 成立,所以 $\operatorname{sg}(x, y)=mex(S_x\cup S_y)=mex(S_{x\mid y})$.

又因为 $x\mid y\leq x+y=z$ 在已经证明的 $z$ 的范围内,根据 $S$ 和 $f$ 的定义,显然 $mex(S_{x\mid y})=f(x\mid y)$.

故结论 $1, 2$ 得证。

解法

根据上述结论,$\operatorname{sg}(x, y)=f(x\mid y)$,可以快速地求出每组的 $sg$ 值。将所有组的 $\operatorname{sg}$ 值异或起来,即可判断是否必胜。

$\rm{Code}$

#include<bits/stdc++.h>

using namespace std;
int T, n;
int lowzero(int x){
    for (int i = 0;; i++, x >>= 1) {
        if (!(x & 1)) return i;
    }
}
int main() {
	scanf("%d", &T);
	while(T--) {
        int ans = 0;
        scanf("%d", &n); n >>= 1;
        while(n--) {
            int x, y;
            scanf("%d%d", &x, &y);
            ans ^= lowzero((x - 1) | (y - 1));
        }
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

参考资料

威佐夫博弈:https://blog.csdn.net/wu_tongtong/article/details/79295069

关于异或:https://blog.csdn.net/hndu__lz/article/details/61925818

P2148:https://www.luogu.com.cn/blog/Sooke/solution-p2148

NIM的石子游戏:P1247 取火柴游戏

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();