c语言五子棋蒙特卡洛,五子棋对弈——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

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

但是直接选择最高的一个其实是有问题的。因为如果每次都从最高的开始