极大极小搜索
对于围棋的每一步可以用如图树形结构表示
假设每一种走法的回报是已知的，黑棋先走
每次轮到黑棋走时，走对黑棋最有利的；轮到白棋走时，走对黑棋最不利的
这样这可以达到最优解
蒙特卡洛树搜索
上图中每个节点代表一个局面。而 A/B 代表这个节点被访问 B 次，黑棋胜利了 A 次。例如一开始的根节点是 12/21，代表总共模拟了 21 次，黑棋胜利了 12 次。
我们将不断重复一个过程（很多万次）：
这个过程的第一步叫选择（Selection）。从根节点往下走，每次都选一个“最值得看的子节点”（具体规则稍后说），直到来到一个“存在未扩展的子节点”的节点，如图中的 3/3 节点。什么叫做“存在未扩展的子节点”，其实就是指这个局面存在未走过的后续着法。
第二步叫扩展（Expansion），我们给这个节点加上一个 0/0 子节点，对应之前所说的“未扩展的子节点”，就是还没有试过的一个着法。
第三步是模拟（Simluation）。从上面这个没有试过的着法开始，用快速走子策略（Rollout policy）走到底，得到一个胜负结果。按照普遍的观点，快速走子策略适合选择一个棋力很弱但走子很快的策略。因为如果这个策略走得慢（比如用 AlphaGo 的策略网络走棋），虽然棋力会更强，结果会更准确，但由于耗时多了，在单位时间内的模拟次数就少了，所以不一定会棋力更强，有可能会更弱。这也是为什么我们一般只模拟一次，因为如果模拟多次，虽然更准确，但更慢。
第四步是回溯（Backpropagation）。把模拟的结果加到它的所有父节点上。例如第三步模拟的结果是 0/1（代表黑棋失败），那么就把这个节点的所有父节点加上 0/1。
怎么选择走法？
和极大极小算法一样：如果轮到黑棋走，就选对于黑棋有利的；如果轮到白棋走，就选对于黑棋最不利的。但不能太贪心，不能每次都只选择“最有利的/最不利的”，因为这会意味着搜索树的广度不够，容易忽略实际更好的选择。
因此，最简单有效的选择公式是这样的：
其中 x 是节点的当前胜率估计（注意，如前所述，要考虑当前是黑棋走还是白棋走！），N 是节点的访问次数。C 是一个常数。C 越大就越偏向于广度搜索，C 越小就越偏向于深度搜索。注意对于原始的 UCT 有一个理论最优的 C 值，但由于我们的目标并不是最小化“遗憾”，因此需要根据实际情况调参。
AlphaGo
策略网络：输入棋盘特征到CNN拟合每个位置的最佳概率
价值网络：输入棋盘特征到CNN拟合当前情况的价值函数（胜算）
AlphaGo中使用rollouts策略网络取代MC随机rollouts
以减小搜索的宽度
用value网络取代MC随机rollouts
以减小搜索的深度
用监督学习（人类棋谱）的方式学习两个策略网络
Rollout policy（快速下棋策略） 和 SL policy network
RL policy network 采用强化学习的方式训练（胜利reward 1 失败 -1 平局0）
value 网络用 SL policy 和 RL policy输出的下棋策略学习价值函数
这里看一下DQN就明白了
AlphaGo 蒙特卡洛树搜索
具体计算细节可参考原论文
安利一下这个 AlphaGo 的 PPT
https://blog.csdn.net/songrotek/article/details/51065143
AlphaGo Zero
大概思想是
- 基于MCTS Self-play 并且训练策略/值网络
- 策略网络和值网络共享部分参数
- 采用深度残差网络
- 没有监督学习过程
AlphaGo 中先训练 SL / rollout Network
然后训练 RL Network
再训练 Value Network
最后用 SL / rollout / Value Network 结合MCTS走子
推荐阅读《深入浅出看懂AlphaGo Zero》
http://www.sohu.com/a/199892682_500659
总结
AlphaGo 是MCTS+DNN+RL等技术结合起来的产物
MCTS是下棋框架
DNN和RL是优化MCTS的工具
网友评论