双人象棋小游戏一文读懂蒙特卡洛方法 谷歌围棋机器人科普

它诞生于上个世纪40年代美国的曼哈顿计划，名字来源于赌城蒙特卡罗，象征概率。

做为一种通用的计算方法，蒙特卡洛采样法的思想是当我们在求解一个确定但未知的值的时候，“在概念上”巧妙构造一个随机过程，使得这个随机过程的某个数字特征依概率于我们要求的值，然后“在实际操作中”通过对该随机过程进行采样来对这个值进行统计估计。

1有些围棋软件会在特定条件下触发“死活棋判断”或者“劫争”模式，但这些优化更像是在特殊情况下的一种特殊战术，而不是作为一种基本思考模式。

有人会问，为了分析当前盘面一定要穷举所有未来走势的可能性吗？有没有可能存在一个高效的算法可以在避免遍历呈指数级增长的可能性空间的 同时仍然对当前盘面做出准确评估呢？答案是，对于国际象棋和围棋，我们可以从数学上证明，不仅仅是穷举复杂度，其局势变化的计算复杂度也必须随所考虑的步 数呈指数级增长！对于任意一个给定的盘面，我们定义这个盘面的“最优值”为当博弈双方都下出“完美走法”的情况下导致的最终博弈结果。如果一个盘面的最优 值是“黑棋胜”，那就是说在黑棋自己不出错的情况下白棋无论如何努力都是必败的。理论计算机科学家先后在1981年和1983年证明国际象棋和围棋都属于 EXPTIME-Complete类问题，这意味着“任何”能正确计算盘面最优值的方法所花费的时间“必然”随棋盘大小(亦或棋局的平均步数)呈指数级增 长。事实上大部分流行的“双人零和”棋类的计算复杂度都是指数级的。有一些棋类如西洋跳棋、五子棋，它们的规模足够小，所以其初始盘面的最优值已经被计算 出来了。但是像国际象棋和围棋这样的复杂棋类，计算其初始盘面的最优值，以现在的硬件计算能力看来还遥遥无期。

对弈双方的水平差距较大时，常会采用让子棋的方式，也就是水平较弱的一方先在棋盘的固定放上1～9个子(分别称为让先、让二子、让三子……)，然后双方再轮子。

这种选择很大程度上跟现有围棋弈棋系统对盘面静态评估方法的整体有关。前面提到，由于人们在设计具有一定通用性的围棋盘面静态评估函数的问题上长期止步不前，大概在2002年之后人们开始思考采用另一种完全不同的方式对盘面进行快速评估，这就是蒙特卡洛采样。

围棋

的方法加以推广，就可以计算任意一个积分的值。

x12+y12是否小于1)。根据中心极限，这些随机点落在单位圆内的比例依大概率快速趋于π/4。所以我们选取的随机点数量越多，越有可能得到的一个离的真值更接近的估计。

某产品由八个零件堆叠组成。也就是说，这八个零件的厚度总和，等于该产品的厚度。

相同的“蒙特卡洛”思想也可以用于围棋盘面评估。前面提到了，每个围棋盘面都有一个“最优值”，对应于对弈双方都采用完美走法的情况下该盘面的最终结果。对于围棋已经证明，计算这个最优值的时间至少随该盘面到终盘之间的步数呈指数级数增长(平均200步，每步平均增长200倍数量的可能盘面)。既然从理论上无法得到最优值，有没有可能根据蒙特卡洛思想对整个可能性空间进行某种采样，然后通过统计估值的方法逼近这个最优值呢？人们对这个问题的思考在2006年终于取得了突破性进展，提出了一种称为蒙特卡洛树搜索的动态评估方法。

蒙特卡洛树搜索法

围棋盘由19条横线和19条竖线组成，共有19×19＝361个交叉点。此外，也有13×13、9×9的小棋盘。围棋子分为黑白两色，对弈双方各执一种颜色的棋子，轮流将一枚棋子下在交叉点上。终局时，占领(围起)的“地盘”(即其中的交叉点个数)多的一方获胜。

比如说，一种计算圆周率π的蒙特卡洛方法是，在一个二维坐标系中0≤x≤1和0≤y≤1对应的方形区域里随机选取若干个点，并判断每个点(x1,y1)是否落在“以原点为圆心半径为1的单位圆”内(也即判定

需要指出的是，现有的蒙特卡洛树搜索法虽然能大量采样的结果最终到盘面最优值，但为达到“足够”所需的采样次数仍然是随整个可能性空间的规模指数级增长的。但是在围棋弈棋系统的实践中，蒙特卡洛树搜索在比赛时间受限的情况下确实表现出远远超过传统方法的棋力。最近几年人们受这一观察的鼓舞，在选择策略中加入更多和围棋相关的专家知识，使得基于蒙特卡洛树搜索的围棋弈棋系统水平不断提高。

又称零和博弈(Zero-Sum Game)，是博弈论中的一个概念，指游戏(博弈)双方是竞争而不是合作关系，或者说是一种“你死我活”的状态。例如两人对弈，一方赢，另一方必然是输，不存在“双赢”。赢棋得1分，输棋减1分，两人得分之和就总是0，所以称为零和游戏。

蒙特卡罗方法是一种计算方法。原理是通过大量随机样本，去了解一个系统，进而得到所要计算的值。

已知你的成本在每股5.5元到7.5元之间，平均是6.5元。请问接下来的交易，你的净利润会是多少？

取1000个随机样本，每个样本有两个数值：一个是证券的成本（5.5元到7.5元之间的均匀分布），另一个是当前市场状态（冷清、活跃、温和，各有三分之一可能）。

指数级增长可算是大规模计算第一大“拦虎”了。在一个著名的传说中，国际象棋的发明者印度人塞萨(Sessa)向他的国王请求赏赐，他 说，希望因为发明国际象棋棋盘的第一个格而得到一粒米，因为第二个格得到两粒米，因为第三格得到四粒米，如此在每后一个格都增加一倍的米量。不识指数级增 长威力的国王欣然答允，甚至还有些责怪塞萨要求太少，然而事后才发现整个国库的米都倒干净了仍然无法填满整个棋盘。故事的结局是，国王恼羞之下偷偷派人把 塞萨杀掉了。学过等比数列的现代人按一按计算器就知道，国王因为这64个棋盘格子总共要支出2^64-1=709551615＞10^19粒米，这据估计已经超出整个人类历史上产米量的总和！

模拟计算得到，平均净利润为92, 427美元。

已知该产品的厚度，必须控制在27mm以内，但是每个零件有一定的概率，厚度会超出误差。请问有多大的概率，产品的厚度会超出27mm？

2这里“思考深度”定义为对每个变化的展开步数。假设一台机器原本一秒钟可以考察b^d个变化，对应思考深度为d。增加b倍硬件能力使得机器一秒钟可以考察b×b^d=b^(d+1)个变化，对应思考深度为d+1。使用αβ剪枝法使得机器仅需考察(b^2d)^(1/2)=b^d个变化就达到和考察b^2d个变化一样的效果，对应的思考深度为2d。

如果这些点均匀分布，那么圆内的点应该占到所有点的 π/4，因此将这个比值乘以4，就是π的值。通过R语言脚本随机模拟30000个点，π的估算值与真实值相差0.07%。

4不仅如此，蒙特卡洛树搜索方法目前已经作为一种通用的动态评估方法广泛应用于“通用博弈比赛”(这种比赛要求为事先不知道具体规则的棋类游戏设计对弈程序)。

零和游戏

“指数级增长”与“EXPTIME-Complete问题”

这个函数在 (1,1) 点的取值为1，所以整个红色区域在一个面积为1的正方形里面。在该正方形内部，产生大量随机点，可以计算出有多少点落在红色区域（判断条件 y x2）。这个比重就是所要求的积分值。

转自

现在，在这个正方形内部，随机产生10000个点（即10000个坐标对 (x, y)），计算它们与中心点的距离，从而判断是否落在圆的内部。

正方形内部有一个相切的圆，它们的面积之比是π/4。

第一个例子是，如何用蒙特卡罗方法计算圆周率π。

上图中，横轴代表距离（从左到右），纵轴代表时间（从上到下），因此每一行就表示下一秒的道情况。

可以看到，该模型会随机产生交通拥堵（图形上黑色聚集的部分）。这就证明了，单车道即使没有任何原因，也会产生交通堵塞。

（本文来源网络，如有侵权，请联系删除）

它非常强大和灵活，又相当简单易懂，很容易实现。对于许多问题来说，它往往是最简单的计算方法，有时甚至是唯一可行的方法。

回到局势变化的复杂度问题上。即使10^19这样的天文数字也“只不过”是一个从当前盘面出发，每次只考虑2种走法，持续64步之后的可 能性空间的大小。对于国际象棋和围棋这样的复杂棋类，从初始盘面出发穷尽所有变化的复杂度(也称穷举复杂度)更是大得难以想象。信息论创始人克劳德香农在 1950年第一个估计出国际象棋的穷举复杂度大概在10^120种变化左右，具体数字被后人称为“香农数”。而围棋的穷举复杂度又远远超出国际象棋，达到 了惊人的10^360。作为比较，目前可观测中的原子总数据估计“只有”10^75个。

查看原文阅读数

3前面已经强调过了，国际象棋使用的策略只是在“效果上”等价于对一定阶段内所有变化的穷举，而并不在实际运算过程中真的穷举整个可能性空间。

使用蒙特卡罗方法估算π值。图/

比如，计算函数 y = x2在 [0, 1] 区间的积分，就是求出下图红色部分的面积。

电脑是如何下棋的：蒙特卡洛树搜索法

在一条直线上，随机产生100个点，代表道上的100辆车，另取概率 p 为 0.3 。

用Matlab模拟100万个随机点，结果为0.3328。

选取的随机点(n)越多，估计值离π的真值越近。图/

取100000个随机样本，每个样本有8个值，对应8个零件各自的厚度。计算发现，产品的合格率为99.9979%，即百万分之21的概率，厚度会超出27mm。

空白的交叉点称为“目”，围到的地盘又称为“空”。对弈过程中，棋手经常会“数目”，也就是计算双方目前所围的“空”的大小，以此判断形势优劣。