10简单博弈论

简单博弈论

Nim游戏

证明

  • 0 ^ 0 ^ 0 … 0 这是一个必败态。显然可得。
  • 如果

    a

    1

    a_{1}

    a1​ ^

    a

    2

    a_{2}

    a2​ ^ … ^

    a

    n

    a_{n}

    an​ = x != 0 ，我们总能拿掉一些石子，使它们的异或为0。
    证明：不妨设x的二进制表示中最高一位1在第k位，那么在

    a

    1

    ,

    a

    2

    ,

    …

    ,

    a

    n

    a_{1},a_{2},…,a_{n}

    a1​,a2​,…,an​中，必然有一个数

    a

    i

    a_{i}

    ai​，它的第k位是1，且

    a

    i

    a_{i}

    ai​ < x，则

    a

    i

    a_{i}

    ai​ ^ x <

    a

    i

    a_{i}

    ai​，从第i堆石子中拿走

    a

    i

    a_{i}

    ai​ –

    a

    i

    a_{i}

    ai​ ^ x，第i堆石子剩下

    a

    i

    a_{i}

    ai​ – (

    a

    i

    a_{i}

    ai​ –

    a

    i

    a_{i}

    ai​ ^ x) =

    a

    i

    a_{i}

    ai​ ^ x，则所有石子数异或为0。

  • 如果

    a

    1

    a_{1}

    a1​ ^

    a

    2

    a_{2}

    a2​ ^ … ^

    a

    n

    a_{n}

    an​ = 0，无论怎么拿，之后的状态异或都不是0。
    反证法：假设从第i堆石子里拿走若干个，剩下

    a

    ′

    a’

    a′个，并且

    a

    1

    a_{1}

    a1​ ^

    a

    2

    a_{2}

    a2​ ^ … ^

    a

    i

    ′

    a_{i}’

    ai′​ ^ … ^

    a

    n

    a_{n}

    an​ = 0，则(

    a

    1

    a_{1}

    a1​ ^

    a

    2

    a_{2}

    a2​ ^ … ^

    a

    i

    ′

    a_{i}’

    ai′​ ^ … ^

    a

    n

    a_{n}

    an​) ^ (

    a

    1

    a_{1}

    a1​ ^

    a

    2

    a_{2}

    a2​ ^ … ^

    a

    i

    a_{i}

    ai​ ^ … ^

    a

    n

    a_{n}

    an​) =

    a

    i

    ′

    a_{i}’

    ai′​ ^

    a

    i

    a_{i}

    ai​ = 0，这说明

    a

    i

    ′

    a_{i}’

    ai′​ =

    a

    i

    a_{i}

    ai​，矛盾。

结论

如果当前状态a1 ^ a2 ^ … ^ an != 0，我总能使它变成0，而后手无论怎么拿，都会使状态非0，也就是我每次都留给0的状态给对手，而石子不是无限的，所以对手一定会遇到0 ^ … ^ 0的状态，即必胜。反之，必败

原题链接：Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

#include <iostream>

using namespace std;

/*
1. 0 ^ 0 ^ 0 ^...^ 0 这是一个必败态
2. 如果a1 ^ a2 ^ ... ^ an != 0 ，我们总能拿掉一些石子，使它们的异或为0
3. 如果a1 ^ a2 ^ ... ^ an == 0，无论怎么拿，之后的状态异或都是0，反证法 

结论：如果当前状态a1 ^ a2 ^ ... ^ an != 0，我总能使它变成0，而后手无论怎么拿，都会使状态非0，也就是我每次都留给0的状态给对手，而石子不是无限的，
所以对手一定会遇到0 ^ ... ^ 0的状态，即必胜。反之，必败 
*/

int main() {
	int n, res = 0;// 0 ^ x == x
	int t;
	cin >> n;
	for (int i = 0; i < n; i ++ ) {
		scanf("%d", &t);
		res ^= t;
	} 
	if (res != 0) printf("Yes\n");
	else printf("No\n");
	return 0;
}

台阶-Nim游戏

思路

此时我们需要将奇数台阶看做一个经典的Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

  • 证明：
    先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手
    于是轮到后手：
    ①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
    ②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0
    因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。
    （核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！
思路原链接：https://www.acwing.com/solution/content/13187/

原题链接：台阶-Nim游戏

现在，有一个 n 级台阶的楼梯，每级台阶上都有若干个石子，其中第 i 级台阶上有 ai 个石子(i≥1)。
两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。
已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

#include <iostream>

using namespace std;

// 因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败

int n;
int res;

int main() {
	cin >> n;
	int t;
	for (int i = 1; i <= n; i ++ ) {
		scanf("%d", &t);
		// 判断i的奇偶
		if (i % 2) res ^= t;
	}
	if (res) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

集合-Nim游戏

SG函数

SG函数

介绍SG函数之前，先介绍mex{}操作，最小的不属于这个集合的非负整数，例如mex{0,1,2,4}=3 ，而SG(x) = mex{SG(a), SG(b)…}，其中a，b为x所能到达的状态。

性质：

  1. SG(i)=k，则i最大能到达的点的SG值为k−1。
  2. 非0可以走向0
  3. 0只能走向非0

原题链接：集合-Nim游戏

给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合 S，最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

定理

对于n个图，如果SG(G1)SG(G2) ^ … SG(Gn)!=0 ,则先手必胜，反之必败

  • 证明（类似与Nim游戏）：
    ①当SG(Gi)=0 时 ，xor=0 ， 显然先手必败
    （PS：结束状态必是状态①，但状态①不一定是结束状态）
    ②当xor = x != 0时，因为肯定存在一个SG(xi)^x < SG(xi),而根据SG()的性质1可知，SG(k)可以走到0~k−1的任何一个状态，
    因此，必定可以从SG(xi)−>SG(xi)^x ， 于是使得xor=0
    ③当xor=0时，当移动任何一个节点时，对应的SG值必然减小，可以证明：xor!=0
    下证：xor!=0
    假设:xor=0,则说明移动的那个节点的值并没有变化，即从SG(k)变成了k，但是这与SG函数的性质1相矛盾，因此不成立

证明转载：https://www.acwing.com/solution/content/13191/

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

// 找到每堆石子的初始sg，求它们的异或，为0必败
// sg(x) = mex{sg(a), sg(b),...,}，a, b...表x所能到达的所有状态 
// mex{}，最小的不属于这个集合的非负整数，例如mex{0,1,2,4}=3 

const int N = 105;
const int M = 10010;

int k, n;
int s[N], h[N];
int f[M];

int sg(int x) {
	// 记忆搜索 
	if (f[x] != -1) return f[x];
	// 将x所能到达的状态存入sta 
	set<int> sta;
	for (int i = 0; i < k; i ++ )
		if (x - s[i] >= 0)
			sta.insert(sg(x - s[i]));
	
	// mex操作 
	for (int i = 0; ; i ++ ) 
		if (sta.count(i) == 0) {
			f[x] = i;
			break;
		}
	return f[x];
}

int main() {
	memset(f, -1, sizeof(f));
	cin >> k;
	for (int i = 0; i < k; i ++ ) cin >> s[i];
	cin >> n;
	int t, res = 0;
	for (int i = 0; i < n; i ++ ) {
		cin >> t;
		res ^= sg(t);
	}
	if (res) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0; 
}

拆分-Nim游戏

思路：需要存储的状态就是sg(b[i])^sg(b[j])（与集合-Nim的唯一区别）

原题链接：拆分-Nim游戏

给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

注：每次操作都将ai变成两个更小的数，但并不相加到当前已有的堆里，是创建两个新堆，例如将100分成99和99

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

// 每次将ak分成两个更小的数bi, bj，不妨令ak > bi >= bj 保证不重复 

const int N = 105;

int n; 
int f[N];

int sg(int x) {
	// 记忆搜索 
	if (f[x] != -1) return f[x];
	// 将x所能到达的状态存入sta 
	set<int> sta;
	// 保证bi >= bj，不会重复 
	for (int i = 0; i < x; i ++ )
		for (int j = 0; j <= i; j ++ )
			sta.insert(sg(i) ^ sg(j));
	
	// mex操作 
	for (int i = 0; ; i ++ ) 
		if (sta.count(i) == 0) {
			f[x] = i;
			break;
		}
	return f[x];
}

int main() {
	memset(f, -1, sizeof(f));
	cin >> n;
	int t, res = 0;
	for (int i = 0; i < n; i ++ ) {
		cin >> t;
		res ^= sg(t);
	}
	if (res) cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0; 
}
版权声明：本文为weixin_44692221原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。