【博弈论】组合游戏及SG函数浅析

目录

预备知识

普通的Nim游戏

SG函数

预备知识

公平组合游戏(ICG)

若一个游戏满足:

  • 由两名玩家交替行动;
  • 游戏中任意时刻,合法操作集合只取决于这个局面本身;
  • 若轮到某位选手时,若该选手无合法操作,则这名选手判负;

则称该游戏为一个公平组合游戏

Nim游戏

有若干堆石子,每堆石子的数量都是有限的,合法的移动是“选择一堆石子并拿走若干颗(不能不拿)”,如果轮到某个人时所有的石子堆都已经被拿空了,则判负(因为他此刻没有任何合法的移动)。

mex(minimal exdudant)函数

\(S\) 表示一个非负整数集合。定义 \(mex(S)\) 为求出不属于集合 \(S\) 的最小非负整数的运算。
如:{ \(0,1,3\) } 对应的 \(mex值\) 就是 \(2\)

SG函数简介

定义 \(SG(x)=mex(S)\) ,其中 \(S\)\(x\) 的后继状态对应的 \(SG函数值\) 的集合。

\(SG\)函数板块对应的模板题中(见下),\(x\) 代表着该堆石子的数量。

普通的Nim游戏

题目传送门:https://www.acwing.com/problem/content/893/
题面:给定n堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。

分析

这题的结论十分地简洁,就是:
\(a_{1} \bigoplus a_{2} \bigoplus a_{3}…\bigoplus a_{n}=0\) ,则先手必负,否则先手必胜。

证明:

我们记 \(a_{1} \bigoplus a_{2} \bigoplus a_{3}…\bigoplus a_{n}\) 为数列a的异或和,以下简记为异或和

先给出两条引理:

  • \(a_{1} \bigoplus a_{2} \bigoplus a_{3}…\bigoplus a_{n}=x~(x>0)\) 时,必可以从一堆石子中拿走若干个石子,使得异或和\(0\)
    证明:\(x\) 的最高位(记为第 \(k\) 位)是 \(1\)\(a\) 中必然存在 \(a_i\) 满足 \(a_i\)\(k\) 位是 \(1\) ,那么我们将 \(a_i\) 变为 \(a_i \bigoplus x\) (因为 \(x\not=0\),所以这样操作一定合法),那么变换后的异或和即为 \(0\)

  • \(a_{1} \bigoplus a_{2} \bigoplus a_{3}…\bigoplus a_{n}=0\) 时,不存在合法操作,使得异或和仍为 \(0\)
    证明:假设将 \(a_i\) 变为 \(v\)异或和\(0\)
    \(a_{1} \bigoplus a_{2}… \bigoplus a_{i}…\bigoplus a_{n}=0\) ,我们将这个式子与上式 \(a_{1} \bigoplus a_{2}… \bigoplus v…\bigoplus a_{n}=0\) 联立,即得 \(a_{i}\bigoplus v=0\),意味着 \(a_{i}=v\) ,即 \(a_{i}\) 不变,不是合法操作,故矛盾。

证明完引理后就不难了:
若轮到先手时,异或和\(0\) ,那么无论先手如何行动,后手都可以进行操作,使再次轮到先手时异或和仍为 \(0\) ,而游戏结束时异或和必然为 \(0\) ,故先手必败。
反之(即若轮到先手时,异或和不为 \(0\) )后手必败。

代码:

#include<bits/stdc++.h>
using namespace std;

int main(){
	int n;
	cin>>n;
	int res=0;
	for(int i=1;i<=n;i++){
		int k; cin>>k;
		res^=k;
	}
	if(res) puts("Yes");
	else puts("No");
	return 0;
}

SG函数

利用一道模板题引入:
题目传送门https://www.acwing.com/problem/content/description/895/
题面
给定 \(n\) 堆石子以及一个由 \(k\) 个不同正整数构成的数字集合 \(S\)

现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合 \(S\) ,最后无法进行操作的人视为失败。

问如果两人都采用最优策略,先手是否必胜。

分析

先从一堆石子分析开始:

例如:该堆石子有 \(6\) 个,每次可取 \(2\)\(3\) 个,求 \(SG(6)\)
我们可以画出一棵树,代表着两人的决策树。

注意到 \(SG(0)=0\)

根据 \(SG\) 函数的定义,对于决策树上的点对应 \(SG\) 函数值为:

我们还可以自己构造一棵 \(SG\) 函数值构成的树:

从中我们可以直观地看出 \(SG\) 的两个重要性质:

  • \(0\) 结点可以到 \(0\) 结点
  • \(0\) 结点一定不可以到非 \(0\) 结点

根据 \(SG\) 函数的性质以及游戏规则,\(SG(x)=0\) 时意味着相应的玩家必负。

分析多堆石子的情况:

我们规定,对于每堆石子 \(G_i\) ,对应的 \(SG(G_i)=SG(x)\) ,其中 \(x\) 是该堆石子最初的数量

结合这棵树:

\(SG\) 函数可以看出,当先手进行决策后,对应的的 \(SG\) 函数值可以为 \([0,SG(x)-1]\),这恰好就像我们最初讨论的普通的Nim问题中取石子的规则!

在这里,我们将 \(SG\) 函数值看成是普通的Nim问题中石子的数量就可以用相同的方法解决了。

\(SG\) 函数的办法

我采取的是记忆化搜索的办法,见下:

int f[M]; // SG函数的值
int s[N]; // 可以取多少石子

int sg(int x){
	if(f[x]!=-1) return f[x]; // 当已经更新过就直接返回。
	
	unordered_set<int> S;
	for(int i=1;i<=k;i++)
		if(x-s[i]>=0) S.insert(sg(x-s[i]));
	
	for(int i=0;;i++)
		if(!S.count(i)) return f[x]=i;
}

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=105 ,M=1e4+5;
int n,k;
int f[M]; // SG函数的值
int s[N]; // 可以取多少石子

int sg(int x){
	if(f[x]!=-1) return f[x]; // 当已经更新过就直接返回。
	
	unordered_set<int> S;
	for(int i=1;i<=k;i++)
		if(x-s[i]>=0) S.insert(sg(x-s[i]));
	
	for(int i=0;;i++)
		if(!S.count(i)) return f[x]=i;
}

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

给TA买糖
共{{data.count}}人
人已赞赏
经验教程

时间同步chrony,最全最细

2021-3-17 17:47:00

经验教程

顺序容器初探(上)

2021-3-17 20:22:00

⚠️
免责声明:根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。 本站为个人博客非盈利性站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途,网站会员捐赠是您喜欢本站而产生的赞助支持行为,仅为维持服务器的开支与维护,全凭自愿无任何强求。本站部份代码及教程来源于互联网,仅供网友学习交流,若您喜欢本文可附上原文链接随意转载。
无意侵害您的权益,请发送邮件至 momeis6@qq.com 或点击右侧 私信:momeis 反馈,我们将尽快处理。
0 条回复 A文章作者 M管理员
    暂无讨论,说说你的看法吧
个人中心
今日签到
有新私信 私信列表
搜索