17--3-5计算机是如何下棋的

电脑是如何下棋的深入了解人工智能你喜欢下棋吗？有没有和计算机下过？现在，弈棋计算机的棋艺日益高强让我们通过分析以围棋和国际象棋为代表的弈棋计算机，对人工智能的研究有一个更为深入的理解弈棋自古被视为一种关乎智力的高级挑战和其他智力测试相比，弈棋具有直接对抗的特点，没有什么比在紧张的对局中看到对手一手精妙凶狠的棋招更能让人感觉到一种智力上的刺激和挑战了围棋起源于中国，是最古老的棋类运动之一，我们常说的〃琴棋书画〃中的〃棋〃就是指围棋围棋盘由19条横线和19条竖线组成洪有19x19=361个交叉点此外，也有13x

13、9x9的小棋盘围棋子分为黑白两色，对弈双方各执一种颜色的棋子，轮流将一枚棋子下在交叉点上终局时，占领（围起）的〃地盘〃（即其中的交叉点个数）多的一方获胜空白的交叉点称为〃目〃，围到的地盘又称为〃空〃对弈过程中，棋手经常会〃数目〃，也就是计算双方目前所围的〃空〃的大小，以此判断形势优劣对弈双方的水平差距较大时，常会采用让子棋的方式，也就是水平较弱的一方先在棋盘的固定位置放上1〜9个子（分别称为让先、让二子、让三子……），然后双方再轮流落子本文转自《科学世界》你喜欢下棋吗？有没有和计算机下过？现在，弈棋计算机的棋艺日益高强让我们通过分析以围棋和国际象棋为代表的弈棋计算机，对人工智能的研究有一个更为深入的理解弈棋计算机弈棋自古被视为一种关乎智力的高级挑战和其他智力测试相比，弈棋具有直接对抗的特点，没有什么比在紧张的对局中看到对手一手精妙凶狠的棋招更能让人感觉到一种智力上的刺激和挑战了弈棋相比于其他牌类游戏而言，随机和不可控因素更小，因此对局双方的决策能够更直接地控制整个局面的走势，这进-步增强了智力的对抗性毫不意外，在国际象棋更加流行的西方国家，人工智能领域自创建之初就在考虑如何制造一个会下国际象棋的机器几乎所有人工智能先驱，包括信息论创始人香农、〃人工智能〃之父约翰・麦卡锡（John McCarthy）,计算机科学创始人图灵，都曾严肃思考过制造国际象棋机器的问题20世纪80年代初，贝尔实验室的工程师们（其中包括著名操作系统Unix的联合创作者肯汤姆森）开发出历史上第一个具有人类大师级水平的国际象•棋机器〃Belle〃到80年代末，卡内基梅隆大学的许峰雄博士在Bella〃的思路基础上（将在后面详细介绍）进一步改进，研制出了第一个特级大师水平的国际象棋机器，取名〃深思〃（源自《银河系漫游指南》中的超级计算机）随后，许博士加入IBM研究院，在那里和其他几个团队成员一起研制出了实力更强的弈棋机器〃深蓝〃，并最终于1997年的一场历史性的人机大战中以

3.5:

2.5的比分战胜了人类国际象棋冠军卡斯帕罗夫（卡斯帕罗夫不但是当时的人类冠军，同时也是人类历史上国际象棋等级分最高的职业选手）需要指出的是，现有的蒙特卡洛树搜索法虽然能保证大量采样的结果最终收敛到盘面最优值，但为达到‘足够收敛〃所需的采样次数仍然是随整个可能性空间的规模指数级增长的但是在围棋弈棋系统的实践中，蒙特卡洛树搜索在比赛时间受限的情况下确实表现出远远超过传统方法的棋力最近几年人们受这一观察的鼓舞，在选择策略中加入更多和围棋相关的专家知识，使得基于蒙特卡洛树搜索的围棋弈棋系统水平不断提高弈棋计算机是人工智能吗？弈棋是一种刺激性极强的直接对抗计算机弈棋代表了一种机器对人类的〃符号意义上〃的挑战，因而备受关注〃人类弈棋大师在整体智力上超出常人〃这一事实，也使得〃计算机在弈棋上向人类高手发起的挑战〃被很自然地认作是一种关乎〃智力极限〃的挑战那么，从人工智能的角度，我们应该如何看待弈棋系统及其相关的研究活动呢？首先我们应该意识到，被我们视为智力挑战的问题，机器做起来往往未必困难；反而是一些人类觉得稀松平常的脑力活动，机器实现起来却可能非常困难比如速算曾经同样是智力超群的象征，但是现代计算机无论在计算速度还是准确率上都毫无争议地完胜人类要理性衡量计算机弈棋与人工智能的关系，还要对照上期我们总结的人工智能的主要特征来分析根据人工智能的主要特征，虽然弈棋满足了智能行为的标准，但目前的所有计算机弈棋系统都不满足通用性要求，因此还不能算是完整的人工智能系统考虑到国际象棋领域里一台〃不算完整人工智能系统〃的机器已经战胜了人类，那么当围棋机器战胜人类的那一天到来的时候，也未必就意味着什么人工智能新时代的开始然而，〃弈棋系统本身不是人工智能系统〃不代表〃弈棋系统研究不是人工智能研究〃棋类运动被称为是人工智能领域的〃果蝇〃，我们对果蝇进行研究，根本目的并不是为了制造一个〃更强壮的果蝇〃，而是为了以此探索一些具有普遍性的生物系统规律，帮忙我们认识和研究比果蝇更复杂的生物系统在笔者看来，弈棋系统研究在人工智能方面的意义主要有两个，第一个是为相关的自动推理/规划、自动学习、知识表示等等人工智能技术提供实验场所，第二个就是为打败人类而发明的如〃推演〃和〃规划〃部分的相关技术在通用智能中的推广和应用最后，一个经常被提及的话题是关于如何对待人类领域知识在弈棋系统中的作用有些人认为，使用了〃人类职业棋手〃的知识的弈棋系统有〃作弊〃之嫌，认为弈棋系统只有〃零知识〃才算真本领笔者认为没有必要苛求于此所谓名师出高徒，有几个人类冠军是自学成才的？即使是职业棋手的知识也不一定是他自己想出来的，毕竟人类已经积累了上千年的领域知识事实上，能够积累、运用和传授知识正是人类智能最厉害的地方之一，而〃知识表示与管理〃也是通用人工智能系统的必要组成部分另一方面，〃形式化人类领域知识〃也并不是〃显然可行〃的事情国际象棋方面，是在深蓝成功之后才真正证明国际象棋大师的经验〃可以〃形式化表达（深蓝团队在这方面做了大量工作），而围棋盘面静态评估甚至至今尚未找到有效形式化的方法可以说，针对围棋弈棋的研究在知识表示上尚处于努力证明〃可以形式化〃的阶段；而与此同时，〃通用博弈比赛〃相关的研究则已经开始对〃统一化的知识表示〃的初步探索本文由《科学世界》杂志授权转载在围棋更加流行的东方，围棋大师的头衔同样是智力超群的象征自从计算机在国际象棋上挑战人类成功之后，所有人的目光就聚焦在了围棋这项古老的东方棋类运动上然而对计算机来说，围棋似乎是个比国际象棋更〃难〃的东西1985年，企业家应昌期先生悬赏一百万美金寻找能够打败人类职业棋手的计算机，可时至30年后的今日仍然没有一台计算机能够做到20世纪90年代，以我国陈志行教授开发的〃手谈〃程序以及著名开源软件组织GNU开发的〃GNU Go〃程序为代表的〃计算机围棋冠军〃们，棋力尚且不及人类的业余初段进入21世纪之后，研究者们开始探索一套被称为〃蒙特卡洛树搜索〃的全新思路（将在后面详细介绍），并终于在2006年在9x9的〃小棋盘〃上率先产生突破以法国的MoG和CrazyStone为代表的新一代围棋程序在9路围棋上基本已经达到人类职业棋手的水平，甚至曾在公开场合战胜过职业棋手周俊勋九段另一方面，在真正的19路围棋棋盘上,以日本的ZEN（天顶围棋）和法国的CrazyStone为代表的一流围棋程序沿着〃蒙特卡洛方法〃的思路不断改进，在和人类顶尖职业棋手进行的一系列让子棋比赛中屡有佳绩，而近些年人类棋手能〃让〃计算机的子数也越来越少最有趣的是在2013年，计算机程序CrazyStone在受让四子的情况下战胜被称为〃人脑计算机〃的日本棋手石田芳夫九段，并被认为已有业余五~六段的水平截至目前，尽管计算机在公平的围棋比赛中还不足以直接抗衡人类职业棋手，但相关的研究热度却很高，大家普遍对近期前景持较为乐观的态度〃深蓝之父〃许峰雄博士甚至在2007年10月的一期《正EE Spectrum》杂志上表示，相信10年内超级计算机将能挑战世界冠军级别的人类棋手（框文）【围棋围棋起源于中国，是最古老的棋类运动之一，我们常说的〃琴棋书画〃中的〃棋〃就是指围棋（图）【左为唐代《围棋仕女图》绢画，1972年出土于吐鲁番阿斯塔那；右为隋代白釉瓷围棋盘，1959年出土于河南安阳图/维基百科】（图）】计算机下棋的思考模式现在主流弈棋计算机的基本〃思考模式〃很简单，就是对当前局面下的每一种合法走法所直接导致的局面进行评估，然后选择〃获胜概率〃最高的局面所对应的那个走法也就是说，〃准确评估给定局面的胜率〃是主流弈棋计算机的核心问题，同时也是主要难点所在在进一步深入讨论这一核心技术问题之前，我们先在基本思考模式层面简单比较一下计算机棋手与人类棋手的异同可以说，计算机的基本策略是所有〃人类有可能采用〃的策略中最原始最简单的一种毫无疑问，人类的思考模式中必然也包含〃局面评估〃的部分，然而人类至少还同时拥有另一个重要的思考模式——战略性思考，也就是把一个基本目标有效分解成一系列〃子目标〃以围棋为例，〃获胜〃是围棋的最终目的，而胜的定义是〃结束比赛时拥有更多棋子和空〃（中国规则）但是人类棋手在对弈时显然并不是每时每刻都在基于这个〃胜〃的定义进行思考的——通常我们只在棋局进入中后期时才经常性地〃数目〃在对弈的大部分时间里我们是在思考诸如〃如何借助右上角黑棋的毛病扩张〃、〃如何做活〃、〃如何侵消对手的模样〃、〃如何在劫争中转换〃、〃如何分断〃等等一系列具体问题我们注意到，每一个这样的〃具体问题〃实际上是改变了思考的目标，把一个〃求胜〃的问题转化成了一系列〃分断〃或者〃做活〃之类的子问题这样的一个〃战略计划〃，其背后的逻辑当然是，我们的大脑相信在当前情况下〃分断对手大龙〃是最有可能导致最终赢棋的子目标一旦确立了子目标，人类棋手便集中精力考虑具体战术走法来完成这个子目标，而不是〃赢棋〃这个最终目标与之不同的是，目前主流的弈棋计算机从基本思考模式上并不依赖于〃生成并确定子目标〃的战略能力在大多数时刻，这些弈棋计算机只关心一个问题，就是按照〃胜〃的基本定义来赢得比赛〃〃1〃在当前局面下，我走在X点的话最终能赢几子〃，计算机就是通过不停地重复问自己这个问题来完成对弈的尽管这听起来很〃原始’’，但正如前面所说，这样思考的计算机却已经在很多棋类中达到了相当令人惊讶的水平！现在我们回到〃评估局面胜率〃这一计算机弈棋的核心问题上主流方法中一次局面评估通常由被称为〃静态评估〃和〃动态评估〃的两个部分协同配合完成基于〃特征识别〃的静态评估黑方影响的区域|白方影响的区域对围棋局面基于〃粒子-场〃模型的静态评估结果局面静态评估好比人类棋手的〃感觉〃（也叫〃第一感〃、〃棋感〃目前使用的方法很容易理解就像网上经常遇到的性格测试让一个人做10道选择题，每道题如果选A加1分，选B不加分，然后根据10道题的总分对这个人的性格进行分类，0~2分的是黏液质性格，8~1分的是多血质性格……国际象棋的局面静态评估过程和性格测试非常类似，对于一个给定的局面（对应性格测试里的一个人），评估算法问〃当前局面里我方有没有皇后〃，有的话加10分，没有不加分；再问〃有没有兵〃，有的话每个兵加1分，没有不加分……然后评估算法把所有问题的总分加起来，总分越高代表该局面胜率越大我们看到，计算机对国际象棋局面的静态评估过程相当于给局面做了一次测试卷，其中每一道测试题对应了局面的一个特征一般来说，优秀的国际象棋计算机所使用的〃测试卷〃中的每一道题都是由人类大师根据自己多年的弈棋经验精心设计的，而里面每道题的〃分值〃或者由象棋大师直接设定，或者由计算机根据海量棋谱通过被称为〃机器学习〃的技术自行决定前一种方法往往面临的一个问题是，人类大师其实根本就不用这种〃给局面做测试卷〃的方式思考，所以他们的经验有时很难直接指导分值设定而在后一种基于机器学习技术的做法下，象棋大师除了设计用于评估局面的〃考题〃（每道题分值待定）之外，〃只〃需要对用于〃训练〃计算机的棋谱中出现的每一个局面打一个〃局面总分〃（这个总分并不基于大师为计算机设计的任何〃考题〃，而是直接根据自己的经验得出），计算机就可以自动为每道考题选择一个合适的分值，使得当我们使用如此学习出来的分值去考察棋谱中的每个局面时,由〃考卷〃累加得到的分数都恰好比较接近象棋大师根据经验为该局面评估的分数！围棋计算机程序使用的静态评估过程一般也基于类似的〃打分原理〃只不过围棋里面棋子的〃位置特征〃比〃数量特征〃更重要，所以围棋程序在选取特征时往往并不基于单个棋子，而是基于由若干子组成的〃基本形状〃更重要的区别是，围棋局面评估并不仅仅是把来自每个特征的得分简单相加，而是基于一些更复杂有趣的综合过程比如，在这方面有一类很有意思的研究叫做〃基于动态系统的围棋局面评估〃这种观点把围棋棋盘看作一个二维〃静力场〃，里面每一个棋子或每一个基本形状拥有一个类似于〃电荷〃的属性，并根据这个属性向外辐射〃影响力〃，强度随着距离递减这样，对于给定局面，棋盘中的每一个点都具有一个〃场强〃，它根据来自棋盘上所有黑子和白子的影响力相互叠加和抵消后决定所有点的场强可以通过多轮迭代计算得出（类似于物理中求解〃多体问题〃的过程），根据这些场强我们就可以决定对于棋盘中每一个点，黑白哪一方〃势力〃更大从某种意义上讲，基于动态系统的围棋局面评估实际就是在试图建立一套〃围棋世界里的物理定律〃，使得依据这些定律做出的判断符合顶级高手间的实战经验，或甚至是符合〃完美走法〃下的结果当然，目前的〃粒子-场〃模型可能更多只是对我们所熟知的经典力学模型的简单模仿，也许我们应该基于一套完全不同的理论来描述围棋棋盘里的天地（比如基于概率模型），又或许从原则上根本不存在能够精确描述局面走势的〃围棋定律〃……无论如何，对围棋局面静态评估的研究一旦产生突破，很有可能使得人类对围棋这项古老棋类运动本身产生更深刻的理解，同时也会极大地改变围棋弈棋计算机研究的现状截至目前，对围棋局面的静态评估效果还远远比不上国际象棋，一般只对处于棋局初期的局面有一定作用，而对当棋局进入激烈厮杀后的中后盘，尚未找到有效的静态评估方法下面马上就要提到，正是由于静态评估部分的缺陷，直接导致了围棋程序在〃局面动态评估〃部分采用了一套与国际象棋程序差异很大的策略另外值得注意的是，在上述局面静态评估的构建过程中，机器作为一个〃智能个体〃，最多参与到特征的〃权重〃设定，而对于更重要的〃应该使用什么样的特征〃以及〃根据什么方式对所有特征进行整合〃的问题则完全由人类专家负责可以说，特征自动提取〃一直是机器学习这个人工智能分支多年来的主要挑战之一后面还会再次提到这个问题基于〃预测分析〃的动态评估如果说对棋局盘面的静态评估好比人类棋手的〃感觉〃过程，那么动态评估就好比人类棋手的〃推理〃过程在静态评估中机器得益于人类专家的很多帮助，而动态评估的部分可是机器大显身手的地方了简单讲，〃动态评估〃试图对从当前盘面出发〃有可能〃出现的大量局面变化所导致的结果进行预判，并综合分析所有这些可能性，对当前盘面进行一次评估这也是人类在动态环境中做决策时经常使用的策略，也就是希望通过〃看得更远〃来提前发觉潜在的危险或机会经过高度优化的弈棋计算机每秒钟可以计算数以亿计的变化，即使是运行在普通个人电脑上的弈棋程序也经常可以做到每秒计算几十万种变化，这种高速运算能力极大地弥补了计算机在静态评估时的不足对于像国际象棋和围棋这种历史悠久的复杂棋类运动，只基于静态评估的计算机程序通常连入门级业余棋手都未必下得过，而一旦配备了动态评估能力之后，弈棋计算机却能达到普通棋手甚至人类世界冠军都无法达到的水平盘面动态评估可以说是计算机弈棋领域的研究重点所在，几十年来人工智能研究者和计算机科学研究者提出了许许多多的方法这里我们简单介绍一些共通的基本原理，以及围棋和国际象棋这两个最受关注的棋类的主流动态评估方法基于一套给定规则，任意给定的棋局盘面会有一个〃合法走法〃的集合，其中每个走法都会把棋局引向一个新盘面，而这个新盘面又会有自己的另一个合法走法集合，每个走法又对应一个新的盘面如果假设每个盘面都有种合法走法，那么从当前盘面走一步之后一共有b种可能〃到达〃的盘面，两步之后有b八2种可能盘面，三步之后有b八3种可能……如此展开下去，从最初的给定盘面经过d步之后可能到达bAd种不同的盘面，它们就是在〃未来d步内所有可能的局面变化〃我们看到，从给定盘面开始的局势变化的复杂度是随考虑的步数呈指数级增长的对于包括围棋和国际象棋的绝大多数复杂棋类运动而言，这意味着从原则上不存在准确计算盘面的最优结果的有效方法不过,这对于对局双方来说未必是个坏消息——虽然我无法计算最优解，对手也同样无法计算事实上一个游戏之所以成为游戏，恰恰就是因为对局双方都相信对手不具备完美决策的能力，而自己要做的只是比对手〃错得更少一些〃另一方面，对于弈棋计算机的设计者来说，〃不可能对局势变化的所有可能性进行有效计算〃意味着想做得比对手更好需要从原理上解决两个关键问题

（1）决定一个〃筛选策略〃，从所有从当前盘面出发有可能导致的变化中选择一部分作为〃我们实际考虑的那些局面变化〃；

（2）决定一个〃汇总策略〃，把所有实际考虑的变化的静态评估结果综合起来，对当前盘面的胜率完成评估无论是国际象棋、中国象棋、围棋、或者其他如西洋跳棋、黑白棋、五子棋，所有棋类程序的动态评估方法从根本上都符合由〃筛选策略〃和〃汇总策略〃组成的基本框架它们之间的区别仅在于使用的具体策略不同，以及由此产生的针对实现特定策略的优化手段的不同下面，我们就来看一下在最具代表性的国际象棋和围棋中，弈棋计算机分别使用的两套截然不同的动态评估策略吧〃指数级增长〃与EXPTIME-Complete问题〃指数级增长可算是大规模计算第一大〃拦路虎〃了在一个著名的传说中，国际象棋的发明者印度人塞萨（Sessa）向他的国王请求赏赐，他说，希望因为发明国际象棋棋盘的第一个格而得到一粒米，因为第二个格得到两粒米，因为第三格得到四粒米，如此在每后一个格都增加一倍的米量不识指数级增长威力的国王欣然答允，甚至还有些责怪塞萨要求太少，然而事后才发现整个国库的米都倒干净了仍然无法填满整个棋盘故事的结局是，国王恼羞之下偷偷派人把塞萨杀掉了学过等比数列的现代人按一按计算器就知道，国王因为这64个棋盘格子总共要支出2A64-1A19粒米，这据估计已经超出整个人类历史上产米量的总和！回到局势变化的复杂度问题上即使10八19这样的天文数字也〃只不过〃是一个从当前盘面出发，每次只考虑2种走法，持续64步之后的可能性空间的大小对于国际象棋和围棋这样的复杂棋类，从初始盘面出发穷尽所有变化的复杂度（也称穷举复杂度）更是大得难以想象信息论创始人克劳德香农在1950年第一个估计出国际象棋的穷举复杂度大概在10八120种变化左右，具体数字被后人称为〃香农教〃而围棋的穷举复杂度又远远超出国际象棋，达到了惊人的10人360作为比较，目前可观测宇宙中的原子总数据估计〃只有〃10人75个有人会问，为了分析当前盘面一定要穷举所有未来走势的可能性吗？有没有可能存在一个高效的算法可以在避免遍历呈指数级增长的可能性空间的同时仍然对当前盘面做出准确评估呢？答案是，对于国际象棋和围棋，我们可以从数学上证明，不仅仅是穷举复杂度，其局势变化的计算复杂度也必须随所考虑的步数呈指数级增长！对于任意一个给定的盘面，我们定义这个盘面的〃最优值〃为当博弈双方都下出〃完美走法〃的情况下导致的最终博弈结果如果一个盘面的最优值是〃黑棋胜〃，那就是说在黑棋自己不出错的情况下白棋无论如何努力都是必败的理论计算机科学家先后在1981年和1983年证明国际象棋和围棋都属于EXPTIME-Complete类问题，这意味着〃任何〃能正确计算盘面最优值的方法所花费的时间〃必然’随棋盘大小（亦或棋局的平均步数）呈指数级增长事实上大部分流行的〃双人零和〃棋类的计算复杂度都是指数级的有一些棋类如西洋跳棋、五子棋，它们的规模足够小，所以其初始盘面的最优值已经被计算出来了但是像国际象棋和围棋这样的复杂棋类，计算其初始盘面的最优值，以现在的硬件计算能力看来还遥遥无期局面动态评估〃激进〃与〃保守〃之间的平衡取舍主流的国际象棋程序往往采用一种比较〃保守〃的局势筛选策略，搭配一种比较〃激进〃的信息汇总策略而主流的围棋程序则正好相反，在局势筛选方面相当〃大胆〃，却对从这些局势变化收集来的信息的使用相当〃谨慎〃这主要是由于目前对这两种棋类的盘面静态评估的质量不同导致的对于国际象棋，已经找到了一种在〃很多情况〃下可以既快速又相对准确地对盘面进行静态评估的方法一—当遇到这类〃大致可以进行静态评估’的盘面时，这个静态评估方法有相当的可信度，而对于其他情况的盘面却完全不起作用由于拥有这样一个具有〃部分可靠性〃的静态评估，国际象棋程序的策略〃从概念上〃可以理解为是对从当前盘面出发的每一种可能的变化都不停向前展开，直到遇到一个可以大致静态评估的盘面或者超出了一个预定的〃最大展开步数〃为止这样的〃保守〃选择策略使得计算机对于一定阶段之内的所有变化都有了大致评估接下来计算机在〃假设〃这些评估是正确的前提下，计算按照完美下法哪一种变化是最优的根据硬件计算能力，计算机还会设定一个〃最小展开步数〃，即使一个变化在展开不到最小步数时就遇到了一个〃比较好评估的局面〃，系统依然会继续往前看，而不会就此停止这是为了最大限度地弥补〃对比较好评估的局面进行静态评估时依然有可能出错〃的缺陷在开发第一个人类大师级水平的计算机〃Be lie〃的过程中，人们发现弈棋计算机的最小展开步数越大，其棋力越强也就是说，原则上只要通过不断增强硬件的计算能力，国际象棋机器就可以通过看得越来越深而下得越来越好1997年的〃深蓝〃计算机在配备了400多块专门设计的硬件加速卡之后,获得了每秒钟展开并评估2亿次盘面的恐怖计算能力，历史上第一次代表机器战胜了人类国际象棋冠军在随后的十几年里，按照〃摩尔定律〃增长的计算机硬件能力变得愈加强大，计算机又先后多次战胜人类国际象棋冠军越来越多的人相信，机器在国际象棋领域早已超越了人类的弈棋能力然而，计算机能够战胜人类国际象棋冠军并不全靠超强的硬件计算能力，软件算法方面的持续改进同样必不可少，甚至影响更大比如上面提到，国际象棋系统在〃概念上〃穷尽了一定步数之内的所有变化但在真实的弈棋计算机中，一系列优化算法使得系统在不完全展开某些变化的同时也能够得到和完全展开一样（或类似）的效果这样节省下来的时间可以用于把已知变化〃看得更深〃，从而极大提高了系统在〃概念上〃的等效计算能力其中最经典的例子是由人工智能先驱约翰麦卡锡提出的/〃/剪枝法，它巧妙利用了〃国际象棋是双人零和游•戏〃的特点，以最优的方式避免所有不必要的变化展开零和游戏又称零和博弈（Zero-Sum Game）,是博弈论中的一个概念,指游戏（博弈）双方是竞争而不是合作关系,或者说是一种〃你死我活〃的状态例如两人对弈，一方赢，另一方必然是输，不存在〃双赢〃赢棋得1分，输棋减1分，两人得分之和就总是0,所以称为零和游戏根据计算机科学家唐纳德・克努特（Donald Knuth）的数学分析，在理想情况下，剪枝法仅需评估所有b Ad个变化中的b八（d/2）个,就可以保证得到和评估所有bAd个变化完全一样的结果换句话说，我们需要增加倍硬件计算能力才能使动态评估加深一步，而使用aB剪枝法则可以使动态评估轻松增加整整一倍的“思考深度*2!c（B剪枝法成型于20世纪60年代，是国际象棋弈棋的诸多优化算法里最经典的一种如今的国际象棋程序中还使用了大量其他优化方法，使得实际的动态评估过程远远比简单的〃枚举〃要高效得多，只是〃从概念上〃，它们从评估质量上等效（或接近）于一次对未来若干步内所有局势变化的穷举展开而已aB剪枝法的一个简单示例假设A盘面下我方行动，并试图最大化我方胜率；而B盘面下对手行动,并试图最小化我方胜率如果A代表当前盘面，而B代表我方走了某一步之后到达的新盘面现在假设已知B盘面下对手存在一种走法使得我方胜率至多有30%,同时已知A盘面下我方存在一种走法使得我方胜率至少有40%,那么我们已经可以确定无需再检查B盘面下其他未展开的变化了在层层展开的动态评估过程中这样的〃剪枝〃可以反复使用，从而大量减少需要实际评估的变化数量国际象棋的动态评估方法（或其变种）也广泛应用于大多数其他棋类的对弈系统，其中很多达到或超越了人类冠军的水平然而，这套思路却在围棋博弈中遭遇了滑铁卢截至目前，没有一个基于国际象棋的动态评估思路的围棋系统可以超过人类业余入门级水平很多人把这一失败归因于围棋比国际象棋更大的计算复杂度（这当然看起来是最明显的原因之一）但是，根据许峰雄博士在2007年发表的那篇名为Tracking GO〃（破解围棋）的文章，在拥有接近国际象棋的静态评估质量的前提下，我们完全可以在软件和硬件两方面进行一系列优化，使得国际象棋的动态评估方法在围棋中也达到类似的思考深度如果我们假设围棋大师们的智力并不显著高于国际象棋大师的话，这样的思考深度也许会使机器在围棋上再次战胜人类也就是说，对于当今的硬件能力，围棋的复杂度并不是不可逾越的鸿沟那么，到底是什么原因导致国际象棋的策略无法适用于围棋呢？笔者的观点是，〃穷举型〃策略〃〃3至今未在围棋中广泛应用，更大的障碍恐怕还是缺少一个像国际象棋那样能够对于〃一大类〃盘面进行〃大致准确的评估〃的方法前面介绍静态评估方法的部分已经提到了，目前围棋盘面的静态评估方法一般只在棋局前期黑白双方尚未〃短兵相接〃时有一定效果当棋局进入关键的中盘厮杀之后，如果仍然使用现有的静态评估方法，我们就会发现在达到硬件计算能力可承受的最大预判步数时，大部分棋局变化都处于不能〃大致准确评估〃的状态基于这些十分不〃靠谱〃的评估结果去考虑所谓〃完美〃走法，得到的结果自然也是不大靠谱的正是由于缺少〃靠谱〃的静态评估方法，目前所有顶级围棋程序转而采取一种比较〃谨慎〃的信息汇总策略在国际象棋中，如果一个盘面有两种走法，一个估计胜率30%,另一个估计胜率80%（如图⑶中盘面B所示），计算机会倾向于相信这些结果都是大概〃靠谱〃的，因此该盘面自身的胜率应该等于所有走法中的最优结果（我方盘面取最大值，对手盘面取最小值），因此认为盘面B的胜率是30%这是一种比较〃激进〃的信息汇总策略当发现了30%胜率的走法时，系统会完全丢弃80%胜率的走法所带来的信息，选择全部相信30%胜率的走法而在围棋程序中，计算机认为对每个盘面的直接静态评估结果都是不可靠的，但是相信〃对该盘面下所有走法的全部评估结果〃却整体上仍然对该盘面的胜率具有指向性现有围棋程序一般采用对所有评估结果进行加权平均的方式来体现这种指向性，其中〃权重〃基于对当前评估结果的可信度进行设定举例来说在图b中，假设对盘面B下两种走法所直接导致的盘面进行静态评估的结果胜率分别为30%和80%,而盘面C下的两种走法胜率分别为50%和40%因为这4个估计值可能都存在偏差，所以我们并不偏信其中任何一个；另一方面，在偏差没有系统性地倒向〃某一类盘面〃或〃某一类走法〃的前提下，我们有理由相信这4个盘面评估结果具有相同的可信度或〃不可信度〃，因此应该具有相同的权重所以在只知道这4个静态评估结果的情况下，我们认为盘面B的评估胜率是

0.5x30%+

0.5x80%=55%，盘面C的评估胜率是

0.5x50%+

0.5x40%=45%同时，这样做出的对B和C的判断自身仍然有可能存在偏差，所以在以盘面B和oC为基础再评估盘面A时也要考虑到这一点，因此A的评估结果同样是B和C的结果的再次加权平均

0.5x45%+

0.5x55%=50%o我们看到，这样根据等权重得到的对A的评估结果实际上是综合了所有当前已知信息之后给出的一个〃模棱两可〃的评估考虑到〃已知信息〃本质上的低可靠度，这也许就是我们在这种情况下〃应该〃得到的答案当然，这样一个仅仅基于4次静态评估的结果并不是计算机给出的最终答案对于一个给定盘面，我们考察的变化越多，获取的信息量也越大，因此对这个盘面的评估值也倾向于更可靠，从而这个评估值在参与加权平均时也理应获得更大的权重换句话说，我们根据对一个盘面〃深思熟虑〃的程度来量化对其评估结果的〃可信度〃，认为一个进行大量分析后得到的评估结果在可信度上优于分析较少的评估结果这就涉及到如何选择那些需要进一步深思熟虑的变化的问题相同情况下的不同信息汇总策略⑶为以国际象棋程序为代表的〃激进〃策略，取最大小值为汇总结果；b~d为以围棋程序为代表的〃保守〃策略，取加权平均值为汇总结果其中b对应评估初期等权重下的结果，如果其中30%的静态评估正确，则算法经过150次蒙特卡洛采样后会导向⑹所示结果，否则会导向d所示结果有意思的是，在采取较为谨慎的信息汇总策略的同时，围棋程序在局势变化的选择策略上却相当〃大胆〃如果说国际象棋程序希望考察在一定阶段内的所有变化，那么围棋程序却只通过对所有这些变化进行某种有策略的采样来进行评估，把更多的时间精力投入到那些〃看似〃更有希望的变化上这就是被称为蒙特卡洛树搜索的动态评估方法这种方法在〃从当前盘面出发所有有可能的局势变化〃组成的巨大可能性空间中进行反复采样通过巧妙设计的选择策略，配合前面所说的基于加权平均值的信息汇总策略，计算机会根据已有的采样结果调整新一轮采样所选择的变化，从而保证最优走法逐渐获得更多的选择机会，因此获得更大的权重这样的长期结果是，大量采样之后对当前盘面下所有走法的〃加权平均〃结果会逐渐逼近当前盘面的最优值！仍然回到图10的例子我们看到图b中基于4次静态评估的加权平均结果高于图⑶中按照传统国际象棋思路得到的结果，这主要是因为我们对当前胜率评估为30%的这个盘面〃不大信任〃导致的在接下来的动态评估采样中有两种可能1当前的30%的评估结果是正确的，在这种情况下蒙特卡洛树搜索算法对盘面B下的变化采样会更倾向于30%这个走法,因此B的评估值会逐渐下降到接近30%,而这又会导致B的评估值低于C,因此C获得更多采样机会，从而在对A的加权平均评估时获得比B更大的权重如图⑹所示，在150次采样之后,A的评估值接近C,而C的评估值接近40%——这和图⑶的评估结果一致（因为当初30%的静态评估结果恰好是正确的！）

（2）如果图（b）中30%的结果是错误的，假设机器经过对这个走法进一步考察（75次采样）后发现它的胜率其实应该是80%这种情况下,B的评估值会逐渐上升到80%,而这导致B相对于A的权重变高，因此A的评估值也随之上升，从而得到和前面不一样的最终评估结果总而言之，目前的主流围棋程序试图用一种系统性的方法去〃管理〃在评估过程中不可避免带来的〃不确定性〃截至目前，所有一流的围棋程序全部采用蒙特卡洛树搜索方法进行盘面动态评估〃〃4它们从基本〃思维模式〃和局面胜率评估的〃基本框架〃上继承了以国际象棋弈棋计算机为代表的传统方法；同时，采用蒙特卡洛采样思想来进一步管理知识中的〃不确定性〃，在选择策略上化保守为激进，在汇总策略上化激进为保守，在无法对变幻莫测的围棋盘面进行有效静态评估的情况下仍然达到了业余高级水平的棋力蒙特卡洛树搜索法使用蒙特卡罗方法估算TI值图/维基百科选取的随机点（n）越多，估计值离II的真值越近图/维基百科这种选择很大程度上跟现有围棋弈棋系统对盘面静态评估方法的整体舍弃有关前面提到，由于人们在设计具有一定通用性的围棋盘面静态评估函数的问题上长期止步不前，大概在2002年之后人们开始思考采用另一种完全不同的方式对盘面进行快速评估，这就是蒙特卡洛采样做为一种通用的计算方法，蒙特卡洛采样法的思想是当我们在求解一个确定但未知的值的时候，〃在概念上〃巧妙构造一个随机过程，使得这个随机过程的某个数字特征依概率收敛于我们要求的值，然后〃在实际操作中〃通过对该随机过程进行采样来对这个值进行统计估计比如说，一种计算圆周率〃〃的蒙特卡洛方法是，在一个二维坐标系中〃〃和〃〃对应的方形区域里随机选取若干个点，并判断每个点〃〃是否落在〃以原点为圆心半径为1的单位圆〃内（也即判定〃〃是否小于Do根据中心极限定理，这些随机点落在单位圆内的比例依大概率快速趋于〃〃所以我们选取的随机点数量越多，越有可能得到的一个离的真值更接近的估计相同的〃蒙特卡洛〃思想也可以用于围棋盘面评估前面提到了，每个围棋盘面都有一个〃最优值〃，对应于对弈双方都采用完美走法的情况下该盘面的最终结果对于围棋已经证明，计算这个最优值的时间至少随该盘面到终盘之间的步数呈指数级数增长（平均200步，每步平均增长200倍数量的可能盘面）既然从理论上无法得到最优值，有没有可能根据蒙特卡洛思想对整个可能性空间进行某种采样，然后通过统计估值的方法逼近这个最优值呢？人们对这个问题的思考在2006年终于取得了突破性进展，提出了一种称为蒙特卡洛树搜索的动态评估方法。