登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.3 博弈论 › 博弈论 / 搜索
JSON MD

7.3 博弈论

sg函数 sg
56 行
CPP JSON
【sg函数(sg)】 SG 函数(Sprague-Grundy)模板,用于公平组合游戏的胜负判定。 核心函数: void get_sg(int n) — 获取值 关键配置: N=1e5 + 5 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 56 行 CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int sg[N], f[105], k; // f存允许的步数(需升序), k是步数种类
int vis[N];

void get_sg(int n) {
	for (int i = 1; i <= n; i++) {
		// vis时间戳黑科技:严格O(1)标记,绝对不写 memset
		for (int j = 1; j <= k && f[j] <= i; j++) {
			vis[sg[i - f[j]]] = i;
		}
		// 求 mex
		for (int j = 0; ; j++) {
			if (vis[j] != i) {
				sg[i] = j;
				break;
			}
		}
	}
}
int main() {
	// 1. 初始化规则数组 (必须升序!)
	k = 3;
	f[1] = 1; 
	f[2] = 3; 
	f[3] = 4;
	// sort(f + 1, f + 1 + k); // 如果题目给的规则没排序,一定要加上这句!
	
	// 2. 预处理 SG 函数
	// 假设题目告诉你,单堆石子最多 10000 个
	get_sg(10000); 
	
	// 3. 处理多堆石子的异或和
	int m;
	cin >> m; // m 堆石子
	
	int ans = 0;
	for (int i = 1; i <= m; i++) {
		int a;
		cin >> a; // 读入这一堆有 a 个石子
		
		// 核心:把这一堆的 sg 值异或进去
		ans ^= sg[a]; 
	}
	
	// 4. 审判时刻
	if (ans != 0) {
		cout << "先手必胜!" << endl;
	} else {
		cout << "后手必胜!" << endl;
	}
	
	return 0;
}
对抗搜索+Alpha-Beta (一双木棋chess TLE) 最大分数
54 行
CPP JSON
【对抗搜索+Alpha-Beta (一双木棋chess TLE)(最大分数)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 int findmin(Re alpha,Re op) — 查找(并查集寻根/二分查找) int findmax(Re beta,Re op) — 查找(并查集寻根/二分查找) 关键配置: N=13,inf=2e9 说明:freopen("123.txt","r",stdin); 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 53 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=13,inf=2e9;
int n,m,cnt,h[N],can[N],vis[N][N],A[2][N][N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int findmin(Re alpha,Re op);
inline int findmax(Re beta,Re op);
inline int findmin(Re alpha,Re op){
	if(cnt==n*m)return 0;
	Re ans=inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			ans=min(ans,-A[op][i][j]+findmax(ans+A[op][i][j],op^1));
			vis[i][j]=-1,--cnt,--h[i];
			if(ans<=alpha)return ans;
		}
	return ans;
}
inline int findmax(Re beta,Re op){
	if(cnt==n*m)return 0;
	Re ans=-inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			ans=max(ans,A[op][i][j]+findmin(ans-A[op][i][j],op^1));
			vis[i][j]=-1,--cnt,--h[i];
			if(ans>=beta)return ans;
		}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[1][i][j]);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[0][i][j]);
	memset(vis,-1,sizeof(vis));
	h[0]=inf; 
	printf("%d\n",findmax(inf,1));
}
对抗搜索+Alpha-Beta (Find the Winning Move) 胜负
72 行
CPP JSON
【对抗搜索+Alpha-Beta (Find the Winning Move)(胜负)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 int check(Re op) — 判定/检查函数 int findmin(Re alpha,Re op) — 查找(并查集寻根/二分查找) int findmax(Re beta,Re op) — 查找(并查集寻根/二分查找) 关键配置: N=6,inf=2e9 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 71 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#define LL long long
#define Re register int
using namespace std;
const int N=6,inf=2e9;
int n=4,cnt,ansX,ansY,A[N][N];char op[5],s[N];
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline int check(Re op){
	for(Re i=1;i<=n;++i){
		Re cnt1=0,cnt2=0;
		for(Re j=1;j<=n;++j)cnt1+=(A[i][j]==op),cnt2+=(A[j][i]==op);
		if(cnt1==4||cnt2==4)return 1;
	}
	Re cnt1=0,cnt2=0;
	for(Re i=1;i<=n;++i)cnt1+=(A[i][i]==op),cnt2+=(A[i][n-i+1]==op);
	if(cnt1==4||cnt2==4)return 1;
	return 0;
}
inline int findmin(Re alpha,Re op);
inline int findmax(Re beta,Re op);//[op=1:�ҵĻغ�]
inline int findmin(Re alpha,Re op){
	if(cnt==16)return 0;
	if(check(op^1))return inf;
	Re ans=inf;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			if(A[i][j]==-1){
				A[i][j]=op,++cnt;
				ans=min(ans,findmax(ans,op^1));
				A[i][j]=-1,--cnt;
				if(ans<=alpha)return ans;
			}
	return ans;
}
inline int findmax(Re beta,Re op){
	if(cnt==16)return 0;
	if(check(op^1))return -inf;
	Re ans=-inf;
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=n;++j)
			if(A[i][j]==-1){
				A[i][j]=op,++cnt;
				ans=max(ans,findmin(ans,op^1));
				A[i][j]=-1,--cnt;
				ansX=i,ansY=j;
				if(ans>=beta)return ans;
			}
	return ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	while(~scanf("%s",op)&&op[0]!='$'){
		cnt=0;
		for(Re i=1;i<=n;++i){
			scanf("%s",s+1);
			for(Re j=1;j<=n;++j)
				if(s[j]=='.')A[i][j]=-1,++cnt;
				else A[i][j]=(s[j]=='x');
		}
		if(cnt<=4)puts("#####");
		else if(findmax(inf,1)==inf)printf("(%d,%d)\n",ansX-1,ansY-1);
		else puts("#####");
	}
}
对抗搜索+记忆化 (一双木棋chess) 最大分数
45 行
CPP JSON
【对抗搜索+记忆化 (一双木棋chess)(最大分数)】 博弈论算法模板。 核心函数: void in(Re &x) — 核心算法函数 LL Hash(Re op) — 哈希计算 int dfs(Re op) — 深度优先搜索遍历 关键配置: N=13,inf=2e9 说明:freopen("123.txt","r",stdin); 适用场景:公平组合游戏胜负判定、Nim-like 游戏分析
C++ 44 行 CPP
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<map>
#define LL long long
#define Re register int
using namespace std;
const int N=13,inf=2e9;
int n,m,cnt,h[N],can[N],vis[N][N],A[2][N][N];
map<LL,int>pan;
inline void in(Re &x){
    int f=0;x=0;char c=getchar();
    while(c<'0'||c>'9')f|=c=='-',c=getchar();
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
    x=f?-x:x;
}
inline LL Hash(Re op){LL ans=op+1;for(Re i=1;i<=n;++i)ans=ans*11ll+h[i];return ans;}
inline int dfs(Re op){
	if(cnt==n*m)return 0;
	LL H=Hash(op);
	if(pan.find(H)!=pan.end())return pan[H];
	Re ans=op?-inf:inf;
	for(Re i=1,j;i<=n;++i)
		if(h[i]<m&&vis[i][j=h[i]+1]==-1&&h[i-1]>=j){
			vis[i][j]=op,++cnt,++h[i];
			if(op)ans=max(ans,dfs(op^1)+A[op][i][j]);
			else ans=min(ans,dfs(op^1)-A[op][i][j]);
			vis[i][j]=-1,--cnt,--h[i];
		}
	return pan[H]=ans;
}
int main(){
//	freopen("123.txt","r",stdin);
	in(n),in(m);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[1][i][j]);
	for(Re i=1;i<=n;++i)
		for(Re j=1;j<=m;++j)
			in(A[0][i][j]);
	memset(vis,-1,sizeof(vis));
	h[0]=inf;
	printf("%d\n",dfs(1));
}
已复制