使用蒙特卡洛树搜索实现围棋落子算法

上一节我们完成了最大最小搜索树，加上alhpa-beta剪枝算法实现了围棋落子走法。它存在一个问题是，树搜索的层次不高，尽管如此，围棋机器人下棋时还是要多次扫描棋盘，进行复杂的运算比较后才能做出决定，这个过程异常耗时，以至于好几分钟都无法运算完。

在计算机科学中，当面对一个计算量大的复杂问题时，一种常用的做法就是引入概率和随机性，我们不一定要寻找理论上的最优做法，我们只要以一定的概率寻找到相对优越的做法即可。本节我们引入一种带有随机性的树搜索算法叫蒙特卡洛树搜索，它属于蒙特卡洛随机化算法中的一个分支，这种算法的特性是使用概率和随机化的方法去分析极度复杂和棘手的问题。之所以把这类算法叫做蒙特卡洛，是因为在摩洛哥有一片赌场区就叫蒙特卡洛。

接下来我们看看蒙特卡洛算法步骤。该算法有两个特点，一是对棋盘进行随机模拟，二是根据模拟的结果进行统计。假设当前有一个棋局，其中轮到黑棋落子：

根据上图，我们把当前棋盘状况抽象成一个树节点，它有两个值，’/‘左边的值是获胜的数量，右边的值是模拟次数，比如说给定一个棋盘局面，我让两个围棋机器人在当前局面下随机落子直到分出胜负为止，假设当前棋盘是黑棋落子，我们让机器人下100盘后，黑棋赢了70盘，那么节点中的值就是70/100。

算法第二部是根据当前节点展开，如果当前棋盘是黑棋落子，同时黑棋有3种走法，于是上面节点就可以展开三个子节点，每个子节点对应黑棋采取相应走法后的棋盘状况：

接着我们构造两个机器人，然他们基于三个叶子节点的棋盘状况随机落子，直到分出胜负：

父节点对应的棋盘轮到黑棋落子，黑棋有三种落子方式，于是衍生出三个子节点，然后我们构造机器人在三个子节点对应的棋盘上模拟对弈直到分出胜负，假设第一个节点模拟结果是黑棋胜，第二个棋盘模拟结果是黑棋输，第三个节点模拟结果是黑棋胜，于是三个子节点的值变为1/1,0/1,1/1，然后我们把子节点的结果上传到父节点：

算法每次都会以某种规则选择一个叶子节点进行机器人模拟对弈，然后将结果上传到它的所有父节点。上图模拟后表明第一个节点胜率是100%，第二个节点是0，第三个节点是100%，如此说明黑棋以第一种和第三种方式落子所得的赢面更大，当然这是不一定的，因为当前结果只是一次随机模拟的结果，很可能中间节点对应走法更好，只不过随机模拟时，因概率性问题没得到好结果而已，对于这个问题我们后面会有办法处理。

接下来我们选择一个赢率大的节点继续展开，例如我们选择第二层第一个节点，此时轮到白棋落子，假设此时白棋有两种落子方式，于是我们根据这两种落子方式形成两种棋盘，对应两个子节点：

接着我们在展开后的节点对应棋盘上进行随机模拟对弈，也就是让两个机器人在当前棋盘上随机落子，得到结果后，将结果上传到父节点进行综合：

注意到此时第二层第一个节点的赢率下降到2/3，因此下次再选择时，根据赢率最大原则，我们选择第一层第3个节点展开：

从这一系列流程中，我们发现一个问题，那就是如果一直对赢率最大的节点展开模拟，中间节点就永远得不到展开模拟的机会，很可能中间节点对应的走法才是最好的，但是由于随机模拟的方式，它的优势因概率的原因没有展现出来，毕竟我们只对它进行一次模拟，模拟次数太少就不足以在统计上说明它的优劣。同时我们还要注意一个问题，那就是每次模拟我们都对一个叶子节点展开后，将其变成父节点，然后再对其展开的叶子节点进行模拟对弈。

我们到底是继续对当前赢率最大的节点展开模拟，还是尝试一下当前赢率比较小的节点，这种两难抉择在算法上叫做exploitation-exploration，exploitation是压榨的意思，它意味着我们将资源投入到当前看起来回报最高的地方，exploration表示探索，它意味着我们尝试一下把资源投入到目前看起来回报不高的地方，探索很可能会带来新的收获，如何以科学的方法平衡这两种选择，是算法设计上一个难点。

我们如何决定到底是exploitation还是exploration呢？我们用一个数学公式来计算：

其中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后，树的根节点选择一个赢率最大的子节点对应的落子方式作为它的下一步走法。

更多细节，我们从代码实现中理解。