翻译Deep Learning and the Game of Go（4）第3章：实现你第一个围棋AI（上）

本章涵盖

• 使用Python实现一个围棋棋盘
• 落子并模拟一个游戏
• 依据围棋规则来编程确保合法落子
• 构建一个可以自我对弈的简单机器人
• 可以与您的AI下完整的一盘棋

• 跟踪你与人类对手比赛的进度。
• 跟踪两个AI之间游戏的进度。这似乎与前面的观点完全相同，但事实证明，存在一些细微的差别。最值得注意的是，单纯的AI很难识别棋局是否结束。让两个AI互相对弈是一个重要的技术，将会在接下来一章来使用，所以值得在这里说明
• 比较同一棋盘盘面的多个搜索序列。
• 导入对局记录，并由其生成训练数据

我们从几个简单的概念开始，比如棋手或落子是什么。这些概念将为在后面的章节中处理所有上述任务奠定了基础。

首先，创建一个新文件夹dlgo，并将一个空的_init_py文件放入其中，作为一个Python模块初始文件。另外，创建两个名为gotypes.py和goboard_slow.py的附加文件我放所有的棋盘和游戏的功能。此时您的文件夹结构应该如下所示：

dlgo__init__.pygotypes.py goboard_slow.py

在围棋中黑棋和白棋会轮流开始下棋，这里我们就使用枚举类型来代表不同类型的棋子。一个棋手要么是黑棋要么是白棋。当一个棋手下了之后，你会让Player对象中的另一个实例去下棋，把这个Player对象放到gotypes.py文件里

import copy
from dlgo.gotypes import Player# 定义操作类（包括落子、投降，不允许用户pass）
class Move:def __init__(self, point=None,if_pass=False,if_resign=False):# 断言，两种条件（落子为空,玩家投降了)都不会执行下面语句，直接跳出assert (point is not None) ^ if_pass ^ if_resignself.point = pointself.is_play = (point is not None)  # 是否落子self.if_resign = if_resignself.if_pass = if_pass# 落子@classmethoddef play(cls, new_point):return Move(point=new_point)#pass@classmethoddef pass_turn(cls):return Move(if_pass=True)# 投降@classmethoddef resign(cls):return Move(if_resign=True)

在下面的内容中，我们通常不会直接调用去Move构造函数，而是去调用Move.play、Move.resign来构造一个Move的实例。注意到目前为止，Player、Point和Move类都是普通数据类型。

虽然它们是代表棋盘的基础，但它们不包含任何游戏逻辑，这是做使有目的的，你将从像这样把游戏和落子分开的方式中获益。

下一步，你们可以使用前面三个类去更新游戏状态：

3.1.1 实现围棋棋盘

1. 你要去看邻接棋子是否还有留下的气
2. 你要去检查任何一个邻接棋子的邻接棋子还有留下的气
3.  再去检测邻接棋子的邻接棋子的邻接棋子等等

这一程序可能需要数百个步骤才能完成。想象一下，一条长链在带有200个棋子的对手地盘上蜿蜒而行。为了加快速度，你可以以一个整体跟踪所有直接连接的棋子。

3.1.2.追踪围棋中相连的棋子组合：棋子串

您在前面的部分中看到，单独地观察棋子可以增加计算的复杂度。换个方法，你可以检查一组相同颜色的相连棋子和它们的气。在实现游戏逻辑时，这样做要有效得多。

                                                          图3.1 三个白棋6口气，一个单独棋子3口气 

1. 棋子串是一组相同颜色的棋子集合
2. merge_with返回一个拥有两个棋子串所有棋子的棋子串

# 棋子串(颜色,一串棋子和气)
class GoString:def __init__(self, color, stones, liberties):self.color = colorself.stones = set(stones)  # 棋子集合self.liberties = set(liberties)  # 空点集合# 拿掉一口气，实际上就是去掉空点集合中的一个空点def remove_liberty(self, point):self.liberties.remove(point)# 增加一口气，实际上就是增加空点集合中的一个空点def add_liberty(self, point):self.liberties.add(point)# 连接棋子串(要求棋子串颜色要相同）# 合并后的气应该是两个棋子串合并前的气之和减去两个棋子串的棋子个数之和def merge_with(self, other_string):assert self.color == other_string.colorunited_stones = self.stones | other_string.stonesreturn GoString(self.color, united_stones, (self.liberties | other_string.liberties) - united_stones)# 棋子串气的个数@propertydef num_liberties(self):return len(self.liberties)# 判断两个棋子串是否相等def __eq__(self, other):return isinstance(other, GoString) and self.color == other.color\and self.stones == other.stones and self.liberties == other.liberties

•   请注意，GoString类直接可以获取自己的气，您可以通过调用num_liberties来得到任意时刻的棋子串的气，这比前面的计算单个棋子气要好用的多。
• 此外，您还可以通过使用remove_liberty和add_liberty从给这个棋子串中添加和删除气。如果对方的棋子在附近下，你的棋子串的气通常会减少，当与字符串相邻的对方棋子被吃了后，你的字符串气就会增加。
• 还有，请注意与GoString中的merge_with方法，这是在一个棋手落子后可以使得两个同色棋子串相连的时候才调用的。

3.1.3 在围棋棋盘上落子和吃子

在讨论了棋子和棋子串之后，下一步自然就是讨论如何在棋盘上放置棋子。使用GoString类，放置棋子的算法看起来像这样：

1.合并同一颜色的任意相邻棋子串

2.减少任何颜色相反的相邻棋子串的气。

3.如果任何相反的颜色棋子串没气了，请把它从棋盘上拿掉。

此外，如果新形成的棋子串没有气，则不能下进去。这自然会形成围棋Board类的以下实现，您也将其放到在goboard_slow.py文件里。你应该允许棋盘有任意数量的行或列，并用num_rows和num_cols表示棋盘的行数和列数。为了保持对棋盘状态的追踪，请使用私有变量_grid，来作为储存棋子串的字典。首先，让我们通过指定大小来初始化一个围棋棋盘。

# 棋盘
class Board:def __init__(self, num_rows,num_cols):self.num_rows = num_rowsself.num_cols = num_colsself.grid = {}  # 存储所有棋盘上的棋子串

一个棋盘用特定大小的行和列以及一个空的棋子串集合来初始化

接下来，我们讨论了在棋盘上放置棋子的方法。在place_stone方法中，你首先必须检查所有相邻的棋子串在给定点被占了后的气。

# 棋盘
class Board:def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself.grid = {}  # 存储所有棋盘上的棋子串# 判断交叉点是否在棋盘内def is_on_board(self, point):return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_cols# 删除棋子串def remove_string(self, string):for point in string.stones:for neighbor in point.neighbors():neighbor_string = self.grid.get(neighbor)if neighbor_string is None:continueelse:neighbor_string.add_liberty(point)self.grid[point] = None  # 将该点映射的棋子串置为空def get(self, point):string = self.grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):  # <2>string = self.grid.get(point)if string is None:return Nonereturn string# 落子(当前落子方，落子点）def place_stone(self, player, point):assert self.is_on_board(point)  # 该点是否超出棋盘外assert self.grid.get(point) is None  # 该点是否已经有子same_color = []  # 相同颜色棋盘块集合opposite_color = []  # 不同颜色棋盘块集合liberties = []  # 该点邻接空点集合for neighbor in point.neighbors():# 该点邻接的这个点不在棋盘上不用管if not self.is_on_board(neighbor):continueneighbor_string = self.grid.get(neighbor) # 获取这个邻接点所在的棋盘块# 如果为空，就加入集合if neighbor_string is None:liberties.append(neighbor)elif neighbor_string.color == player:if neighbor_string not in same_color:same_color.append(neighbor_string)else:if neighbor_string not in opposite_color:opposite_color.append(neighbor_string)# 先将新落下的棋子当成一个新的棋子串，再判断有无棋子块可以与它相连new_string = GoString(player, [point],liberties)

1.首先，你要考察这一点的直接相邻点。

注：如上方代码的前两行使用assert方法来检查给定棋盘的点是否在棋盘内，并且该点是否已经被下过

# 判断交叉点是否在棋盘内def is_on_board(self,point):return 1 <= point.row <= self.num_rows and 1<= point.cols <= self.num_cols

 继续去定义上面的place_stone方法，要注意三点：

• 要合并所有与该落子点相连的同色棋子串
• 将与该落子点相连的异色棋子串空点集合去掉当前点，从而减少它的气
• 如果去掉后棋子串的气变成0就应该从棋盘上拿掉

 # 遍历相同颜色邻接棋盘块集合，执行合并操作for same_color_string in same_color:new_string = same_color_string.merge_with(new_string)# 对新形成的棋子串将每个棋子都实现棋子与该串的映射，即字典for same_color_point in new_string.stones:self.grid[same_color_point] = new_string# 对于不同颜色的邻接棋盘块集合，由于该点被占据而气变少了，因此需要减掉,如果气变0了就要从棋盘上拿掉for opposite_color_string in opposite_color:opposite_color_string.remove_liberty(point)if opposite_color_string.num_liberties == 0:self.remove_string(opposite_color_string)

  现在，剩下的唯一个问题就是如何定义从围棋棋盘中移除棋子串的方法。这是相当简单的，但您必须要注意，其他棋子串在该棋子串被移除后可能会获得新的气时，例如，在图3.2中，您可以看到黑色吃了一个白棋，从而为每一串相邻的黑色棋子串获得了一个额外的气

方法实现如下：

# 删除棋子串，并将该棋子串上每个点相邻的棋子串的气增加
def remove_string(self, string):for point in string.stones:for neighbor in point.neighbors():neighbor_string = self.grid.get(neighbor)if neighbor_string is None:continueelse:neighbor_string.add_liberty(point)self.grid[point] = None  # 将该点映射的棋子串置为空

3.2 捕捉游戏状态和检查非法落子

现在您已经实现了在棋盘上落子和吃子的规则，让我们继续实现GameState类中来捕获游戏的当前状态。粗略地说，GameState类应该能够获取棋盘盘面，知晓落子方，获悉上一个游戏状态，以及知道上一个操作。接下来的只是定义的开始。你会在本节中增加更多的功能。同样地，你要把这个类放进goboard_slow.py文件中。

# 游戏状态类
class GameState:def __init__(self, board, current_player, previous_state, move):self.board = boardself.current_player = next_playerself.previous_state = previous_stateself.move = movedef apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)  # 将落子前的盘面进行深度拷贝next_board.place_stone(self.current_player, move.point)# 新开一局游戏@classmethoddef new_game(cls, board_size):if isinstance(board_size, int):board = Board(board_size, board_size)return GameState(board, Player.black, None, None)

此时，您可以通过在GameState类中添加以下代码来决定游戏何时结束

  # 判断棋局有无结束def is_over(self):if self.move is None:return Falseelif self.move.if_resign:return True

现在您已经实现了如何将操作应用到当前的游戏状态，可以使用apply_move方法，不过你还应该编写代码来识别哪些操作是合法的。人类和AI都可能会意外地尝试一些非法的操作，因此你需要把它检测出来。你依据的是这样三个规则：

• 你想落的交叉点必须是空的
• 落下这个子后不会造成自填
• 打劫时未找劫财不可直接提回。

第一点实现比较简单，其他两个比较难，需要单独处理

3.2.1自填

当你的棋子串只有一口气了，你还下到那口气上，我们就叫自填，像下面这张图

白色可以随时下在标记点上吃掉黑棋，黑棋没有办法去阻止。但是如果黑棋在标记点上会怎么样？所有的黑棋都没有气了然后被吃掉。大多数规则都禁止这样下，您将在代码中实现禁止自填规则，这样就会减少您的AI需要考虑的落子点

如果您稍微改变上图的周围棋子，会出现完全不同的情况，如下图所示。

请注意，通常情况下，在检查新下的棋子是否还有气之前，您必须首先移除对手的无气的棋子，因此上图下在标记点是合法的，不是自填，因为黑棋可以通过下在这里吃掉两个白棋从而获得气。

还有，Board类没有禁止自填，因此在GameState类中，你需要在apply_move方法中去判别有无自填，判别自填方法如下：

# 判别有无自填def is_self_capture(self, player, move):if not move.is_play:return Falsenew_board = copy.deepcopy(self.board)  # 深度拷贝为了思考过程不会影响原有棋局new_board.place_stone(player,move.point)new_string = self.board.grid.get(move.point)return new_string.num_liberties == 0

3.2.2劫

在检查了自填之后，您现在可以继续实现劫的规则了。因为每个GameState实例都保留一个指向前一个状态的指针，所以您可以通过检查新局面在之前的局面里有无出现过就可以判断是否违反劫的规则了。你可以像下面那样实现：

#判断未找劫财直接提劫(就是判断局面是否出现过）
def is_ko_illegal(self, player, move):if not move.is_play:return Falsenew_board = copy.deepcopy(self.board)new_board.place_stone(player, move.point)new_situation = (player.other, new_board)past_state =self.previous_statewhile past_state is not None:if past_state.situation == new_situation:return Truepast_state = past_state.previous_statereturn False

3.3结束一个游戏

计算机围棋的一个关键概念是自我对弈。在自我对弈中，计算机通常会从一个弱的AI开始，然后让它自己对抗自己，并利用游戏结果构建出一个更强大的机器人。第4章，你会用自我对弈来评估棋盘盘面。在第9章到第12章中，您将使用自我对弈来评估单个落子以及选择落子的算法。

为了有效利用这一技术，你需要确保你的AI自我对弈可以结束。人类会在下一步都无法取得优势的情况下让游戏结束。而即使对人类来说，这也是一个棘手的概念。初学者往往通过在对手的地盘上下无用的棋，或者眼睁睁地看着他们的对手进入到自己坚实的地盘而导致棋局结束。而对于电脑来说，这种结束就更加难以捉摸了。如果我们的AI继续下，只要合乎规则的落子点仍然存在，它就会去填补自己的气，最终失去所有的棋子

你可以人为规定一些准则来帮助机器人完成游戏。例如：

1. 不要总是在一个完全被相同颜色的棋子包围的区域下棋。
2. 不要落在只有一口气的地方。
3. 只有在对方棋子串有一口气才能去吃。

不幸的是，所有这些规则都太严格了。如果我们的机器人遵循这些规则，强大的对手就会利用机会杀死原先应该是活棋的群体，拯救了那些本该是死棋的群体，或者简单地获得一个更好的局面。一般来说，我们人工制作的规则应该尽可能少地限制机器人的选择，这样更复杂的算法就可以自由地学习先进的战术。

要解决这个问题，你可以看看游戏的历史。在古代，棋盘上棋子多的一方就是胜者，棋手会在游戏结束时填满他们所能得到的每一个交叉点，只剩下他们棋子块的眼。不过这可能使一盘棋的时间太长，于是棋手们想出了一种方法。如果黑棋明显地控制了棋盘的一块地盘（在那个区域里的所有死棋最终都会被吃掉），那么就不需要用黑棋来填满那个地盘，双方都会同意把那块地盘算成黑棋。这就是地盘概念的起源，几个世纪以来，规则就是这样演变的，使得我们对地盘进行了明确的统计

上面的这种方法避免了什么是地盘和什么不是的问题，但您仍然必须防止您的AI自杀；如下图（AI是白棋）

AI无论填在A还是B，虽然是落子合乎规则，但是一旦下了后，白棋就只有一只眼，就从原来的活棋变成了死棋，平白无故的死了一块棋，这显然是不可接受的，因此我们需要写一个方法阻止这种情况发生。在dlgo下创建新的文件夹，名字叫agent，然后文件夹里放入空的__init__.py，并把下面的is_point_an_eye函数放入进去

需要明确的是，我们防止是填真眼，真眼除需要上下左右都是同色棋外，还需要一些条件：

1. 在中央只要眼的东北、东南、西南、西北有三个同色棋即可
2. 角部与边上的点的斜对角同色棋保持和棋盘外的角数目为4且棋盘内的斜对角有同色棋即可

from dlgo.gotypes import Point#判断一个点是否为真眼
def is_point_true_eye(board, point, color):if board.grid.get(point) is not None:  # 判断该点是否有子return False#判断点是否为眼for neighbor in point.neighbors():if board.is_on_board(neighbor):neighbor_string =  board.grid.get(neighbor)if neighbor_string is None:return Falseelif neighbor_string.color != color:return False#判断是否为真眼same_corners = 0  # 斜对角同色outside_corners = 0  # 棋盘外的斜对角corners = [Point(point.row - 1, point.col - 1),Point(point.row - 1, point.col + 1),Point(point.row + 1, point.col - 1),Point(point.row + 1, point.col + 1)]  # 斜对角集合for corner in corners:if board.is_on_board(corner):corner_string = board.grid.get(corner)if corner_string is not None and corner_string.color == color:same_corners += 1else:outside_corners += 1# 点在边角if outside_corners > 0:return same_corners + outside_corners == 4else:return same_corners >= 3

   在本章中，您还无法确定游戏的结果，但是在游戏结束时点目绝对是一个重要的东西。在整本书中，您将让您的AI遵循AGA规则的计数，也称为中文计数法。