专栏首页Coding迪斯尼从零开始再造打爆李世石的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

有了上面代码基础后,我们就可以实现自我博弈围棋机器人,那将是下一节的内容。

本文分享自微信公众号 - Coding迪斯尼(gh_c9f933e7765d)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-03-05

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 用Python从零开始设计数字图片识别神经网络--搭建基本架构

    望月从良
  • 生成型对抗性网络入门实战一波流

    前几节用代码介绍了生成型对抗性网络的实现,但后来我觉得代码的实现七拐八弯,很多不必要的烦琐会增加读者的理解负担,于是花时间把代码进行强力精简,希望由此能帮助有需...

    望月从良
  • 生成型对抗性网络介绍与实现原理

    如何无中生有是AI领域研究的重点。原有神经网络大多是对已有问题的识别和研究,例如让神经网络学会识别图片中的动物是猫还是狗,随着研究的进一步深入,目前能够做到让网...

    望月从良
  • python笔记:随机数,md5,en/decoder

    超级大猪
  • pygame-KidsCanCode系列jumpy-part13-改进跳跃

    这节研究下跳跃如何做得更自然,先看看之前的跳跃有什么问题,我们把settings.py里的初始化参数调整下:

    菩提树下的杨过
  • iOS自动打开闪光灯

    czjwarrior
  • iOS框架·Masonry源码深度解析及学习启示:设计模式与链式编程思想

    可见,系统传统的代码布局有点繁琐。为了简化上述传统布局代码,被广泛应用的第三方框架 Masonry 对AutoLayout 进行了封装,Swift版则是 Sna...

    陈满iOS
  • Leetcode 783. 二叉搜索树结点最小距离

    二叉搜索树属于有序树结构,一个可以利用的特点就是中序遍历可以得到有序数组,得到有序数组后遍历一次即可得到两节点最小差值。

    zhipingChen
  • PyQt5 多线程绘制曼德勃罗集分形图

    本篇的代码来自于PyQt4官方demo,其功能是使用多线程,计算每一像素的的RGB,生成一张曼德勃罗集分形图,支持平移与缩放。

    用户6021899
  • python的tkinter编程(九)Text多行文本框的详细解读

    一天不写程序难受

扫码关注云+社区

领取腾讯云代金券