五子棋对弈——MCTS学习

初识AlphaZero

AlphaZero能够基于强化学习实现较高技巧的棋类博弈，我看过nb网友实现的基于MCTS的五子棋模型后，惊叹不已！特此记录一下其中训练的一些方法和技巧。

MCTS

MCTS是指蒙特卡洛搜索树。

蒙特卡洛搜索树没听过的话，想必你是知道蒙特卡罗模拟的。这个模拟过程就是暴力的按照概率去操作所有过程，最后得出一个统计的结果。举一个很简单的例子，比如你要计算圆周率(pi)，那么可以画一个正方形和一个内切圆。用两个面积之比可以得到圆周率的值，于是我们进行蒙特卡洛模拟，具体过程是在正方形内撒点，在每个区域内点数均匀的情况下，我们可以认为一个区域内的点数正比于面积，那么我们通过统计点数之比就可以近似得到面积之比。

而MCTS与模拟有一些区别，分为四个部分：SELECTION,EXPANSION,SIMULATION,BACK_PROPAGATION。

关于MCTS的详细内容可以参考这篇文章。

UCB

树上的上限置信区间算法是一个能很好权衡探索与利用的算法。

[UCT(v) = frac{Q(v)}{N(v)} + c sqrt{frac{2ln N(u)}{N(v)}} ]

式中(Q)是赢的次数，(N)是这个点经过次数，(u)是(v)节点的父亲节点。通过调节系数(c)我们也能改变对exploration和exploitation的倾向。

SELECTION

第一步，从当前根节点选择一个子节点，作为下一次的根。提供一个判断标准，我们算出每个叶子节点的分数，选择最高的一个吧？

但是直接选择最高的一个其实是有问题的。因为如果每次都从最高的开始选，可能存在一些效果更好的选择但是我们从来没有探索过，所以我们一般采用(UCB)来作为评估手段。

EXPANSION

在第一步中，我们始终在向下进行选择，然而一定会到达一种状态

游戏结束
有一个节点没有探索过

对于上面第二种结果，我们就要应用我们的EXPANSION了。扩展这个没有儿子节点的node的所有后续可能局面。

SIMULATION

在上一步的基础上，我们按照游戏规则模拟整局游戏，直到游戏结束，这一步是比较简单的。

BACK_PROPAGATION

得到游戏结果，包括打分和赢家，我们对这一条树上路径进行往回更新，更新祖先节点的分数和行动概率，以改良结果。

值得一提的是，上面讲到的是传统MCTS，我们还实现一个基于深度模型预测的MCTS，这个东西比上面所提到的有些进步，它的EXPANSION决策不再是随机的，而是按照Model给出的预测结果进行选择的，最后的结果也将会影响Model的参数。

Policy Value Net

网络结构

接下来说一说训练代码的模型结构。
公共的三层全卷积网络，然后分成Policy和Value两个输出端。

policy端，4个1X1的filter进行滤波，接全连接层，然后做softmax得到落子概率。
value端，filter后接全连接层，tanh后得到([-1,1])的评分。

输入描述

输入为4个(width imes height)的矩阵，前两个表示两个玩家的落子位置，第三个是对手上一次落子位置，第四个表示是否先手（原文中用了四个，但我认为前两个矩阵的顺序完全可以决定当前玩家是谁，比如规定第一个矩阵表示当前玩家的落子位置。如果知道原因的大佬希望评论区留言）。

train目标

输入是局面(state)，网络输出的落子概率和最终评分分别是(p)和(v)，MCTS模拟结果的落子概率和评分分别是(pi)和(z)，我们的目标就是网络输出和MCTS的结果尽量相同，这样模型预测的结果尽量代替上千次MCTS的模拟，MCTS又在模型基础上模拟出更多的训练数据。

定义损失函数为

[l = (z-v)^2 - pi ^T log p + c || heta||^2 ]

前两项分别是下一步概率和评分的损失，最后一项是防止过拟合。

self play

训练时，两个玩家分别是纯粹MCTS策略玩家和有模型优化的MCTS_AlphaZero策略。他们在下棋的时候，不会直接落子，而是自己和自己self-play若干局，这样就在当前局面中构造了一个蒙特卡洛搜索树。MCTS的EXPANSION策略上面讲过了，这里说一下后者是怎么做的。

为了达到exporation的效果，我们的(UCT)还不够。self-play时，我们的“树玩家”并不是严格执行着某一个落子结果，而是按照概率随机进行的，而且在原有move probability的基础上，还加了一个迪利克雷分布的噪声，

[P(s, a) = (1 - varepsilon)p_a + varepsilon eta_a ]

有助于探索更多局面。文中作者找到的一个比较好的参数为

[varepsilon = 0.25, eta_a sim Dir(0.3) ]

AlphaZero玩家还会不停地给Policy Value Net返回训练需要的((state, p, v))结果，但需要注意的是，每次计算的时候，考虑的都是当前玩家的最优策略，注意Game Theory。

Policy Value Net拿到数据之后，去梯度下降，用最新的模型去和纯MCTS的玩家博弈，看看平均胜率，如果比历史的模型胜率更高，那么就更新我们的best_model。

Tricks

每次训练得到的数据不要直接扔进去训练，我们做一个操作：由于五子棋游戏本身的各种旋转、对称局面等价性，我们对同一种数据做旋转和对称，那么这些state的结果也是一样的。

参考

https://zhuanlan.zhihu.com/p/32089487
https://www.cnblogs.com/yifdu25/p/8303462.html

一个人没有梦想，和咸鱼有什么区别！