首页 > 搜索 > 开发围棋算法,蒙特卡洛算法与电脑围棋

开发围棋算法,蒙特卡洛算法与电脑围棋

互联网 2020-10-28 01:55:58
在线算命,八字测算命理
 局面动态评估:“激进”与“保守”之间的平衡取舍

主流的国际象棋程序往往采用一种比较“保守”的局势筛选策略,搭配一种比较“激进”的信息汇总策略。而主流的围棋程序则正好相反,在局势筛选方面相当“大胆”,却对从这些局势变化收集来的信息的使用相当“谨慎”。这主要是由于目前对这两种棋类的盘面静态评估的质量不同导致的。

对于国际象棋,已经找到了一种在“很多情况”下可以既快速又相对准确地对盘面进行静态评估的方法——当遇到这类“大致可以进行静态评估”的盘面时,这个静态评估方法有相当的可信度,而对于其他情况的盘面却完全不起作用。由于拥有这样一个具有“部分可靠性”的静态评估,国际象棋程序的策略“从概念上”可以理解为是对从当前盘面出发的每一种可能的变化都不停向前展开,直到遇到一个可以大致静态评估的盘面或者超出了一个预定的“最大展开步数”为止。这样的“保守”选择策略使得计算机对于一定阶段之内的所有变化都有了大致评估。接下来计算机在“假设”这些评估是正确的前提下,计算按照完美下法哪一种变化是最优的。

根据硬件计算能力,计算机还会设定一个“最小展开步数”,即使一个变化在展开不到最小步数时就遇到了一个“比较好评估的局面”,系统依然会继续往前看,而不会就此停止。这是为了最大限度地弥补“对比较好评估的局面进行静态评估时依然有可能出错”的缺陷。在开发第一个人类大师级水平的计算机“Belle”的过程中,人们发现弈棋计算机的最小展开步数越大,其棋力越强。也就是说,原则上只要通过不断增强硬件的计算能力,国际象棋机器就可以通过看得越来越深而下得越来越好。

1997年的“深蓝”计算机在配备了400多块专门设计的硬件加速卡之后,获得了每秒钟展开并评估2亿次盘面的恐怖计算能力,历史上第一次代表机器战胜了人类国际象棋冠军。在随后的十几年里,按照“摩尔定律”增长的计算机硬件能力变得愈加强大,计算机又先后多次战胜人类国际象棋冠军。越来越多的人相信,机器在国际象棋领域早已超越了人类的弈棋能力。

然而,计算机能够战胜人类国际象棋冠军并不全靠超强的硬件计算能力,软件算法方面的持续改进同样必不可少,甚至影响更大。

比如上面提到,国际象棋系统在“概念上”穷尽了一定步数之内的所有变化。但在真实的弈棋计算机中,一系列优化算法使得系统在不完全展开某些变化的同时也能够得到和完全展开一样(或类似)的效果。这样节省下来的时间可以用于把已知变化“看得更深”,从而极大提高了系统在“概念上”的等效计算能力。

其中最经典的例子是由人工智能先驱约翰·麦卡锡提出的αβ剪枝法,它巧妙利用了“国际象棋是双人零和游戏”的特点,以最优的方式避免所有不必要的变化展开。

根据计算机科学家唐纳德·克努特(Donald Knuth)的数学分析,在理想情况下,αβ剪枝法仅需评估所有b^d个变化中的b^(d/2)个,就可以保证得到和评估所有b^d个变化完全一样的结果。换句话说,我们需要增加 倍硬件计算能力才能使动态评估加深一步,而使用αβ剪枝法则可以使动态评估轻松增加整整一倍的“思考深度”*2!

αβ剪枝法成型于20世纪60年代,是国际象棋弈棋的诸多优化算法里最经典的一种。如今的国际象棋程序中还使用了大量其他优化方法,使得实际的动态评估过程远远比简单的“枚举”要高效得多,只是“从概念上”,它们从评估质量上等效(或接近)于一次对未来若干步内所有局势变化的穷举展开而已。

αβ剪枝法的一个简单示例 。假设A盘面下我方行动,并试图最大化我方胜率;而B盘面下对手行动,并试图最小化我方胜率。如果A代表当前盘面,而B代表我方走了某一步之后到达的新盘面。现在假设已知B盘面下对手存在一种走法使得我方胜率至多有30%,同时已知A盘面下我方存在一种走法使得我方胜率至少有40%,那么我们已经可以确定无需再检查B盘面下其他未展开的变化了。在层层展开的动态评估过程中这样的“剪枝”可以反复使用,从而大量减少需要实际评估的变化数量。    αβ剪枝法的一个简单示例。

假设A盘面下我方行动,并试图最大化我方胜率;而B盘面下对手行动,并试图最小化我方胜率。如果A代表当前盘面,而B代表我方走了某一步之后到达的新盘面。现在假设已知B盘面下对手存在一种走法使得我方胜率至多有30%,同时已知A盘面下我方存在一种走法使得我方胜率至少有40%,那么我们已经可以确定无需再检查B盘面下其他未展开的变化了。在层层展开的动态评估过程中这样的“剪枝”可以反复使用,从而大量减少需要实际评估的变化数量。

国际象棋的动态评估方法(或其变种)也广泛应用于大多数其他棋类的对弈系统,其中很多达到或超越了人类冠军的水平。然而,这套思路却在围棋博弈中遭遇了滑铁卢。截至目前,没有一个基于国际象棋的动态评估思路的围棋系统可以超过人类业余入门级水平。很多人把这一失败归因于围棋比国际象棋更大的计算复杂度(这当然看起来是最明显的原因之一)。

但是,根据许峰雄博士在2007年发表的那篇名为“Cracking GO”(破解围棋)的文章,在拥有接近国际象棋的静态评估质量的前提下,我们完全可以在软件和硬件两方面进行一系列优化,使得国际象棋的动态评估方法在围棋中也达到类似的思考深度。如果我们假设围棋大师们的智力并不显著高于国际象棋大师的话,这样的思考深度也许会使机器在围棋上再次战胜人类。也就是说,对于当今的硬件能力,围棋的复杂度并不是不可逾越的鸿沟。那么,到底是什么原因导致国际象棋的策略无法适用于围棋呢?

笔者的观点是,“穷举型” 策略*3至今未在围棋中广泛应用,更大的障碍恐怕还是缺少一个像国际象棋那样能够对于“一大类”盘面进行“大致准确的评估”的方法。前面介绍静态评估方法的部分已经提到了,目前围棋盘面的静态评估方法一般只在棋局前期黑白双方尚未“短兵相接”时有一定效果。当棋局进入关键的中盘厮杀之后,如果仍然使用现有的静态评估方法,我们就会发现:在达到硬件计算能力可承受的最大预判步数时,大部分棋局变化都处于不能“大致准确评估”的状态。基于这些十分不“靠谱”的评估结果去考虑所谓“完美”走法,得到的结果自然也是不大靠谱的。

正是由于缺少“靠谱”的静态评估方法,目前所有顶级围棋程序转而采取一种比较“谨慎”的信息汇总策略。

在国际象棋中,如果一个盘面有两种走法,一个估计胜率30%,另一个估计胜率80%(如图(a)中盘面B所示),计算机会倾向于相信这些结果都是大概“靠谱”的,因此该盘面自身的胜率应该等于所有走法中的最优结果(我方盘面取最大值,对手盘面取最小值),因此认为盘面B的胜率是30%。这是一种比较“激进”的信息汇总策略:当发现了30%胜率的走法时,系统会完全丢弃80%胜率的走法所带来的信息,选择全部相信30%胜率的走法。

相同情况下的不同信息汇总策略。(a)为以国际象棋程序为代表的“激进”策略,取最大(小)值为汇总结果;(b)~(d)为以围棋程序为代表的“保守”策略,取加权平均值为汇总结果。其中(b)对应评估初期等权重下的结果,如果其中30%的静态评估正确,则算法经过150次蒙特卡洛采样后会导向(c)所示结果,否则会导向(d)所示结果。相同情况下的不同信息汇总策略。(a)为以国际象棋程序为代表的“激进”策略,取最大(小)值为汇总结果;(b)~(d)为以围棋程序为代表的“保守”策略,取加权平均值为汇总结果。其中(b)对应评估初期等权重下的结果,如果其中30%的静态评估正确,则算法经过150次蒙特卡洛采样后会导向(c)所示结果,否则会导向(d)所示结果。

而在围棋程序中,计算机认为对每个盘面的直接静态评估结果都是不可靠的,但是相信“对该盘面下所有走法的全部评估结果”却整体上仍然对该盘面的胜率 具有指向性。现有围棋程序一般采用对所有评估结果进行加权平均的方式来体现这种指向性,其中“权重”基于对当前评估结果的可信度进行设定。举例来说。在图 (b)中,假设对盘面B下两种走法所直接导致的盘面进行静态评估的结果胜率分别为30%和80%,而盘面C下的两种走法胜率分别为50%和40%。因为这 4个估计值可能都存在偏差,所以我们并不偏信其中任何一个;另一方面,在偏差没有系统性地倒向“某一类盘面”或“某一类走法”的前提下,我们有理由相信这 4个盘面评估结果具有相同的可信度(或“不可信度”),因此应该具有相同的权重。所以在只知道这4个静态评估结果的情况下,我们认为盘面B的评估胜率是 0.5×30%+0.5×80%=55%,盘面C的评估胜率是0.5×50%+0.5×40%=45%。同时,这样做出的对B和C的判断自身仍然有可能存 在偏差,所以在以盘面B和C为基础再评估盘面A时也要考虑到这一点,因此A的评估结果同样是B和C的结果的再次加权平均 0.5×45%+0.5×55%=50%。

我们看到,这样根据等权重得到的对A的评估结果实际上是综合了所有当前已知信息之后给出的一个“模棱两可”的评估。考虑到“已知信息”本质上的 低可靠度,这也许就是我们在这种情况下“应该”得到的答案。当然,这样一个仅仅基于4次静态评估的结果并不是计算机给出的最终答案。对于一个给定盘面,我 们考察的变化越多,获取的信息量也越大,因此对这个盘面的评估值也倾向于更可靠,从而这个评估值在参与加权平均时也理应获得更大的权重。换句话说,我们根 据对一个盘面“深思熟虑”的程度来量化对其评估结果的“可信度”,认为一个进行大量分析后得到的评估结果在可信度上优于分析较少的评估结果。这就涉及到如 何选择那些需要进一步深思熟虑的变化的问题。

有意思的是,在采取较为谨慎的信息汇总策略的同时,围棋程序在局势变化的选择策略上却相当“大胆”。如果说国际象棋程序希望考察在一定阶段内的所有变化,那么围棋程序却只通过对所有这些变化进行某种有策略的采样来进行评估,把更多的时间精力投入到那些“看似”更有希望的变化上。这就是被称为蒙特卡洛树搜索的动态评估方法。这种方法在“从当前盘面出发所有有可能的局势变化”组成的巨大可能性空间中进行反复采样。通过巧妙设计的选择策略,配合前面所说的基于加权平均值的信息汇总策略,计算机会根据已有的采样结果调整新一轮采样所选择的变化,从而保证最优走法逐渐获得更多的选择机会,因此获得更大的权重。这样的长期结果是,大量采样之后对当前盘面下所有走法的“加权平均”结果会逐渐逼近当前盘面的最优值!

仍然回到图10的例子。我们看到图(b)中基于4次静态评估的加权平均结果高于图(a)中按照传统国际象棋思路得到的结果,这主要是因为我们对当前胜率评估为30%的这个盘面“不大信任”导致的。在接下来的动态评估采样中有两种可能:(1)当前的30%的评估结果是正确的,在这种情况下蒙特卡洛树搜索算法对盘面B下的变化采样会更倾向于30%这个走法,因此B的评估值会逐渐下降到接近30%,而这又会导致B的评估值低于C,因此C获得更多采样机会,从而在对A的加权平均评估时获得比B更大的权重。如图(c)所示,在150次采样之后,A的评估值接近C,而C的评估值接近40%——这和图(a)的评估结果一致(因为当初30%的静态评估结果恰好是正确的!)。(2)如果图(b)中30%的结果是错误的,假设机器经过对这个走法进一步考察(75次采样)后发现它的胜率其实应该是80%。这种情况下,B的评估值会逐渐上升到80%,而这导致B相对于A的权重变高,因此A的评估值也随之上升,从而得到和前面不一样的最终评估结果。

总而言之,目前的主流围棋程序试图用一种系统性的方法去“管理”在评估过程中不可避免带来的“不确定性”。截至目前,所有一流的围棋程序全部采用蒙特卡洛树搜索方法进行盘面动态评估////4。它们从基本“思维模式”和局面胜率评估的“基本框架”上继承了以国际象棋弈棋计算机为代表的传统方法;同时,采用蒙特卡洛采样思想来进一步管理知识中的“不确定性”,在选择策略上化保守为激进,在汇总策略上化激进为保守,在无法对变幻莫测的围棋盘面进行有效静态评估的情况下仍然达到了业余高级水平的棋力。

弈棋计算机是人工智能吗?

弈棋是一种刺激性极强的直接对抗。计算机弈棋代表了一种机器对人类的“符号意义上”的挑战,因而备受关注。“人类弈棋大师在整体智力上超出常人”这一事实,也使得“计算机在弈棋上向人类高手发起的挑战”被很自然地认作是一种关乎“智力极限”的挑战。

那么,从人工智能的角度,我们应该如何看待弈棋系统及其相关的研究活动呢?

首先我们应该意识到,被我们视为智力挑战的问题,机器做起来往往未必困难;反而是一些人类觉得稀松平常的脑力活动,机器实现起来却可能非常困 难。比如速算曾经同样是智力超群的象征,但是现代计算机无论在计算速度还是准确率上都毫无争议地完胜人类。要理性衡量计算机弈棋与人工智能的关系,还要对 照上期我们总结的人工智能的主要特征来分析。

根据人工智能的主要特征,虽然弈棋满足了智能行为的标准,但目前的所有计算机弈棋系统都不满足通用性要求,因此还不能算是完整的人工智能系统。 考虑到国际象棋领域里一台“不算完整人工智能系统”的机器已经战胜了人类,那么当围棋机器战胜人类的那一天到来的时候,也未必就意味着什么人工智能新时代 的开始。

然而,“弈棋系统本身不是人工智能系统”不代表“弈棋系统研究不是人工智能研究”。棋类运动被称为是人工智能领域的“果蝇”,我们对果蝇进行研 究,根本目的并不是为了制造一个“更强壮的果蝇”,而是为了以此探索一些具有普遍性的生物系统规律,帮忙我们认识和研究比果蝇更复杂的生物系统。在笔者看 来,弈棋系统研究在人工智能方面的意义主要有两个,第一个是为相关的自动推理/规划、自动学习、知识表示等等人工智能技术提供实验场所,第二个就是为打败 人类而发明的如“推演”和“规划”部分的相关技术在通用智能中的推广和应用。

最后,一个经常被提及的话题是关于如何对待人类领域知识在弈棋系统中的作用。有些人认为,使用了“人类职业棋手”的知识的弈棋系统有“作弊”之 嫌,认为弈棋系统只有“零知识”才算真本领。笔者认为没有必要苛求于此。所谓名师出高徒,有几个人类冠军是自学成才的?即使是职业棋手的知识也不一定是他 自己想出来的,毕竟人类已经积累了上千年的领域知识。事实上,能够积累、运用和传授知识正是人类智能最厉害的地方之一,而“知识表示与管理”也是通用人工 智能系统的必要组成部分。

另一方面,“形式化人类领域知识”也并不是“显然可行”的事情。国际象棋方面,是在深蓝成功之后才真正证明国际象棋大师的经验“可以”形式化表 达(深蓝团队在这方面做了大量工作),而围棋盘面静态评估甚至至今尚未找到有效形式化的方法。可以说,针对围棋弈棋的研究在知识表示上尚处于努力证明“可 以形式化”的阶段;而与此同时,“通用博弈比赛”相关的研究则已经开始对“统一化的知识表示”的初步探索。

本文由《科学世界》杂志授权转载

概念解释:

围棋

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

免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多