技术:电脑是怎么下棋的：蒙特卡洛树搜索法

本篇文章1819字，读完约5分钟

棋盘由19条横线和19条竖线组成，共计有19×19=361个交叉点。 此外，还有13×13、9×9的棋盘。 围棋分为黑白两种，对战对手各拿一种颜色的棋子，按顺序把一枚棋子落在交叉点上。 结果，占领的“地盘”(也就是其中的十字路口数量)多的一方获胜了。

空白的十字路口称为“目”，包围的地盘称为“空”。 对局中，棋手经常计算“数”，即双方现在包围的“空”的大小，评价形势的优劣。

在双方的水平差大的情况下，通常，让子的方法，即水平弱的一方先在棋盘的固定位置上放置1~9个子(分别让子、双胞胎、让三胞胎……)，双方轮流落下。

“指数增长”和“exptime-complete问题”

指数增长可以说是大规模计算的第一位“拦路虎”。 因为是22222，所以名字也没用，没用。

即使如此，作为比较，现在能够观测到的宇宙的原子总数据估计为“只有”10^75个。

有人可能听说为了分解现在的盘面必须囊括将来的所有趋势吗？ 可能有一种高效的算法，可以在不产生扫描可能以指数方式增加的空间的情况下正确判断现在的盘面吗？ 答案是，关于国际象棋和围棋，数学上可以说明，不仅要贫穷、复杂，而且要计算形势变化，还要配合考虑到复杂程度的步数，以指数函数增加。 对于任意给定的棋盘，将该棋盘的“最佳值”定义为游戏双方打出“完美之手”时的最终游戏结果。 如果一个棋盘的最佳值是“黑棋胜”，那么只要黑棋己没错，白棋战无论怎么努力都一定会输。 理论计算机科学家在1981年和1983年说明了国际象棋和围棋是exptime-complete类的问题。 这意味着用能正确计算“任何”盘面的最佳值的方法消耗的时间在“必然”中根据棋盘的大小(也就是棋局的平均步数)指数性地增加。 事实上，大部分流行的“两人零和”国际象棋类计算很多，复杂度是指数。 有西方跳棋手、五子棋等几个种类，它们的规模足够小，因此其初始盘面的最佳值已经计算出来了。 是

呃。

田这个，待在家里

然后，通式，上述式，上述式，上述式，上述式，(式)，()来进行( )。

例如，计算圆周率π的蒙特卡罗法在一个二维坐标系中，在与0、x、1、0、y、1对应的方形区域随机选择多个点，评价各点( x1、y1 )是否在"以原点为中心的半径1的单位圆"内" 根据中心极限定理，这些随机点收敛在单位圆内的比例以大致的比率迅速走向π/4。 所以我们选择的随机点数越多，可能得到的真正值估计得越近。

同样的“蒙特卡洛”思想也可以用于围棋盘面判定。 如上所述，各围棋棋局都有“最佳值”，与游戏双方使用完美招数时该棋局的最终结果相对应。 关于围棋，说明了计算该最佳值的时间至少根据从其盘面到最终盘之间的步数呈指数函数增加(平均200步，每步平均200倍数的可能盘面)。 。 既然理论上得不到最佳值，可以根据蒙特卡洛思想对整个可能性空间进行采样，用统计评价的方法近似这个最佳值吗？ 关于这个问题的想法在2006年终于取得了突破性的进展，提出了被称为蒙特卡洛树搜索的动态判断方法。

另外，以往的蒙特卡罗树搜索法虽然保证了大量采样的结果最终收敛到盘面的最佳值，但是“充分收敛”所需的采样次数根据可能性空间整体的规模指数而增加。 但是在围棋游戏系统的实践中，蒙特卡洛树搜索在比赛时间有限的情况下，表现出远远超过以前传来的做法的棋艺水平。 近年来，人们受到这种注意的鼓舞，在选择战略中与围棋相关的专家知识增加，基于蒙特卡洛树搜索的围棋游戏系统的水平提高。

1有些围棋软件在特定条件下触发“死活棋评价”或“抢夺”模式，但这些优化不是作为基本的思维模式，而是像特殊情况下的特殊策略。

*2这里“思考深度”定义为针对各个变化的展开步骤数。 假设一台机器本来一秒钟可以考察b^d个变化，对应的思考深度是d。 加上b倍的硬件能力，机器1秒钟可以考察b×b^d=b^(d+1)个变化，与思考深度相对应，为d+1。 通过采用αβ剪枝法，机器只要考察( b^2d)^(1/2)=b^d个变化就能得到与考察b^2d个变化相同的效果，对应的思考深度为2d。

*3已经强调了，国际象棋采用的战略只是“有效地”在一定阶段等于对所有变化的网罗，并不是在实际的计算过程中囊括整个可能性空间。

*4不仅如此，蒙特卡洛树的搜索方法现在作为共同的动态判断方法被广泛应用于“共同游戏比赛”(这场比赛的要求是为不知道具体规则的国际象棋游戏设计游戏程序)。 。

上一页1234下一页