题解
9 分钟 读完 (大约 1348 个字) 0次访问

UVA751 - Triangle War

【UVA751】Triangle War
题目链接1: https://www.luogu.com.cn/problem/UVA751
题目链接2: https://www.luogu.com.cn/jump/uva/751

前言

最近看R在玩某树来做黑白棋AI，让我也想学习博弈相关内容。然后学了max-min策略，然后又学了alpha-beta剪枝。

这个题是练习max-min策略+alpha-beta剪枝的好题，但是我们也可以记忆化搜索。

并且此题状态少，记忆化只需要20ms，比用alpha-beta剪枝的做法要快一些。

分析

当然我做这道题还是想学习alpha-beta剪枝的，使用此算法的题解已有，所以不多加解释。

此题有两种max-min策略的解法，解法1是最大最小化最终胜负（1为先手胜利，-1为后手胜利），解法2是最大最小化最终得分差（先手得分-后手得分），当然流程就是先手最大化此值，后手最小化此值。

至于局面的存储，与已有题解类似，存储边的编号，然后用二进制表示已连接的边。而三角形连接我们就手写一个数组表示需要哪三条边（很麻烦）。这个题只有单位三角形得分，似乎题意里没说。

再来说两种解法的差异，因为最终胜负在一方大于等于5分就可判定，所以解法1效率较高，并且我们还可用使用alpha-beta剪枝来优化。

当然我们也可以用解法2。有一个显然的结论，无论此步是A还是B，一个状态只会对应一个最优得分。那么就可以使用记忆化，已知状态总共有$(1 << 18) - 1$种，这样效率就高了。并且我们每组数据前不需要清空记忆化数组，因为一个状态对应一个分数，并不需要知道你是如何到达此状态的。

实现时先模拟给出的N步，然后记录双方已得分数。然后max_min搜索，如果此步得分，继续操作，如果此步不得分，就让对手操作，然后减去对手操作的分数，如果全部连接就返回0，每层都是最大化自己的得分。至于为什么双方都是最大化，我给出以下解释：A最大化(A的得分-B的得分)，B最大化(B的得分-A的得分)，所以都是最大化。

在最终判定胜负时，设当前玩家为p(p为0或1)，若p已得分数+max_min(从p开始)的结果>(p^1)的分数就判定p胜利，否则(p^1)胜利。

代码

解法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <stdio.h>
using namespace std;
int edg[11][11];
int tri[] = {(1 << 0) + (1 << 1) + (1 << 2),
			 (1 << 3) + (1 << 4) + (1 << 7),
			 (1 << 2) + (1 << 4) + (1 << 5),
			 (1 << 5) + (1 << 6) + (1 << 10),
			 (1 << 8) + (1 << 9) + (1 << 15),
			 (1 << 7) + (1 << 9) + (1 << 11),
			 (1 << 11) + (1 << 12) + (1 << 16),
			 (1 << 10) + (1 << 12) + (1 << 13),
			 (1 << 13) + (1 << 14) + (1 << 17)};
#define addedge(x, y, z) (edg[x][y] = edg[y][x] = z)
void init() {
	addedge(1, 2, 0);
	addedge(1, 3, 1);
	addedge(2, 3, 2);
	// ...
	// 本连边方式不推荐学习，因此部分内容已省略，相信有更好的方式
	return;
}
int T, n, tmpx, tmpy;
int nextStep(int lst, int nst) {
	int cnt = 0;
	// lst 为之前状态 nst 为当前状态
	for(int i = 0; i < 9; i++)
		if((lst & tri[i]) != tri[i] && (nst & tri[i]) == tri[i]) ++cnt;
	return cnt;
}
const int full = (1 << 18) - 1;
int alpha_beta(int nowp, int st, int alpha, int beta, int ans[2]) {
	if(ans[0] >= 5) return 1;
	if(ans[1] >= 5) return -1;
	int fst = full ^ st, nst;
	while(fst) {
		int edge = fst & (-fst);
		// 枚举连边
		int res = nextStep(st, (nst = st | edge));
		if(res) {
			ans[nowp] += res;
			(nowp ? beta : alpha) = (nowp ? min< int > : max< int >)((nowp ? beta : alpha), alpha_beta(nowp, nst, alpha, beta, ans));
			ans[nowp] -= res;
		}
		else {
			(nowp ? beta : alpha) = (nowp ? min< int > : max< int >)((nowp ? beta : alpha), alpha_beta(nowp ^ 1, nst, alpha, beta, ans));
		}
		// 压行写法
		if(alpha >= beta) break;
		// alpha-beta剪枝
		fst -= edge;
	}
	return nowp ? beta : alpha;
}
int main() {
	init();
	cin >> T;
	for(int t = 1; t <= T; t++) {
		cin >> n;
		int st = 0, p = 0, ans[2] = {0};
		for(int i = 1; i <= n; i++) {
			cin >> tmpx >> tmpy;
			int res = nextStep(st, st | (1 << edg[tmpx][tmpy]));
			st = st | (1 << edg[tmpx][tmpy]);
			if(res) {
				ans[p] += res;
			}
			else {
				p ^= 1;
			}
		}
		// 模拟
		int res = alpha_beta(p, st, -0x3f3f3f3f, 0x3f3f3f3f, ans);
		cout << "Game " << t << ": ";
		if(res >= 0) {
			cout << "A wins." << endl;
		}
		else {
			cout << "B wins." << endl;
		}
	}
	return 0;
}

解法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <iostream>
#include <stdio.h>
using namespace std;
int edg[11][11];
int tri[] = {(1 << 0) + (1 << 1) + (1 << 2),
			 (1 << 3) + (1 << 4) + (1 << 7),
			 (1 << 2) + (1 << 4) + (1 << 5),
			 (1 << 5) + (1 << 6) + (1 << 10),
			 (1 << 8) + (1 << 9) + (1 << 15),
			 (1 << 7) + (1 << 9) + (1 << 11),
			 (1 << 11) + (1 << 12) + (1 << 16),
			 (1 << 10) + (1 << 12) + (1 << 13),
			 (1 << 13) + (1 << 14) + (1 << 17)};
#define addedge(x, y, z) (edg[x][y] = edg[y][x] = z)

const int full = (1 << 18) - 1;
int mm[full + 1];

void init() {
	addedge(1, 2, 0);
	addedge(1, 3, 1);
	addedge(2, 3, 2);
	// ...
	// 本连边方式不推荐学习，因此部分内容已省略，相信有更好的方式
	for(int i = 0; i < full; i++) mm[i] = -0x3f3f3f3f;
	mm[full] = 0;
	return;
}


int T, n, tmpx, tmpy;
int nextStep(int lst, int nst) {
	// lst 为之前状态 nst 为当前状态
	int cnt = 0;
	for(int i = 0; i < 9; i++)
		if((lst & tri[i]) != tri[i] && (nst & tri[i]) == tri[i]) ++cnt;
	// 本次得分
	return cnt;
}

int max_min(int nowp, int st) {
	if(mm[st] != -0x3f3f3f3f) return mm[st];
	int fst = full ^ st, nst, maxx = -0x3f3f3f3f;
	while(fst) {
		int edge = fst & (-fst);
		// 枚举连边
		int res = nextStep(st, (nst = st | edge));
		if(res) {
			maxx = max(maxx, res + max_min(nowp, nst));
		}
		else {
			maxx = max(maxx, -max_min(nowp ^ 1, nst));
		}
		fst -= edge;
	}
	return mm[st] = maxx;
}
int main() {
	init();
	cin >> T;
	for(int t = 1; t <= T; t++) {
		cin >> n;
		int st = 0, p = 0, ans[2] = {0};
		for(int i = 1; i <= n; i++) {
			cin >> tmpx >> tmpy;
			int res = nextStep(st, st | (1 << edg[tmpx][tmpy]));
			st = st | (1 << edg[tmpx][tmpy]);
			if(res) {
				ans[p] += res;
			}
			else {
				p ^= 1;
			}
		}
		// 模拟
		int res = max_min(p, st);
		cout << "Game " << t << ": ";
		if((ans[p] + res > ans[p ^ 1]) ^ p) {
			cout << "A wins." << endl;
		}
		else {
			cout << "B wins." << endl;
		}
	}
	return 0;
}

后记

不过这个题3s时限怕是有点水了。

然后还可以做 【九省联考2018】一双木棋chess，也可以使用max-min策略+记忆化搜索。

# , , ,
LuoguP3695 - CYaRon!语
CSP-S 2019 · AFO游记

评论

关注我

链接

分类

标签云

Cpp GCD HTML JavaScript LCA STL ST表 alpha-beta剪枝 主席树 二分查找 分块 前缀和 动态规划 块状链表 字典树 字符串 左偏树 并查集 技巧 搜索 数论 整除分块 模拟 比赛 爬虫 状压DP 码风 离散化 粤语 线段树 背包 莫比乌斯反演 莫队 解释器 记忆 记忆化搜索 语录 边压Trie 闲聊 随机化搜索 项目 颓废 题解

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22

最新文章

归档

标签

Cpp 29
GCD 1
HTML 1
JavaScript 1
LCA 1
STL 2
ST表 1
alpha-beta剪枝 1
主席树 1
二分查找 1
分块 3
前缀和 1
动态规划 5
块状链表 1
字典树 1
字符串 1
左偏树 1
并查集 2
技巧 3
搜索 6
数论 1
整除分块 1
模拟 4
比赛 1
爬虫 3
状压DP 2
码风 1
离散化 1
粤语 1
线段树 1
背包 1
莫比乌斯反演 1
莫队 1
解释器 1
记忆 1
记忆化搜索 1
语录 1
边压Trie 1
闲聊 7
随机化搜索 2
项目 3
颓废 6
题解 22
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×