從本節(jié)開(kāi)始，我們廢話(huà)少說(shuō)，迅速進(jìn)入代碼編寫(xiě)階段。對(duì)技術(shù)而言“做”永遠(yuǎn)是比“講”更好的說(shuō)，很多用語(yǔ)言講不清楚的道理，看一下代碼自然就明白了。我們要實(shí)現(xiàn)的圍棋機(jī)器人必須做到以下幾點(diǎn)：

1， 跟蹤當(dāng)前所下的每一步棋。
2， 跟蹤當(dāng)前的棋局進(jìn)展。如果是機(jī)器人自我對(duì)弈，那么代碼對(duì)棋局的跟蹤與人和機(jī)器人對(duì)弈是對(duì)棋局的跟蹤有所不同。
3， 根據(jù)當(dāng)前棋盤(pán)局勢(shì)，搜索多種可行的下法，并從中評(píng)估出最好的走法。
4， 將棋局轉(zhuǎn)換為可以擁有訓(xùn)練網(wǎng)絡(luò)的數(shù)據(jù)。

我們從易到難，先解決好小范圍的問(wèn)題，打好基礎(chǔ)后才能處理更復(fù)雜的問(wèn)題。首先我們要用代碼編制好棋盤(pán)，player，落子等對(duì)象。首先我們用代碼實(shí)現(xiàn)棋手:

import enumclass Player(enum.Enum):black = 1white = 2'''返回對(duì)方棋子顏色，如果本方是白棋，那就返回Player.black'''@propertydef other(self):if self == Player.white:return Player.blackelse:return Player.white

上一節(jié)我們講過(guò)，圍棋棋盤(pán)是由多條橫線(xiàn)和豎線(xiàn)交織而成，棋子必須落在橫線(xiàn)和豎線(xiàn)交叉點(diǎn)上，我們用以下代碼表示交叉點(diǎn)：

from collections import namedtupleclass Point(namedtuple('Point', 'row col')):def neghbors(self):'''返回當(dāng)前點(diǎn)的相鄰點(diǎn)，也就是相對(duì)于當(dāng)前點(diǎn)的上下左右四個(gè)點(diǎn)'''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的語(yǔ)言特性增加可讀性，Point類(lèi)其實(shí)包含兩個(gè)整形成員，分別命名為row和col，我們可以使用point.row和point.col來(lái)訪(fǎng)問(wèn)兩個(gè)成員，如果不使用nametuple，那么我們得通過(guò)point[0]，piont[1]來(lái)訪(fǎng)問(wèn)兩個(gè)成員，如此可讀性就大大降低。

接下來(lái)我們需要用代碼來(lái)表示“落子”：

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.pint is not None)self.is_pass = is_passself.is_resign = is_resign@classmethoddef play(cls, point):return Move(point = point)@classmethod#讓對(duì)方繼續(xù)下def pass_turn(cls):return move(is_pass = True)@classmethod#投子認(rèn)負(fù)def resign(cls):return move(is_resign = True)

在圍棋中，“落子”分三種情況，一種是把棋子放到某個(gè)點(diǎn)；一種是放棄下子，讓對(duì)方繼續(xù)下，類(lèi)似于撲克中的“大”，“過(guò)”；第三是投子認(rèn)負(fù)，我們上面代碼中都對(duì)應(yīng)了三種情況。

上面代碼只是擁有表示下棋時(shí)的一下基本概念，并不包含邏輯，接下來(lái)我們要編寫(xiě)圍棋的規(guī)則及邏輯代碼。首先要做的是棋盤(pán)，棋盤(pán)在每次落子之后它要檢測(cè)是否有對(duì)方棋子被吃，它要檢測(cè)相鄰棋子的所有自由點(diǎn)是否全部堵上，由于很可能有很多個(gè)棋子相鄰在一起，因此這一步或許或比較耗時(shí)，我們先用代碼表示相鄰在一起的多個(gè)棋子：

class GoString():def __init__(self, color, stones, liberties):self.color = colorself.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):#落子之后，兩片相鄰棋子可能會(huì)合成一片'''假設(shè)*代表黑棋，o代表白棋，x代表沒(méi)有落子的棋盤(pán)點(diǎn)，當(dāng)前棋盤(pán)如下：x x x x x xx * x! * o *x x x * o xx x * x o xx x * o x x注意看帶!的x，如果我們把黑子下在那個(gè)地方，那么x!左邊的黑棋和新下的黑棋會(huì)調(diào)用當(dāng)前函數(shù)進(jìn)行合并，同時(shí)x!上方的x和下面的x就會(huì)成為合并后相鄰棋子共同具有的自由點(diǎn)。同時(shí)x!原來(lái)屬于左邊黑棋的自由點(diǎn)，現(xiàn)在被一個(gè)黑棋占據(jù)了，所以下面代碼要把該點(diǎn)從原來(lái)的自由點(diǎn)集合中去掉'''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

上面代碼中的merge_with函數(shù)不好理解，必須要仔細(xì)理解上面注釋才好理解代碼邏輯,同時(shí)我們可以借助下圖來(lái)理解merge_with函數(shù)的邏輯：

試想在第二行兩個(gè)分離的黑棋中落一個(gè)黑棋，那么左邊單個(gè)黑棋和右邊兩個(gè)黑棋就會(huì)連成一片，左邊黑棋與落在中間黑棋連接成片時(shí)，它的自由點(diǎn)集合要減去中間落入的黑棋，同理右邊兩個(gè)黑棋的自由點(diǎn)也要減去落在中間黑棋所占據(jù)的位置，這就是為何要執(zhí)行語(yǔ)句(self.liberties | go_string.liberties) - combined_stones。

接下來(lái)我們使用代碼實(shí)現(xiàn)棋盤(pán)：

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):#確保位置在棋盤(pán)內(nèi)assert self.is_on_grid(point)#確定給定位置沒(méi)有被占據(jù)assert self._grid.get(point) is Noneajecent_same_color = []adjacent_oppsite_color = []liberties = []for neighbor in point.neighbors():#判斷落子點(diǎn)上下左右的鄰接點(diǎn)情況if not self.is_on_grid(neighbor):continueneighbor_string = self._grid.get(neighbor)if neighbor_string is None:#如果鄰接點(diǎn)沒(méi)有被占據(jù)，那么就是當(dāng)前落子點(diǎn)的自由點(diǎn)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:#記錄落點(diǎn)鄰接點(diǎn)與棋子不同色的棋子adjacent_opposite_color.append(neighbor_string)#將當(dāng)前落子與棋盤(pán)上相鄰的棋子合并成一片 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:#訪(fǎng)問(wèn)棋盤(pán)某個(gè)點(diǎn)時(shí)返回與該點(diǎn)棋子相鄰的所有棋子集合self._grid[new_string_point] = new_stringfor other_color_string in adjacent_opposite_color:#當(dāng)該點(diǎn)被占據(jù)前，它屬于反色棋子的自由點(diǎn)，占據(jù)后就不再屬于反色棋子自由點(diǎn)other_color_string.remove_libertiy(point)for other_color_string in adjacent_opposite_color:#如果落子后，相鄰反色棋子的所有自由點(diǎn)都被堵住，對(duì)方棋子被吃掉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):#從棋盤(pán)上刪除一整片連接棋子for point in string.stones:for neighbor in point.neighbors():neighbor_string = self._grid.get(neighbor)if neighbor_string is None:continueif neigbor_string is not string:neighbor_string.add_liberty(point)self._grid[point] = None

這里我們需要解釋_remove_string的邏輯。如下圖：

當(dāng)我們?cè)谙裼疫吢淙牒谧雍?#xff0c;中間被包圍的白子被吃掉后需要從棋盤(pán)上拿開(kāi)。此時(shí)我們需要把被拿走棋子所在的點(diǎn)設(shè)置成未被占據(jù)狀態(tài)，同時(shí)查找改點(diǎn)上下左右四邊的棋子片，為這些棋片增加一個(gè)自由點(diǎn)。

落子和棋盤(pán)都完成了，由于每次落子到棋盤(pán)上后，棋局的狀態(tài)會(huì)發(fā)生變化，接下來(lái)我們完成棋盤(pán)狀態(tài)的檢測(cè)和落子法性檢測(cè)，狀態(tài)檢測(cè)會(huì)讓程序得知以下信息：各個(gè)棋子的擺放位置；輪到誰(shuí)落子；落子前的棋盤(pán)狀態(tài)，以及最后一次落子信息，以及落子后棋盤(pán)的狀態(tài)變化：

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.deecopy(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#如果兩個(gè)棋手同時(shí)放棄落子，棋局結(jié)束return self.last_move.is_pass and second_lass_move.is_pass

接下來(lái)我們需要確定，落子時(shí)是否合法。因此我們需要確定三個(gè)條件，落子的位置沒(méi)有被占據(jù)；落子時(shí)不構(gòu)成自己吃自己；落子不違反ko原則。第一個(gè)原則檢測(cè)很簡(jiǎn)單，我們看看第二原則：

我們看上圖，三個(gè)黑棋連片只有一個(gè)自由點(diǎn)，那就是小方塊所在位置。但不管黑棋要不要堵住那個(gè)店，三個(gè)黑子終究要被吃掉，因此黑棋不能在小方塊所在位置落點(diǎn)，因?yàn)槁潼c(diǎn)后，四個(gè)黑棋連片，但卻再也沒(méi)有自由點(diǎn)，于是黑棋下在小方塊位置，反而被對(duì)方吃的更多，這就叫自己吃自己，絕大多數(shù)圍棋比賽都不允許這樣的下法。

當(dāng)時(shí)下面請(qǐng)看就不同了：

當(dāng)黑棋下在小方塊處，它能把中間兩個(gè)白棋吃掉，因此就不算是自己吃自己，因?yàn)橹虚g兩個(gè)白棋拿掉后，黑棋就會(huì)有自由點(diǎn)。因此程序必須在落子結(jié)束，拿掉所有被吃棋子后，才能檢查該步是否形成自己吃自己：

def 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_sting.num_liberties == 0

接下來(lái)我們完成ko的檢測(cè)，也就是對(duì)方落子后，你的走棋方式不能把棋盤(pán)恢復(fù)到對(duì)方落子前的局面。由于我們上面實(shí)現(xiàn)的GameState類(lèi)保留了落子前狀態(tài)，因此當(dāng)有新落子后，我們把當(dāng)前狀態(tài)跟以前狀態(tài)比對(duì)，如果發(fā)現(xiàn)有比對(duì)上的，那表明當(dāng)前落子屬于ko，代碼實(shí)現(xiàn)如下：

@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不僅僅看是否返回上一步的棋盤(pán)而是檢測(cè)是否返回以前有過(guò)的棋盤(pán)狀態(tài)while past_state is not None:if past_state.situtation == next_situtation:return Truereturn Falsedef 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 and not self.is_move_self_capture(self.next_player, move) andnot self.does_move_violate_ko(self.next_player, move))

我們上面實(shí)現(xiàn)的does_move_violate_ko效率比較差，因?yàn)槊肯乱徊狡?#xff0c;我們就得執(zhí)行該函數(shù)，它會(huì)搜索過(guò)往所有棋盤(pán)狀態(tài)進(jìn)行比較，如果當(dāng)前已經(jīng)下了幾百手，那么每下一步，它就得進(jìn)行幾百次比對(duì)，因此效率會(huì)非常慢，后面我們會(huì)有辦法改進(jìn)它的效率。

最后我們需要預(yù)防機(jī)器人下棋時(shí)，把自己的棋眼給堵死，例如下面棋局：

如果機(jī)器人下的是白棋，那么它不能自己把A,B點(diǎn)給堵上，因?yàn)槎律虾?#xff0c;黑棋會(huì)把所有白棋吃掉，因此我們必須增加代碼邏輯檢測(cè)這種情況。我們隊(duì)棋眼的定義是，所有的鄰接點(diǎn)都被己方棋子占據(jù)的位置,并且該棋子四個(gè)對(duì)角線(xiàn)位置中至少有3個(gè)被己方棋子占據(jù)，如果棋子落子棋盤(pán)邊緣，那么我們要求它所有對(duì)角線(xiàn)位置都被己方棋子占據(jù)，實(shí)現(xiàn)代碼如下：

def is_point_an_eye(board, point, color):if board.get(point) is not None:return Falsefor neighbor in point.neighbors():#檢測(cè)鄰接點(diǎn)全是己方棋子if board.is_on_grid(neighbor):neighbor_color = board.get(neighbor)if neighbor_color != color:return False#四個(gè)對(duì)角線(xiàn)位置至少有三個(gè)被己方棋子占據(jù) 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:friedly_corner += 1else:off_board_corners += 1if off_board_corners > 0:return off_board_corners + friendly_corners == 4return friendly_corners >= 3

有了上面代碼基礎(chǔ)后，我們就可以實(shí)現(xiàn)自我博弈圍棋機(jī)器人，那將是下一節(jié)的內(nèi)容。

更詳細(xì)的講解和代碼調(diào)試演示過(guò)程，請(qǐng)點(diǎn)擊鏈接

更多技術(shù)信息，包括操作系統(tǒng)，編譯器，面試算法，機(jī)器學(xué)習(xí)，人工智能，請(qǐng)關(guān)照我的公眾號(hào)：

總結(jié)

以上是生活随笔為你收集整理的从零开始再造打爆李世石的AlphaGo:快速构建棋盘和围棋规则的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。