poj 1568 Find the Winning Move 极大极小搜索+alphabeta剪枝优化

缘起

继续研究 alphabeta剪枝. poj 1568 Find the Winning Move

分析

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
小时候玩的井字棋(外国人叫 tick tack toe,圈圈叉叉棋)
给出一个4*4的棋盘，一盘棋已经进行了部分，接下来是先手下，如果出现了连续4个同样的，就算胜。
问先手有没有必胜策略,若有，输出能够赢的最小的坐标？
(所谓最小指的是(0,0)是第一个坐标,(0,1)是第二个,...(3,3)是最后一个,
最小是指下哪一步能使得最快获胜,这就是告诉我们要按照从上到下,从左到右顺序搜索)

【输入】
多样例. 每个样例以 ? 开头, 全部数据以 $ 结束.  每个样例用4*4数组刻画, . 表示空白处, x表示叉
o表示圈. x先手.

【输出】
如果x有必胜策略, 输出第一步最小的坐标, 否则输出#####

【样例输入】
?
....
.xo.
.ox.
....
?
o...
.ox.
.xxx
xooo
$

【样例输出】
#####
(0,1)

【限制】
3s

这种棋类博弈问题属于典型的极大极小搜索问题. 而且这个游戏搜索深度比较浅, 不需要设置搜索深度. 注意, 和【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
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

char a[4][4];
int tot = 0,ans, ansx, ansy, aa[4][4];

bool finish(int num, int &ret)
{
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			if (a[i][j]=='.') // . 代表0 
			{
				aa[i][j] = 0;
			}
			else if (a[i][j]=='o') // o 代表 -1
			{
				aa[i][j] = -1;
			}
			else
			{
				aa[i][j] = 1; // x代表1
			}
		}
	} // 将a数字化, 方便判断
	int sum;
	for (int i = 0; i<4; i++)
	{
		sum = 0;
		for (int j = 0; j<4; j++)
		{
			sum+=aa[i][j];
		}
		if (sum==-4) // o胜
		{
			ret = -1;
			return true; // 胜负已分
		}
		else if (sum==4) // x胜
		{
			ret = 1;
			return true; // 胜负已分
		}
	} // 检查行有没有出现四个一样的
	for (int i = 0; i<4; i++)
	{
		sum = 0;
		for (int j = 0; j<4; j++)
		{
			sum+=aa[j][i];
		}
		if (sum==-4) // o胜
		{
			ret = -1;
			return true; // 胜负已分
		}
		else if (sum==4) // x胜
		{
			ret = 1;
			return true; // 胜负已分
		}
	} // 检查列有没有出现四个一样的
	sum=0;
	for (int i = 0; i<4; i++)
	{
		sum+=aa[i][i];
	}
	if (sum==-4) // o胜
	{
		ret = -1;
		return true; // 胜负已分
	}
	else if (sum==4) // x胜
	{
		ret = 1;
		return true; // 胜负已分
	} // 检查主对角线
	sum=0;
	for (int i = 0; i<4; i++)
	{
		sum+=aa[i][3-i];
	}
	if (sum==-4) // o胜
	{
		ret = -1;
		return true; // 胜负已分
	}
	else if (sum==4) // x胜
	{
		ret = 1;
		return true; // 胜负已分
	} // 检查副对角线
	if (num==16)
	{
		ret = 0;
		return true;
	} // 虽然棋子下完, 但是和棋
	return false; // 棋盘还没下满, 而且胜负未定, 注意, 棋盘下满, 依旧可能和棋, 棋盘未满, 未必胜负未分
}
int Min(int, int);
int Max(int alpha, int num)  // num是已经放了多少个棋子,这是为了方便finish函数中判断
{
	int ret; // 胜(1)平(0)负(-1)
	if (finish(num, ret)) // 如果胜负已定
	{
		return ret;
	}
	int ans = -1;
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++) // 注意, 因为要取最小的让x获胜的落子位置, 所以要按照从上至下, 从左至右的顺序遍历(因为是找到了就return不玩了的)
		{
			if (a[i][j]=='.') 
			{
				a[i][j] = 'x';
				int val = Min(ans, num+1);
				a[i][j] = '.';
				ans = max(ans, val);
				if (ans==1 && num==tot) // 如果是在递归的最表层（即num==tot）, 则更新答案
				{
					ansx = i;
					ansy = j;
				}
				if (ans>=alpha)
				{
					return ans;
				}
			}
		}
	}
	return ans;
}

int Min(int beta, int num)
{
	int ret;
	if (finish(num, ret))
	{
		return ret;
	}
	int ans = 1;
	for (int i = 0; i<4; i++)
	{
		for (int j = 0; j<4; j++)
		{
			if (a[i][j]=='.') 
			{
				a[i][j] = 'o';
				int val = Max(ans, num+1);
				a[i][j] = '.';
				ans = min(ans, val);
				if (ans<=beta)
				{
					return ans;
				}
			}
		}
	}
	return ans;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(1)
	{
		if (getchar()=='$')
		{
			break;
		}
		tot = 0;
		getchar(); // 吸收多余换行符
		for (int i = 0;i<4;i++)
		{
			for (int j = 0;j<4; j++)
			{
				a[i][j] = getchar();
				tot += a[i][j]!='.';
			}
			getchar(); // 吸收多余换行符
		}
		if (tot<=4) // 强力的剪枝——如果当前只下了4个或者4个以内的棋子，则必定没有必胜策略
		{
			puts("#####");
			continue;
		}
		Max(1,tot)==1?printf("(%d,%d)\n", ansx, ansy):puts("#####");
	}
	return 0;
}

ac情况

Status Accepted
Memory 96kB
Length 3049
Lang C++
Submitted 2019-10-17 16:57:37
Shared
RemoteRunId 20967019

参考

【1】https://yfsyfs.github.io/2019/10/16/poj-1085-Triangle-War-%E6%9E%81%E5%B0%8F%E5%8C%96%E6%9E%81%E5%A4%A7-alphabeta%E5%89%AA%E6%9E%9D/