我们在上节完成了围棋规则和棋盘状态监测功能，本节我们在基于上节的基础上，设计一个能自己下棋的围棋机器人
主要有两点：
一个是让机器人能自己跟自己下棋
一个是让机器人跟我们下棋
在完成这一节之后，AlphaGo所需要的所有基础设施就基本完备了。
首先我们设计一个类叫Agent,它的初始化代码如下
class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()代码中的select_move用于机器人选择当前走法。该函数是整个机器人的核心所在，因为所有智能表现都集中在走法的评估和选择上，一开始我们只使用简单规则和推理来设定机器人的落子算法，因此机器人在实现初期会非常弱鸡，后面我们会在该函数中加入相应智能算法，让它变得像AlphGo一样强大。
现在我们实现方法非常简单，就是随便选择一个不违反规则的地方落子，只要机器人能避开棋眼以及防止出现ko情形。因此我们现在对select_move的逻辑是，遍历整个棋盘状态，找到一个不违背给定规则的位置就可以落子：
class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate) and notis_point_an_eye(game_state.board,candidate,game_state.next_player)):candidates.append(candidate)if not candidates:return Move.pass_turn()#在所有可能位置随便选一个return Move.play(random.choice(candidates))有了上面代码后，我们可以实现机器人的自我对弈，当然过程颇为简单和无聊，无法是两个机器人随机扫描棋盘，找到一个合理点后落子。接着我们要绘制棋盘，通常情况下，我们应该用贴图方式绘制出游戏那种美轮美奂的棋盘，但为了简便行事，我们使用简单的点和线来构造一个简易棋盘。
棋盘上可落子的空位，我们用'.'来代替，已经被棋子占据的位置，我们用'x'来表示黑子，用一个圆圈’o‘来表示白子。我们看看实现简易棋盘的代码：
到目前为止的总的代码
AlphaGo.py
import enumclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whitefrom collections import namedtupleclass Point(namedtuple('Point', 'row col')):def neighbors(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),]import copyclass Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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) #stone就是棋子self.liberties = set(liberties) #自由点def remove_liberty(self, point):self.liberties.remove(point)def add_liberty(self, point):self.liberties.add(point)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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#实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}def place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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_stringfor other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点other_color_string.remove_liberty(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_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:neighbor_string.add_liberty(point)self._grid[point] = None#棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = movedef apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_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.situation == next_situation:return Truepast_state = past_state.previous_statereturn False# O(n^2)->O(1) 3*19*19 [0, 3*19*19] bit64def is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()import randomclass RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))import timedef main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bots = {Player.black: RandomBot(),Player.white: RandomBot()}while not game.is_over():time.sleep(0.3)print(chr(27) + "[2J")# 打印棋盘print_board(game.board)bot_move = bots[game.next_player].select_move(game)print_move(game.next_player, bot_move)game = game.apply_move(bot_move)if __name__ == '__main__':main()当上面代码运行的时候，程序运行速度比较慢，要等一会才能等到其结束。主要原因就在于以前实现的does_move_violate_ko，该函数会一直追溯回过去所有棋盘状况去比较，随着落子次数越多，过去的棋盘状况数量就越多，因此该函数的执行非常耗时，要想加快速度就必须改进该函数的比对算法。
一种常用算法是对每一步落子进行编码，然后把落子编码与棋盘编码做异或运算，具体过程如下，首先我们面对一个空白棋盘，给它的编码为0：
接着有棋子落在C3时，我们给它一个二进制编码0x1001001：
于是我们做一次异或运算 0x00 XOR 0x1001001 = 0x1001001，接着白棋落子在D3，我们对此进行的编码为0x101000：
于是我们再次与前面数值做异或运算: 0x1001001 XOR 0x101000 = 0x100001，如果此时我们把白子拿走，于是棋盘返回到上一个状态，由于位置D3上的变化被我们编码为0x101000，那么我们再次用该值与先前值做异或运算：0x100001 XOR 0x101000 = 0x1001001：
由此我们比对数值就可以发现棋盘状态是否产生了回滚，不需要像原来那样进行一次二维数组的扫描比对，如果棋盘对应的二维数组维度为n，一次扫描比对需要的时间是O(n^2)，但是一次数值比对的时间是O(1)，由此在效率上能够提高两个数量级！！
上面描述的编码其实很简单，对于一个19*19的棋盘而言，我们给每一个位置一个整数值，因此总共对应3*19*19个整数，其中3对应3种状态，也就是位置空着，位置落黑棋，位置落白棋，我们把对应整数转换为二进制数进行运算即可，实现代码如下：
也就是用了哈希散列的思想
import enumimport timeimport randomfrom collections import namedtupleimport copyclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whiteclass Point(namedtuple('Point', 'row col')):def neighbors(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),]class Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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) #stone就是棋子self.liberties = set(liberties) #自由点def remove_liberty(self, point):self.liberties.remove(point)def add_liberty(self, point):self.liberties.add(point)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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#实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}def place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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_stringfor other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点other_color_string.remove_liberty(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_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:neighbor_string.add_liberty(point)self._grid[point] = None#棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = movedef apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_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.situation == next_situation:return Truepast_state = past_state.previous_statereturn False# O(n^2)->O(1) 3*19*19 [0, 3*19*19] bit64def is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))def to_python(player_state):if player_state is None:return 'None'if player_state == Player.black:return Player.blackreturn Player.white# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}#用一个64位整型对应每个棋盘MAX63 = 0x7fffffffffffffff#3*19*19 / MAX63#发明这种编码算法的人叫zobristzobrist_HASH_CODE = {}zobrist_EMPTY_BOARD = 0for row in range(1,20):for col in range(1,20):for state in (None,Player.black,Player.white):# 随机选取一个整数对应当前位置,这里默认当前取随机值时不会与前面取值发生碰撞code = random.randint(0, MAX63)zobrist_HASH_CODE[Point(row, col), state] = codeprint('HASH_CODE = {')for (pt, state), hash_code in zobrist_HASH_CODE.items():print(' (%r, %s): %r,' % (pt, to_python(state), hash_code))print('}')print(' ')print('EMPTY_BOARD = %d' % (zobrist_EMPTY_BOARD,))def main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bots = {Player.black: RandomBot(),Player.white: RandomBot()}while not game.is_over():time.sleep(0.3)print(chr(27) + "[2J")# 打印棋盘print_board(game.board)bot_move = bots[game.next_player].select_move(game)print_move(game.next_player, bot_move)game = game.apply_move(bot_move)if __name__ == '__main__':# main()pass接下来我们对代码的一些函数做相应修改
对GoString()、Board()、GameState()等都有修改
目前最新AlphaGo.py
import enumimport timeimport randomfrom collections import namedtupleimport copyclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whiteclass Point(namedtuple('Point', 'row col')):def neighbors(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),]class Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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 #黑/白# 将两个集合修改为immutable类型self.stones = frozenset(stones) #stone就是棋子self.liberties = frozenset(liberties) #自由点# 替换掉原来的remove_liberty 和 add_libertydef without_liberty(self, point):new_liberties = self.liberties - set([point])return GoString(self.color, self.stones, new_liberties)def with_liberty(self, point):new_liberties = self.liberties | set([point])return GoString(self.color, self.stones, new_liberties)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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#实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}# 添加hashself._hash = zobrist_EMPTY_BOARDdef zobrist_hash(self):return self._hashdef place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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# 增加落子的hash值记录self._hash ^= zobrist_HASH_CODE[point, None]self._hash ^= zobrist_HASH_CODE[point, player]for other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点# 修改成without_libertyreplacement = other_color_string.without_liberty(point)if replacement.num_liberties:self._replace_string(other_color_string.without_liberty(point))else:# 如果落子后，相邻反色棋子的所有自由点都被堵住，对方棋子被吃掉self._remove_string(other_color_string)# 增加一个新函数def _replace_string(self, new_string):for point in new_string.stones:self._grid[point] = new_stringdef is_on_grid(self, point):return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:# 修改self._replace_string(neighbor_string.with_liberty(point))self._grid[point] = None# 由于棋子被拿掉后，对应位置状态发生变化，因此修改编码self._hash ^= zobrist_HASH_CODE[point, string.color]self._hash ^= zobrist_HASH_CODE[point, None]#棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = move# 添加新修改if previous is None:self.previous_states = frozenset()else:self.previous_states = frozenset(previous.previous_states | {(previous.next_player,previous.board.zobrist_hash())})def apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)next_board.place_stone(player, move.point)next_situation = (player.other, next_board)# 判断Ko不仅仅看是否返回上一步的棋盘而是检测是否返回以前有过的棋盘状态# 修改,我们不用在循环检测，只要看当前数值与前面数值是否匹配即可return next_situation in self.previous_statesdef is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))def to_python(player_state):if player_state is None:return 'None'if player_state == Player.black:return Player.blackreturn Player.white# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}#用一个64位整型对应每个棋盘MAX63 = 0x7fffffffffffffff#3*19*19 / MAX63#发明这种编码算法的人叫zobristzobrist_HASH_CODE = {}zobrist_EMPTY_BOARD = 0for row in range(1,20):for col in range(1,20):for state in (None,Player.black,Player.white):# 随机选取一个整数对应当前位置,这里默认当前取随机值时不会与前面取值发生碰撞code = random.randint(0, MAX63)zobrist_HASH_CODE[Point(row, col), state] = codeprint('HASH_CODE = {')for (pt, state), hash_code in zobrist_HASH_CODE.items():print(' (%r, %s): %r,' % (pt, to_python(state), hash_code))print('}')print(' ')print('EMPTY_BOARD = %d' % (zobrist_EMPTY_BOARD,))def main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bots = {Player.black: RandomBot(),Player.white: RandomBot()}while not game.is_over():time.sleep(0.3)print(chr(27) + "[2J")# 打印棋盘print_board(game.board)bot_move = bots[game.next_player].select_move(game)print_move(game.next_player, bot_move)game = game.apply_move(bot_move)if __name__ == '__main__':main()修改完上面代码后，我们再次运行main函数，会发现它的执行比原来快了很多。
最后我们再添加人与机器人对弈的功能，要实现人机对弈，我们必须把人的落子位置告知程序，这一点不难，只要我们输入类似A3,D4这样的信息即可，由此我们增加一个辅助函数用于输入人类棋手的落子位置
目前最新AlphaGo.py
import enumimport timeimport randomfrom collections import namedtupleimport copyfrom six.moves import inputclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whiteclass Point(namedtuple('Point', 'row col')):def neighbors(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),]class Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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 #黑/白# 将两个集合修改为immutable类型self.stones = frozenset(stones) #stone就是棋子self.liberties = frozenset(liberties) #自由点# 替换掉原来的remove_liberty 和 add_libertydef without_liberty(self, point):new_liberties = self.liberties - set([point])return GoString(self.color, self.stones, new_liberties)def with_liberty(self, point):new_liberties = self.liberties | set([point])return GoString(self.color, self.stones, new_liberties)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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#实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}# 添加hashself._hash = zobrist_EMPTY_BOARDdef zobrist_hash(self):return self._hashdef place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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# 增加落子的hash值记录self._hash ^= zobrist_HASH_CODE[point, None]self._hash ^= zobrist_HASH_CODE[point, player]for other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点# 修改成without_libertyreplacement = other_color_string.without_liberty(point)if replacement.num_liberties:self._replace_string(other_color_string.without_liberty(point))else:# 如果落子后，相邻反色棋子的所有自由点都被堵住，对方棋子被吃掉self._remove_string(other_color_string)# 增加一个新函数def _replace_string(self, new_string):for point in new_string.stones:self._grid[point] = new_stringdef is_on_grid(self, point):return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:# 修改self._replace_string(neighbor_string.with_liberty(point))self._grid[point] = None# 由于棋子被拿掉后，对应位置状态发生变化，因此修改编码self._hash ^= zobrist_HASH_CODE[point, string.color]self._hash ^= zobrist_HASH_CODE[point, None]#棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = move# 添加新修改if previous is None:self.previous_states = frozenset()else:self.previous_states = frozenset(previous.previous_states | {(previous.next_player,previous.board.zobrist_hash())})def apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)next_board.place_stone(player, move.point)next_situation = (player.other, next_board)# 判断Ko不仅仅看是否返回上一步的棋盘而是检测是否返回以前有过的棋盘状态# 修改,我们不用在循环检测，只要看当前数值与前面数值是否匹配即可return next_situation in self.previous_statesdef is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))def to_python(player_state):if player_state is None:return 'None'if player_state == Player.black:return Player.blackreturn Player.white#把A3,D3这样的输入转换成具体坐标def point_from_coords(coords):#获取表示列的字母col = COLS.index(coords[0]) + 1#获取表示行的数字row = int(coords[1:])return Point(row=row, col = col)# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}#用一个64位整型对应每个棋盘MAX63 = 0x7fffffffffffffff#3*19*19 / MAX63#发明这种编码算法的人叫zobristzobrist_HASH_CODE = {}zobrist_EMPTY_BOARD = 0for row in range(1,20):for col in range(1,20):for state in (None,Player.black,Player.white):# 随机选取一个整数对应当前位置,这里默认当前取随机值时不会与前面取值发生碰撞code = random.randint(0, MAX63)zobrist_HASH_CODE[Point(row, col), state] = codeprint('HASH_CODE = {')for (pt, state), hash_code in zobrist_HASH_CODE.items():print(' (%r, %s): %r,' % (pt, to_python(state), hash_code))print('}')print(' ')print('EMPTY_BOARD = %d' % (zobrist_EMPTY_BOARD,))def main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bot = RandomBot()while not game.is_over():#time.sleep(0.3)print(chr(27) + "[2J")print_board(game.board)# 人类用黑棋if game.next_player == Player.black:human_move = input('--')point = point_from_coords(human_move.strip())move = Move.play(point)else:move = bot.select_move(game)print_move(game.next_player, move)game = game.apply_move(move)if __name__ == '__main__':main()
自己添加了棋盘的版本
但是从棋盘上拿走棋子的功能还没有实现
上面机机对弈的改良
import enumimport timeimport randomfrom collections import namedtupleimport copyimport turtledef bgpic(self,picname=None):if picname is None:return self._bgpicnameif picname not in self._bgpics:self._bgpics[picname] = self._image(picname)self._setbgpic(self._bgpic, self._bgpics[picname])self._bgpicname = picnameclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whiteclass Point(namedtuple('Point', 'row col')):def neighbors(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),]class Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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 # 黑/白# 将两个集合修改为immutable类型self.stones = frozenset(stones) # stone就是棋子self.liberties = frozenset(liberties) # 自由点# 替换掉原来的remove_liberty 和 add_libertydef without_liberty(self, point):new_liberties = self.liberties - set([point])return GoString(self.color, self.stones, new_liberties)def with_liberty(self, point):new_liberties = self.liberties | set([point])return GoString(self.color, self.stones, new_liberties)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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# 实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}# 添加hashself._hash = zobrist_EMPTY_BOARDdef zobrist_hash(self):return self._hashdef place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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# 增加落子的hash值记录self._hash ^= zobrist_HASH_CODE[point, None]self._hash ^= zobrist_HASH_CODE[point, player]for other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点# 修改成without_libertyreplacement = other_color_string.without_liberty(point)if replacement.num_liberties:self._replace_string(other_color_string.without_liberty(point))else:# 如果落子后，相邻反色棋子的所有自由点都被堵住，对方棋子被吃掉self._remove_string(other_color_string)# 增加一个新函数def _replace_string(self, new_string):for point in new_string.stones:self._grid[point] = new_stringdef is_on_grid(self, point):return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:# 修改self._replace_string(neighbor_string.with_liberty(point))self._grid[point] = None# 由于棋子被拿掉后，对应位置状态发生变化，因此修改编码self._hash ^= zobrist_HASH_CODE[point, string.color]self._hash ^= zobrist_HASH_CODE[point, None]# 棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = move# 添加新修改if previous is None:self.previous_states = frozenset()else:self.previous_states = frozenset(previous.previous_states | {(previous.next_player,previous.board.zobrist_hash())})def apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)next_board.place_stone(player, move.point)next_situation = (player.other, next_board)# 判断Ko不仅仅看是否返回上一步的棋盘而是检测是否返回以前有过的棋盘状态# 修改,我们不用在循环检测，只要看当前数值与前面数值是否匹配即可return next_situation in self.previous_statesdef is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))def to_python(player_state):if player_state is None:return 'None'if player_state == Player.black:return Player.blackreturn Player.white#把A3,D3这样的输入转换成具体坐标def point_from_coords(coords):#获取表示列的字母col = COLS.index(coords[0]) + 1#获取表示行的数字row = int(coords[1:])return Point(row=row, col = col)# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}# 用一个64位整型对应每个棋盘MAX63 = 0x7fffffffffffffff# 3*19*19 / MAX63# 发明这种编码算法的人叫zobristzobrist_HASH_CODE = {}zobrist_EMPTY_BOARD = 0for row in range(1, 20):for col in range(1, 20):for state in (None, Player.black, Player.white):# 随机选取一个整数对应当前位置,这里默认当前取随机值时不会与前面取值发生碰撞code = random.randint(0, MAX63)zobrist_HASH_CODE[Point(row, col), state] = codeprint('HASH_CODE = {')for (pt, state), hash_code in zobrist_HASH_CODE.items():print(' (%r, %s): %r,' % (pt, to_python(state), hash_code))print('}')print(' ')print('EMPTY_BOARD = %d' % (zobrist_EMPTY_BOARD,))n = 50 # 两条线间隔x = -200 # x初始值y = -200 # y初始值turtle.speed(9)turtle.screensize(400, 400)turtle.penup()turtle.pencolor('black')turtle.bgpic(r'bg.gif')for i in range(9):turtle.goto(x, y + n * i)turtle.pendown()turtle.forward(8 * n) # 下面一条横线turtle.penup()# 19条横线已画完turtle.left(90)for i in range(9):turtle.goto(x + n * i, y)turtle.pendown()turtle.forward(8 * n)turtle.penup()# 19条坚线已画完turtle.right(90)turtle.hideturtle()def hua(point, player):#print(point.row, point.col)#print(type(player))#print(player)x0 = x + (point.col - 1) * ny0 = y + (point.row - 1) * n - n * 0.25turtle.goto(x0, y0)turtle.begin_fill()if player == 'Player.white':turtle.fillcolor('white')else:turtle.fillcolor('black')turtle.circle(n * 0.25)turtle.end_fill()def main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bots = {Player.black: RandomBot(),Player.white: RandomBot()}while not game.is_over():time.sleep(0.3)print(chr(27) + "[2J")# 打印棋盘print_board(game.board)bot_move = bots[game.next_player].select_move(game)if bot_move.point is not None:point = point_from_coords('%s%d' % (COLS[bot_move.point.col - 1], bot_move.point.row))hua(point,str(game.next_player))print_move(game.next_player, bot_move)game = game.apply_move(bot_move)if __name__ == '__main__':main()人机对弈的改良
import enumimport timeimport randomfrom collections import namedtupleimport copyfrom six.moves import inputimport turtledef bgpic(self, picname=None):if picname is None:return self._bgpicnameif picname not in self._bgpics:self._bgpics[picname] = self._image(picname)self._setbgpic(self._bgpic, self._bgpics[picname])self._bgpicname = picnameclass Player(enum.Enum):black = 1white = 2'''返回对方棋子颜色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.whiteclass Point(namedtuple('Point', 'row col')):def neighbors(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),]class Move():def __init__(self, point=None, is_pass=False, is_resign=False):assert (point is not None) ^ is_pass ^ is_resignself.point = point# 是否轮到我下self.is_play = (self.point is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef 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 # 黑/白# 将两个集合修改为immutable类型self.stones = frozenset(stones) # stone就是棋子self.liberties = frozenset(liberties) # 自由点# 替换掉原来的remove_liberty 和 add_libertydef without_liberty(self, point):new_liberties = self.liberties - set([point])return GoString(self.color, self.stones, new_liberties)def with_liberty(self, point):new_liberties = self.liberties | set([point])return GoString(self.color, self.stones, new_liberties)def merged_with(self, go_string):# 落子之后，两片相邻棋子可能会合成一片'''假设*代表黑棋，o代表白棋，x代表没有落子的棋盘点，当前棋盘如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看带!的x，如果我们把黑子下在那个地方，那么x!左边的黑棋和新下的黑棋会调用当前函数进行合并，同时x!上方的x和下面的x就会成为合并后相邻棋子共同具有的自由点。同时x!原来属于左边黑棋的自由点，现在被一个黑棋占据了，所以下面代码要把该点从原来的自由点集合中去掉'''assert go_string.color == self.colorcombined_stones = self.stones | go_string.stonesreturn GoString(self.color, combined_stones,(self.liberties | go_string.liberties) - combined_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# 实现棋盘class Board():def __init__(self, num_rows, num_cols):self.num_rows = num_rowsself.num_cols = num_colsself._grid = {}# 添加hashself._hash = zobrist_EMPTY_BOARDdef zobrist_hash(self):return self._hashdef place_stone(self, player, point):# 确保位置在棋盘内assert self.is_on_grid(point)# 确定给定位置没有被占据assert self._grid.get(point) is Noneadjacent_same_color = []adjacent_opposite_color = []liberties = []for neighbor in point.neighbors():# 判断落子点上下左右的邻接点情况if not self.is_on_grid(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 adjacent_same_color:# 记录与棋子同色的连接棋子adjacent_same_color.append(neighbor_string)else:if neighbor_string not in adjacent_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# 增加落子的hash值记录self._hash ^= zobrist_HASH_CODE[point, None]self._hash ^= zobrist_HASH_CODE[point, player]for other_color_string in adjacent_opposite_color:# 当该点被占据前，它属于反色棋子的自由点，占据后就不再属于反色棋子自由点# 修改成without_libertyreplacement = other_color_string.without_liberty(point)if replacement.num_liberties:self._replace_string(other_color_string.without_liberty(point))else:# 如果落子后，相邻反色棋子的所有自由点都被堵住，对方棋子被吃掉self._remove_string(other_color_string)# 增加一个新函数def _replace_string(self, new_string):for point in new_string.stones:self._grid[point] = new_stringdef is_on_grid(self, point):return 1 <= point.row <= self.num_rows and 1 <= point.col <= self.num_colsdef get(self, point):string = self._grid.get(point)if string is None:return Nonereturn string.colordef get_go_string(self, point):string = self._grid.get(point)if string is None:return Nonereturn stringdef _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:continueif neighbor_string is not string:# 修改self._replace_string(neighbor_string.with_liberty(point))self._grid[point] = None# 由于棋子被拿掉后，对应位置状态发生变化，因此修改编码self._hash ^= zobrist_HASH_CODE[point, string.color]self._hash ^= zobrist_HASH_CODE[point, None]# 棋盘状态的检测和落子检测class GameState():def __init__(self, board, next_player, previous, move):self.board = boardself.next_player = next_playerself.previous_state = previousself.last_move = move# 添加新修改if previous is None:self.previous_states = frozenset()else:self.previous_states = frozenset(previous.previous_states | {(previous.next_player,previous.board.zobrist_hash())})def apply_move(self, move):if move.is_play:next_board = copy.deepcopy(self.board)next_board.place_stone(self.next_player, move.point)else:next_board = self.boardreturn GameState(next_board, self.next_player.other, self, move)@classmethoddef 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 Falseif self.last_move.is_resign:return Truesecond_last_move = self.previous_state.last_moveif second_last_move is None:return False# 如果两个棋手同时放弃落子，棋局结束return self.last_move.is_pass and second_last_move.is_passdef is_move_self_capture(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)# 先落子，完成吃子后再判断是否是自己吃自己next_board.place_stone(player, move.point)new_string = next_board.get_go_string(move.point)return new_string.num_liberties == 0@propertydef situation(self):return (self.next_player, self.board)def does_move_violate_ko(self, player, move):if not move.is_play:return Falsenext_board = copy.deepcopy(self.board)next_board.place_stone(player, move.point)next_situation = (player.other, next_board)# 判断Ko不仅仅看是否返回上一步的棋盘而是检测是否返回以前有过的棋盘状态# 修改,我们不用在循环检测，只要看当前数值与前面数值是否匹配即可return next_situation in self.previous_statesdef is_valid_move(self, move):if self.is_over():return Falseif move.is_pass or move.is_resign:return Truereturn (self.board.get(move.point) is None andnot self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():# 检测邻接点全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False# 四个对角线位置至少有三个被己方棋子占据friendly_corners = 0off_board_corners = 0corners = [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:friendly_corners += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3class Agent:def __init__(self):passdef select_move(self, game_state):raise NotImplementedError()class RandomBot(Agent):def select_move(self, game_state):'''遍历棋盘，只要看到一个不违反规则的位置就落子'''candidates = []for r in range(1, game_state.board.num_rows + 1):for c in range(1, game_state.board.num_cols + 1):candidate = Point(row=r, col=c)if game_state.is_valid_move(Move.play(candidate)) and not \is_point_an_eye(game_state.board,candidate,game_state.next_player):candidates.append(candidate)if not candidates:return Move.pass_turn()# 在所有可选位置随便选一个return Move.play(random.choice(candidates))def print_move(player, move):if move.is_pass:move_str = 'passes'elif move.is_resign:move_str = 'resign'else:move_str = '%s%d' % (COLS[move.point.col - 1], move.point.row)print('%s %s' % (player, move_str))def print_board(board):for row in range(board.num_rows, 0, -1):bump = ' ' if row <= 9 else ''line = []for col in range(1, board.num_cols + 1):stone = board.get(Point(row=row, col=col))line.append(STONE_TO_CHAR[stone])print('%s%d %s' % (bump, row, ''.join(line)))print(' ' + ' '.join(COLS[:board.num_cols]))def to_python(player_state):if player_state is None:return 'None'if player_state == Player.black:return Player.blackreturn Player.white# 把A3,D3这样的输入转换成具体坐标def point_from_coords(coords):# 获取表示列的字母col = COLS.index(coords[0]) + 1# 获取表示行的数字row = int(coords[1:])return Point(row=row, col=col)# 棋盘的列用字母表示COLS = 'ABCDEFGHJKLMNOPQRST'STONE_TO_CHAR = {None: ' . ',Player.black: 'x',Player.white: 'o'}# 用一个64位整型对应每个棋盘MAX63 = 0x7fffffffffffffff# 3*19*19 / MAX63# 发明这种编码算法的人叫zobristzobrist_HASH_CODE = {}zobrist_EMPTY_BOARD = 0for row in range(1, 20):for col in range(1, 20):for state in (None, Player.black, Player.white):# 随机选取一个整数对应当前位置,这里默认当前取随机值时不会与前面取值发生碰撞code = random.randint(0, MAX63)zobrist_HASH_CODE[Point(row, col), state] = codeprint('HASH_CODE = {')for (pt, state), hash_code in zobrist_HASH_CODE.items():print(' (%r, %s): %r,' % (pt, to_python(state), hash_code))print('}')print(' ')print('EMPTY_BOARD = %d' % (zobrist_EMPTY_BOARD,))n = 50 # 两条线间隔x = -200 # x初始值y = -200 # y初始值turtle.speed(9)turtle.screensize(400, 400)turtle.penup()turtle.pencolor('black')turtle.bgpic(r'bg.gif')for i in range(9):turtle.goto(x, y + n * i)turtle.pendown()turtle.forward(8 * n) # 下面一条横线turtle.penup()# 19条横线已画完turtle.left(90)for i in range(9):turtle.goto(x + n * i, y)turtle.pendown()turtle.forward(8 * n)turtle.penup()# 19条坚线已画完turtle.right(90)turtle.hideturtle()def hua(point, color):print(point.row, point.col)x0 = x + (point.col - 1) * ny0 = y + (point.row - 1) * n - n * 0.25turtle.goto(x0, y0)turtle.begin_fill()if color == 1:turtle.fillcolor('white')else:turtle.fillcolor('black')turtle.circle(n * 0.25)turtle.end_fill()def main():# 初始化9*9棋盘board_size = 9game = GameState.new_game(board_size)bot = RandomBot()while not game.is_over():# time.sleep(0.3)print(chr(27) + "[2J")print_board(game.board)# 人类用黑棋if game.next_player == Player.black:human_move = input('--')print(human_move.strip())point = point_from_coords(human_move.strip())hua(point, 0)move = Move.play(point)else:move = bot.select_move(game)point = point_from_coords('%s%d' % (COLS[move.point.col - 1], move.point.row))print(point)hua(point, 1)print_move(game.next_player, move)game = game.apply_move(move)if __name__ == '__main__':main()
参考：
/p/1912a4f5ddcd
