上一节我们完成了最大最小搜索树，加上alhpa-beta剪枝算法实现了围棋落子走法。它存在一个问题是，树搜索的层次不高，尽管如此，围棋机器人下棋时还是要多次扫描棋盘，进行复杂的运算比较后才能做出决定，这个过程异常耗时，以至于好几分钟都无法运算完。
在计算机科学中，当面对一个计算量大的复杂问题时，一种常用的做法就是引入概率和随机性，我们不一定要寻找理论上的最优做法，我们只要以一定的概率寻找到相对优越的做法即可。本节我们引入一种带有随机性的树搜索算法叫蒙特卡洛树搜索，它属于蒙特卡洛随机化算法中的一个分支，这种算法的特性是使用概率和随机化的方法去分析极度复杂和棘手的问题。之所以把这类算法叫做蒙特卡洛，是因为在摩洛哥有一片赌场区就叫蒙特卡洛。
接下来我们看看蒙特卡洛算法步骤。该算法有两个特点，一是对棋盘进行随机模拟，二是根据模拟的结果进行统计。假设当前有一个棋局，其中轮到黑棋落子：
1.png
根据上图，我们把当前棋盘状况抽象成一个树节点，它有两个值，'/'左边的值是获胜的数量，右边的值是模拟次数，比如说给定一个棋盘局面，我让两个围棋机器人在当前局面下随机落子直到分出胜负为止，假设当前棋盘是黑棋落子，我们让机器人下100盘后，黑棋赢了70盘，那么节点中的值就是70/100。
算法第二部是根据当前节点展开，如果当前棋盘是黑棋落子，同时黑棋有3种走法，于是上面节点就可以展开三个子节点，每个子节点对应黑棋采取相应走法后的棋盘状况：
2.png
接着我们构造两个机器人，然他们基于三个叶子节点的棋盘状况随机落子，直到分出胜负：
3.png
父节点对应的棋盘轮到黑棋落子，黑棋有三种落子方式，于是衍生出三个子节点，然后我们构造机器人在三个子节点对应的棋盘上模拟对弈直到分出胜负，假设第一个节点模拟结果是黑棋胜，第二个棋盘模拟结果是黑棋输，第三个节点模拟结果是黑棋胜，于是三个子节点的值变为1/1,0/1,1/1，然后我们把子节点的结果上传到父节点：
4.png
算法每次都会以某种规则选择一个叶子节点进行机器人模拟对弈，然后将结果上传到它的所有父节点。上图模拟后表明第一个节点胜率是100%，第二个节点是0，第三个节点是100%，如此说明黑棋以第一种和第三种方式落子所得的赢面更大，当然这是不一定的，因为当前结果只是一次随机模拟的结果，很可能中间节点对应走法更好，只不过随机模拟时，因概率性问题没得到好结果而已，对于这个问题我们后面会有办法处理。
接下来我们选择一个赢率大的节点继续展开，例如我们选择第二层第一个节点，此时轮到白棋落子，假设此时白棋有两种落子方式，于是我们根据这两种落子方式形成两种棋盘，对应两个子节点：
5.png
接着我们在展开后的节点对应棋盘上进行随机模拟对弈，也就是让两个机器人在当前棋盘上随机落子，得到结果后，将结果上传到父节点进行综合：
6.png
注意到此时第二层第一个节点的赢率下降到2/3，因此下次再选择时，根据赢率最大原则，我们选择第一层第3个节点展开：
7.png
从这一系列流程中，我们发现一个问题，那就是如果一直对赢率最大的节点展开模拟，中间节点就永远得不到展开模拟的机会，很可能中间节点对应的走法才是最好的，但是由于随机模拟的方式，它的优势因概率的原因没有展现出来，毕竟我们只对它进行一次模拟，模拟次数太少就不足以在统计上说明它的优劣。同时我们还要注意一个问题，那就是每次模拟我们都对一个叶子节点展开后，将其变成父节点，然后再对其展开的叶子节点进行模拟对弈。
我们到底是继续对当前赢率最大的节点展开模拟，还是尝试一下当前赢率比较小的节点，这种两难抉择在算法上叫做exploitation-exploration，exploitation是压榨的意思，它意味着我们将资源投入到当前看起来回报最高的地方，exploration表示探索，它意味着我们尝试一下把资源投入到目前看起来回报不高的地方，探索很可能会带来新的收获，如何以科学的方法平衡这两种选择，是算法设计上一个难点。
我们如何决定到底是exploitation还是exploration呢？我们用一个数学公式来计算：
8.gif
其中w是当前节点的胜率，N对应的是符号’/'右边的数字，也就是从该节点开始包括它的子节点总共模拟了多少盘棋局，n是当前节点孩子节点中符号'/'右边对应的数字。temperature用于控制exploitation和exploration的比例，如果这个值大，意味着你更愿意冒险，也就是你愿意多尝试把资源投入到当前赢率小的节点，如果该值小，意味着你比较保守，你更愿意把资源投入到当前赢率更大的节点，一般而言这个值取1.5的效果比较好，这个公式叫置信区间商界公式，有它对应的数理统计原理，在这里我们不深究。
举个实际例子，就上图而言，对于顶层节点，我们如何选取三个子节点中的某一个进行模拟呢？此时N=7，如果我们选定第一个子节点，那么n=3,子节点对应的赢率是2/3，带入公式计算：
2/3 + 1.5 * (log(7) / 3) ^(1/2) = 1.87
对于第二层第二个节点而言，n=1, 带入上面公式有：
0 + 1.5 * （log(7) / 1) ^ (1/2) = 2.1
根据上面运算结果，2.1 > 1.64，因此此时应该对第二层中间节点进行展开，随着节点不断展开，每个节点的赢率发生不同变化，上面公式计算的结果也就不同，因此每次都有可能选择不同节点进行展开模拟。
这里还需要注意的问题有，每次选定一个节点后，如果当前节点对应的棋盘，其对应落子方有n种走法，那么我们要一下子为其展开n个子节点，然后对每个子节点进行模拟博弈。还有一个问题是，算法什么时候该结束呢？一般而言我们设定模拟博弈的总次数，每个子节点模拟博弈一次，总次数就减少一次，当总次数减少到0后，树的根节点选择一个赢率最大的子节点对应的落子方式作为它的下一步走法。
更多细节，我们从代码实现中理解。首先，我们先用代码定义上面“树节点”：
class MCTSNode(object):
'''
描述蒙特卡洛树节点
'''
def __init__(self, game_state, parent = None, move = None):
self.game_state = game_state
#parent指向根节点
self.parent = parent
#move表示当前节点选择的落子步骤
self.move = move
#统计胜率
self.win_counts = {
Player.black: 0,
Player.white: 0
}
#记录胜负总数
self.num_rollouts = 0
self.children = []
#记录当前可行的所有步骤
self.unvisited_moves = game_state.legal_moves()
def add_random_child(self):
#从所有可行走法中随机选取一种
index = random.randint(0, len(self.unvisited_moves) - 1)
new_move = self.unvisited_moves.pop(index)
#根据选择走法形成新的棋盘
new_game_state = self.game_state.apply_move(new_move)
#形成子节点
new_node = MCTSNode(new_game_state, self, new_move)
self.children.append(new_node)
return new_node
def record_win(self, winner):
#统计胜率
self.win_counts[winner] += 1
self.num_rollouts += 1
def can_add_child(self):
#是否来可以添加新的子节点
return len(self.unvisited_moves) > 0
def is_terminal(self):
#当前节点是否胜负已分
return self.game_state.is_over()
def winning_frac(self, player):
#获取胜率
return float(self.win_counts[player]) / float(self.num_rollouts)
上面我们定义了一个多叉树节点，它只有一个父亲，parent字段表示，它所有的子节点都存储在children数组里。由于每个节点对应一种棋盘局势，因此它含有game_state字段，add_random_child从所有可走步骤中随机选择一种，按照选择的步骤落子后形成新棋盘局势，也形成当前节点的子节点。
接下来我们实现使用蒙特卡洛树搜索的围棋机器人：
import math
import time
class MCTSAgent(Agent):
def __init__(self, num_rounds, temperature):
Agent.__init__(self)
#限制模拟对弈的总次数
self.num_rounds = num_rounds
#exploitation-exploration 的分配比例
self.temperature = temperature
def select_move(self, game_state):
'''
在给定棋盘状况下，通过使用蒙特卡洛树搜索获得下一步走法
'''
#根据当前棋盘状况设置根节点
root = MCTSNode(game_state)
for i in range(self.num_rounds):
node = root
#如果当前节点已经展开了它所有子节点，那么从子节点中选择下一个要展开的节点
while(not node.can_add_child() ) and (not node.is_terminal()):
#根据选择公式，通过计算决定选择哪个子节点
node = self.select_child(node)
#从当前节点对应的棋局中选择可走步骤形成下一个子节点
if node.can_add_child():
node = node.add_random_child()
#创建机器人，在展开节点对应棋盘基础上进行随机博弈
print('before simulate in round: ', i)
winner = self.simulate_random_game(node.game_state)
print('after simulate in round: ', i)
#统计博弈结果，并将结果上传到所有父节点进行综合统计
while node is not None:
node.record_win(winner)
node = node.parent
#在模拟完给定次数后，选择胜率最大的子节点对应的走法作为下一步棋的走法
scored_moves = [
(child.winning_frac(game_state.next_player), child.move, child.num_rollouts)
for child in root.children
]
scored_moves.sort(key = lambda x: x[0], reverse = True)
for s, m, n in scored_moves[:10]:
print('%s - %.3f (%d)' % (m, s, n))
best_move = None
best_pct = -1.0
for child in root.children:
child_pct = child.winning_frac(game_state.next_player)
if child_pct > best_pct:
best_pct = child_pct
best_move = child.move
print('Select move %s with win pct %.3f' % (best_move, best_pct))
return best_move
def select_child(self, node):
'''
根据选择公式计算每个子节点的得分，然后选择得分最大的子节点
'''
N = node.num_rollouts
log_N = math.log(N)
best_score = -1
best_child = None
for child in node.children:
w = child.winning_frac(node.game_state.next_player)
n = child.num_rollouts
score = w + self.temperature * math.sqrt(log_N / n)
if score > best_score:
best_score = score
best_child = child
return best_child
@staticmethod
def simulate_random_game(game):
#启动两个机器人，在给定棋盘下随机落子
bots = {
Player.black: FastRandomBot(),
Player.white: FastRandomBot()
}
while not game.is_over():
bot_move = bots[game.next_player].select_move(game)
game = game.apply_move(bot_move)
return game.winner()
MCTSAgent代表使用蒙特卡洛树搜索来寻求落子方法的机器人。每次轮到它落子时，它会把当前棋盘当做一个节点，计算出在给定棋盘下，它有几种走法，然后根据所有可行走法一次展开棋盘，被展开的棋盘就是执行所有可行走法中某一种走法后的棋盘局面。
然后它在展开的棋盘上，创建两个随机落子机器人进行随机落子，一直到结束为止，然后统计胜率并上传到父节点,特别是每次选定一个节点时，都要遍历该节点对应棋盘的所有可行步骤，生成所有子节点。
如果某个节点已经充分展开后，机器人根据置信区间上届公式搜索可以深入展开的节点，从该节点展开子节点后再进行模拟随机对弈，并将对弈结果统计更新到所有父节点。
代码中规定了总共的模拟次数是500，因此模拟对弈500次后，机器人从所有子节点中选择胜率最大的那个节点对应的落子方法作为下一步走法。这里我们为了加快运行速度，将以前使用的RandomBot改进为FastRandomBot，RandomBot在搜索任意落子步骤时总是对棋盘做全扫描，这是一种浪费，其实只要扫描一次，把所有可行步骤缓存起来，下次需要时从缓存的步骤中取，无需在对棋盘做全扫描：
class FastRandomBot(Agent):
def __init__(self):
Agent.__init__(self)
self.dim = None
#把所有可走步骤缓存起来
self.point_cache = []
def _update_cache(self, dim):
#如果换了棋盘，那么要重新扫描棋盘，重新获取可走步骤
self.dim = dim
rows, cols = dim
for r in range(1, rows + 1):
for c in range(1, cols + 1):
self.point_cache.append(Point(row = r, col = c))
def select_move(self, game_state):
dim = (game_state.board.num_rows, game_state.board.num_cols)
if dim != self.dim:
self._update_cache(dim)
idx = np.arange(len(self.point_cache))
np.random.shuffle(idx)
#每次选择落子步骤时不再重新扫描棋盘，而是从缓存中选取一种，从而加快速度
for i in idx:
p = self.point_cache[i]
if game_state.is_valid_move(Move.play(p)) and not is_point_an_eye(game_state.board,
p,
game_state.next_player):
return Move.play(p)
return Move.pass_turn()
最后我们将上面代码运行起来：
import numpy as np
import math
def main():
board_size = 5
game = GameState.new_game(board_size)
bot = MCTSAgent(500, temperature=1.5)
while not game.is_over():
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)
main()
上面代码中，我们使用5*5的棋盘，因为当前使用的蒙特卡洛树搜索算法，其速度依然不高，使用棋盘规格过大，搜索所消耗的时间依然过长，因此我们先用小棋盘，等后面算法改进了再使用大棋盘，上面代码运行后，结果如下：
屏幕快照 2019-03-29 上午11.34.42.png
机器人在使用蒙特卡洛树搜索进行500次模拟对弈后，打印出当前它所有落子方式的赢率，并从中选择赢率最大的一种走法。从下一节开始，我们将引入人工智能，特别是深度学习技术，让围棋机器人变得更加“智慧起来”
更多技术信息，包括操作系统，编译器，面试算法，机器学习，人工智能，请关照我的公众号：
这里写图片描述
网友评论