深挖围棋AI技术：alphaGo在下一盘什么棋？（上）

把它们放到KGS上比赛，darkforest能到1k-1d的水平，darkforest1能到2d的水平，darkforest2能到3d的水平【注：KGS的3d应该到不了实际的业余3段】，下面是具体的情况。

Tree Policy: 走法首先通过DCNN排序，然后按顺序选择，除非累计的概率超过0.8或者超过一定次数的top走法。Expansion使用的UCT算法。

Default Policy:参考的Pachi的tree policy，有3*3的pattern，对手打吃的点（opponent atari point），点眼的检测（detection of nakade points）等。

这个版本的软件叫darkforest3，在KGS上能到5d的水平。

DCNN预测的top3/5的走法可能不包含局部战役的一个关键点，所以它的局部作战能力还比较弱。

对于一些打劫点即使没用，DCNN还是会给高分。

当局面不好的情况下，它会越走越差（这是MCTS的弱点，因为没有好的走法，模拟出来都是输棋，一些比较顽强的抵抗的走法不能走出来）。

从上面的分析可以看出：DCNN给出的走法大局观还是不错的，这正是传统的方法很难解决的问题。局部的作战更多靠计算，MCTS会有帮助。但是我个人觉得MCTS搜索到结束，没有必要。一个局部的计算也许可以用传统的alpha-beta搜索来解决，比如征子的计算，要看6线有没有对手的棋子，另外即使有对手的棋子，也要看位置的高低，这样的计算DCNN是没法解决的，需要靠计算。

终于轮到主角上阵了，您可能不耐烦了。不过有了前面的基础，理解AlphaGo就容易多了，这里我们主要分析AlphaGo的创新点。

上图是AlphaGo所使用的两个网络以及训练过程。和之前的工作比，除了Policy Network之外，AlphaGo多了一个Value Network。

Policy Network我们通过之前的介绍以及了解到了，它的作用是Tree Policy时候的Node Selection。（rollout阶段不能使用Policy Network，因为DCNN的计算速度相对于Simulation来说太慢，所以AlphaGo又训练了一个简单的Rollout Policy，它基于一些local的pattern之类的feature训练了一个线性的softmax）。

那么Value Network又是做什么用的呢？这个Value Network就是我们之前说的很多工作都“回避”的问题——给一个局面打分，就是之前在象棋和minimax部分讨论的局面的估值函数，只不过AlphaGo是使用深度强化学习(deep reinforcment learning)学习出来，而不是像Deep Blue或者其它象棋程序那样是人工提取的feature甚至手工调整权重（当然Deep Blue是很多年前的工作了，现在也有用深度强化学习来搞国际象棋的，比如这篇论文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。

前面在讨论Tian等人的工作时我们也分析过了，光用Move Prediction的软件大局观还不错，但是局部的战术就比较差，因为局部的战术更多靠计算，人类也是这样。围棋由于估值函数比较困难，所以大都是用MCTS搜索到游戏结束。但是MCTS如果盲目搜索（使用随机的default policy去rollout/playout）肯定不好，使用各种领域知识来缩小rollout的范围就非常重要。前面我们也看到，传统的MCTS只能到2d的水平，而用DCNN的tree policy的MCTS就能到5d的水平（如果default policy如果能用DCNN指导肯定更好，可惜DCNN的速度太慢）。

这个和之前介绍的差不了太多。AlphaGo相比之前多了Rollout Policy，之前的Rollout Policy大多是使用手工编制的pattern，而AlphaGo用训练Policy Network相同的数据训练了一个简单的模型来做Rollout。

训练数据来自3千万的KGS的数据，使用了13层的CNN，预测准确率是57%，这和之前Tian等人的工作是差不多的。

之前训练的SL Policy Network优化的目标是预测走法，作者认为人类的走法会在很多promising的走法里选择，这不一定能提高AlphaGo的下棋水平。为什么？文中没有解释，我个人认为可能是一个局面（尤其是优势）的情况下有很多走法，有保守一点但是保证能赢一点点的走法，也有激进但需要算度准确的但能赢很多的走法。这取决于个人的能力（比如官子能力怎么样）和当时的情况（包括时间是否宽裕等等）。

所以AlphaGo使用强化学习通过自己跟自己对弈来调整参数学习更适合自己的Policy。

具体的做法是当前版本跟之前的某一个版本（把之前所有版本都保留和不是用最近的一个可以避免overfitting）对弈，对弈的走法是根据Policy Network来选择的，然后根据结果调整参数。这个公式用自然语言来描述就是最终得分z_t(获胜或者失败)，在t时刻局面是s_t我选择了走法a_t，P(a_t|s_t)表示局面s_t时选择走法a_t的概率，就像神经网络的反向传播算法一样，损失z_t(或者收益)是要由这个走法来负责的。我们调整参数的目的就是让这个概率变小。再通俗一点说就是，比如第一步我们的模型说必须走马(概率是1)，那么如果最终输棋，我们复盘时可能会觉得下次走马的概率应该少一点，所以我们调整参数让走马的概率小一点（就是这个梯度）。

RL Policy Network的初始参数就是SL Policy Network的参数。最后学到的RL Policy Network与SL Policy Network对弈，胜率超过80%。

另外RL Policy Network与开源的Pachi对弈（这个能到2d也就是业余两段的水平），Pachi每步做100,000次Simulation，RL Policy Network的胜率超过85%，这说明不用搜索只用Move Prediction能超过2d的水平。这和Tian等人的工作的结论是一致的，他们的darkforest2也只用Move Prediction在KGS上也能到3d的水平。

一个局面在policy p下的估值公式。用通俗的话说就是：在t时刻的局面是s，然后我们用p来下棋直到游戏结束，我们重复很多次，然后求平均的得分。当然，最理想的情况是我们能知道双方都是最优策略下的得分，可惜我们并不知道，所以只能用我们之前学到的SL Policy Network或者RL Policy Network来估计一个局面的得分，然后训练一个Value Network V(s)。前面我们也讨论过了，RL Policy Network胜率更高，而我们学出来的Value Network是用于rollout阶段作为先验概率的，所以AlphaGo使用了RL Policy Network的局面评估来训练V(s)。

V(s)的输入时一个局面，输出是一个局面的好坏得分，这是一个回归问题。AlphaGo使用了和Policy Network相同的参数，不过输出是一个值而不是361个值（用softmax归一化成概率）。

上面的公式说明：V(s)的参数theta就是简单的用梯度下降来训练

不过用一盘对局的所有(s,v(s))训练是有问题的，因为同一盘对局的相邻的局面是非常相关的，相邻的局面只差一个棋子，所有非常容易overfitting，导致模型“记住”了局面而不是学习到重要的feature。作者用这样的数据训练了一个模型，在训练数据上的MSE只有0.19，而在测试数据上是0.37，这明显overfitting了。为了解决这个问题，作者用RL Policy Network自己跟自己对局了3千万次，然后每个对局随机选择一个局面，这样得到的模型在训练数据和测试数据上的MSE是0.226和0.234，从而解决了overfitting的问题。

上面花了大力气训练了SL Policy Network,Rollout Policy和Value Network，那么怎么把它们融合到MCTS中呢？

首先每个节点表示一个局面，每一条边表示局面+一个合法的走法(s,a)。每条边保存Q(s,a)，表示MCTS当前累计的reward，N(s,a)表示这条边的访问次数，P(s,a)表示先验概率。

每次Simulation使用如下的公式从根节点开始一直选择边直到叶子节点（也就是这条边对于的局面还没有expand）。

Q(s_t,a)就是exploit term，而u(s_t,a)就是explore term，而且是于先验概率P(s,a)相关的，优先探索SL Policy Network认为好的走法。

对于叶子节点，AlphaGo不仅仅使用Rollout(使用Rollout Policy)计算得分，而且也使用Value Network打分，最终把两个分数融合起来：

n次Simulation之后更新统计量（从而影响Selection），为什么是n次，这涉及到多线程并行搜索以及运行与GPU的Policy Network与Value Network与CPU主搜索线程通信的问题

（编辑：PHP编程网 - 襄阳站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!