【随笔】博弈题基础回顾

前言：

首先，本篇主要用于个人的学习整理回顾，有关内容请注意辨别正确与否，本文仅供参考，如有错误欢迎大佬指正🤣

【转载说明】本文优先发布于我的个人博客www.226yzy.com ，转载请注明出处并注明作者：星空下的YZY。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0许可协议。

有题目测试是非常好的，但奈何杭电OJ有时不公开了（写本篇的时候又突然可以了），找题目倒成了件头大的事😵‍💫

博弈题目特点

公平组合游戏(Impartral Combinatorial Game,ICG)是满足以下特征的一类问题：

基本上是两名选手，交替进行题目限定的操作
会假设两名选手在游戏过程中的操作都是最优的
基本上都是以选手无法进行合法的操作时，判定该选手游戏失败

巴什博弈（Bash Game）

问题模型：一堆石子共n个，两人轮流取，可以取1~m个，最后取光者得胜。

相关题目：

1318. 取石子游戏 - AcWing题库

Problem - 1846 (hdu.edu.cn)

尝试：

n=0时，先手败
n<m时，先手胜
n=k(m+1)时，对于每份m+1,设先手取x个(0<x<m+1)，后手都能将剩下的m+1-x个取完，然后先手又面临n=k(m+1)的情况，以此类推，先手最终败。
n=k(m+1)+r时，先手只要取r个，就可以让该情况下的后手成为上面提到的n=k(m+1)时的先手。所以n=k(m+1)+r时先手最终胜。

结论：

综上结论就是双方只要让对手得到的数量为m+1的倍数，自己就可以赢，即先手要胜，那么n%(m+1)>0。

代码：



#include<bits/stdc++.h>
using namespace std;
int main() {
	int n,m;
	scanf("%d%d",&n,&m);
	if(n%(m+1)==0)
		printf("2");
	else 
		printf("1");
	return 0;
}

尼姆博弈（Nim Game）

问题模型：有n堆物品，两人轮流取，每次取某堆中不少于1个，最后取完者胜。

题目：

2234 — Matches Game (poj.org)

Problem - 5795 (hdu.edu.cn)

尝试：

这个就还是看其他大佬的推论吧😂

博弈—尼姆博弈讲解BBHHTT的博客-CSDN博客尼姆博弈

结论：

把每堆物品数全部异或起来，如果得到的值为0，那么先手败

比如（1,2,3）

1	0001^0010^0011=0000

所以（1,2,3），先手败

代码：



#include <iostream>
using namespace std;
int t,ans,r;
int main(){
    while(~scanf("%d",&t)){
        scanf("%d",&ans);
        for(int i=1;i<t;i++){
           scanf("%d",&r);
           ans^=r;
        }
        if(ans>0)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

斐波那契博弈（Fibonacci Nim Game）

问题模型：一堆石子有n个(n>=2)，两人轮流取，先取者第一次可以取任意多个，但是不能取完。之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍。最后取光者得胜。

Problem - 2516 (hdu.edu.cn)

尝试：

n=2时，先手败

n=3时，先手败

n=4时，先手胜（先手取1）

n=5时，先手败

n=6时，先手胜（先手取1后，后手取2，显然最终先手胜；后手取1，则先手回到了n=4时的必胜态）

n=7时，。。。

好吧，虽然若有若无的有点斐波拉契数列的影子，但不太明显，还是看其他大佬的推论吧🤣

斐波那契博弈ACdreamers的博客-CSDN博客斐波那契博弈

结论：

当且仅当石子数为斐波那契数时，先手必败。

代码：



#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100010;
int f[N];
map<int,int>mp;
void fib(){
    f[1]=1,f[2]=1;
    for(int i=3;i<N;i++){
    	f[i]=f[i-1]+f[i-2];
    	mp[f[i]]=1;
	}
}
int main(){
	int n;
	fib();
	scanf("%d",&n);	
	if(mp[n]==1)printf("Sha");
	else printf("Xian");
}

威佐夫博弈（Wythoff Game）

问题模型：有两堆各若干的物品，两个人轮流从任意一堆中至少取出一个或者从两堆中取出同样多的物品，规定每次至少取一个，至多不限，最后取光者胜。

题目：

P2252 SHOI2002]取石子游戏|【模板】威佐夫博弈 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

Problem - 1527 (hdu.edu.cn)

尝试：

这个具体的推论还是也看大佬的吧（我太菜了🤣）

ICG博弈威佐夫博弈（Wythoff Game）及证明单眼皮的根号3的博客-CSDN博客_威佐夫博弈证明

hdu 1527 （威佐夫博弈） - 两点够吗 - 博客园 (cnblogs.com)

不过我们可以列出几个必输局势：（0，0）、（1，2）、（3，5）、（4，7）、（6，10）、（8，13）、（9，15）、（11，18）、（12，20）。从这些必输局势你也许可以发现，每组的第一个是前面没有出现的最小正整数。

通过其他大佬的分析得知，第一个值 ≈差值 * 1.618

而1.618 ≈（sqrt（5）+ 1） / 2

1.618是黄金分割率

结论：

先求出差值，差值*黄金分割比 == 最小值的话后手赢

代码：



#include<bits/stdc++.h>
using namespace std;
int main() {
	int a,b;
	scanf("%d%d",&a,&b);
	int s=abs(a-b);
	int g=s*((sqrt(5)+1)/2);
	if(g==min(a,b))
		printf("0");
	else
		printf("1");
	return 0;
}

SG函数及SG定理

目前还在整理学习中，待续。。。。😂

如需要这些内容不妨先看看下文参考文献中大佬的文章

参考文献

【博弈论】ACM博弈论知识总结Nefu_qky的博客-CSDN博客博弈论acm

ACM-博弈论基础 - 知乎 (zhihu.com)

最后

暂时就写到这了，部分内容还不完善

欢迎访问我的小破站https://www.226yzy.com/ 或者GitHub版镜像 https://226yzy.github.io/ 或Gitee版镜像https://yzy226.gitee.io/

我的Github：226YZY (星空下的YZY) (github.com)

【转载说明】本文优先发布于我的个人博客www.226yzy.com ，转载请注明出处并注明作者：星空下的YZY。

本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0许可协议。

推荐订阅源

星空下的YZY

前言：

博弈题目特点

巴什博弈（Bash Game）

尼姆博弈（Nim Game）

斐波那契博弈（Fibonacci Nim Game）

威佐夫博弈（Wythoff Game）

SG函数及SG定理

参考文献

最后