登录人民网通行证 &&&
人工智能首次排名世界职业围棋第一&中国选手柯洁退居次席
日13:43&&来源：
在占据世界职业围棋排名第一宝座两年后，中国围棋选手柯洁日前退居世界排名第二。根据世界职业围棋排名网站最新排名，超越柯洁的正是人工智能系统“阿尔法围棋”（ＡｌｐｈａＧＯ）。
这是有史以来第一次，人工智能在“人类智慧的最后高地”围棋领域超越人类选手，占据排行榜首位。柯洁最近比赛连败２场，使“阿尔法围棋”能以３６１２分升至世界排名第一。
今年三月在围棋人机大战中战胜韩国棋手李世石后，“阿尔法围棋”如今已家喻户晓，大家似乎把它看做了一个现实存在的“人”，但能否将它列入世界职业围棋排名还有争议。记者发现，法国“疯石”、日本“ｚｅｎ”等其他著名围棋程序并没有进入排行榜，而这些程序也曾和不少顶尖棋手交过手。
１９９７年，ＩＢＭ的超级计算机“深蓝”战胜卡斯帕罗夫，更多使用了硬件加速、暴力计算等计算机的特长。但“阿尔法围棋”不同，它应用了神经网络、深度学习、蒙特卡洛树搜索法等人工智能新技术，在对弈中还可以联网获得外界的棋局资料信息，这使它面对人类棋手具有“不对称优势”。
会深度学习的“阿尔法围棋”不仅掌握全球各种对局，近两年内，它还自己“左右互搏”３０００多万局，不断寻找“碾压”人类智商的各种棋路，棋力提高之快令人叹为观止。战胜李世石后，“阿尔法围棋”仍在不断学习与提高，因此时间拖得越久，人类棋手要战胜它就越困难。
“阿尔法围棋”登场后，围绕“人类和机器谁更聪明”“人工智能未来是否会危害人类”等问题的争议，甚至盖过了对围棋人机大战本身的关注。（记者杨骏）
(责编：覃博雅、常红)
四问美国操纵南海仲裁案：何来资格说三道四
美国早已摆出一副要借仲裁案排演一出“好莱坞大戏”的架势，其中的意图，可谓“司马昭之心路人皆知”。用裹着所谓“正义”和法律外衣的谎言，把自己的规则强加到其他地区，甚至凌驾于国际法之上，是美国推行霸权主义的制胜法宝，也是美国对国际法“利则用、不利则弃”的最佳演绎。但试问，美国的这种做法经得起历史的推敲吗？
足不出户带您遍览中国50个世界遗产项目
7月15日，在土耳其伊斯坦布尔举行的联合国教科文组织世界遗产委员会第40届会议上，中国世界文化遗产提名项目“左江花山岩画文化景观”入选世界遗产名录；在7月17日的会议上，中国申遗项目――湖北神农架通过了世界遗产大会的终审，成功列入世界自然遗产名录。至此，中国的世界遗产数量增加至50项，仅次于意大利，位列世界第二。78被浏览9,805分享邀请回答5添加评论分享收藏感谢收起/chncwang/foolgo74 条评论分享收藏感谢收起阅读正文 :
AlphaGo Zero横空出世：除了下围棋人工智能还可以干什么？
编辑：吴海艳
日消息 还记得那个打败人类围棋选手的AlphaGo吗？10月19日，谷歌旗下公司Deepmind在《自然》杂志发表文章称，最终版围棋程序AlphaGo Zero已经以100:0的战绩击败了原来的AlphaGo。
从一个对围棋没有任何知识的神经网络开始，AlphaGo Zero通过与搜索算法的结合自己学会下围棋，并依靠新算法和大数据击败熟知人类棋谱的顶级围棋高手AlphaGo。超过人脑的计算能力和超过人力的控制能力再一次惊艳了人类，同时也将人工智能这个热门而又备受争议的话题再次推向了风口浪尖。除了围棋，人工智能还可以投入到哪些行业应用中去？在陷入瓶颈发展的行业，人工智能又能够带来什么样的改变？
事实上，象征着新风口的人工智能早已渗透到了医疗、金融服务、物流等各个领域。医疗方面，借助大数据的人工智能可以收集到的用户健康数据，实现个人定制化服务。金融服务方面，人工智能与金融科技（FinTech）相结合，发展&机器人理财&、&智能理财&。物流方面，无人化技术在很大程度上帮助人类降低成本、提升效率，创造出了新的产业价值。
那么手机行业呢？在智能手机陷入瓶颈发展的当下，被视为行业大风口的人工智能，究竟可以带给手机行业哪些新突破？
作为科技发展的未来潮流，人工智能可以赋能手机，让手机这个原本冰冷的机器可以看懂主人的智能学习逻辑，甚至可以具备人类的学习思维，懂人之所想，做人之可为。当用户用手机摄像头对着某一事物时，手机便可以智能识别出这一事物的名称，甚至还可以对用户做出相应的回应或反馈。
在秋季新品发布会上，苹果发布了三款新机iPhone8、iPhone8 Plus、iPhone X。这三款新机均搭载了双核心A11仿生电子芯片，得益于双核架构的&神经网络引擎(neural engine)&的加入，手机变得更加聪明。
不同于苹果，三星则发布了助手Bixby2.0，不仅能够让智能手机进行交流、推荐和提醒，甚至可可以让智能手机识别复杂语音、自主学习和适应用户的需求。
国内手机领导品牌华为则发布了一款搭载了AI麒麟970芯片的旗舰新机Mate10，因为有了NPU(神经网络单元)专用硬件处理单元的助力，可以在图像处理、拍照翻译、一键解锁等层面实现智能加速。
同样是发力人工智能，ivvi手机就完全不同了。依托于母公司超多维，ivvi手机将发力点放在了计算视觉领域，试图以计算视觉技术中的人脸别别、多维成像等方向为着手点，通过AI、AR、等热门技术的融合，为消费者打造全新的娱乐体验。
在未来，ivvi手机将加速开发和布局以深度学习、图形图像计算、模糊逻辑计算等核心技术为支撑，具有创新性的个人消费类市场互联网应用及行业垂直领域的专业应用，通过发力AI、AR、智能3D等新技术，为单一化的智能手机发展提供新的方向。
精彩科技视频
科技产品报价
厂商投稿 产品评测/网站合作/010-84383 友情链接：029- 京公网安备55号
Copyright@
驱动中国 All Rights Reserved电脑围棋中的人工智能技术
电脑围棋中的人工智能技术
本文通过研究几个最出色的电脑围棋程序，从认知科学的角度介绍了电脑围棋，并特别针对电脑围棋编程人员（或有意投身
于此的程序员）揭示围棋作为一个认知科学研究领域的日益增长的重要性。对手谈，Go4++，Many Faces of Go，Go
和Explorer几个目前最优秀的电脑围棋程序，我们概括了它们用到的人工智能技术，必须面对的关键性挑战和博弈树搜索中牵涉的问题，以此揭示为什么计
算机国际象棋技术不能被很好的移植到围棋领域。
1． 挑战围棋的程序
作为正规游戏之一的围棋领域，过去即便是应付一般的人类棋手计算机也难以有所作为。几个一年一度的电脑围棋赛事，如FOST杯赛为第一名提供2，000，000日元奖金，台湾的应氏基金为第一个能在分先七番棋中击败顶尖职业棋手的围棋程序许诺40万美元的奖金。
早以围棋为对象把电脑围棋纳入研究工作是在1962年，尽管第一次由程序下一盘完整的棋是发生在1968年（Zobrist，1970）。随着电脑围棋赛
事的举行和第一个商业程序的发放，电脑围棋作为一个领域于80年代被正式创立，并在90年代变得兴旺起来。目前活跃在电脑围棋竞赛中的顶尖程序有
Explorer，Go Intellect，Go4++，手谈和The Many Faces of
Go，它们的水平大致在4-8级之间。
2． 围棋中的博弈树搜索
二人完美信息博弈中典型的人工智能方法是搜索博弈树以决定走哪一步。标准博弈树搜索由四部分组成：1．状态表示，2．候选走法产生，3．确定目标状态，以及4．一个确定相对优势状态的静态评估函数。有效的博弈树剪枝方法（比如α-β）增强了程序的表现。
博弈树这条途径很成功，如我们在国际象棋程序中所看到的，基于典型的完全广度α-β剪枝博弈树搜索的程序甚至击败了世界冠军。这一节我们从透视电脑围棋的角度检查博弈树搜索的四个构件。
2.1 状态表示
完全信息的角度看，围棋盘面有19X19的3次方格，每个交叉点要么空要么被黑子或白子占据。状态空间的大小（例如可能的位置数）是3的361次方（或
10的172次方），相比之下国际象棋大致为10的50次方而Othello棋为10的30次方（Allis，1994）。另外，博弈树的大小（例如可能
的博弈数）在10的575次方和10的620次方之间，对比国际象棋的10的123次方和Othello棋的10的55次方（Allis，1994）。
于空间的组合尺寸，用19X19格的形式严格表示状态空间对人或机器来说都层次太低而不能有效使用。接下来的层面的描述是把正交的邻接棋子组成串（或
链）。所有的程序把串搜集到更大的单元，然而没有通用的处理方法——即便是对专业棋手来说——把串组合到更大的单元中。依靠他们的围棋理论，程序员开发了
他们自己的启发式，当串有效的连接在一起时用做评估之用（叫做模糊组或块）。
另外，恰当层次的表示能改变对运行时子任务的依赖，例如，战术分析，死活分析，或实地评估。
手在禁止自杀和同型反复（劫）的规则限制下轮流把棋子投放在空的交叉点（包括角和边）。象国际象棋一样，围棋在给定位置的上下文中只有所有合法走法中的一
部分是有效的。围棋的平均分枝因子是很大的，大约是国际象棋的六倍（200对35，Burmeister &
Wiles，1995）。
注意这个分枝因子在全盘中的考虑。而在某些情形下只有局部的考虑是重要的。例如，直接目标搜索被用来判断通常只有一两种可能走法却可以多达60手深度的征子。
实际的走子是个复杂的问题：参见3.4部分。
2.3 目标状态
棋的最终目标是获得比对手更多的实地。有两种方法用来争取实地：建棋子城墙围空以及用棋子包围并吃掉敌方的棋串。实际上很难确定目标状态，因为实地的获得
是靠慢慢积累起来的（不象国际象棋那样将军的最终的目标是突然死亡并且集中在一个子上）。由于在接近终局前很难精确地计算实地，故启发式估计用的较多。这
样的启发方式通常要归并组件和指示领地安全潜力的（例如死活组和影响）次要目标（例如国际象棋里的材料优势）。
当对局双方依次弃权时结束。棋手通
常在没有走法能增加所得和/或无论怎么走都会减少所得时选择弃权。实际上，要确定对局结束（即何时弃权）是相当困难的。人们下棋，计算结果时如果遇到有关
死活的争执要通过继续下直到最终结果出现。在电脑围棋比赛中，如果程序出现算法不能解决的得分争执，计分就由组织比赛的人员来做。
2.4 评估函数
判断盘面的形势优劣时棋块的死活是个重要的考虑点。死活判断是很费时间的，并且是典型的通过战术搜索（参见3.5部分）或死活搜索（参见3.6部分）来获
得的。有意思的是，另一评估棋块死活的复杂之处在于它可能需要评估全盘的形势：如果要一个棋块在劫争中是可活的（即它必须赢得打劫来使自己活下来），就必
须估算所有和对手相比用来决定棋块死活的劫材的数量和大小。如果出现双重或三重劫的形势，打劫分析会变得更复杂。
评估的结果有时不确定，因为明确的死活定义在受限的战术搜索里也许是不可能的，即一个绝对的死活回答可能超出了战术或死活搜索的范围。
从 复杂的类型分析看，由一个绝对位置来确定赢家是P空间难题（Lichtenstein &
Sipser，1980），决定一个棋手能否左右输赢需指数时间来完成（Robson，1983），由此也就不奇怪要用到启发式了。这些理论结果显示不存
在从一个绝对局势出发决定领地结果的多项式时间算法。
3． 参赛程序里的博弈树搜索和人工智能技术
当前活跃在各电脑围棋赛事里的程序有 Martin
Muller（1995）的Explorer（EX），陈恳（陈，；1992）的Go
Intellect（GI），Michael Reiss 的Go4++（Go4），陈志行的HandTalk（HT）以及David
Fotland 的Many Faces of
Go（MFG）。针对第2节讨论的博弈树搜索和围棋专用的人工智能技术：战术搜索，死活搜索和势函数，我们报告这些程序的细节。
3.1 位置表示
所有的程序都有子、串、块的表示，确认串属于某个组的典型方式是采用基于模式的启发来确定串与串之间的关联性。敌方（或块）表示也被用在EX和GI
中，启发式用来确定敌方的影响（GI）和领地区域（EX）。
盘面（例如棋块、敌方）表示的对象属性包括它们的死活状态（也指安全性或生命力）、实地数、眼数和势。某些情况下这些属性值由战术搜索决定。
MFG的表示方式中一些组件由评估函数控制（例如块、联接、眼、实地和势）。Go4的盘面只是简单的由评估函数（例如块、眼、安全性、实地）来表示。
3.2 候选走法
通常，由模式或更常见的是由基于规则的专家系统产生候选走法。走子产生过程最后是通过（线性的或加权求和的）相加棋盘上所有点的参考值为合适的走法给出一个分值。全盘评估一般选最高得分点作为下一手的落子点。
同程序由全局水平变量估值得出的候选走法数也有所不同：GI（陈，1997）有12手，MFG有10手，而Go4至少有50手。程序变量保持的规则
数：EX大约100，MFG大约200。GI含有约20个走子算法，它们或者基于模式库，或者基于面向目标的搜索，或者基于启发式规则（可能含有大量的规
模式通常既包含低级信息也包含高级信息。低级信息与黑白子的位置有关，那些点必须是空着的，已经被子占据的点不在此列。高级信息则是关于气
的数量、安全性、眼位和领地的信息。模式匹配不仅与子的配置匹配，而且跟包含在子或串里的任何高级需求有关。大量的模式匹配计算是很耗时的，并且由于棋盘
上的对称性而变得更复杂。这已经导致了发展特殊算法来克服与模式匹配有关的问题（比如MFG的哈希函数，EX的串匹配）。
知识以不同的方式组合到
程序当中：一些程序几乎完全依据第一原则工作，另一些根据存储的模式匹配当前位置。不同的程序其模式数量相差很大：Go4约有15个；MFG大约2000
个；而EX则在3000个左右。有些程序也包含开放的走法模式数据库（定式）（例如，MFG含有约45，000个定式模式）。
数情况下，大量的实地比起少量的实地加相应的外势更合乎需要。尽管有时也存在着实地和外势间地转化（特别是在布局和中盘阶段）。然而，虽然实地的启发式评
估是可能的，实地依然不总是形势优劣最好的指示明灯。在对局的早期阶段，占有大量的实地可能表明一种过于集中的形势，从实地安全的角度看，这样的形对对局
的后面阶段或许是有害的。开局造就最大可能的势而不是实地通常导致局末对更多实地的追求。外势是可能用来确定形势优劣的子目标的一个例子。
定形势优劣的大量子目标的相对优先度在电脑围棋中看来没有一致性可言。典型的块和实地的死活状态（安全性）被包含在目标和子目标中。在手谈中，战术手段是
重点，而MFG集中在联接性、眼和块的生命力。Go4则好像完全贯注于联接性上，几乎任何东西都是从联接概率图上派生（直接或间接地）出来。
3.4 评估过程
估围棋的形势是个很慢的过程（例如，比起国际象棋程序的每秒10,000-100,000次评估，MFG是以低于每秒10次的速度完成对整局棋不超过
10,000种全盘形势的评估）。由于比赛时间的限制，程序执行的全局评估数通常是有限的（例如，MFG在选择下一步时全局的评估数不超过100）。
的50种候选走法中每一个都通过一个六步的过程来评估：1.启用一个联接概率图。对于盘面上的每一个黑子和白子，计算它与32个（实际的或假定的）友好点
的联接概率（要处理大量的数据）。确定联接性还要用到战术搜索；2.棋块由联接图和战术搜索来确定；3.眼位（利用模式）由联接性和棋块数据确定；4.眼
位的数量确定了棋块的安全性；5.每个子的安全性按联接概率图的比率辐射并在所有棋子上相加；6.黑白领地由辐射值估计。黑白领地的差别作为一个给定走法
的评估结果返回。
MFG的评估是个多步过程，并且在很大程度上依赖于战术搜索。战术搜索检查所有少于四口和一部分有四口气的串以确定是不是死串。
战术搜索也被用来鉴别联接性和眼位。在这一环节，串组成了棋块。棋块的生命力由基于死活的考虑（例如，联接、眼位等）决定，并且用来确定黑白子在盘面每个
点（在-50至+50的范围之间）行使控制的总量统计。在总和每个点的值的基础上确定领地，给出最终的估计值。多达6轮的静态搜索可以被执行，有时用一个
特殊的模式集找出能使形势稳定下来的局部走法。
GI的评估用在做全局搜索时。如果所有候选走法中有一种走法的得分要明显高于其它的走法，它就被选
为要走的下一步。如果候选走法中有些走法的得分大致相等，靠评估带来方便的全局搜索决定选择走哪一步。评估时，敌子的安全性是为盘上每个点指定一个在
-64到+64之间的黑白控度的基础，所有点的分值加起来返回一个评估值。全局搜索检查的步数不多于6到7步，搜索的深度不超过6层。
3.5 战术搜索
术搜索是有选择的、面向目标的搜索，并且为一大堆目的而使用，包括确定串是死是活（Go4，MFG，EX，GI）、联接是安全的还是可被切断的
（Go4，MFG）、是否可以形成眼位（MFG）、产生候选走法（GI）和确定棋块的死活（EX）。就是在全局的水平，战术搜索也要用来做棋步产生和评
估。战术评估和全盘评估有区别，这跟搜索的目标（例如，一个串的气的数量）有关。由于时间上的制约，战术搜索通常在节点数、枝因子和层的深度上受到限制。
因此，尽管象死活这类的问题通常被认为是战术性的，棋子却可以在战略上就死去了，即使它们可能不能通过战术手段被抓获。由此，从围棋评估的方方面面看，战
术搜索只是一种启发式装备而已。
MFG提供了一个战术搜索操作的很好的例证（通过“战术家”）：每个有三口或更少的气的串和许多有四口气的串被
“战术家”检查过。每个串检查两次，一次白先走一次黑先走。“战术家”决定一个串是否被抓（比如，即使它先走也不能活）、被威胁（比如，如果它先走则活，
后走则死），或者是牢固的。“战术家”依靠简单的启发式（例如，气数和联接性）。
“战术家”有两个分离的走子器；一个执行攻击走法，一个执行防卫
走法。走子器建议的走法按一些规则分类，这些规则包括二次气（气的气）、切点和简单的眼形。一旦分类，根据依赖走法分类的质量的搜索的表现，一种α-β深
度优先搜索被派上用场。走子和分类解释了多数时间依靠战术搜索的原因。
战术搜索直接针对目标并被限制一个最大节点数。抓子时这个限制是大约
100，然而当只有一步可走时就不考虑这个限制。采用这种方式，可以毫不费力地确定征子的胜方。根据第一层走子产生赋予走法的分值，一次搜索的节点数分配
到树枝中，因此不同的树枝可能在不同的深度结束。每一成功的层的枝因子被“战术家”逐步强化；枝因子从第一层5降到第五层的1或2。
对局过程中，MFG作大约100,000-150,000次战术搜索，以每秒2,000-2,500个节点的速度遍历1.5-2百万个节点。平均起来每次战术搜索访问约10-20个节点，尽管由于一些搜索因节点限制而终止，许多搜索访问过节点数要少于5个。
3.6 死活搜索
不是所有的程序都做明确的死活分析，很多程序对此使用了战术搜索。MFG用与它的战术搜索过程类似的方式作死活分析，除了它是在块上作死活分析而不是分析串。
一个静态死活评估器在多步过程中确定每个块的死活状态，而没有以从简单的结构中进一步产生复杂结构的方式向前搜索。静态死活评估器使用“战术家”并且为棋块中的每个合适的串至少调用两次。
活搜索是直接面向目标的（例如，拯救或杀死一个棋块）。如果在一个特定点没有获得搜索目标，合适走法由死活搜索引擎自身的走法器产生，并继续搜索。为了在
一次死活搜索期间确定目标是否已经达到，静态死活评估器在每个点被调用。死活搜索引擎使用深度优先α、β搜索，每一个特定的枝的搜索深度由启发式决定。搜
索树的大小是强制性的，通常可以达到7层的深度和20个节点的大小。死活搜索是很慢的，整棵树要装到缓存里以减少花在重复搜索上的开销。死活搜索的缓慢也
意味着它不会被用在全盘评估中。
3.7 势函数
势是一种围棋概念，它表明了每一方棋子对空点的最大可能的控制潜力。通过确保开局时子力投放不过于集中，棋手在后面的对局中将取得最大限度获得领地的机会。
通过势函数建立可计算模型（Zobrist，1969；Ryder，1971；Chen，1989）。通常，子力以盘上每个点的辐射影响值的和（黑白子辐
射正负相反的值）对周边的点施加辐射影响（MFG的黑白子的势是分离的）。子力辐射按距离函数递减：GI是2的距离次方分之一，MFG是距离分之一。但过
于依赖势函数的程序表现不佳（EX和Go4不再使用势函数，尽管Go4的辐射函数很象一个势函数，EX采取另一些措施，象同色点或可联接点的距离）。
应用势的启发包括确定联接性和敌子（GI），以及确定领地（MFG）。MFG的块势初始值依赖于块的强度等，强壮的块比弱块或将死的块辐射更大的影响。这也意味着死块辐射负影响等，因为它对敌方有利。在MFG和GI中势都没有通过子辐射；MFG也没有通过敌链辐射影响。
前的围棋程序都使用了一定量的“知识”。由于建立在设计者下棋成功经验的启发之上，每个程序都可被看作一种（可能是含蓄的）围棋理论的一次以经验为依据的
实验。围棋理论成立的关键要靠数据结构的选择，因为它们决定了编码不同类型知识的难易和应用这些知识的计算开销。随着程序员同时在围棋和电脑围棋方面获得
技能，程序会有发展（例如，在过去的十五年中随着 Fotland
的棋力从15级发展到2段，MFG也增长了棋力并且代码长度增加到目前的4万行）。程序的性能由它最弱的部件决定，而向程序增加新知识的难易是提高程序性
能的重要部分。
由此可见，电脑围棋领域在关于怎样构筑一个围棋程序或者指配不同围棋知识的优先性（例如，Go4注重联接性而MFG注重死活）方面
还没有一致性可言。必须提到的一点是：关于人类是怎样下围棋的至今也没个一致的说法，这是目前认知科学研究的一个课题（见Saito
Yoshikawa，1977，作为回顾）。这个领域的任何进展都会对围棋理论有个直接的促进，并可能导致电脑围棋程序算法的改进。
本文对目前比
较成功的几个程序作了比较。通过这项工作，我们在博弈树搜索的框架内分析了围棋，并通过对示例电脑围棋编程的观察把有关的问题暴露出来。这种困难在电脑围
棋领域是常识，但在更为广泛的人工智能范畴却很少被人们认识和接受。围棋全盘评估需要确定棋块的死活状态，不管是通过死活搜索还是战术搜索，评估是非常消
耗计算资源的。缺乏快速有效的评估函数是电脑围棋遭遇的一个基本问题，并且和巨大的树枝因素、用户和电脑比赛的实时需求（一般来说，相对于国际象棋的每秒
180步围棋每秒只有24步）等搅和在一起。因此，计算机国际象棋通常要用到的完全广度博弈树搜索在电脑围棋里是行不通的。
除了所列出的围棋领域
固有的问题外，本文还探讨当前的程序怎样地处理这些问题，由此为未来的围棋程序员提供一个跳板。请注意电脑围棋是个商业的领域，程序本身（不是学术论文）
就是它的主要产品。跟其它的参考不同的是，这里报告的细节都已经通过个人交流征询了（慷慨贡献自己的知识的）程序作者本人的意见，并且有相关的电脑围棋邮
件列表&[email]computer-go@anu.edu.au[/email]&和FTP站点&[url]ftp:
//igs.nuri.net/Go/comp/[/url]&的信息为依据。
电脑围棋的挑战性在于要扩展当前的围棋理论或发展新理论——
特别是与评估有关的，针对实时限制设计合适的数据结构和算法，解决知识瓶颈。目前还没有一个有力的程序使用学习技术，尽管有过几次这样的尝试
（如，Pell，1991；Schraudolph, Dayan & Sejnowski，1994；Donnelly, Corr
Crookes，1994）。回顾这些程序已经超出了本文的范围，但我们推测这些程序也没有成功，因为它们的设计者的含蓄的围棋理论缺乏对围棋复杂性的必
要理解。怎样把学习能力赋予现有的程序（或者它们暗示的围棋理论）是个等待解决的问题。
电脑棋手的“思维”
1. 博弈与计算科学
现在的世界上有各种各样电脑棋手。能够在普通计算机上运行的国际象棋程序已经达到了职业棋手的水平，就黑白棋而言，人类已经不是计算机的对手。但是就围棋而言，计算机与人进行抗衡的路还很遥远。
如果电脑棋手战胜了人类棋手，那么是否就可以说它和人一样具有智能？这个问题，将放到最后进行讨论。我首先将向大家展示，电脑棋手是如何下棋的。
2. 择优而行
电脑棋手下棋的原理，简单地说，就是选出它所认为最有利的下法。
|...4 3 -1
们来看上面这个图。假设在某一个时刻，摆在电脑棋手面前的是一个局面A。当然，电脑棋手懂下棋的规则，于是它发现一共有三种符合规则的下法（为了画图方
便，所以少了一些，事实上，在国际象棋和中国象棋中，符合规则的下法一般为数十种，围棋则多达两三百种）。这三种下法将分别形成局面B、C、D。现在，我
们假设电脑棋手能够判断局面的优劣，为每一个局面都计算一个分数，比如局面B的得分为4，局面C的得分为3，局面D的得分为-1。当然，我们可以作一些规
定：分数越高局面越好，分数越低局面越差；当分数为0时表示双方均势，则正分表示电脑棋手方优势，负分表示电脑棋手处于劣势。于是，电脑棋手就选择对它最
有利的下法，即第一种下法，最后形成了局面B。此时，在这种情况下，作为一个副产品，那就是局面A被认为是4分，因为后面两种下法对计算机而言是没有意义
的，所以B的分数也就是A的分数。
接下来的问题是计算机如何做到为每一个局面评出一个得分。这在下棋中被称为形势判断。
现在以中国象
棋或国际象棋为例（这个问题对围棋而言是很复杂的），最简单的形势判断就是评价以下棋局中双方的子力对比。例如，在中国象棋中，每个车记8分，每个马或炮
记3.5分，每个兵、士、相都记1分，将帅无价，姑且记1000分，那么很容易就可以计算出双方的兵力，两者的差就形成了一种最简单的形势判断。当然，这
种形势判断是十分粗糙的。
稍稍复杂一些的形势判断，除了考虑子力优势之外，还要考虑局面优势。比如一方的马处于十分积极的盘河位置，而另一方的
马则还留在原位没有跳出，两者之间显然存在着差距。这时，需要将这些差距折算成分数，加到形势判断中去。在计算机中，这是最通俗、或者说最常用的形势判断
一般说，对局面的形势判断可以用一个数学式子计算得出。举一个简单的例子：
设在形势中一共考虑n个因素（或特征）。用xi表示
第i个因素是否在当前的局面G中出现，如果出现则取1，没有出现则取0，比如第6个因素是指一方的第1个车，那么当这个车还存在时，x6=1，这个车不存
在时，x6=0。用wi表示第i个因素在形势判断中所计算的分数，这被称为权重，例如一个车的分数为8，则w6=8。那么对局面G的形势判断为：
| f(G)=W1*X1+W2*X2+...Wi*Xi=S(i=1 to i)WiXi
符号S被称为累加符，如果读者以前不知道这个符号，只要看着上面的等式，将它想像为在for循环中套了一个加法的命令，就很容易理解了。这是为了书写方便而引入的符号。
3. 搜索的魔术
果形势判断十分准确，故事就简单地结束了。可惜的是，问题没有这么简单。我们（无论是计算机还是人类）永远不可能得到一个准确的形势判断。这是因为，形势
判断是静态的，而棋局是动态的，要从静态的特征中获取动态的信息，这并非易事。当然，如果需要做到万无一失，那么在形势判断中，必须包括所有可以想到的对
局面产生影响的因素，但这时，因素的数量是一个天文数字，我们既不可能对所有的因素都赋一个权重，也不可能在有限的时间内计算出局面的形势判断。
我们回过来看，人在下棋时也不能一眼就对静态的局势作出准确的判断，笼统地说，他们往往需要向后面计算几步，看看在走了几步棋之后，局面的形势如何。这被称为“多算胜”，也就是说，谁看得越深远，谁就可以获胜。这个思维方式立刻被用到了计算机上。
3.1 最小最大树
以第2部分中出现过的图为例，假设向后再多考虑一步，得到下图
|...........A
|........./ | /
|........B C D
|......./ | / / | /
|.......E F G H I J
|.......5 3 2.5 2 -2 10
是一棵树。从图中看到，假设在三个局面B、C、D下，都恰好有两种符合规则的下法，可以形成局面E、F、G、H、I、J，而这些局面的形势判断已经得到
了。电脑棋手的任务是利用这些已知条件，选择局面B、C、D的中对它最有利的一个局面。我们可以发现，局面J的得分最大，那么是不是应该选择局面D，以便
形成对电脑棋手最有利的局面J呢？
假设电脑棋手的对手（可能是人，也可能是一个计算机程序，现在为了便于说明问题时不产生混淆，假设对手是人）
面对的是局面B，那么他一定会选择对自己最有利的下法。由于是零和博弈，对人最有利的下法就是计算机最不利的下法，那么在E和F之中，他会选择F。这时，
如果电脑棋手选择局面B，那么对方就会选择F，最后电脑棋手得到的结果是3，也就是说，B的形势判断结果应该为3。同样道理，如果人处于C中，他会选择
H，于是f(C) = f(H) = 2。同理，f(D) = -2。最后，发现是B的得分最高，因此电脑会选择B，此时f(A) =
f(B) = 3。
按前面的猜测，如果因为f(J)=10而计算机选择了局面D，那么对手就会选择I，最后计算机得到了最差的结果-2。
从这里我们
可以看出，在电脑棋手下棋的局面中，它总是选择下一个层次中由该局面衍生出的局面中得分最高的，而在对手下棋的局面中，它总是选择下一个层次中由该局面衍
生出的局面中得分最低的。用数据结构中的术语，假设对于某一个局面，已经将在几步棋之后的所有可能形成的局面的得分都计算了出来，那么从这棵树的最底层一
层层向上推，在对手下棋的层次中，每一个结点取其子结点的最小值，在电脑下棋的层次中，每一个结点取子结点的最大值。这就被称为最小最大树。
后，问题转化为对某一局面下衍生出的最小最大树的遍历。这种遍历用一个深度优先搜索就很可以处理了。在搜索的过程中，当前路径上的每一个结点上都保存着搜
索到目前为止的当前最优值。搜索用一个递归函数实现，该函数的功能是计算某个结点的最优值。每当一个结点得到子结点的返回值时，就从当前最优值和返回值中
选取一个更优的值作为当前最优值。当一个结点的子结点都搜索完毕之时，其当前最优值就是该结点的实际最优值，也就是这个结点的得分，这时，将这个值返回其
父结点。下面给出最大最小搜索的伪码：
…………………………………………
需要注意的是，在搜索过程中，我们不仅仅关心每个局面的得分是
多少，我们同样关心是如何得到这个得分的，也就是说，在这个局面下，电脑棋手或是对手应选择什么下法，才能得到这个得分。这个功能没有包括在上面的伪码
中。不过只要读者理解了上面的伪码，就一定能够自己将相应的代码加进去。
进一步，由于是零和博弈，假设从对手角度考虑形式判断函数为g，则有g =
-f。这样，在深度优先搜索中，电脑下棋的结点时考虑取子结点中f最大的，而对手下棋的结点中取f最小的，也就是g最大的，这样两者就完全统一成取最大
值。而在返回值时，只需要把符号改变一下，就可以把f和g值相互转换了。例如在前面的例子中，当位于对手下棋的局面B时，有g(E)=
-f(E)= -5，g(F)= -f(F)= -3，g(B)取最大值，则g(B)=
-3，随后返回到电脑下棋的局面A时，改变符号，使用f(B)= -g(B)=
3，在A点取f的最大值。这被称为负最大搜索，它比最小最大搜索来得简单。下面给出负最大搜索的伪码，相信有一定基础的读者看了之后就会明白。
……………………………………………………..
3.2 a-b裁剪(alphabeta裁剪)
的问题又出现了，假设我们考虑的是中国象棋或国际象棋，现在希望每次都可以搜索到5个回合之后。5个回合就相当于双方一共下10步棋，每一次都有几十种下
法可以选择，姑且算每次有30种选择，于是最小最大树的叶结点个数总共多达30^10，这是一个非常庞大的数字。搜索的结点越多就相当于在搜索中花费的时
间更多，我们总不能忍受电脑棋手一年才下一步棋。减少搜索结点的最简单的方法是减小搜索深度，但这大大影响了电脑棋手的棋力。是否有办法在不减小搜索深度
的前提下将需要搜索的结点减小一些？
|......A 3
|......B 2
|..../ | /
|....C D E
|....4 ? ?
设上图是在深度优先搜索过程中的一个局部，用fnow表示搜索到当前状态结点的当前最优值。B是电脑下棋的结点，A和C则是对手下棋的结点，当前正处于结
点C所属的子树已经搜索完毕，从结点C返回至结点B的时刻，方框中的结点表示搜索到目前为止的当前最优值，即
fnow(A)=3，fnow(B)=2，fnow(C)=f(C)=4。我们知道，由于B是电脑下棋的结点，因此当f(C)&fnow(B)时，
应当更新结点B的当前最优值，即令fnow (B)=f
(C)=4。此时，虽然结点E、F尚未搜索，但由于结点B处为电脑下棋，应取子结点中最大值，其当前最优值随着搜索的进行只会增加而不会减小，因此有
f(B)&=fnow(B)=4。而结点A是对手下棋，应取子结点的最小值，而f(B)&=4&3=fnow(A)，其当前值必然小于
结点B的实际最优值，因此对手处于结点A时必然不会选择到结点B的下法，也就是说，结点B不会对结点A的最优值产生影响。因此，不必再进行结点E和结点F
的搜索，结点B就可以直接返回其父结点A。
在搜索过程中，电脑下棋结点的当前最优值被称为a值（即前面的例子中局面B的最大值），对手下棋结点
的当前最优值被称为b值（即例子中A的最小值）。在搜索过程中，a值递增，b值递减，两者构成了一个区间。这个区间被称为窗口，而对手下棋的结点最终的最
优值将落在这个窗口中。一旦在电脑下棋的结点得到其子结点的返回值大于b值，则发生剪枝。
同样，a-b裁剪也有简洁的负最大的版本，这时对手的a值即负的电脑的b值，对手的a值即负的电脑的b值。a-b裁剪的伪码如下：
…………………………………………………….
3.3 NegaScout搜索
常情况下，在搜索树的根结点，也就是电脑棋手需要决策的局面，我们可以调用3.2中给出的函数alphabeta来得到根结点的分值，同时也可以得到应该
走哪一步棋的结论。这时，调用该函数时，我们应使参数alpha=-1000，beta=1000，这里1000是一个足够大的数。这是因为在根结点时，
我们需要把窗口初始化成最大，在搜索过程中，随着信息的获得，这个窗口会渐渐地减小，最后收敛到根结点的最优值上。
现在我们来看一个有趣的现象：如果我们调用alphabeta( d, b & 0.1, b, p
)会产生什么结果？这里0.1是一个较小的常数，而b是某一个数值。
接从程序中分析，现在形式参数beta就等于b。如果函数的返回值大于b（也就是beta），说明对于局面p，至少有一个子结点的返回值比b大，所以其最
优值必然大于b。这时，我们知道b是局面p最优值的下界。注意，在这种情况下，后面也许还有子结点根本来不及搜索就被裁剪了，所以这时的返回值并不代表局
面p的实际最优值，可能比实际最优值小。如果函数的返回值小于b，说明没有一个子结点的最优值比b大，于是局面p的最优值必然小于b（事实行，由于初始的
窗口在函数递归过程中被反复传递下去，所有的返回值都只体现了是否比b大的信息，所以返回值不是局面p的实际最优值）。此时，b是局面p最优值的上界。于
是，我们得到结论，运用这种类型的alphabeta函数调用，根据返回值是否比b大，可以得出局面p的最优值是否比b大的结论。
注意到在函数调用过程中，alpha和beta很接近，因此窗口很小，在窗口很小的情况下，搜索树的各个层次中，得到的返回值比beta大的可能性就大大增加了，这样剪枝的可能性也变大了。
种类型的alphabeta函数调用被称为零窗口a-b搜索，由于产生了大量的剪枝，它的时间消耗比正规的a-b裁剪少。但正规的a-b裁剪可以得到一个
局面的实际最优值，而零窗口a-b调用只能得到实际最优值和某一个特定值b比大小的结果，也就是说，一个上界或下界的信息。
于是，我们可以对
a-b裁剪作一个改进：在每次向下搜索之前，首先先用零窗口a-b调用判断一下，这个搜索是否能够改善当前的最优值，即局面p某一个子结点的实际最优值是
否比alpha大。如果比alpha小，则跳过这个子结点。进一步，当该子结点的返回值大于alpha时，从前面的分析中已经知道，它的实际最优值大于这
个值，所以当返回值大于beta时，其实际最优值也超过了beta，这时就应该进行剪枝。这就是NegaScout搜索。在这个新算法中，增加的时间消耗
是零窗口a-b调用，而如果零窗口a-b调用的返回值比alpha小，那么就可以节约一个较大窗口的a-b调用花费的时间，当零窗口a-b调用的返回值比
beta大时，则直接产生了进一步的剪枝。实践证明，由于零窗口a-b裁剪中产生了大量的剪枝，所以其实践消耗相对于大窗口a-b调用而言是很小的。总的
说，NegaScout搜索较a-b裁剪有效。下面依照前述的思想，给出一个不算太规范的NegaScout算法的伪码（这里也使用了负最大搜索）：
…………………………………………………..
关于NegaScout的细节及其进一步的优化，读者可以查阅文献[1]。
3.4 魔术所在
按理说，搜索技术发展到这个地步，似乎已经很完善了。而事实上，这只是一个开始而已。
先出现的是一些改进的技术。例如，在前面讨论的各种搜索中，除了保存当前的搜索路径（搜索树的一个分支）的堆栈之外，不需要其它的内存消耗。这种做法并没
有充分利用资源。在实际的计算机博弈程序中，需要建立散列，用以保存在以前的搜索过程中所遇到的局面。这样，一旦在搜索过程中再次遇到相同的局面（这很常
见，如几种不同的行棋次序可能导致相同的局面），就可以利用以前计算的结果。关于这方面的细节，有兴趣的读者可以参阅文献[2]。
然而，真正的革命在于搜索算法全新的变化。
MTD(f) （全称是Memory-enhanced Test
Driver）就是其中一个相当优秀的新方法。它的思想非常简单：既然零窗口的a-b调用可以判断局面的最优值是否大于或小于一个固定的值，那么就反复运
用这个调用。假设已知局面的最优值f的范围是min &= f &=
max（例如在最初，min=-1000，max=1000），那么就在这个范围选一个值g，然后用这个值进行零窗口a-b调用。如果调用结果比g大，那
么说明g是f的下界，就得到min=g，反之max=g，这样，范围就缩小了。以上过程反复进行，直到上下界收敛到相同的一个值为止。
MTD(f)算法中，虽然也利用了a-b裁剪，但其仅仅作为一个辅助工具出现。其思想却非常有趣，完全跳出了前面的思维，以全新的方式出现在了我们的面前。
如果在搜索过程中能够使用散列保存已经搜索过的局面的特性，那么这个算法的效率将优于NegaScout。关于MTD(f)的细节，请有兴趣的读者查阅文献[3]。在此，我只简单地给出算法的伪码：
……………………………………………………………….
需 要注意的是，既然算法的名称中有Memory-enhanced，在这里使用的a-b裁剪应使用散列保存以前的搜索结果（这里使用了函数
alphabetawithmemory，以区分于原先的不使用散列的a-b裁剪）。在MTD(f)中，被重复搜索的相同局面大大增加，当以前的结果被保
留下来时，才可能提高效率。在国际象棋的实验中，该算法使效率提高了15%。
此外，还有其它的一些搜索算法，如SSS*[4]、B*[5]、Probcut[6]，这些算法和我们讨论的算法多少有些不同（或在局面的评价上、或在剪枝上、或在搜索的次序上），在这里就不再论述，有兴趣的读者可以自行参阅文献，进行研究。
4. 电脑棋手的学习
机器学习技术的发展为电脑下棋水平的提高带来了新的希望。各种各样的学习技术都被试图应用于博弈的某一个部分。文献[7]综述了机器学习在计算机象棋对弈中的应用。
在此，我将展示一个典型的方案：对形势判断函数进行学习。
4.1 监督学习
回顾一下第2部分中的内容，一个一般的形势判断函数（或称估价函数）具有如下的形式：
| f(G)=W1*X1+W2*X2+...+WiXi=S(i=0 to n)WiXi
中，xi表示局面的某一个因素（或特征），而wi是这个特征在形势判断中所起的重要程度（即相应的分值），通常被称为权重。如果当这个因素是子力时，在中
国象棋或国际象棋中，还是比较容易给出一个相对准确的值，而当这个因素是某些局面性的优势时，如何准确地估价这些优势，可能令有经验的大师都会感到烦恼。
虽然大师们很难对于一个孤立的局面因素给出具有普遍性的估计，例如在中国象棋中，一个处于巡河位置的车具有多大的分值，但对于一些特定的局面，大师们还是可以较为准确地给出综合评价。这为学习形势判断函数提供了可能。
一个很简单的方法就是找出许多局面，然后请大师为每一个局面作出自己的形势判断。然后把大师们给出的形势判断作为标准答案，训练形势判断函数。这种学习方式被称为监督学习（或称有师学习），因为这种学习就如在老师的监督指导下进行。
例 如现在有k个局面G1, G2, …,
Gk。第j个局面Gj的n个特征用X1j,X2j,...,Xnj表示。对这k个局面，大师给出的形势判断为h1, h2, …,
hk。现在的任务是找出合适的权重w1, w2, …, wn，使得以下的方程组尽可能地得到满足：
| j=1 W1X1j+W2X2j+...+WnXnj=h1
| j=2 W1X1j+W2X2j+...+WnXnj=h2
| j= ... M
| j=k W1X1j+W2X2j+...+WnXnj=hk
注意，之所以说是尽可能得到满足，是因为以上关于w1, w2, …, wn的方程组不一定有解，我们所希望的是实际形势判断结果f1,
f2, …, fk与大师给出的结果h1, h2, …, hk尽可能接近。
形势判断函数非常复杂时，这个问题实际上是一个优化问题。解决这个问题的通用方法是梯度下降法（有兴趣的读者可以参阅有关最优化的书籍）。由于现在的形势
判断函数非常简单，也可以应用许多其它方法（如最小二乘）。下面仅仅给出梯度下降方法在这个简单的实际问题上的应用。
首先对所有的权重w1, w2, …, wn赋以随机的数值。然后反复进行以下的迭代：在时刻t，对局面G1, G2, …,
Gk计算形势判断结果f1, f2, …, fk，依照下式得到下一时刻（即t +1时刻）的权重为
| wi(t+1)=wi(t)+H*S(j=1 to k)(hj-fj)*xij
以上对权重的更新过程反复进行，直到形势判断的结果不能再改善为止。式子中的H被称为学习速率，当取值较大时，学习速度较快（即需要迭代的次数变少），但学习的精度较低（准确地说，在最后阶段会产生振荡），当取值较小时精度提高，但学习速度变慢。
如果哪位读者对人工神经网络有一定的了解，也可以将以上的过程看作是一个连续型感知器的学习过程。
4.2 强化学习
监督学习并不是一个令人满意的学习方法（虽然在某些情况下是不可替代的）。毕竟，当这样的“老师”也是很累的，很难想像去请一个大师对数百个甚至数千个局面给出自己的形势判断。
化学习是监督学习的一个特例。这时，“老师”不再每次都给出准确的答案，他（她、它）只是对电脑的计算结果给出一个好或不好的评价，或者是告诉电脑究竟好
到何种程度，作为一个带有模糊性的判断。在下棋中，这种“老师”是随处可得的。电脑棋手和每一个对手的对局都有可能成为这种“老师”，对局的胜负就可以看
作是“老师”对电脑棋手的评价。当然，如何有效地利用这种评价是学习技术的关键。
以中国象棋或国际象棋为例，在一局棋的进行过程中，一个形势判 断函数的结果往往时好时差。这是因为在形势判断函数中的权重w1, w2,
wn中，有些比较准确（比如子力因素的权重），而其它的一些并不准确（如一些表示局面优势因素的权重）。在棋局的进行中，经常出现的状况是一方首先取得了
局面优势，随后转化成了子力的优势，最后取胜，或者更一般地说，一方首先取得了一些潜在的优势，随后将这些潜在的优势转化为实在的优势。一般地说，电脑棋
手对潜在的优势往往不能给出准确的判断，而对较为实在的优势（例如子力优势或者直接构成的杀局）则判断正确。于是我们可以得到一个基本准确的结论，电脑棋
手在其对局的后期（更特殊的状况是对局结束的时刻），得到的形势判断往往是比较正确的。同时，我们可以设想，在对局的前面的一些时刻，正确的形势判断应该
和对局后期的形势判断较为接近。如果计算机能够有效地参考对局后期正确的形势判断，就有可能自行给出对局前期的一些局面的相对准确的形势判断，作为在前一
节所提到的监督训练中的标准答案h1, h2, …, hk。
TD( )就是一个实用的强化学习技术。TD（Temporal
Difference）即瞬时差异，就是指在一个对局中相邻两个时刻的局面的形势判断之差。如果这个形势判断函数比较准确，则这个差（即瞬时差异）应该接
近于0。假设G1, G2, …, Gk,
Gk+1是在一个对局中，从某一时刻到对局结束的连续的k+1个局面。这时根据前面的假设，在对局结束时的形势判断是准确的，即对于第k+1个局面，形势
判断的标准答案hk+1=f(Gk+1)。现在我们利用这个值来形成前k个局面的形势判断标准答案：从对局结束开始，向前一步步倒退，在每一个时刻，其形
势判断标准答案为
|.......h =(1-y)f(G )+y*k
|........i i+1 i+1
从这个式子中
可以看到，当y=0时，第i个局面的形势判断标准答案应该接近于在此之后的局面的形势判断；当y=1时，所有局面的形势判断标准答案都接近于hk+1，即
对局结束时刻的形势判断。于是，当y取介于0和1之间的某一个数值时，形势判断的标准答案将成为以上两者的折中。经过了学习之后的形势判断函数将在对局中
的一系列连续的局面中，相邻局面的判断结果相似，并逐渐逼近终局时的结果。
)被应用于多个计算机博弈程序之中。在文献[8]中，一个应用了该技术（稍作了一些改变，有兴趣的读者请自行查阅文献）的国际象棋程序在国际互联网上进行了300多局对局后，其等级分从1650分（一般水平）上涨到了2110分（美国大师水平）。
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。