【学习笔记】博弈论基础

博弈论基础

这里主要讨论两人博弈的博弈，不讨论前沿的多人博弈。

前置知识：

• 注意，无特殊说明，所有博弈论的题目均已双方会选择最优方案的前提下进行。

（所以据说我们 \(K8He\) 老师想要出一个概率出错的博弈论（

• 平等组合游戏 \(ICG\)：两人轮流操作，限制条件对两人相同，有有限状态集合，有终止状态且可以达到的游戏。

所以说五子棋不算平等组合游戏，因为执黑不等于执白。

而我们的博弈游戏，大多是平等组合游戏。

• 必胜状态 \(N\)，必败状态 \(P\)：

（以下所有都不用英文字母表示状态，答案是我猪脑过载反应不过来）

P-position 表示 previous，代表先手必败，即后手必胜，N-position 表示 next，代表先手必胜，后手必败。

很多博文都用字母表示，需要知道（

nim游戏：

有 \(n\) 堆石子，初音ミク 和 歌爱ユキ 轮流选一堆石子取若干（不可不取），没有石子可取的人失败。

（我觉得看完前置知识可以思考一下所以可以不要往下急着走）

ewq

有点复杂是吧？

一点点来推吧：

参考：百度百科

最终状态是一个不剩，是必败状态。

• 如果只剩下一堆石子，全拿走可以转换到最终状态（必败状态），所以只剩下一堆石子是必胜状态。

• 如果只剩下两堆石子：

拿 \((3,3)\) 举例子：

（ps：因为只要能转移到必败状态就是必胜状态，所以省去了一下边和点）

从左上到右下解释一下，因为 \((0,0)\) 是先手必败，所以能转移到它的父局面 \((0,1)\) 是先手必胜，只能转移到 \((0,1)\) 的父局面 \((1,1)\) 是先手必败，\((1,3)\) 能够转移到必败的 \((1,1)\) 是先手必胜。

就像 dfs 一样，而存在大量的重合子，可以考虑记忆化搜索。

时间复杂度是 \(O(a_1\cdot a_2 \cdot a_3\cdot …… \cdot a_n)\)。

但是通过一个定理可以让时间复杂度极大地降低。

定理：如果所有石子数量亦或为 \(0\)，先手必败，否则先手必胜。

而证明这个定理就要证明三个小定理：

• 定理 \(1\)：最终状态是必败状态。

• 定理 \(2\)：对于 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n \neq 0\) 来说，一定存在某种对策使其等于 \(0\)。

• 定理 \(3\)：对于 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n = 0\) 来说，无论如何对策都没有继续等于 \(0\) 的可能。

我们主要来证明难以理解的定理 \(2\)：

设 \(a_1\bigoplus a_2 \bigoplus …\bigoplus a_n=k,(k\in Z,k\neq 0)\)，而其二进制最高位数是 \(d\)。

要让其成为 \(0\)，那么就要让 \(a_i=a_i\bigoplus k\)。

其第 \(d\) 位置上数是 \(1\)，代表着一定有奇数个 \(a_i\) 的第 \(d\) 位置是 \(1\)。

那么一定有 \(a_i \bigoplus k> a_i\)。

具有合法对策。

证毕。

Nim游戏模板

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
namespace mystd{
	il int Max(int a,int b)<%if(a<b) return b;return a; %>
	il int Min(int a,int b)<%if(a>b) return b;return a; %>
	il int Abs(int a)<% if(a<0) return a*(-1);return a; %>
	il double fMax(double a,double b)<%if(a<b) return b;return a; %>
	il double fMin(double a,double b)<%if(a>b) return b;return a; %>
	il double fAbs(double a)<% if(a<0) return a*(-1);return a; %>
	il int dcmp(double a){
		if(a<-eps)	return -1;
		if(a>eps)	return 1;
		return 0;
	}
}const int maxn=1e4+50;

int T,n,a[maxn];
int mj;
il void clear(){
	for(rg i=1;i<=n;++i)	a[i]=0;
	mj=0;
}

int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d",&n);
		for(rg i=1;i<=n;++i){
			scanf("%d",&a[i]);
		}
		for(rg i=1;i<=n;++i)	mj=mj^a[i];
		if(mj==0)	printf("No\n");
		else	printf("Yes\n");
		clear();
	}
	return 0;
} 

杂题乱写（？）

[ARC131C] Zero XOR

[ARC131C] Zero XOR

洛谷题目链接

AtCoder题目链接

题面翻译

给定 \(n\) 堆石子，个数分别为 \(A_1,A_2,\cdots,A_n\)，两两不同。

两个玩家轮流在上面操作，每次操作将任意一堆石子的个数变为 \(0\)，当拿走后 \(A_1\;\text{XOR}\;A_2\;\text{XOR}\;\cdots\;\text{XOR}\;A_n=0\)，则该玩家获胜。

若先手有必胜策略，输出 Win ，否则输出 Lose 。

题目描述

机の上に $ N $ 枚のクッキーがあります。クッキーの表面にはそれぞれ正の整数 $ A_1,\ A_2,\ \dots,\ A_N $ が書かれており、これらはすべて異なります。

このクッキーを使って 2 人でゲームを行います。このゲームでは、各プレイヤーは次の行動を交互に行います。

机にあるクッキーを 1 枚選んで食べる。
その際に、机に残ったクッキーに書かれた整数の $ \mathrm{XOR} $ が $ 0 $ になったならば、そのプレイヤーは勝利し、ゲームは終了する。

あなたは E869120 君に対戦を申し込みました。あなたは先手で、E869120 君は後手です。さて、両者が最適に行動したときに、あなたは E869120 君に勝ちますか？

$ \mathrm{XOR} $ とは 整数 $ A,\ B $ のビット単位 XOR、$ A\ \mathrm{XOR}\ B $ は、以下のように定義されます。

• $ A\ \mathrm{XOR}\ B $ を二進表記した際の $ 2^k $ ( \(k\geq0\)) の位の数は、$ A,\ B $ を二進表記した際の $ 2^k $ の位の数のうち一方のみが $ 1 $ であれば $ 1 $、そうでなければ $ 0 $ である。

例えば、$ 3\ \mathrm{XOR}\ 5\ =\ 6 $ となります (二進表記すると: \(011\mathrm{XOR}101=110\))。
一般に、$ k $ 個の整数 $ p_1,\ p_2,\ p_3,\ \dots,\ p_k$ のビット単位 XOR は $ (\dots\ ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) $ と定義され、これは $ p_1,\ p_2,\ p_3,\ \dots\ p_k $ の順番によらないことが証明できます。特に $ k\ =\ 0 $ の場合、$ \mathrm{XOR} $ は $ 0 $ となります。

输入格式

入力は以下の形式で標準入力から与えられます。

$ N $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $

输出格式

両者が最適に行動したときにあなたが勝つなら Win、負けるなら Lose と出力してください。

样例 #1

样例输入 #1

6
9 14 11 3 5 8

样例输出 #1

Lose

样例 #2

样例输入 #2

1
131

样例输出 #2

Win

样例 #3

样例输入 #3

8
12 23 34 45 56 78 89 98

样例输出 #3

Win

提示

制約

• $ 1\ \leq\ N\ \leq\ 400000 $
• $ 1\ \leq\ A_i\ \leq\ 10^9\ (1\ \leq\ i\ \leq\ N) $
• $ A_1,\ A_2,\ \dots,\ A_N $ はすべて異なる
• $ A_1,\ A_2,\ \dots,\ A_N $ の $ \mathrm{XOR} $ は $ 0 $ ではない
• 入力はすべて整数

Sample Explanation 1

この例では、あなたがどんな方法を使っても、E869120 君が最適に行動し続ければ負けてしまいます。 例えば、最初に $ 11 $ が書かれたクッキーを食べるとしましょう。すると、次に E869120 君が $ 9 $ が書かれたクッキーを食べることで、残ったクッキーに書かれた数 $ 14,\ 3,\ 5,\ 8 $ の $ \mathrm{XOR} $ が $ 0 $ になるので、E869120 君が勝ちます。 それ以外の行動をとっても、最終的には E869120 君が勝ちます。

Sample Explanation 2

この例では、あなたは最初のターンで $ 131 $ が書かれたクッキーを食べることしかできません。すると、机の上からクッキーがなくなるので、残ったクッキーに書かれた数の $ \mathrm{XOR} $ は $ 0 $ になります。したがって、E869120 君が何もできないまま、あなたが勝ちます。

解题：

形式化一下：有长度为 \(n\) 的数列，任意删数，最后数列亦或和为 \(0\) 赢。