从零开始再造打爆李世石的AlphaGo:快速构建棋盘和围棋规则
从零开始再造打爆李世石的AlphaGo:快速构建棋盘和围棋规则
从本节开始，我们废话少说，迅速进入代码编写阶段。对技术而言“做”永远是比“讲”更好的说，很多用语言讲不清楚的道理，看一下代码自然就明白了。我们要实现的围棋机器人必须做到以下几点：
1， 跟踪当前所下的每一步棋。 2， 跟踪当前的棋局进展。如果是机器人自我对弈，那么代码对棋局的跟踪与人和机器人对弈是对棋局的跟踪有所不同。 3， 根据当前棋盘局势，搜索多种可行的下法，并从中评估出最好的走法。 4， 将棋局转换为可以拥有训练网络的数据。
我们从易到难，先解决好小范围的问题，打好基础后才能处理更复杂的问题。首先我们要用代码编制好棋盘，player，落子等对象。首先我们用代码实现棋手:
import enum
class Player(enum.Enum):
black = 1
white = 2
'''
返回对方棋子颜色，如果本方是白棋，那就返回Player.black
'''
@property
def other(self):
if self == Player.white:
return Player.black
else:
return Player.white上一节我们讲过，围棋棋盘是由多条横线和竖线交织而成，棋子必须落在横线和竖线交叉点上，我们用以下代码表示交叉点：
from collections import namedtuple
class Point(namedtuple('Point', 'row col')):
def neghbors(self):
'''
返回当前点的相邻点，也就是相对于当前点的上下左右四个点
'''
return [
Point(self.row - 1, self.col),
Point(self.row + 1, self.col),
Point(self.row, self.col - 1),
Point(self.row, self.col + 1),
]这里我们使用python3的语言特性增加可读性，Point类其实包含两个整形成员，分别命名为row和col，我们可以使用point.row和point.col来访问两个成员，如果不使用nametuple，那么我们得通过point[0]，piont[1]来访问两个成员，如此可读性就大大降低。
接下来我们需要用代码来表示“落子”：
import copy
class Move():
def __init__(self, point = None, is_pass = False, is_resign = False):
assert(point is not None) ^is_pass ^is_resign
self.point = point
#是否轮到我下
self.is_play (self.pint is not None)
self.is_pass = is_pass
self.is_resign = is_resign
@classmethod
def play(cls, point):
return Move(point = point)
@classmethod
#让对方继续下
def pass_turn(cls):
return move(is_pass = True)
@classmethod
#投子认负
def resign(cls):
return move(is_resign = True)在围棋中，“落子”分三种情况，一种是把棋子放到某个点；一种是放弃下子，让对方继续下，类似于扑克中的“大”，“过”；第三是投子认负，我们上面代码中都对应了三种情况。
上面代码只是拥有表示下棋时的一下基本概念，并不包含逻辑，接下来我们要编写围棋的规则及逻辑代码。首先要做的是棋盘，棋盘在每次落子之后它要检测是否有对方棋子被吃，它要检测相邻棋子的所有自由点是否全部堵上，由于很可能有很多个棋子相邻在一起，因此这一步或许或比较耗时，我们先用代码表示相邻在一起的多个棋子：
class GoString():
def __init__(self, color, stones, liberties):
self.color = color
self.stones = set(stones)
self.liberties = set(liberties)
def remove_liberty(self, point):
self.liverties.remove(point)
def add_liberty(self, point):
self.liberties.add(point)
def merged_with(self, go_string):
#落子之后，两片相邻棋子可能会合成一片
'''
假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：
x x x x x x
x * x! * o *
x x x * o x
x x * x o x
x x * o x x
注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，
同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，
现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉
'''
assert go_string.color == self.color
combined_stones = self.stones | go_string.stones
return GoString(self.color, combined_stones,
(self.liberties | go_string.liberties) - combined_stones)
@property
def 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上面代码中的merge_with函数不好理解，必须要仔细理解上面注释才好理解代码逻辑,同时我们可以借助下图来理解merge_with函数的逻辑：
试想在第二行两个分离的黑棋中落一个黑棋，那么左边单个黑棋和右边两个黑棋就会连成一片，左边黑棋与落在中间黑棋连接成片时，它的自由点集合要减去中间落入的黑棋，同理右边两个黑棋的自由点也要减去落在中间黑棋所占据的位置，这就是为何要执行语句(self.liberties | go_string.liberties) - combined_stones。
接下来我们使用代码实现棋盘：
class Board():
def __init__(self, num_rows, num_cols):
self.num_rows = num_rows
self.num_cols = num_cols
self._grid = {}
def place_stone(self, player, point):
#确保位置在棋盘内
assert self.is_on_grid(point)
#确定给定位置没有被占据
assert self._grid.get(point) is None
ajecent_same_color = []
adjacent_oppsite_color = []
liberties = []
for neighbor in point.neighbors():
#判断落子点上下左右的邻接点情况
if not self.is_on_grid(neighbor):
continue
neighbor_string = self._grid.get(neighbor)
if neighbor_string is None:
#如果邻接点没有被占据，那么就是当前落子点的自由点
liberties.append(neighbor)
elif neighbor_string.color == player:
if neighbor_string not in adjacent_same_color:
#记录与棋子同色的连接棋子
adjacent_same_color.append(neighbor_string)
else:
if neighbor_string not in ajacent_opposite_color:
#记录落点邻接点与棋子不同色的棋子
adjacent_opposite_color.append(neighbor_string)
#将当前落子与棋盘上相邻的棋子合并成一片
new_string = GoString(player, [point], liberties)
for same_color_string in adjacent_same_color:
new_string = new_string.merged_with(same_color_string)
for new_string_point in new_string.stones:
#访问棋盘某个点时返回与该点棋子相邻的所有棋子集合
self._grid[new_string_point] = new_string
for other_color_string in adjacent_opposite_color:
#当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点
other_color_string.remove_libertiy(point)
for other_color_string in adjacent_opposite_color:
#如果落子后，相邻反色棋子的所有自由点都被堵住，对方棋子被吃掉
if other_color_string.num_liberties == 0:
self._remove_string(other_color_string)
def is_on_grid(self, point):
return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_cols
def get(self, point):
string = self._grid.get(point)
if string is None:
return None
return string.color
def get_go_string(self, point):
string = self._grid.get(point)
if string is None:
return None
return string
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:
continue
if neigbor_string is not string:
neighbor_string.add_liberty(point)
self._grid[point] = None这里我们需要解释_remove_string的逻辑。如下图：
当我们在像右边落入黑子后，中间被包围的白子被吃掉后需要从棋盘上拿开。此时我们需要把被拿走棋子所在的点设置成未被占据状态，同时查找改点上下左右四边的棋子片，为这些棋片增加一个自由点。
落子和棋盘都完成了，由于每次落子到棋盘上后，棋局的状态会发生变化，接下来我们完成棋盘状态的检测和落子法性检测，状态检测会让程序得知以下信息：各个棋子的摆放位置；轮到谁落子；落子前的棋盘状态，以及最后一次落子信息，以及落子后棋盘的状态变化：
class GameState():
def __init__(self, board, next_player, previous, move):
self.board = board
self.next_player = next_player
self.previous_state = previous
self.last_move = move
def apply_move(self, move):
if move.is_play:
next_board = copy.deecopy(self.board)
next_board.place_stone(self.next_player, move.point)
else:
next_board = self.board
return GameState(next_board, self.next_player.other, self, move)
@classmethod
def new_game(cls, board_size):
if isinstance(board_size, int):
board_size = (board_size, board_size)
board = Board(*board_size)
return GameState(board, Player.black, None, None)
def is_over(self):
if self.last_move is None:
return False
if self.last_move.is_resign:
return True
second_last_move = self.previous_state.last_move
if second_last_move is None:
return False
#如果两个棋手同时放弃落子，棋局结束
return self.last_move.is_pass and second_lass_move.is_pass接下来我们需要确定，落子时是否合法。因此我们需要确定三个条件，落子的位置没有被占据；落子时不构成自己吃自己；落子不违反ko原则。第一个原则检测很简单，我们看看第二原则：
我们看上图，三个黑棋连片只有一个自由点，那就是小方块所在位置。但不管黑棋要不要堵住那个店，三个黑子终究要被吃掉，因此黑棋不能在小方块所在位置落点，因为落点后，四个黑棋连片，但却再也没有自由点，于是黑棋下在小方块位置，反而被对方吃的更多，这就叫自己吃自己，绝大多数围棋比赛都不允许这样的下法。
当时下面请看就不同了：
当黑棋下在小方块处，它能把中间两个白棋吃掉，因此就不算是自己吃自己，因为中间两个白棋拿掉后，黑棋就会有自由点。因此程序必须在落子结束，拿掉所有被吃棋子后，才能检查该步是否形成自己吃自己：
def is_move_self_capture(self, player, move):
if not move.is_play:
return False
next_board = copy.deepcopy(self.board)
#先落子，完成吃子后再判断是否是自己吃自己
next_board.place_stone(player, move.point)
new_string = next_board.get_go_string(move.point)
return new_sting.num_liberties == 0接下来我们完成ko的检测，也就是对方落子后，你的走棋方式不能把棋盘恢复到对方落子前的局面。由于我们上面实现的GameState类保留了落子前状态，因此当有新落子后，我们把当前状态跟以前状态比对，如果发现有比对上的，那表明当前落子属于ko，代码实现如下：
@property
def situation(self):
return (self.next_player, self.board)
def does_move_violate_ko(self, player, move):
if not move.is_play:
return False
next_board = copy.deepcopy(self.board)
next_board.place_stone(player, move.point)
next_situation = (player.other, next_board)
past_state = self.previous_state
#判断Ko不仅仅看是否返回上一步的棋盘而是检测是否返回以前有过的棋盘状态
while past_state is not None:
if past_state.situtation == next_situtation:
return True
return False
def is_valid_move(self, move):
if self.is_over():
return False
if move.is_pass or move.is_resign:
return True
return (self.board.get(move.point) is None and
not self.is_move_self_capture(self.next_player, move) and
not self.does_move_violate_ko(self.next_player, move))我们上面实现的does_move_violate_ko效率比较差，因为每下一步棋，我们就得执行该函数，它会搜索过往所有棋盘状态进行比较，如果当前已经下了几百手，那么每下一步，它就得进行几百次比对，因此效率会非常慢，后面我们会有办法改进它的效率。
最后我们需要预防机器人下棋时，把自己的棋眼给堵死，例如下面棋局：
如果机器人下的是白棋，那么它不能自己把A,B点给堵上，因为堵上后，黑棋会把所有白棋吃掉，因此我们必须增加代码逻辑检测这种情况。我们队棋眼的定义是，所有的邻接点都被己方棋子占据的位置,并且该棋子四个对角线位置中至少有3个被己方棋子占据，如果棋子落子棋盘边缘，那么我们要求它所有对角线位置都被己方棋子占据，实现代码如下：
def is_point_an_eye(board, point, color):
if board.get(point) is not None:
return False
for neighbor in point.neighbors():
#检测邻接点全是己方棋子
if board.is_on_grid(neighbor):
neighbor_color = board.get(neighbor)
if neighbor_color != color:
return False
#四个对角线位置至少有三个被己方棋子占据
friendly_corners = 0
off_board_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_grid(corner):
corner_color = board.get(corner)
if corner_color == color:
friedly_corner += 1
else:
off_board_corners += 1
if off_board_corners > 0:
return off_board_corners + friendly_corners == 4
return friendly_corners >= 3有了上面代码基础后，我们就可以实现自我博弈围棋机器人，那将是下一节的内容。