poj 3317 Stake Your Claim 极大极小搜索+alphabeta剪枝

缘起

继续学习 极大极小搜索+alphabeta剪枝 poj 3317 Stake Your Claim

分析

1
2
3
一款新的游戏. 给定n和m, 初始n*n的棋盘上放置着 m个0和m个1. player0在棋盘上放置0，而player1在
棋盘上放置1. player0先手. 当棋盘放满之后, player0(1)的得分就是棋盘上最大的连通的0(1)的区域包含
方块的个数. 得分多的选手获胜. 并且该玩家获得的分数是它的个数减去另一个玩家的个数. 两个终局的样例如下

img

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
为了测试这款游戏, 游戏公司要求你写一个程序————对于任意的开局, 计算对于当前要走的玩家它的最佳走法是
什么? 所谓最佳走法就是能让它得分最大（或者说让对手得分最少）.

【输入】
多样例. 每个样例开始于一个正整数n(n<=8), 然后给出 n*n的数组. 每个位置填写1或者0或者 ., 其中.表示
空白. 0的个数>=1的个数（相等的话, 就是player0走，>的话, 就是player1走）
输入保证空格的个数在[1,10]范围内.

【输出】
对于每个样例，输出最佳的坐标（如果有多个, 则输出字典序最小的那个）. 以及得分

【样例输入】
4
01.1
00..
.01.
...1
4
0.01
0.01
1..0
.1..
0

【样例输出】
(1,2) 2
(2,2) -1

【限制】
2s

其实本游戏也就是先给你一个残局, 不难判断当前是谁走. 然后使用ab剪枝. 计算最大得分. 和【1】很像.

但是区别在于【1】仅仅判定获胜即可, 而本题要计算的是最大得分.

本题展示记忆化搜索如何加速极大极小搜索~ 因为本题空格个数较少（<=10个）,所以完全可以使用三进制压缩空格的填充状态——0表示空白未填, 1表示填写了0, 2表示填写了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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

int n,best, bestx, besty, dir[4][2] = {{-1,0}, {1,0},{0,1},{0,-1}}, tot, top, dp[60000], m[10][10], pow3[15]; // top是空格的个数, dp是记忆化数组, m[i][j]用于表示a[i][j]这个空格是从上至下从左至右第几个空格
char a[10][10];
bool v[10][10];
const int inf = 0x3f3f3f3f;
bool ok(int i, int j)
{
	return ~i && i<n && ~j && j<n && !v[i][j];
}

int dfs(int i, int j)
{
	int ans = 1;
	v[i][j] = true;
	for (int k = 0, nxti, nxtj; k<4; k++)
	{
		nxti = i+dir[k][0], nxtj = j+dir[k][1];
		if (ok(nxti, nxtj) && a[nxti][nxtj] == a[i][j])
		{
			ans+=dfs(nxti, nxtj);
		}
	}
	return ans;
}

int score()
{
	int tot0 = 0, tot1 = 0;
	memset(v, 0, sizeof(v));
	for (int i = 0;i<n; i++)
	{
		for (int j= 0; j<n; j++)
		{
			if (a[i][j]=='0')
			{
				if (!v[i][j])
				{
					tot0 = max(tot0, dfs(i,j));
				}
			}
			else
			{
				if (!v[i][j])
				{
					tot1 = max(tot1, dfs(i,j));
				}
			}
		}
	}
	return tot0-tot1;
}
int Min(int state, int alpha, int num);
int Max(int state, int alpha, int num) // state是空格的填充情况（一个三进制数） num是已经填好的格子个数(注意, 当然可以根据state判断是否已经填满所有空格, 但是没有num来的简洁迅速)
{
	if (dp[state]!=-inf) 
	{
		return dp[state];
	}
	if (num==n*n)
	{
		return dp[state] = score();
	}
	int ans = -inf;
	for (int i = 0;i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			if (a[i][j] == '.')
			{
				a[i][j] = '0';
				int val = Min(state+pow3[m[i][j]], ans, num+1);
				a[i][j] = '.';
				ans = max(ans, val);
				if (num==tot && best<ans) // 在递归的最表层更新答案,因为要字典序最小的那个, 所以必须严格<才更新答案
				{
					best = ans;
					bestx = i;
					besty = j;
				}
				if (ans>=alpha)
				{
					return ans;
				}
			}
		}
	}
	return dp[state] = ans;
}

int Min(int state, int beta, int num)
{
	if (dp[state]!=-inf) 
	{
		return dp[state];
	}
	if (num==n*n)
	{
		return dp[state] = score();
	}
	int ans = inf;
	for (int i = 0;i<n; i++)
	{
		for (int j = 0; j<n; j++)
		{
			if (a[i][j] == '.')
			{
				a[i][j] = '1';
				int val = Max(state+2*pow3[m[i][j]], ans, num+1);
				a[i][j] = '.';
				ans = min(ans, val);
				if (num==tot && best<-ans) // 为什么是-ans? 因为ans依旧也是站在player0的角度给的评分(最小评分),而对于player0的最小评分的相反数不就是player1的最大评分么?
				{
					best = -ans;
					bestx = i;
					besty = j;
				}
				if (ans<=beta)
				{
					return ans;
				}
			}
		}
	}
	return dp[state] = ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	pow3[0] = 1;
	for (int i = 1;i<=10; i++)
	{
		pow3[i] =  3*pow3[i-1];
	} // 初始化3的幂次, 这个在alphabeta的状态演进的计算中可以方便的拿来使用而不需要重复计算
	while(scanf("%d", &n), n)
	{
		int tot0 = 0, tot1 = 0;
		top = 0;
		memset(m,-1, sizeof(m));
		best = -inf;
		for (int i = 0;i<60000; i++)
		{
			dp[i] =  -inf;
		} // 初始化dp
		for (int i = 0;i<n; i++)
		{
			getchar();
			for (int j = 0; j<n; j++)
			{
				a[i][j] = getchar();
				if (a[i][j]=='0')
				{
					++tot0;
				}
				else if (a[i][j]=='1')
				{
					++tot1;
				}
				else
				{
					m[i][j] = top++;
				}
			}
		}
		tot = tot0+tot1; // 伊始总共填写了tot个空格
		tot0==tot1?Max(0,inf,tot):Min(0,-inf,tot); // 初始state为0表示一个空格都没有填写
		printf("(%d,%d) %d\n", bestx, besty, best);
	}
	return 0;
}

ac情况

Status Accepted
Time 47ms
Memory 580kB
Length 3150
Lang G++
Submitted 2019-10-20 06:41:26
Shared
RemoteRunId 20973756

好了, 真是太不容易了~ 极大极小+ab剪枝的板子基本已经成熟了~ 当时第一遍这个算法的时候差点想到脑裂~

参考

【1】https://yfsyfs.github.io/2019/10/17/poj-1568-Find-the-Winning-Move-%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2-alphabeta%E5%89%AA%E6%9E%9D%E4%BC%98%E5%8C%96/

【2】https://yfsyfs.github.io/2019/10/17/%E6%9E%81%E5%A4%A7%E6%9E%81%E5%B0%8F%E6%90%9C%E7%B4%A2%E4%BB%A5%E5%8F%8Aalphabeta%E5%89%AA%E6%9E%9D%E4%BC%98%E5%8C%96/