Othello

12 Sep 2019 6095字 21分次人工智能
如果这篇博客帮助到你，可以请我喝一杯咖啡~
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

In order to reduce the complexity of the game, we think the board is 6×6.
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
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的基础上修改。使用时按照如下格式：

输入的第一个参数 t，代表游戏进行的次数；
对于每一次游戏
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 下一步，并分别打印盘面。

#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，黑胜。

$ ./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

Othello 晓风の个人博客

Othello

Tasks

Codes

Results