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

2014年07月28日 10:29   新浪科技    收藏本文     

  概念解释:

  围棋

围棋围棋

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

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

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

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

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

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

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

  零和游戏

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

  蒙特卡洛树搜索法

使用蒙特卡罗方法估算π值。图/维基百科使用蒙特卡罗方法估算π值。图/维基百科

使用蒙特卡罗方法估算π值。图/维基百科选取的随机点(n)越多,估计值离π的真值越近。图/维基百科

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

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

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

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

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

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

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

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

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

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

上一页1234下一页

文章关键词: 人工智能弈棋计算机深蓝

分享到:
收藏  |  保存  |  打印  |  关闭

已收藏!

您可通过新浪首页(www.sina.com.cn)顶部 “我的收藏”, 查看所有收藏过的文章。

知道了

0
收藏成功 查看我的收藏
猜你喜欢

看过本文的人还看过