第11卷第6期 智能系统学报 Vol.11 No.6 2016年12月 CAAI Transactions on Intelligent Systems Dec.2016 D0I:10.11992/is.201609006 网络出版地址：http://www.cnki.net/kcms/detail,/23.1538.TP.20170111.1705.030.html 计算机博弈的研究与发展 王亚杰，邱虹坤，吴燕燕，李飞，杨周凤 (沈阳航空航天大学工程训练中心，辽宁沈阳110136) 摘要：计算机博弈是人工智能领域重要而极具挑战性的研究方向。本文首先回顾了计算机博弈的发展历程，以及 国内外的计算机博弈赛事情况，各种竞赛为计算机博奔技术的发展提供了一个技术验证与学术交流的平台。然后 介绍了计算机博弈系统的构成，一个博弈系统包括博弈平台、博弈树搜索、局面评估、着法生成、机器学习等多方面 技术：重点阐述了极大极小搜索、剪枝搜索、蒙特卡罗搜索等常用算法的原理与特点：对局面评估方法和各种优化算 法也进行了分析，其中的并行计算、遗传算法和基于神经网铬的深度学习算法等都是提升机器智能的有效方法。最 后，分析了计算机博弈研究面临的问题，并展望了未来的发展方向与趋势。 关键词：人工智能：计算机博弈：蒙特卡罗搜索：神经网络：遗传算法：深度学习 中图分类号：TP391文献标志码：A文章编号：1673-4785(2016)06-0788-011 中文引用格式：王亚杰，邱虹坤，吴燕燕，等.计算机博弈的研究与发展[J].智能系统学报，2016,11(6)：788-798. 英文引用格式：WANG Yajie,QIU Hongkun,WU Yanyan,etal.Research and development of computer games[J】.CAAI Trans-- actions on Intelligent Systems,2016,11(2):788-798. Research and development of computer games WANG Yajie,QIU Hongkun,WU Yanyan,LI Fei,YANG Zhoufeng (Engineering Training Center,Shenyang Aerospace University,Shenyang 110136,China) Abstract:Computer gaming is one of the most important and challenging research directions in the field of Artificial Intelligence (AI).First,this paper reviewed the development of computer games,and the competitions in China and abroad.All types of competitions provide a platform of technical verification and academic communication for the development of computer game technology.Second,the computer game system was introduced,which includes the game platform,the game tree search,the situation evaluation,the move generation,the machine learning and other technologies.The principles and features of the typically used algorithms were stated,such as the Minimax searching algorithm,the pruning searching algorithm,the Monte Carlo searching algorithm,and so on.The situa- tion evaluation method and many optimization algorithms were also analyzed,among which,parallel computing,the genetic algorithm and the deep learning algorithm,based on a neural network,were effective methods to promote machine intelligence.Finally,the challenges of computer games were analyzed,and the development and future trends were proposed. Keywords:artificial intelligence;computer game;Monte Carlo tree search;neural networks;genetic algorithm; deep learning 计算机博弈，也称之为机器博弈，是人工智能领域的挑战性课题。它从模仿人脑智能的角度出发， 以计算机下棋为研究载体，通过模拟人类棋手的思 收稿日期：2016-09-07. 基金项目：航空科学基金项目(20152C54008):辽宁省教育厅基金项目 维过程，构建一种更接近人类智能的博弈信息处理 (L2015407). 系统，并可以拓展到其他相关领域，解决实际工程和 通信作者：邱虹坤.E-mail:qiuhk@sina.com
第 １１ 卷第 ６ 期 智 能 系 统 学 报 Ｖｏｌ．１１ №．６ ２０１６ 年 １２ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｄｅｃ． ２０１６ ＤＯＩ：１０．１１９９２ ／ ｔｉｓ．２０１６０９００６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ＴＰ．２０１７０１１１．１７０５．０３０．ｈｔｍｌ 计算机博弈的研究与发展 王亚杰，邱虹坤，吴燕燕，李飞，杨周凤 （沈阳航空航天大学 工程训练中心，辽宁 沈阳 １１０１３６） 摘 要：计算机博弈是人工智能领域重要而极具挑战性的研究方向。 本文首先回顾了计算机博弈的发展历程，以及 国内外的计算机博弈赛事情况，各种竞赛为计算机博弈技术的发展提供了一个技术验证与学术交流的平台。 然后 介绍了计算机博弈系统的构成， 一个博弈系统包括博弈平台、博弈树搜索、局面评估、着法生成、机器学习等多方面 技术；重点阐述了极大极小搜索、剪枝搜索、蒙特卡罗搜索等常用算法的原理与特点；对局面评估方法和各种优化算 法也进行了分析，其中的并行计算、遗传算法和基于神经网络的深度学习算法等都是提升机器智能的有效方法。 最 后，分析了计算机博弈研究面临的问题，并展望了未来的发展方向与趋势。 关键词：人工智能；计算机博弈；蒙特卡罗搜索；神经网络；遗传算法；深度学习 中图分类号： ＴＰ３９１ 文献标志码：Ａ 文章编号：１６７３－４７８５（２０１６）０６－０７８８－０１１ 中文引用格式：王亚杰，邱虹坤，吴燕燕，等． 计算机博弈的研究与发展［Ｊ］． 智能系统学报， ２０１６， １１（６）： ７８８－７９８． 英文引用格式：ＷＡＮＧ Ｙａｊｉｅ， ＱＩＵ Ｈｏｎｇｋｕｎ， ＷＵ Ｙａｎｙａｎ， ｅｔ ａｌ． Ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅｓ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓ⁃ ａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１６， １１（２）： ７８８－７９８． Ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅｓ ＷＡＮＧ Ｙａｊｉｅ， ＱＩＵ Ｈｏｎｇｋｕｎ， ＷＵ Ｙａｎｙａｎ， ＬＩ Ｆｅｉ， ＹＡＮＧ Ｚｈｏｕｆｅｎｇ （Ｅｎｇｉｎｅｅｒｉｎｇ Ｔｒａｉｎｉｎｇ Ｃｅｎｔｅｒ， Ｓｈｅｎｙａｎｇ Ａｅｒｏｓｐａｃｅ Ｕｎｉｖｅｒｓｉｔｙ， Ｓｈｅｎｙａｎｇ １１０１３６， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｃｏｍｐｕｔｅｒ ｇａｍｉｎｇ ｉｓ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｉｍｐｏｒｔａｎｔ ａｎｄ ｃｈａｌｌｅｎｇｉｎｇ ｒｅｓｅａｒｃｈ ｄｉｒｅｃｔｉｏｎｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ＡＩ）． Ｆｉｒｓｔ， ｔｈｉｓ ｐａｐｅｒ ｒｅｖｉｅｗｅｄ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅｓ， ａｎｄ ｔｈｅ ｃｏｍｐｅｔｉｔｉｏｎｓ ｉｎ Ｃｈｉｎａ ａｎｄ ａｂｒｏａｄ． Ａｌｌ ｔｙｐｅｓ ｏｆ ｃｏｍｐｅｔｉｔｉｏｎｓ ｐｒｏｖｉｄｅ ａ ｐｌａｔｆｏｒｍ ｏｆ ｔｅｃｈｎｉｃａｌ ｖｅｒｉｆｉｃａｔｉｏｎ ａｎｄ ａｃａｄｅｍｉｃ ｃｏｍｍｕｎｉｃａｔｉｏｎ ｆｏｒ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｔｅｃｈｎｏｌｏｇｙ． Ｓｅｃｏｎｄ， ｔｈｅ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｓｙｓｔｅｍ ｗａｓ ｉｎｔｒｏｄｕｃｅｄ， ｗｈｉｃｈ ｉｎｃｌｕｄｅｓ ｔｈｅ ｇａｍｅ ｐｌａｔｆｏｒｍ， ｔｈｅ ｇａｍｅ ｔｒｅｅ ｓｅａｒｃｈ， ｔｈｅ ｓｉｔｕａｔｉｏｎ ｅｖａｌｕａｔｉｏｎ， ｔｈｅ ｍｏｖｅ ｇｅｎｅｒａｔｉｏｎ， ｔｈｅ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ａｎｄ ｏｔｈｅｒ ｔｅｃｈｎｏｌｏｇｉｅｓ． Ｔｈｅ ｐｒｉｎｃｉｐｌｅｓ ａｎｄ ｆｅａｔｕｒｅｓ ｏｆ ｔｈｅ ｔｙｐｉｃａｌｌｙ ｕｓｅｄ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ｓｔａｔｅｄ， ｓｕｃｈ ａｓ ｔｈｅ Ｍｉｎｉｍａｘ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ， ｔｈｅ ｐｒｕｎｉｎｇ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ， ｔｈｅ Ｍｏｎｔｅ Ｃａｒｌｏ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ， ａｎｄ ｓｏ ｏｎ． Ｔｈｅ ｓｉｔｕａ⁃ ｔｉｏｎ ｅｖａｌｕａｔｉｏｎ ｍｅｔｈｏｄ ａｎｄ ｍａｎｙ ｏｐｔｉｍｉｚａｔｉｏｎ ａｌｇｏｒｉｔｈｍｓ ｗｅｒｅ ａｌｓｏ ａｎａｌｙｚｅｄ， ａｍｏｎｇ ｗｈｉｃｈ， ｐａｒａｌｌｅｌ ｃｏｍｐｕｔｉｎｇ， ｔｈｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｄｅｅｐ ｌｅａｒｎｉｎｇ ａｌｇｏｒｉｔｈｍ， ｂａｓｅｄ ｏｎ ａ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ， ｗｅｒｅ ｅｆｆｅｃｔｉｖｅ ｍｅｔｈｏｄｓ ｔｏ ｐｒｏｍｏｔｅ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｆｉｎａｌｌｙ， ｔｈｅ ｃｈａｌｌｅｎｇｅｓ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅｓ ｗｅｒｅ ａｎａｌｙｚｅｄ， ａｎｄ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ａｎｄ ｆｕｔｕｒｅ ｔｒｅｎｄｓ ｗｅｒｅ ｐｒｏｐｏｓｅｄ． Ｋｅｙｗｏｒｄｓ： ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ； ｃｏｍｐｕｔｅｒ ｇａｍｅ； Ｍｏｎｔｅ Ｃａｒｌｏ ｔｒｅｅ ｓｅａｒｃｈ； ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ； ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ； ｄｅｅｐ ｌｅａｒｎｉｎｇ 收稿日期：２０１６－０９－０７． 基金项目：航空科学基金项目（ ２０１５ＺＣ５４００８）；辽宁省教育厅基金项目 （Ｌ２０１５４０７）． 通信作者：邱虹坤．Ｅ⁃ｍａｉｌ：ｑｉｕｈｋ＠ ｓｉｎａ．ｃｏｍ． 计算机博弈，也称之为机器博弈，是人工智能领 域的挑战性课题。 它从模仿人脑智能的角度出发， 以计算机下棋为研究载体，通过模拟人类棋手的思 维过程，构建一种更接近人类智能的博弈信息处理 系统，并可以拓展到其他相关领域，解决实际工程和
第6期 王亚杰，等：计算机博弈的研究与发展 ·789. 科学研究领域中与博弈相关的难以解决的复杂问 1989年BM公司研制的“深思”在与世界棋王卡斯 题-]。作为人工智能研究的一个重要分支，它是 帕罗夫进行的“人机大战”中，以0：2败北。1995 检验计算机技术及人工智能发展水平的一个重要方 年BM更新了“深蓝”程序，并使用新的集成电路将 向，为人工智能带来了很多重要的方法和理论，极大 思考速度提高到每秒300万步，在1996年与卡斯帕 地推动了科研进步，并产生了广泛的社会影响和学 罗夫的挑战赛中以2：4败北。1997年“超级深蓝” 术影响3-]。 融入了更深的开发，以3.5：2.5击败了卡斯帕罗 计算机博弈是知识工程演绎的平台，是研究人 夫，这场胜利引起了世界范围内的轰动，它表明“计 工智能科学的“果蝇”)。如何提高机器智能，是计 算机智能战胜了人类天才”。 算机博弈研究的精髓所在。针对该领域技术进行研 在国内，南开大学黄云龙教授和他的学生在20 究，有助于更好地理解人类的智能，更好地推动人工 世纪80年代，开发了一系列中国象棋程序。中山大 智能技术和相关产业的融合与发展。 学化学系教授陈志行先生在90年代初开发了围棋 程序“手谈”，曾经获得世界冠军。 1计算机博弈发展 1.3成熟阶段 1.1起步阶段 20世纪末期，国内外有许多科研机构和学者在 20世纪50年代开始，许多世界上著名的学者 计算机博弈领域进行深入探讨和实质性的研究。随 都曾经涉足计算机博弈领域的研究工作，为机器博 着极大极小算法(minimax algorithm))、a&-B剪 弈的研究与开发奠定了良好的基础。阿兰·图灵 枝[9，)、上限置信区间算法(upper confidence bound (Alan Turing)先生最早写下了能够让机器下棋的指 apply to tree,.UCT)I)、并行搜索算法[i4]、遗传算 令，计算机之父冯·诺依曼(John von Neumann)提 法[5]、人工神经网络[16]等技术日趋成熟，人工神经 出了用于博弈的极大极小定理，信息论创始人科劳 网络、类脑思维等科学也不断取得突破性进展，各种 德·香农[6(Claude E.Shannon)首次提出了国际象 机器学习模型，例如支持向量机、Boosting算法、最 棋的解决方案，人工智能的创始人麦卡锡(John Me- 大嫡方法等相继被提出，计算机博弈研究进入了一 Carthy)首次提出“人工智能”(artificial intelligence) 个前所未有的阶段。 这一概念。1958年阿伯恩斯坦(Alex Bernstein) 2006年，Hinton和他的学生在Science上发表 等)在BM704机上开发了第1个成熟的达到孩童 了一篇关于用神经网络降低数据维数的论文[16]，开 博弈水平的国际象棋程序。1959年，人工智能的创 启了深度学习在学术界的浪潮。2007年科学杂志 始人之一塞缪[8)(A.L.Samuel)编了一个能够战胜 评出的人类10大科学突破中，包括了加拿大阿尔波 设计者本人的西洋跳棋程序，1962年该程序击败了 特大学研究人员历时18年破解了国际跳棋(64)的 美国的一个州冠军。 研究成果，这是整个机器博弈发展史上的一个里程 研究机器博弈的学者们发现，博弈程序的智能 碑) 水平与搜索深度有很大关系。他们研究的内容主要 2003年，台湾交通大学吴毅成教授发明了六子 涉及：如何建立有效、快速的评价函数和评价方法， 棋(connect6)【7」，目前被认为是最公平的棋类。 使评价的效率更高，花费的时间和空间的代价更小： 之后，东北大学徐心和教授[181和他的团队[9]研 如何在生成的博弈树上更准确有效地找到最优解， 究开发了中国象棋软件“棋天大圣”，具有挑战国内 并由此发展出来各种搜索算法[9山。 中国象棋顶级高手的实力：北邮刘知青[2-2]带领学 1.2发展阶段 生开发的“本手(LNGO)”围棋程序，能够战胜高水 20世纪80年代末，随着计算机硬件和软件技 平业余围棋选手；哈工大王轩2、南航夏正 术不断发展，计算机博弈理论日趋完善，学者们开始 友[2”-]分别带领学生开发了四国军棋博弈系统，这 对电脑能否战胜人脑这个话题产生了浓厚的兴趣， 些程序都表现出较高的智能水平。 并提出了以棋类对弈的方式，向人类发起挑战，计算 1.4飞跃阶段 机博弈研究进入了快速发展的阶段。 最近几年，基于人工神经网络[)取得了突破性 在国外，1986年7月，Hinton等12)在自然杂志 的进展。运用该技术，成功地解决了计算机博弈领 (Nature)上发表论文，首次系统简洁地阐述了反向 域中许多实际问题。 传播算法在神经网络模型上的应用，给机器学习带 2012年6月，谷歌公司的Google Brain项目用 来了希望，掀起了基于统计模型的机器学习热潮。 并行计算平台训练一种称为“深度神经网络”(deep
科学研究领域中与博弈相关的难以解决的复杂问 题［１－２］ 。 作为人工智能研究的一个重要分支，它是 检验计算机技术及人工智能发展水平的一个重要方 向，为人工智能带来了很多重要的方法和理论，极大 地推动了科研进步，并产生了广泛的社会影响和学 术影响［３－５］ 。 计算机博弈是知识工程演绎的平台，是研究人 工智能科学的“果蝇” ［１］ 。 如何提高机器智能，是计 算机博弈研究的精髓所在。 针对该领域技术进行研 究，有助于更好地理解人类的智能，更好地推动人工 智能技术和相关产业的融合与发展。 １ 计算机博弈发展 １．１ 起步阶段 ２０ 世纪 ５０ 年代开始，许多世界上著名的学者 都曾经涉足计算机博弈领域的研究工作，为机器博 弈的研究与开发奠定了良好的基础。 阿兰·图灵 （Ａｌａｎ Ｔｕｒｉｎｇ）先生最早写下了能够让机器下棋的指 令，计算机之父冯·诺依曼（ Ｊｏｈｎ ｖｏｎ Ｎｅｕｍａｎｎ） 提 出了用于博弈的极大极小定理，信息论创始人科劳 德·香农［６］ （Ｃｌａｕｄｅ Ｅ． Ｓｈａｎｎｏｎ）首次提出了国际象 棋的解决方案，人工智能的创始人麦卡锡（Ｊｏｈｎ Ｍｃ⁃ Ｃａｒｔｈｙ）首次提出“人工智能” （ ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ） 这一概念。 １９５８ 年阿伯恩斯坦 （ Ａｌｅｘ Ｂｅｒｎｓｔｅｉｎ） 等［７］在 ＩＢＭ７０４ 机上开发了第 １ 个成熟的达到孩童 博弈水平的国际象棋程序。 １９５９ 年，人工智能的创 始人之一塞缪［８］ （Ａ．Ｌ． Ｓａｍｕｅｌ） 编了一个能够战胜 设计者本人的西洋跳棋程序，１９６２ 年该程序击败了 美国的一个州冠军。 研究机器博弈的学者们发现，博弈程序的智能 水平与搜索深度有很大关系。 他们研究的内容主要 涉及：如何建立有效、快速的评价函数和评价方法， 使评价的效率更高，花费的时间和空间的代价更小； 如何在生成的博弈树上更准确有效地找到最优解， 并由此发展出来各种搜索算法［９－１１］ 。 １．２ 发展阶段 ２０ 世纪 ８０ 年代末，随着计算机硬件和软件技 术不断发展，计算机博弈理论日趋完善，学者们开始 对电脑能否战胜人脑这个话题产生了浓厚的兴趣， 并提出了以棋类对弈的方式，向人类发起挑战，计算 机博弈研究进入了快速发展的阶段。 在国外，１９８６ 年 ７ 月，Ｈｉｎｔｏｎ 等［１２］ 在自然杂志 （Ｎａｔｕｒｅ）上发表论文，首次系统简洁地阐述了反向 传播算法在神经网络模型上的应用，给机器学习带 来了希望，掀起了基于统计模型的机器学习热潮。 １９８９ 年 ＩＢＭ 公司研制的“深思”在与世界棋王卡斯 帕罗夫进行的“人机大战” 中，以 ０ ∶ ２ 败北。 １９９５ 年 ＩＢＭ 更新了“深蓝”程序，并使用新的集成电路将 思考速度提高到每秒 ３００ 万步，在 １９９６ 年与卡斯帕 罗夫的挑战赛中以 ２ ∶ ４ 败北。 １９９７ 年“超级深蓝” 融入了更深的开发，以 ３． ５ ∶ ２． ５ 击败了卡斯帕罗 夫，这场胜利引起了世界范围内的轰动，它表明“计 算机智能战胜了人类天才”。 在国内，南开大学黄云龙教授和他的学生在 ２０ 世纪 ８０ 年代，开发了一系列中国象棋程序。 中山大 学化学系教授陈志行先生在 ９０ 年代初开发了围棋 程序“手谈”，曾经获得世界冠军。 １．３ 成熟阶段 ２０ 世纪末期，国内外有许多科研机构和学者在 计算机博弈领域进行深入探讨和实质性的研究。 随 着极 大 极 小 算 法 （ ｍｉｎｉｍａｘ ａｌｇｏｒｉｔｈｍ） ［１１］ 、 α⁃β 剪 枝［９，１１］ 、上限置信区间算法（ ｕｐｐｅｒ ｃｏｎｆｉｄｅｎｃｅ ｂｏｕｎｄ ａｐｐｌｙ ｔｏ ｔｒｅｅ，ＵＣＴ） ［１３］ 、并行搜索算法［１４］ 、遗传算 法［１５］ 、人工神经网络［１６］等技术日趋成熟，人工神经 网络、类脑思维等科学也不断取得突破性进展，各种 机器学习模型，例如支持向量机、 Ｂｏｏｓｔｉｎｇ 算法、最 大熵方法等相继被提出，计算机博弈研究进入了一 个前所未有的阶段。 ２００６ 年，Ｈｉｎｔｏｎ 和他的学生在 Ｓｃｉｅｎｃｅ 上发表 了一篇关于用神经网络降低数据维数的论文［１６］ ，开 启了深度学习在学术界的浪潮。 ２００７ 年科学杂志 评出的人类 １０ 大科学突破中，包括了加拿大阿尔波 特大学研究人员历时 １８ 年破解了国际跳棋（６４）的 研究成果，这是整个机器博弈发展史上的一个里程 碑［５］ 。 ２００３ 年，台湾交通大学吴毅成教授发明了六子 棋 （ｃｏｎｎｅｃｔ ６） ［ １７ ］ ，目前被认为是最公平的棋类。 之后，东北大学徐心和教授［ １８ ］ 和他的团队［１９－２１］ 研 究开发了中国象棋软件“棋天大圣”，具有挑战国内 中国象棋顶级高手的实力；北邮刘知青［２２－２３］ 带领学 生开发的“本手（ＬＩＮＧＯ）”围棋程序，能够战胜高水 平业 余 围 棋 选 手； 哈 工 大 王 轩［２４－２６］ 、 南 航 夏 正 友［２７－２８］分别带领学生开发了四国军棋博弈系统，这 些程序都表现出较高的智能水平。 １．４ 飞跃阶段 最近几年，基于人工神经网络［３］ 取得了突破性 的进展。 运用该技术，成功地解决了计算机博弈领 域中许多实际问题。 ２０１２ 年 ６ 月，谷歌公司的 Ｇｏｏｇｌｅ Ｂｒａｉｎ 项目用 并行计算平台训练一种称为“深度神经网络” （ ｄｅｅｐ 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７８９·
.790 智能系统学报 第11卷 neural networks,DNN)的机器学习模型。2013年1 除了以上竞赛，还有各种世界范围内的人机大 月，百度宣布成立“深度学习研究所”(institue of 战活动，这些竞赛活动极大地激发了人们的挑战热 deep learning,IDL)。在2015年10月5：0击败了 情和创新精神，为社会培养了大量的科技精英，在促 欧洲围棋冠军樊麾后，2016年1月，谷歌DeepMind 进了人工智能技术快速发展的同时，还产生了新的 团队在自然杂志(Nature)上发表封面论文称，他们 科研成果。 研发出基于神经网络进行深度学习的人工智能围棋 3计算机博弈系统设计 程序AlphaGo,能够在极其复杂的围棋游戏中战胜 专家级人类选手[)。2016年3月，AlphaGo又以 计算机博弈系统是指在特定规则下具有博弈能 4:1战胜世界围棋冠军李世石，在学术界产生了空 力的智能系统。在设计系统时，需要考虑知识表示、 前的影响，这标志着计算机博弈技术取得重大成功， 着法产生、搜索与评估几个方面。 是计算机博弈发展史上新的跃迁。 典型的计算机博弈系统的核心架构设计如图1 2赛事与学术交流 所示，可以划分为博弈平台和搜索引擎两大模块。 其中，博弈平台主要负责界面显示、棋规判断、行棋 由国际机器博弈协会(International Computer 过程控制、信息传递等]，在其设计过程中，通常考 Games Association,ICGA)组织的国际计算机博弈比 虑通用性、易用性、健壮性、艺术性：博弈引擎主要负 赛(Computer Olympiad,C0)每年一届，已经有了30 责知识学习、开（或残）局库设计[20,6]、棋局评估、博 多年的历史。比赛项目包括中国象棋、六子棋、亚马 弈树搜索、着法生成等。 逊棋、围棋等，通过竞赛促进了世界范围内的计算机 行 博弈技术的发展。同时，ICGA还每年组织学术研讨 信 棋 棋 会，并出版ICGA季刊2,0]。 传 面 判 程 从1969年开始，国际人工智能联合会议(Inter- 递 示 national Joint Conference on Artificial Intelligence.IJ- CAI)每两年举行一次，ICAI是人工智能研究人员 平台要素数字化建模 前端： 博弈平台 最主要国际会议之一。通过学术交流，发表计算机 博弈的最新研究成果[3-] 2006年8月，由中国人工智能学会首次主办中 数据结构定义 后端： 搜索引擎 国计算机博弈锦标赛，至今已举办10届。从2011 年开始，由中国人工智能学会与教育部高等学校计 博 算机类专业教学指导委员会共同主办全国大学生计 局 弈 机 弈 法 知 算机博弈大赛暨全国锦标赛[36-7】，目前已举办6 面 树 识 估 搜 展 成 习 库 届。这项赛事所设定的各项比赛，涉及计算机博弈 开 相关的知识库、博弈平台[38)、搜索引擎、神经网络」 机器学习与局面评估[90]等多种技术，吸引了越来 博弈控制策略 越多的专家、学者与计算机博弈爱好者参与到计算 机博弈相关研究中，为计算机博弈技术的交流与验 图1计算机博弈系统典型架构 证提供了一个公平、开放的平台。目前，竞赛项目涵 Fig.1 Typical architecture of computer game system 盖了多种类型的博弈： 相对整个计算机博弈系统而言，后端搜索引擎 1)按参与人数划分，包括双人博弈（如中国 是整个系统的核心部分，它是决定博弈胜负的关键， 象棋、围棋)和多人博弈（如二打一扑克）： 在搜索引擎的开发过程中，除了考虑与博弈平台的 2)按参与人对他人了解程度划分，包括完备信 接口外，还要根据各个棋种的特点，选择合适的搜索 息博弈]（如中国象棋、围棋、六子棋、亚马逊棋、苏 算法和评估函数[4748】。 拉卡尔塔棋等)和非完全信息博弈[24,44（如幻影围 4博奔树搜索技术 棋、军棋、二打一扑克)： 3)按参与人之间有无合作划分，包括合作博弈 4.1博弈树复杂度 (如桥牌])与非合作博弈（如中国象棋）。 博弈树是由树枝和节点构成单向无环图，如图 2所示。博弈树的节点对应于某一个棋局，其分支
ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ，ＤＮＮ） 的机器学习模型。 ２０１３ 年 １ 月，百度宣布成立“ 深度学习研究所” （ ｉｎｓｔｉｔｕｅ ｏｆ ｄｅｅｐ ｌｅａｒｎｉｎｇ，ＩＤＬ）。 在 ２０１５ 年 １０ 月 ５ ∶ ０ 击败了 欧洲围棋冠军樊麾后，２０１６ 年 １ 月，谷歌 ＤｅｅｐＭｉｎｄ 团队在自然杂志（Ｎａｔｕｒｅ）上发表封面论文称，他们 研发出基于神经网络进行深度学习的人工智能围棋 程序 ＡｌｐｈａＧｏ，能够在极其复杂的围棋游戏中战胜 专家级人类选手［３］ 。 ２０１６ 年 ３ 月， ＡｌｐｈａＧｏ 又以 ４ ∶ １战胜世界围棋冠军李世石，在学术界产生了空 前的影响，这标志着计算机博弈技术取得重大成功， 是计算机博弈发展史上新的跃迁。 ２ 赛事与学术交流 由国际机器博弈协会 （ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｍｐｕｔｅｒ Ｇａｍｅｓ Ａｓｓｏｃｉａｔｉｏｎ，ＩＣＧＡ）组织的国际计算机博弈比 赛（Ｃｏｍｐｕｔｅｒ Ｏｌｙｍｐｉａｄ，ＣＯ）每年一届，已经有了 ３０ 多年的历史。 比赛项目包括中国象棋、六子棋、亚马 逊棋、围棋等，通过竞赛促进了世界范围内的计算机 博弈技术的发展。 同时，ＩＣＧＡ 还每年组织学术研讨 会，并出版 ＩＣＧＡ 季刊［２７，３０－３２］ 。 从 １９６９ 年开始，国际人工智能联合会议（Ｉｎｔｅｒ⁃ ｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ，ＩＪ⁃ ＣＡＩ）每两年举行一次，ＩＪＣＡＩ 是人工智能研究人员 最主要国际会议之一。 通过学术交流，发表计算机 博弈的最新研究成果［３３－３５］ 。 ２００６ 年 ８ 月，由中国人工智能学会首次主办中 国计算机博弈锦标赛，至今已举办 １０ 届。 从 ２０１１ 年开始，由中国人工智能学会与教育部高等学校计 算机类专业教学指导委员会共同主办全国大学生计 算机博弈大赛暨全国锦标赛［３６－３７ ］ ，目前已举办 ６ 届。 这项赛事所设定的各项比赛，涉及计算机博弈 相关的知识库、博弈平台［３８］ 、搜索引擎、神经网络、 机器学习与局面评估［３９－４０］等多种技术，吸引了越来 越多的专家、学者与计算机博弈爱好者参与到计算 机博弈相关研究中，为计算机博弈技术的交流与验 证提供了一个公平、开放的平台。 目前，竞赛项目涵 盖了多种类型的博弈： １）按参与人数划分，包括双人博弈［４１］ （如中国 象棋、围棋）和多人博弈（如二打一扑克［４２］ ）； ２）按参与人对他人了解程度划分，包括完备信 息博弈［４３］ （如中国象棋、围棋、六子棋、亚马逊棋、苏 拉卡尔塔棋等） 和非完全信息博弈［２４，４４］ （如幻影围 棋、军棋、二打一扑克）； ３）按参与人之间有无合作划分，包括合作博弈 （如桥牌［４５］ ）与非合作博弈（如中国象棋）。 除了以上竞赛，还有各种世界范围内的人机大 战活动，这些竞赛活动极大地激发了人们的挑战热 情和创新精神，为社会培养了大量的科技精英，在促 进了人工智能技术快速发展的同时，还产生了新的 科研成果。 ３ 计算机博弈系统设计 计算机博弈系统是指在特定规则下具有博弈能 力的智能系统。 在设计系统时，需要考虑知识表示、 着法产生、搜索与评估几个方面。 典型的计算机博弈系统的核心架构设计如图 １ 所示，可以划分为博弈平台和搜索引擎两大模块。 其中，博弈平台主要负责界面显示、棋规判断、行棋 过程控制、信息传递等［３８］ ，在其设计过程中，通常考 虑通用性、易用性、健壮性、艺术性；博弈引擎主要负 责知识学习、开（或残）局库设计［２０，４６］ 、棋局评估、博 弈树搜索、着法生成等。 图 １ 计算机博弈系统典型架构 Ｆｉｇ．１ Ｔｙｐｉｃａｌ ａｒｃｈｉｔｅｃｔｕｒｅ ｏｆ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｓｙｓｔｅｍ 相对整个计算机博弈系统而言，后端搜索引擎 是整个系统的核心部分，它是决定博弈胜负的关键， 在搜索引擎的开发过程中，除了考虑与博弈平台的 接口外，还要根据各个棋种的特点，选择合适的搜索 算法和评估函数［４７－４８］ 。 ４ 博弈树搜索技术 ４．１ 博弈树复杂度 博弈树是由树枝和节点构成单向无环图，如图 ２ 所示。 博弈树的节点对应于某一个棋局，其分支 ·７９０· 智 能 系 统 学 报 第 １１ 卷
第6期 王亚杰，等：计算机博弈的研究与发展 .791. 表示走一步棋：根部对应于开始位置，其叶表示对弈 4.2博弈树搜索 到此结束。生成博弈着法的过程，对应博弈树的搜 以中国象棋、国际跳棋为代表的二人零和完备 索与展开[9。计算机博弈的过程是双方轮流给出 信息博弈，其搜索理论已经很系统。其中极大极小 着法，使棋局向着对本方有利的方向发展，直至最后 算法[s别是最基本的搜索算法，它奠定了计算机博弈 的胜利。 的理论基础。以极大极小算法为基础的博弈树搜索 算法，从搜索方向考虑，可以分为深度优先搜索和宽 度优先搜索：从控制策略考虑，可以分为盲目搜索和 启发搜索；从搜索范围考虑，可以分为穷尽搜索、裁 剪搜索。 图2博弈树示意图 相对而言，宽度优先搜索、穷尽搜索和盲目搜索 Fig.2 Schematic diagram of game tree 算法时间和空间开销巨大，难以做到很深的搜索。 搜索博弈树的目的就是在假设双方的走法都是 因此，在计算机博弈的实际应用中，很少直接使用此 最佳的情况下，找到从根节点到叶子节点的最佳路 类算法解决问题。 径，找出当前的最佳着法。 4.2.1穷尽搜索 博弈树中的每个叶节点，都可以用评估函数来 极大极小算法[54是典型的穷尽搜索方法，通过 对其优劣进行评分，该值对于博弈双方都是最优的。 它可以找到对于博弈双方都是最优的博弈值，但该 博弈树的子树在搜索完成之后会返回一个博弈值， 算法对博弈树的搜索是一种变性搜索，算法实现相 该值对于该子树是局部最优解，但是对整个博弈树 对麻烦。 来说并不一定是全局最优解。 负极大值算法在极大极小算法基础上进行了改 在计算机博弈研究中，求解过程中计算复杂性是 进，把极小节点值（返回给搜索引擎的局面估值）取 个难以逾越的难题。对于NP-complete、PSPACE-com- 绝对值，这样每次递归都选取最大值。 plete及EXPTIME-complete等难解的问题，不必将大量 4.2.2裁剪搜索 的精力花费在寻找问题的解析解上，而只能去寻求某 裁剪算法也称剪枝算法，是计算机博弈中最常 种近似解。国内外学者对计算机博弈的计算复杂 用的主流算法，它包括深度优先的Alpha-Beta剪枝 性[0)进行研究，证明了国际象棋和西洋跳棋属于 搜索)和以此为基础改进与增强的算法，如渴望窗 EXPTIME-complete问题，围棋属于PSPACE-hard问 口搜索(aspiration search)[s均、MTD(f)(memory-en- 题，中国象棋属于EXPTIME-complete问题s2。 hanced test driver with fand n)搜索Is6]等。在具体 对于许多棋种而言，一棵完整博弈树的规模非 应用中，合理地交叉使用各种搜索方法，可以具有更 常庞大，可以达到相当可观的天文数字，表1中列出 高的效率[6]」 几种知名棋种的复杂度[ 1)Alpha--Beta剪枝[9，] 表1几种知名棋类的复杂度 Alpha-Beta剪枝是在极大极小算法基础上的改 Table 1 Complexities of some well-known games 进算法，是其他剪枝算法的基础。目前，多数博弈程 状态空间复杂度 博弈树复杂度 序都采用负极大值形式的Alpha-Beta搜索算法。为 棋种 (10为底数) (10为底数) 保证Alpha-Beta搜索算法的效率，需要调整树的结 国际跳棋(100格) 30 54 构，即对搜索节点排序，确保尽早剪枝。 海克斯(11×11) 57 98 2)渴望搜索[54-5 国际象棋 渴望搜索是在Alpha-Beta搜索算法基础上，缩 46 123 中国象棋 小搜索范围的改进算法。渴望搜索从一开始就使用 48 150 小的窗口，从而在搜索之初，就可以进行大量的剪 亚马逊(10x10)》 40 212 枝。通常，渴望搜索与遍历深化技术结合使用，以提 将棋 71 226 高搜索性能。 六子棋 172 140 3)MTD(f)搜索[] 19路围棋 172 360 MTD(f)搜索实际上就是不断应用零窗口的 显然，把搜索树修整到合理范围内，减少其搜索 Alpha-Beta搜索，缩小上界和下界，并移动初始值使 空间，能够有效地进行展开和遍历搜索。 其接近最优着法。MTD(∫)算法简单高效，在国际
表示走一步棋；根部对应于开始位置，其叶表示对弈 到此结束。 生成博弈着法的过程，对应博弈树的搜 索与展开［４９］ 。 计算机博弈的过程是双方轮流给出 着法，使棋局向着对本方有利的方向发展，直至最后 的胜利。 图 ２ 博弈树示意图 Ｆｉｇ．２ Ｓｃｈｅｍａｔｉｃ ｄｉａｇｒａｍ ｏｆ ｇａｍｅ ｔｒｅｅ 搜索博弈树的目的就是在假设双方的走法都是 最佳的情况下，找到从根节点到叶子节点的最佳路 径，找出当前的最佳着法。 博弈树中的每个叶节点，都可以用评估函数来 对其优劣进行评分，该值对于博弈双方都是最优的。 博弈树的子树在搜索完成之后会返回一个博弈值， 该值对于该子树是局部最优解，但是对整个博弈树 来说并不一定是全局最优解。 在计算机博弈研究中，求解过程中计算复杂性是 个难以逾越的难题。 对于 ＮＰ⁃ｃｏｍｐｌｅｔｅ、ＰＳＰＡＣＥ⁃ｃｏｍ⁃ ｐｌｅｔｅ 及 ＥＸＰＴＩＭＥ⁃ｃｏｍｐｌｅｔｅ 等难解的问题，不必将大量 的精力花费在寻找问题的解析解上，而只能去寻求某 种近似解。 国内外学者对计算机博弈的计算复杂 性［５０－５１］进行研究，证明了国际象棋和西洋跳棋属于 ＥＸＰＴＩＭＥ⁃ｃｏｍｐｌｅｔｅ 问题，围棋属于 ＰＳＰＡＣＥ⁃ｈａｒｄ 问 题，中国象棋属于 ＥＸＰＴＩＭＥ⁃ｃｏｍｐｌｅｔｅ 问题［５２］ 。 对于许多棋种而言，一棵完整博弈树的规模非 常庞大，可以达到相当可观的天文数字，表 １ 中列出 几种知名棋种的复杂度［５３］ 。 表 １ 几种知名棋类的复杂度 Ｔａｂｌｅ １ Ｃｏｍｐｌｅｘｉｔｉｅｓ ｏｆ ｓｏｍｅ ｗｅｌｌ⁃ｋｎｏｗｎ ｇａｍｅｓ 棋种 状态空间复杂度 （１０ 为底数） 博弈树复杂度 （１０ 为底数） 国际跳棋（１００ 格） ３０ ５４ 海克斯 （１１×１１） ５７ ９８ 国际象棋 ４６ １２３ 中国象棋 ４８ １５０ 亚马逊（１０×１０） ４０ ２１２ 将棋 ７１ ２２６ 六子棋 １７２ １４０ １９ 路围棋 １７２ ３６０ 显然，把搜索树修整到合理范围内，减少其搜索 空间，能够有效地进行展开和遍历搜索。 ４．２ 博弈树搜索 以中国象棋、国际跳棋为代表的二人零和完备 信息博弈，其搜索理论已经很系统。 其中极大极小 算法［５３］是最基本的搜索算法，它奠定了计算机博弈 的理论基础。 以极大极小算法为基础的博弈树搜索 算法，从搜索方向考虑，可以分为深度优先搜索和宽 度优先搜索；从控制策略考虑，可以分为盲目搜索和 启发搜索；从搜索范围考虑，可以分为穷尽搜索、裁 剪搜索。 相对而言，宽度优先搜索、穷尽搜索和盲目搜索 算法时间和空间开销巨大，难以做到很深的搜索。 因此，在计算机博弈的实际应用中，很少直接使用此 类算法解决问题。 ４．２．１ 穷尽搜索 极大极小算法［５ ４］是典型的穷尽搜索方法，通过 它可以找到对于博弈双方都是最优的博弈值，但该 算法对博弈树的搜索是一种变性搜索，算法实现相 对麻烦。 负极大值算法在极大极小算法基础上进行了改 进，把极小节点值（返回给搜索引擎的局面估值）取 绝对值，这样每次递归都选取最大值。 ４．２．２ 裁剪搜索 裁剪算法也称剪枝算法，是计算机博弈中最常 用的主流算法，它包括深度优先的 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝 搜索［９］和以此为基础改进与增强的算法，如渴望窗 口搜索（ａｓｐｉｒａｔｉｏｎ ｓｅａｒｃｈ） ［５５］ 、ＭＴＤ（ ｆ ）（ｍｅｍｏｒｙ⁃ｅｎ⁃ ｈａｎｃｅｄ ｔｅｓｔ ｄｒｉｖｅｒ ｗｉｔｈ ｆ ａｎｄ ｎ ） 搜索［５６］ 等。 在具体 应用中，合理地交叉使用各种搜索方法，可以具有更 高的效率［５６］ 。 １）Ａｌｐｈａ⁃Ｂｅｔａ 剪枝［９，３３］ Ａｌｐｈａ⁃Ｂｅｔａ 剪枝是在极大极小算法基础上的改 进算法，是其他剪枝算法的基础。 目前，多数博弈程 序都采用负极大值形式的 Ａｌｐｈａ⁃Ｂｅｔａ 搜索算法。 为 保证 Ａｌｐｈａ⁃Ｂｅｔａ 搜索算法的效率，需要调整树的结 构，即对搜索节点排序，确保尽早剪枝。 ２）渴望搜索［ ５４－５５］ 渴望搜索是在 Ａｌｐｈａ⁃Ｂｅｔａ 搜索算法基础上，缩 小搜索范围的改进算法。 渴望搜索从一开始就使用 小的窗口，从而在搜索之初，就可以进行大量的剪 枝。 通常，渴望搜索与遍历深化技术结合使用，以提 高搜索性能。 ３）ＭＴＤ（ ｆ ）搜索［５６］ ＭＴＤ（ ｆ ） 搜索实际上就是不断应用零窗口的 Ａｌｐｈａ⁃Ｂｅｔａ 搜索，缩小上界和下界，并移动初始值使 其接近最优着法。 ＭＴＤ（ ｆ ）算法简单高效，在国际 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７９１·
.792 智能系统学报 第11卷 象棋、国际跳棋等博弈程序里，MTD(f)算法平均 的时间停止。 表现出色。 迭代深化利用Alpha-Beta剪枝算法对子节点排 此外，还有各种在Apha-Beta搜索基础上优化 序敏感的特点，使用上次迭代后得到的博弈值，作为 的算法，例如，有学者提出在博弈树同层结点中，用 当前迭代的搜索窗口估值，以此为启发式信息计算 广度优先搜索，接力式空窗探测，平均搜索效率高于 当前迭代的博弈值。另外，它利用时间控制遍历次 MTD(f)搜索[。通常，裁剪算法需要与置换表技 数，只要时间一到，搜索立即停止。在关键的开局和 术相结合，以减少博弈树的规模，提高搜索效率。 残局，由于分支较少，可以进行较深层次的搜索。 4.2.3置换表[5]技术 Alpha-Beta剪枝经过一系列技术如置换表、历史启 置换表是一个大的直接访问表，用来存储已经 发、迭代深化等增强后，其性能可大幅提高。 搜索过结点（或者子树）的结果，下次搜索遇到时直 4.2.6最佳优先算法 接运用。置换表的构造，一般使用Hash表和Zo 最佳优先的搜索算法，不受节点排序的影响，其 bristHash技术来实现。 搜索空间小于深度优先的最小树，理论上应该优于 合理使用置换表，可以提高搜索效率，当博弈树 深度优先。实际上，最佳优先算法仍处于理论研究 的深度很大时，置换表对内存空间要求巨大。通常 阶段。最佳优先算法分为两类：采用极大极小算法 的对策是对置换表分配有限大小，并采用散列方式 取值的SSS[63-64]算法和DUAL·算法，不采用极大 管理存取。具体应用到各个棋种中时，还要根据实 极小方法取值的B·[]和PB·[6算法。 际局面的节点类型，进行处理。 1)SSS·和DUAL·算法[63-64] 4.2.4启发式算法 SSS·和DUAL·算法都属于状态空间搜索 “启发”(Heuristic)是指通过排序让Alpha-Beta (State Space Search),把极大极小树看成状态图，在 剪枝的搜索树尽可能地接近最小树，优先搜索好的 不同的分支上展开多条路径，并且维护一个关于状 着法。启发通常有置换表启发、历史启发和杀手启 态图的全局信息表。这两种算法是两个操作相反的 发等常用的算法。 过程，前者在搜索深度为偶数的极大极小搜索中表 1)置换表启发[8-9 现较佳，后者则在深度为奇数搜索中较佳。 置换表启发是置换表与Alpha-Beta剪枝算法相 SSS·和DUAL·算法都过于复杂，难于理解，且时 结合的产物。在中国象棋等棋种中，通过引进置换 间和空间开销较大，在计算机博弈中实际应用较少。 表启发技术来增强搜索效率。 2)B·和PB·算法[6s-66 2)历史启发[0] B·算法用一个乐观值和一个悲观值来评价节点。 历史启发也是迎合alpha-beta搜索对节点排列 当根节点的一个孩子的悲观值不比所有其他节点的乐 顺序敏感的特点来提高剪枝效率的。它通过维护着 观值差的时候，B·算法就结束了。算法搜索控制的关 法历史，每当遇到好的着法，就给其历史得分一个相 键是尽快找到终止条件。由于它对局面估值的依赖性 应的增量，使其具有更高的优先被搜索的权利。 太强，估值的可信度将直接影响最终结果。 历史启发是一种基于经验的择序标准，它克服 PB·算法就是基于概率的B·算法，这个算法对 了基于知识择序存在的知识不足的缺点，使得算法 概率的准确估计比较敏感，实现困难。 的择序具有很强的动态适应性。 4.2.7随机搜索 3)杀手启发[61] 随机搜索有两种算法：拉斯维加斯算法和蒙特 杀手启发可以看作是历史启发的特例。它把同 卡罗算法。采样越多，前者越有机会找到最优解，后 层中引发剪枝最多的节点称为杀手，当下次搜索到 者则越接近最优解。 同一层时，如果杀手移动是合法的话，就优先搜索杀 通常，要根据问题的约束条件来确定随机算法， 手。杀手启发可以对着法进行动态重排序，且提高 如果对采样没有限制，但必须给出最优解，则采用拉 了置换表的使用效率。 斯维加斯算法。反之，如果要求在有限采样内求解， 4.2.5迭代深化[62 但不要求是最优解，则采用蒙特卡罗算法。 迭代深化也称为遍历深化，是一种常用的蛮力 计算机博弈中，每步着法的运算时间、堆栈空间 搜索机制，经常使用在深度优先搜索中。迭代深化 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 最初是作为控制时间的机制而提出的，通过对博弈 算法。由于非完备信息博弈也具有不确定性博弈的 树进行多次遍历，并逐渐提高搜索深度，一直到指定 一些特征，所以蒙特卡罗算法也适用于非完备信息
象棋、国际跳棋等博弈程序里，ＭＴＤ（ ｆ ） 算法平均 表现出色。 此外，还有各种在 Ａｌｐｈａ⁃Ｂｅｔａ 搜索基础上优化 的算法，例如，有学者提出在博弈树同层结点中，用 广度优先搜索，接力式空窗探测，平均搜索效率高于 ＭＴＤ（ ｆ ）搜索［５７］ 。 通常，裁剪算法需要与置换表技 术相结合，以减少博弈树的规模，提高搜索效率。 ４．２．３ 置换表［５８］技术 置换表是一个大的直接访问表，用来存储已经 搜索过结点（或者子树）的结果，下次搜索遇到时直 接运用。 置换表的构造，一般使用 Ｈａｓｈ 表和 Ｚｏ⁃ ｂｒｉｓｔＨａｓｈ 技术来实现。 合理使用置换表，可以提高搜索效率，当博弈树 的深度很大时，置换表对内存空间要求巨大。 通常 的对策是对置换表分配有限大小，并采用散列方式 管理存取。 具体应用到各个棋种中时，还要根据实 际局面的节点类型，进行处理。 ４．２．４ 启发式算法 “启发”（Ｈｅｕｒｉｓｔｉｃ）是指通过排序让 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝的搜索树尽可能地接近最小树，优先搜索好的 着法。 启发通常有置换表启发、历史启发和杀手启 发等常用的算法。 １）置换表启发［５８－５９］ 置换表启发是置换表与 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法相 结合的产物。 在中国象棋等棋种中，通过引进置换 表启发技术来增强搜索效率。 ２）历史启发［６０］ 历史启发也是迎合 ａｌｐｈａ⁃ｂｅｔａ 搜索对节点排列 顺序敏感的特点来提高剪枝效率的。 它通过维护着 法历史，每当遇到好的着法，就给其历史得分一个相 应的增量，使其具有更高的优先被搜索的权利。 历史启发是一种基于经验的择序标准，它克服 了基于知识择序存在的知识不足的缺点，使得算法 的择序具有很强的动态适应性。 ３）杀手启发［６１］ 杀手启发可以看作是历史启发的特例。 它把同 层中引发剪枝最多的节点称为杀手，当下次搜索到 同一层时，如果杀手移动是合法的话，就优先搜索杀 手。 杀手启发可以对着法进行动态重排序，且提高 了置换表的使用效率。 ４．２．５ 迭代深化［６２］ 迭代深化也称为遍历深化，是一种常用的蛮力 搜索机制，经常使用在深度优先搜索中。 迭代深化 最初是作为控制时间的机制而提出的，通过对博弈 树进行多次遍历，并逐渐提高搜索深度，一直到指定 的时间停止。 迭代深化利用 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法对子节点排 序敏感的特点，使用上次迭代后得到的博弈值，作为 当前迭代的搜索窗口估值，以此为启发式信息计算 当前迭代的博弈值。 另外，它利用时间控制遍历次 数，只要时间一到，搜索立即停止。 在关键的开局和 残局，由于分支较少，可以进行较深层次的搜索。 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝经过一系列技术如置换表、历史启 发、迭代深化等增强后，其性能可大幅提高。 ４．２．６ 最佳优先算法 最佳优先的搜索算法，不受节点排序的影响，其 搜索空间小于深度优先的最小树，理论上应该优于 深度优先。 实际上，最佳优先算法仍处于理论研究 阶段。 最佳优先算法分为两类：采用极大极小算法 取值的 ＳＳＳ ∗ ［６３－６４］算法和 ＤＵＡＬ ∗ 算法，不采用极大 极小方法取值的 Ｂ ∗ ［６５］和 ＰＢ ∗ ［６６］算法。 １）ＳＳＳ ∗和 ＤＵＡＬ ∗算法［６３－６４］ ＳＳＳ ∗ 和 ＤＵＡＬ ∗ 算 法 都 属 于 状 态 空 间 搜 索 （Ｓｔａｔｅ Ｓｐａｃｅ Ｓｅａｒｃｈ），把极大极小树看成状态图，在 不同的分支上展开多条路径，并且维护一个关于状 态图的全局信息表。 这两种算法是两个操作相反的 过程，前者在搜索深度为偶数的极大极小搜索中表 现较佳，后者则在深度为奇数搜索中较佳。 ＳＳＳ ∗和 ＤＵＡＬ ∗算法都过于复杂，难于理解，且时 间和空间开销较大，在计算机博弈中实际应用较少。 ２）Ｂ ∗和 ＰＢ ∗算法［６５－６６］ Ｂ ∗算法用一个乐观值和一个悲观值来评价节点。 当根节点的一个孩子的悲观值不比所有其他节点的乐 观值差的时候，Ｂ ∗算法就结束了。 算法搜索控制的关 键是尽快找到终止条件。 由于它对局面估值的依赖性 太强，估值的可信度将直接影响最终结果。 ＰＢ ∗算法就是基于概率的 Ｂ ∗算法，这个算法对 概率的准确估计比较敏感，实现困难。 ４．２．７ 随机搜索 随机搜索有两种算法：拉斯维加斯算法和蒙特 卡罗算法。 采样越多，前者越有机会找到最优解，后 者则越接近最优解。 通常，要根据问题的约束条件来确定随机算法， 如果对采样没有限制，但必须给出最优解，则采用拉 斯维加斯算法。 反之，如果要求在有限采样内求解， 但不要求是最优解，则采用蒙特卡罗算法。 计算机博弈中，每步着法的运算时间、堆栈空间 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 算法。 由于非完备信息博弈也具有不确定性博弈的 一些特征，所以蒙特卡罗算法也适用于非完备信息 ·７９２· 智 能 系 统 学 报 第 １１ 卷