蒙特卡洛树是什么算法？

更正蒙特卡洛树不是一种算法，蒙特卡洛才是一种算法。

蒙特卡洛算法是20世纪十大最伟大的算法，阿法狗就采用了蒙特卡洛算法。

先来个动态图感受下蒙特卡洛树

在五子棋中，因为每一步的选择点并不多，以当前电脑的计算力可以用穷举找到最佳下法。

显然，以当前电脑的计算力，无法对围棋进行暴力穷举。

那么，蒙特卡洛算法有什么神奇之处呢？

一、为什么叫蒙特卡洛(蒙特·卡罗)?

20世纪40年代美国“曼哈顿计划”的成员S.M.乌拉姆和J.冯·诺伊曼首先提出的，用驰名世界的赌城—摩纳哥的Monte Carlo命名。

二、原理

本质是一种统计方法，即用大量的随机样本，以出现概率当作问题的解。

比如计算圆周率π

显然上图1/4圆与正方形的面积比为

那么，如果在正方形内随机产生n个点，通过计算这些点和原点的距离，判断这些点是否在1/4圆内。

在1/4圆内的点数/n = π/4 。即点落在1/4圆内的概率*4 = π。

随机模拟30000个点，π的估算值与真实值相差0.07%

原来概率与统计可以这么用。

推而广之，可以计算任意一个积分的值。

关于蒙特卡洛还有许多神奇的应用，请移步

《A Business Planning Example》

《蒙特卡罗（Monte Carlo）模拟的一个应用实例》

《微观不可预测的交通的蒙特卡罗模拟》

《基于蒙特卡罗数值模拟的大跨桥梁状态评估》

回到问题上，阿法狗是怎么选择下一步的呢？

简单的说

1. 根据一定的策略选出可能的下法

2. 然后进行蒙特卡罗模拟计算胜率

以上2步反复进行，显然，模拟的次数越多，越有可能得到最优解。

这也就是为什么同样的zen7软件，电脑越快、计算时间越久，下法越厉害。