当前位置：首页 > article >正文

博弈论学习笔记【施工中】

article 2024/10/21 9:28:56

SG函数

首先定义就不用我讲了吧，还不会的自己看看传送门

再进一步理解一下吧：
在这里插入图片描述
黑色数字是节点编号，红色是 $SG$ 函数值

看下它的过程：

首先 $5$ 和 $6$ 没有后继节点，为必败态，先赋值为 $0$
$3$ 只有 $6$ 一个后继节点，计算得 $1$
现在我们已经得出了 $2$ 和 $4$ 的所有后继节点的值，进而给它赋值
最后统计 $1$ 的子节点中含有的值有 $0 ， 1 ， 2$ ，取值 $3$

最关键是定义知道了这个东西怎么用呢？首先我们需要明白两点：

$SG$ 函数是 $x or$ 起来用的，故而可能存在两种状态 $x or$ 起来并不能达到必胜/必败态，故而不能仅仅只赋值为 $0$ 和 $1$ 。
$SG$ 函数的值是可以由我们任意决定的，我们主要通过搜索的方式进行赋值。

那么我们来抓个典型

【SSLOJ 1633】B君的游戏

B君和L君要玩一个游戏。刚开始有 $n$ 个正整数 $a_i$ 。

双方轮流操作。每次操作，选一个正整数 $x$ ，将其移除，再添加 $7$ 个数字 $x_1,x_2...x_7$ 。要求对于 $x_i$ ，满足 $0<=x_i<x$ 且 $x \& x_i = x_i$

注意 $0$ 不能被选取，所以这个游戏一定会结束，而谁无法操作谁就失败。

B君根据自己的经验，认为先手胜率高一点，所以B君是先手。

B君想知道自己是否必胜。

第一行一个整数 $n (1 <= n <= 100000)$

以下 $n$ 行 $n$ 个数 $a_i (0 <= a_i < 2^{64})$

输入样例

输出样例

基本思路

很显然，后继状态及结果至于 $x$ 中 $1$ 的个数有关，因为本质就是从 $x$ 中选几个 $1$ 出来嘛。这题我们暴力打出每种 $1$ 的个数下的 $SG$ 函数就可以了。

上代码，我们也借此了解一下 $SG$ 函数是如何被计算的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int M=7e7+10;
int sg[70];
bool vis[M]; 
inline void dfs(int num,int p,int ans,int cur){
//	搜索求解sg函数值 
//	num限制最大值,cur限制最小值,p控制递归层数
	if(p==0){
		vis[ans]=true;
		return;
	}
	for(int i=cur;i<num;i++){
		dfs(num,p-1,ans^sg[i],i);
	}
}
inline void init(){
	printf("{");
	sg[0]=0;
	for(int i=1;i<=64;i++){
		memset(vis,0,sizeof(vis));
		dfs(i,7,0,0);
		for(int j=0;j<M;j++){
			if(vis[j]==false){
				sg[i]=j;
				break;
			}
		}
		cout<<i<<":";
		printf("%d",(sg[i]));
		if(i<64) printf(",");
	}
	cout<<"}";
}
int main(){
//	ios::sync_with_stdio(false);
	init();
	return 0;
}

我们先仔细看看搜索部分

inline void dfs(int num,int p,int ans,int cur){
//	搜索求解sg函数值 
//	num限制最大值,cur限制最小值,p控制递归层数
	if(p==0){
		vis[ans]=true;
		return;
	}
	for(int i=cur;i<num;i++){
		dfs(num,p-1,ans^sg[i],i);
	}
}

Q1:为什么要用 $p$ 来限制递归层数，而且可以在 $ini t$ 中看到限制了 $7$ 层？

这个 $7$ 就是题目中说的选出 $7$ 个数，因为选出来的数 $1$ 的个数都比 $x$ 要少，故而他们的 $SG$ 值都算好了，将他们 $x or$ 起来就可以得到当前答案了。

Q2：为什么要将他们的后继节点的 $SG$ 值都异或起来呢？

因为我们可以发现实际上 $SG$ 函数的用法就是异或起来，据此判断先后手必胜，详细证明会很麻烦。

O3为什么还要限制最小值呢？

因为仔细观察你就会发现这实际上是将全排列转换成了组合计数，减少了时间复杂度，删去了重复的递归，因为后面选择的数是严格大于等于前面选择的数的。

Q4： $v i s$ 数组是干什么用的？

这个显然就是进行 $m e x$ 运算的，记录后继状态中有那些值，然后向 $ini t$ 中求解。

最后输出就像这样：

{1:1,2:2,3:4,4:8,5:16,6:32,7:64,8:128,9:255,10:256,11:512,12:1024,13:2048,14:3855,15:4096,16:8192,17:13107,18:16384,19:21845,20:27306,21:32768,22:38506,23:65536,24:71576,25:92115,26:101470,27:131072,28:138406,29:172589,30:240014,31:262144,32:272069,33:380556,34:524288,35:536169,36:679601,37:847140,38:1048576,39:1072054,40:1258879,41:1397519,42:2005450,43:2097152,44:2121415,45:2496892,46:2738813,47:3993667,48:4194304,49:4241896,50:4617503,51:5821704,52:7559873,53:8388608,54:8439273,55:8861366,56:11119275,57:11973252,58:13280789,59:16777216,60:16844349,61:17102035,62:19984054,63:21979742,64:23734709}
--------------------------------
Process exited after 104 seconds with return value 0
请按任意键继续. . .

我这里还加了编号，用的时候自然得去掉。

核心代码

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
ull sg[70]={0,1,2,4,8,16,32,64,128,255,256,512,
			1024,2048,3855,4096,8192,13107,16384,
			21845,27306,32768,38506,65536,71576,
			92115,101470,131072,138406,172589,240014,
			262144,272069,380556,524288,536169,679601,
			847140,1048576,1072054,1258879,1397519,
			2005450,2097152,2121415,2496892,2738813,
			3993667,4194304,4241896,4617503,5821704,
			7559873,8388608,8439273,8861366,11119275,
			11973252,13280789,16777216,16844349,
			17102035,19984054,21979742,23734709};
ull n,a,ans,sum;
int main() {
	ios::sync_with_stdio(false);
	cin>>n;
	while(n--){
		cin>>a;
		sum=0;
		while(a){
			a^=(a&(-a));
			sum++;
		}
		ans^=sg[sum];
	}
	if(ans) cout<<"B";
	else cout<<"L";
	return 0;
}

再抓个典型巩固一下

【luogu P10501】 Cutting Game

P.S.进一步可点击链接前往往洛谷参考题解。

题面翻译

【题目描述】

Urej 喜欢玩各种类型的沉闷游戏。他通常会邀请其他人和他一起玩。他说，玩这些游戏可以展现他的非凡智慧。最近，Urej 对一个新游戏产生了极大兴趣，而 Erif Nezorf 成为了牺牲品。为了摆脱玩这样一个沉闷游戏的痛苦，Erif Nezorf 请求你的帮助。这个游戏使用一个由 $\times H$ 格网组成的矩形纸张。两名玩家轮流将纸张切割成两个矩形部分。在每个回合中，玩家可以横向或纵向切割，保持每个格网完整。经过 $N$ 轮后，纸张将被切割成 $N + 1$ 片，然后在后续的回合中，玩家可以选择任意一片进行切割。如果一名玩家切割出一个只有一个格网的纸片，他就赢得了游戏。如果这两个人都非常清楚，你应该写一个问题来告诉是否先手的玩家能赢得游戏。

【输入格式】

输入包含多个测试用例。每个测试用例在一行中只包含两个整数 $W$ 和 $\le W , H \le 200)$ ，分别表示原始纸张的宽度和高度。

【输出格式】

对于每个测试用例，应该只输出一行。如果先手的玩家能赢得游戏，则输出 “WIN”，否则输出 “LOSE”。

样例 #1

样例输入 #1

2 2
3 2
4 2

样例输出 #1

LOSE
LOSE
WIN

基本思路

这个也很显然，状态是什么？就是一张纸的长和宽嘛，长和宽就对应了它的 $SG$ 值。可能有同学会疑问，可是我们裁出的是两张纸啊，不一定非要再这张上进行操作，在另一张纸上裁一刀周旋一下嘛。问题是我们最后要把各个状态的 $SG$ 值异或起来啊，一定是会把两个状态（两张纸）异或起来才是答案嘛。

好了，就像上面说的，这次还是搜索求 $SG$ 值吗？显然不会是，我们会用递归（这两个思想还是有点区别的）。上一道题的搜索是在搜什么？就是排列组合它的状态啊，我们这道题还要用上面这种方式找出它的所有后继状态吗？我们裁出的是两张，那直接 $f or$ 循环枚举裁出的长度就可以了。但这道题一定要注意，不能裁出含有一边长度为 $1$ 的，那就是必败了（显然不符合博弈论双方都采用最优措施的设定了）

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=210;
const int S=7e4+10;
int sg[N][N],w,h;
inline int SG(int x,int y){
	if(sg[x][y]!=-1) return sg[x][y];
	bool vis[S];
	memset(vis,0,sizeof(vis));
	for(int i=2;i<x-1;i++) vis[SG(i,y)^SG(x-i,y)]=true;
	for(int i=2;i<y-1;i++) vis[SG(x,i)^SG(x,y-i)]=true;
	//计算
	for(int i=0;i<S;i++)if(vis[i]==false)
		return sg[x][y]=i;
}
int main(){
	ios::sync_with_stdio(false);
	memset(sg,-1,sizeof(sg));
	while(cin>>w>>h){
		if(SG(w,h)==0) cout<<"LOSE\n";
		if(SG(w,h)) cout<<"WIN\n";
	}
    return 0;
}