Menu

Othello

发表于 12 Sep 2019 总计 7061字 阅读时间 24分
CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~

Othello

Othello (or Reversi) is a strategy board game for two players, played on an 8×8 uncheckered board.

There are sixty-four identical game pieces called disks (often spelled 」discs」), which are light on oneside and dark on the other.

Please see figure 1. Players take turns placing disks on the board with their assigned color facing up.

During a play,any disks of the opponent’s color that are in a straight line and bounded by the disk just placed andanother disk of the current player’s color are turned over to the current player’s color.

The object of the game is to have the majority of disks turned to display your color when thelast playable empty square is filled.

You can refer to http://www.tothello.com/html/guideline_of_reversed_othello.htmlformore information of guideline, meanwhile, you can download the software to have a try from http://www.tothello.com/html/download.html.

The game installertothellotrialsetup.execanalso be found in the current folder.

Tasks

  1. In order to reduce the complexity of the game, we think the board is 6×6.
  2. There are several evaluation functions that involve many aspects, you can turn to http://blog.sina.com.cn/s/blog_53ebdba00100cpy2.html for help. In order to reduce the difficulty ofthe task, I have gaven you some hints of evaluation function in the fileHeuristic Functionfor Reversi (Othello).cpp.2
  3. Please choose an appropriate evaluation function and use min-max and $\alpha - \beta$ prunning to implement the Othello game. The framework file you can refer to isOthello.cpp. Of course,I wish your program can beat the computer.

Codes

下述代码在Othello - UVa - 220的基础上修改。使用时按照如下格式：

  1. 输入的第一个参数 t，代表游戏进行的次数；
  2. 对于每一次游戏
    1. 读入一个 6*6 的棋盘，用B代表黑棋，W代表白棋，-代表空位
    2. 读入当前轮到谁下子（也就是说这个框架支持读档功能）
    3. 接下来进入游戏状态，每次可以接受如下指令
      • S：显示当前棋盘状态、双方得分，以及轮到谁落子
      • L：显示当前落子方可下的位置。不存在时，返回No legal move.
      • M<r><c>，在 r 行 c 列下一子，需保证此位置合法。当自己不能下这个位置时，会让对手下这个位置。
      • Q：打印盘面并退出
      • A：本次作业实现的对象，使用 Alpha-Beta 剪枝实现的 AI 来下这一步
      • 指令是可以批处理的，之间用空格分开。例如A S A S就是双方各让 AI 下一步，并分别打印盘面。
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

#include <stdio.h>
struct State
{
	int cnt[2];
	char a[15][15];
} now;
int work(int r, int c, char x, int fill)
{
	if (now.a[r][c] == 'B' || now.a[r][c] == 'W')
		return 0;
	char y = x == 'B' ? 'W' : 'B', ok = 0;
	for (int i = 0, dr[8] = {1, 1, 1, 0, 0, -1, -1, -1}, dc[8] = {1, 0, -1, 1, -1, 1, 0, -1}; i < 8; ++i)
		for (int rr = r + dr[i], cc = c + dc[i]; now.a[rr][cc] == y;)
			if (now.a[rr += dr[i]][cc += dc[i]] == x)
			{
				if (!fill)
					return 1;
				for (ok = 1, --now.cnt[x == 'W'], ++now.cnt[x == 'B']; rr != r || cc != c; rr -= dr[i], cc -= dc[i])
					now.a[rr][cc] = x, ++now.cnt[x == 'W'], --now.cnt[x == 'B'];
				break;
			}
	if (ok)
		now.a[r][c] = x, ++now.cnt[x == 'W'];
	return ok;
}
void showTable()
{
	for (int i = 1; now.a[i][1]; ++i)
		puts(now.a[i] + 1);
}
int dfs(char x, int dep, int alpha, int beta, int *ansr, int *ansc)
{
	*ansr = -1, *ansc = -1;
	if (!dep) //局面评估函数，这里是自己的颜色减去对手的颜色数
		return now.cnt[x == 'W'] - now.cnt[x == 'B'];
	int ok = 0;
	struct State tp = now; // 备份当前状态
	for (int i = 1; now.a[i][1]; ++i)
		for (int j = 1; now.a[i][j]; ++j)
			if (work(i, j, x, 1)) //如果这个位置可以下（填充进去）
			{
				ok = 1;
				int tmpr, tmpc, tmp = -dfs(x == 'B' ? 'W' : 'B', dep - 1, -beta, -alpha, &tmpr, &tmpc);
				now = tp; //（回溯，恢复原状态）
				if (alpha < tmp)
				{
					*ansr = i, *ansc = j, alpha = tmp;
					if (alpha >= beta) // 可以减枝
						break;
				}
			}
	if (!ok) //无可下子，丢给对手决定
	{
		int tmpr, tmpc;
		return -dfs(x == 'B' ? 'W' : 'B', dep - 1, -beta, -alpha, &tmpr, &tmpc);
	}
	return alpha;
}
int main()
{
	int t, n = 6;
	for (scanf("%d", &t); t--; printf(t ? "\n" : ""))
	{
		for (int i = 1; i <= n; ++i)
		{
			scanf("%s", now.a[i] + 1);
			for (int j = 1; now.a[i][j]; ++j)
			{
				if (now.a[i][j] == 'B')
					++now.cnt[0];
				if (now.a[i][j] == 'W')
					++now.cnt[1];
			}
		}
		char cur, cmd[9];
		for (scanf("%s", cmd), cur = cmd[0]; scanf("%s", cmd) != EOF;)
		{
			if (cmd[0] == 'L')
			{
				int cnt = 0;
				for (int i = 1; i <= n; ++i)
					for (int j = 1; j <= n; ++j)
						if (work(i, j, cur, 0))
							printf("%s(%d,%d)", cnt++ ? " " : "", i, j);
				printf(cnt ? "\n" : "No legal move.\n");
			}
			else if (cmd[0] == 'M')
			{
				int r = cmd[1] - '0', c = cmd[2] - '0';
				if (!work(r, c, cur, 0))
					cur = cur == 'B' ? 'W' : 'B';
				work(r, c, cur, 1);
				cur = cur == 'B' ? 'W' : 'B';
				printf("Black - %2d White - %2d\n", now.cnt[0], now.cnt[1]);
			}
			else if (cmd[0] == 'Q')
			{
				showTable();
				break;
			}
			else if (cmd[0] == 'S')
			{
				printf("Black - %2d White - %2d\n", now.cnt[0], now.cnt[1]);
				printf("Cur - %c\n", cur);
				showTable();
			}
			else if (cmd[0] == 'A')
			{
				int r, c;
				dfs(cur, 10, -1e9, 1e9, &r, &c);
				if (r > 0 && c > 0)
					work(r, c, cur, 1);
				cur = cur == 'B' ? 'W' : 'B';
			}
		}
	}
}
/*
1
------
------
--WB--
--BW--
------
------
W
A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S
*/

Results

以下是对局的详细记录。白棋先手，最后黑-20 白-16，黑胜。

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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266

$ ./othello.out
1
------
------
--WB--
--BW--
------
------
W
A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S A S
Black -  1 White -  4
Cur - B
------
---W--
--WW--
--BW--
------
------
Black -  3 White -  3
Cur - W
------
---W--
--WW--
--BBB-
------
------
Black -  2 White -  5
Cur - B
------
---W--
--WW--
--WBB-
--W---
------
Black -  5 White -  3
Cur - W
---B--
---B--
--WB--
--WBB-
--W---
------
Black -  4 White -  5
Cur - B
---BW-
---W--
--WB--
--WBB-
--W---
------
Black -  6 White -  4
Cur - W
---BBB
---W--
--WB--
--WBB-
--W---
------
Black -  4 White -  7
Cur - B
---BBB
---W--
--WB--
--WWWW
--W---
------
Black -  6 White -  6
Cur - W
---BBB
---W--
--WB--
--BWWW
-BW---
------
Black -  5 White -  8
Cur - B
---BBB
---W--
--WB--
-WWWWW
-BW---
------
Black -  9 White -  5
Cur - W
---BBB
---B--
--BB--
-BWWWW
BBW---
------
Black -  8 White -  7
Cur - B
---BBB
---B--
--BB--
WWWWWW
BBW---
------
Black - 11 White -  5
Cur - W
---BBB
---B--
--BB--
WWWBWW
BBBB--
------
Black -  9 White -  8
Cur - B
---BBB
---B--
--BB--
WWWBWW
WWBB--
W-----
Black - 11 White -  7
Cur - W
---BBB
---B--
--BB-B
WWWBBW
WWBB--
W-----
Black - 10 White -  9
Cur - B
---BBB
---B--
--BB-B
WWWBBW
WWWB--
W--W--
Black - 12 White -  8
Cur - W
---BBB
---B--
-BBB-B
WWBBBW
WWWB--
W--W--
Black - 11 White - 10
Cur - B
---BBB
---B--
-BBBWB
WWBWBW
WWWB--
W--W--
Black - 13 White -  9
Cur - W
---BBB
---B--
-BBBWB
WWBBBW
WWWBB-
W--W--
Black - 10 White - 13
Cur - B
---BBB
---B--
WWWWWB
WWBBBW
WWWBB-
W--W--
Black - 13 White - 11
Cur - W
---BBB
--BB--
WWBBWB
WWBBBW
WWWBB-
W--W--
Black -  9 White - 16
Cur - B
--WBBB
--WW--
WWWBWB
WWWBBW
WWWBB-
W--W--
Black - 11 White - 15
Cur - W
--WBBB
-BWW--
WWBBWB
WWWBBW
WWWBB-
W--W--
Black - 10 White - 17
Cur - B
--WBBB
WWWW--
WWBBWB
WWWBBW
WWWBB-
W--W--
Black - 12 White - 16
Cur - W
--WBBB
WWWW--
WWBBWB
WWWBBB
WWWBBB
W--W--
Black -  9 White - 20
Cur - B
--WBBB
WWWW--
WWWBWB
WWWWBB
WWWBWB
W--W-W
Black - 11 White - 19
Cur - W
--WBBB
WWWW--
WWWBWB
WWWWBB
WWWBBB
W--WBW
Black - 10 White - 21
Cur - B
--WBBB
WWWWW-
WWWWWB
WWWWBB
WWWBBB
W--WBW
Black - 14 White - 18
Cur - W
-BBBBB
WWBWW-
WWWBWB
WWWWBB
WWWBBB
W--WBW
Black - 11 White - 22
Cur - B
-BBBBB
WWBWWW
WWWBWW
WWWWBW
WWWBBW
W--WBW
Black - 15 White - 19
Cur - W
BBBBBB
WBBWWW
WWBBWW
WWWBBW
WWWBBW
W--WBW
Black - 13 White - 22
Cur - B
BBBBBB
WBBWWW
WWBBWW
WWWBWW
WWWWBW
W-WWBW
Black - 20 White - 16
Cur - W
BBBBBB
WBBWWW
WBBBWW
WBWBWW
WBBWBW
WBBBBW