【python】蒙特卡洛树搜索（MCTS）简单实现

大家好，又见面了，我是你们的朋友全栈君。

过程包括以下四步：

选择 Selection：从根节点 R 开始，递归选择最优的子节点（后面会解释）直到达到叶子节点 L。
扩展 Expansion：如果 L 不是一个终止节点（也就是，不会导致博弈游戏终止）那么就创建一个或者更多的字子节点，选择其中一个 C。
模拟 Simulation：从 C 开始运行一个模拟的输出，直到博弈游戏结束。
反向传播 Backpropagation：用模拟的结果输出更新当前行动序列。

代码实现：

import sys
import math
import random
import numpy as np

AVAILABLE_CHOICES = [1, -1, 2, -2]
AVAILABLE_CHOICE_NUMBER = len(AVAILABLE_CHOICES)
MAX_ROUND_NUMBER = 10

class Node(object):
	def __init__(self):
		self.parent = None
		self.children=[]
		self.visit_times=0
		self.quality_value = 0.0
		self.state=None
	def set_state(self,state):
		self.state = state
	def get_state(self):
		return self.state
	def set_parent(self,parent):
		self.parent = parent
	def get_parent(self):
		return self.parent
	def set_children(self,children):
		self.children = children
	def get_children(self):
		return self.children
  	def get_visit_times(self):
   		return self.visit_times
	def set_visit_times(self, times):
		self.visit_times = times
	def visit_times_add_one(self):
		self.visit_times +=1
	def get_quality_value(self):
		return self.quality_value
	def set_quality_value(self, value):
		self.quality_value = value
	def quality_value_add_n(self,n):
		self.quality_value +=n
	def is_all_expand(self):
		if len(self.children)==AVAILABLE_CHOICE_NUMBER
			return True
		else:
			return False
	def add_child(self,sub_node):
		sub_node.set_parent(self)
		self.children.append(sub_node)
	def __repr__(self):
		return "Node:{},Q/N:{}/{},state:{}".format(hash(self),self.quality_value,self,visit_times,self.state)

class State(object):#某游戏的状态，例如模拟一个数相加等于1的游戏
	def __init__(self):
		self.current_value=0.0#当前数
		self.current_round_index=0#第几轮
		self.cumulative_choices = []#选择过程记录
	def is_terminal(self):#判断游戏是否结束
		if self.current_round_index = MAX_ROUND_NUMBER-1
			return True
		else:
			return False
	def compute_reward(self):#当前得分，越接近1分值越高
		return -abs(1-self.current_value)
	def set_current_value(self,value):
		self.current_value=value
	def set_current_round_index(self,round):
		self.current_round_index=round
	def set_cumulative_choices(self,choices):
		self.cumulative_choices=choices
	def get_next_state_with_random_choice(self):#得到下个状态
		random_choice=random.choice([choice for choice in AVAILABLE_CHOICES])
		next_state=State()
		next_state.set_current_value(self.current_value+random_choice)
		next_state.set_current_round_index(self.current_round_index+1)
		next_state.set_cumulative_choices(self.cumulative_choices+[random_choice])
		return next_state
def monte_carlo_tree_search(node):#蒙特卡洛树搜索总函数
	computation_budget=1000
	for i in range(computation_budget):
		expend_node = tree_policy(node)
		reward = default_policy(expand_node)
		backup(expand_node,reward)
	best_next_node = best_child(node,False)
	return best_next_node
def best_chile(node,is_exploration):#若子节点都扩展完了，求UCB值最大的子节点
	best_score=-sys.maxize
	best_sub_node = None
	for sub_node in node.get_children():
		if is_exploration:
			C=1/math.sqrt(2.0)
		else:
			C=0.0
		left=sub_node.get_quality_value()/sub_node.get_visit_times()
		right=2.0*math.log(node.get_visit_times())/sub_node.get_visit_times()
		score=left+C*math.sqrt(right)
		if score>best_score:
			best_sub_node = sub_node
	return best_sub_node
def expand(node):#得到未扩展的子节点
	tried_sub_node_states= [sub_node.get_state() for sub_node in node.get_children()]
	new_state = node.get_state().get_next_state_with_random_choice()
	while new_state in tried_sub_node_states:
		new_state=node.get_state().get_next_state_with_random_choice()
	sub_node=Node()
	sub_node.set_state(new_state)
	node.add_child(sub_node)
	return sub_node
def tree_policy(node):#选择子节点的策略
	while node.get_state().is_terminal()==False:
		if node.is_all_expand():
			node=best_child(node,True)
		else:
			sub_node = expand(node)
			return sub_node
	return node
def defaut_policy(node):
	current_state = node.get_state()
	while current_state.is_terminal==False:
		current_state = current_state.get_next_state_with_random_choice()
	final_state_reward=current_state.compute_reward()
	return final_state_reward
def backup(node,reward):
	while node != None:
		node.visit_times_add_one()
		node.quality_value_add_n(reward)
		node = node.parent

提升
很多种 MCTS 强化的技术已经出现了。这些基本上可以归纳为领域知识或者领域独立两大类。

领域知识
特定博弈游戏的领域知识可以用在树上来过滤掉不合理的行动或者在模拟过程中产生重要的对局（更接近人类对手的表现）。这意味着交战结果将会更加的现实而不是随机的模拟，所以节点只需要少量的迭代就能给出一个现实的收益值。

领域知识可以产生巨大的性能提升，但在速度和一般性上也会有一定的损失。

领域独立
领域独立强化能够应用到所有的问题领域中。这些一般用在树种（如 AMAF），还有一些用在模拟（如 在交战时倾向于胜利的行动）。领域独立强化并不和特定的领域绑定，具有一般性，这也是当前研究的重心所在。

AlphaGo的基本原理
围棋是一类完全信息的博弈游戏。然而，其庞大的搜索空间，以及局面棋势的复杂度，使得传统的剪枝搜索算法在围棋面前都望而却步。在AlphaGo出现之前，MCTS算法算是一类比较有效的算法。它通过重复性地模拟两个players的对弈结果，给出对局面s的一个估值v(s)（Monte Carlo rollouts）；并选择估值最高的子节点作为当前的策略（policy）。基于MCTS的围棋博弈程序已经达到了业余爱好者的水平。

然而，传统的MCTS算法的局限性在于，它的估值函数或是策略函数都是一些局面特征的浅层组合，往往很难对一个棋局有一个较为精准的判断。为此，AlphaGo的作者训练了两个卷积神经网络来帮助MCTS算法制定策略：用于评估局面的value network，和用于决策的policy network。（后面会看到，这两个网络的主要区别是在输出层：前者是一个标量；后者则对应着棋盘上的一个概率分布。）

首先，Huang等人利用人类之间的博弈数据训练了两个有监督学习的policy network：pσ（SL policy network）和pπ（fast rollout policy network）。后者用于在MCTS的rollouts中快速地选择策略。接下来，他们在pσ的基础上通过自我对弈训练了一个强化学习版本的policy network：pρ（RL policy network）。与用于预测人类行为的pσ不同，pρ的训练目标被设定为最大化博弈收益（即赢棋）所对应的策略。最后，在自我对弈生成的数据集上，Huang等人又训练了一个value network：vθ，用于对当前棋局的赢家做一个快速的预估。

pipeline of neural networks

因此，用一句话简单概括一下AlphaGo的基本原理：在MCTS的框架下引入两个卷积神经网络policy network和value network以改进纯随机的Monte Carlo模拟，并借助supervised learning和reinforcement learning训练这两个网络。

接下来将对AlphaGo的细节进行展开讨论。

有监督学习的Policy Networks
Huang等人首先训练了一个有监督的Policy Network用来模拟人类专家的走子。SL policy network是一个卷积神经网络；其输出层是一个Softmax分类器，用来计算在给定的棋面状态s下每一个位置的落子概率pσ(a|s)。对一个棋面状态s的描述如下：
input features for policy networks
（这里的Features对应着卷积神经网络里的Channels。）

经过人类高手三千万步围棋走法的训练后，SL policy network模拟人类落子的准确率已经达到了57%；相应地，网络的棋力也得到大大的提升。但是，如果直接用这个网络与人类高手，甚至是MCTS的博弈程序进行对弈，依然是输面居多。而且，这个网络的走子太慢了！平均每步3ms的响应时间，使得这个网络很难被直接用于MCTS的rollout中进行策略的随机。因此，Huang等人通过提取一些pattern features又训练了一个更快速（响应时间达到了2μs）但准确率有所降低（24.2%）的rollout policy network： pπ。

强化学习的Policy Networks
接下来，为了进一步提高policy network的对弈能力，Huang等人又采用一种policy gradient reinforcement learning的技术，训练了一个RL policy network：pρ。这个网络的结构与SL policy network的网络结构相同，依然是一个输出为给定状态下落子概率的卷积神经网络。网络的参数被初始化为pσ的参数；接下来，通过不断地自我对弈（与历史版本），网络的权重向着收益最大化的方向进化。此时，网络的学习目标不再是模拟人类的走法，而是更为终极的目标：赢棋。

具体来说，我们定义了一个reward function r(st)：对于非终止的时间步t<T，总有r(st)=0。每一步的收益z(t)被定义为±r(sT)：即对当前玩家而言对弈的最终结果（+1代表赢棋；−1代表输棋）。网络的权重通过随机梯度上升法进行调整：
Δρ∝∂logpρ(at|st)∂ρzt

通过这种方式训练出来的RL policy network，在与SL policy network对弈时已有80%的赢面。即便是与依赖Monte Carlo搜索的围棋博弈程序相比，不依赖任何搜索的RL policy network，也已经达到了85%的赢面。

强化学习的Value Networks
最后，Huang等人又开始寻求一个能快速预估棋面价值（棋势）的Value Network。一个棋面的价值函数vp(s)，被定义为在给定的一组对弈策略p的情况下，从状态s出发，最终的期望收益（也即赢棋的概率）：
vp(s)=E[zt|st=s,at…T∈p]

显然，理想情况下，我们想知道的是在双方均采用最优策略的条件下得到的最优期望收益v∗(s)。然而，我们并不知道什么才是最优的策略。因此，在实际应用中，Huang等人采用了目前最强的策略函数pρ（RL policy network ）来计算一个棋面的价值vpρ(s)，并训练了一个value network vθ(s)来拟合这个价值函数：vθ(s)≈vpρ(s)≈v∗(s)。

Value Network的网络结构与前面的Policy Network类似，也是一个卷积神经网络，只是输出层变成了一个单神经元的标量。我们可以通过构造一组(s,z)的训练数据，并用随机梯度下降法最小化网络的输出vθ(s)与目标收益z的均方差，来调整网络的参数：
Δθ∝∂vθ(s)∂θ(z−vθ(s))

在构造训练数据时有一些技巧。如果我们从人类对弈的完整棋局中抽取足够数量的训练数据，很容易出现过拟合的问题。这是因为，在同一轮棋局中的两个棋面的相关性很强（往往只相差几个棋子）；此时，网络很容易记住这些棋面的最终结果，而对新棋面的泛化能力很弱。为了解决这个问题，Huang等人再次祭出强化学习的大杀器：通过RL policy network的自我对弈，产生了三千万个从不同棋局中提取出来的棋面－收益组合的训练数据。基于这份数据训练出来的Value Network，在对人类对弈结果的预测中，已经远远超过了使用fast rollout policy network的MCTS的准确率；即便是与使用RL policy network的MCTS相比，也已是不遑多让（而Value Network的计算效率更高）。

accuracy of value network

整合
到这里，我们手头上已经有一个牛逼但是巨慢的SL policy network；有一个不那么牛逼但是很快的fast policy network；有一个一心只想着如何赢棋的RL policy network；还有一个能一眼洞穿棋局的value network。那么，将这些networks放在一起互相补足，会得到什么呢？

答案就是AlphaGo。而把这些networks整合在一起的框架，就是MCTS算法。

与经典的MCTS算法类似，APV-MCTS（asynchronous policy and value MCTS）的每一轮模拟也包含四个步骤：

Selection：APV-MCTS搜索树中的每条连边(s,a)都包含三个状态：决策收益Q(s,a)，访问次数N(s,a)，和一个先验概率P(s,a)。这三个状态共同决定了对一个节点下行为的选择：
at=argmaxa(Q(st,a)+u(st,a))

其中，u(s,a)∝P(s,a)1+N(s,a)
Expansion：步骤1中的selection终止于叶子节点。此时，要对叶子节点进行扩展。这里采用SL policy network pσ计算出叶子节点上每个行为的概率，并作为先验概率P(sL,a)存储下来。
Evaluation。使用value network vθ(s)和fast rollout policy network pπ模拟得到的博弈结果对当前访问到的叶子节点进行估值：
V(sL)=(1−λ)vθ(sL)+λzL
Backup。更新这一轮模拟中所有访问到的路径的状态：
N(s,a)=∑i=1n1(s,a,i)

Q(s,a)=1N(s,a)∑i=1n1(s,a,i)V(siL)

其中，n是模拟的总次数；1(s,a,i)标示第i轮模拟中是否经过边(s,a)；siL是第i轮模拟中访问到的叶子节点。
下图展示了一轮模拟的动态过程。

MCTS with policy networks and value networks

模拟结束后，算法会选择访问次数N(s,a)最大的策略a作为当前的走子策略。

值得注意的是，在整个模拟的过程中，我们见到了SL policy network（用于Expansion中先验概率的计算）；见到了fast rollout policy network（用于Evaluation中的快速走子）；见到了value network（用于Evaluation中对棋势的预估）。等等，RL policy network去哪了？为什么不用RL policy network替代SL policy network？明明RL policy network有着更强的棋力啊（85%的赢面）？

这是因为，与RL policy network相比，由人类专家走法训练出来的SL policy network在策略上的多样性更强；因此更适用于MCTS中的搜索。但是，用RL policy network的自我对弈结果训练出来的value network的泛化能力就要比SL policy network训练出来的value network要强得多了。