第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 但不要求是最优解，则采用蒙特卡罗算法。 迭代深化也称为遍历深化，是一种常用的蛮力 计算机博弈中，每步着法的运算时间、堆栈空间 搜索机制，经常使用在深度优先搜索中。迭代深化 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 最初是作为控制时间的机制而提出的，通过对博弈 算法。由于非完备信息博弈也具有不确定性博弈的 树进行多次遍历，并逐渐提高搜索深度，一直到指定 一些特征，所以蒙特卡罗算法也适用于非完备信息
象棋、国际跳棋等博弈程序里，ＭＴＤ（ ｆ ） 算法平均 表现出色。 此外，还有各种在 Ａｌｐｈａ⁃Ｂｅｔａ 搜索基础上优化 的算法，例如，有学者提出在博弈树同层结点中，用 广度优先搜索，接力式空窗探测，平均搜索效率高于 ＭＴＤ（ ｆ ）搜索［５７］ 。 通常，裁剪算法需要与置换表技 术相结合，以减少博弈树的规模，提高搜索效率。 ４．２．３ 置换表［５８］技术 置换表是一个大的直接访问表，用来存储已经 搜索过结点（或者子树）的结果，下次搜索遇到时直 接运用。 置换表的构造，一般使用 Ｈａｓｈ 表和 Ｚｏ⁃ ｂｒｉｓｔＨａｓｈ 技术来实现。 合理使用置换表，可以提高搜索效率，当博弈树 的深度很大时，置换表对内存空间要求巨大。 通常 的对策是对置换表分配有限大小，并采用散列方式 管理存取。 具体应用到各个棋种中时，还要根据实 际局面的节点类型，进行处理。 ４．２．４ 启发式算法 “启发”（Ｈｅｕｒｉｓｔｉｃ）是指通过排序让 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝的搜索树尽可能地接近最小树，优先搜索好的 着法。 启发通常有置换表启发、历史启发和杀手启 发等常用的算法。 １）置换表启发［５８－５９］ 置换表启发是置换表与 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法相 结合的产物。 在中国象棋等棋种中，通过引进置换 表启发技术来增强搜索效率。 ２）历史启发［６０］ 历史启发也是迎合 ａｌｐｈａ⁃ｂｅｔａ 搜索对节点排列 顺序敏感的特点来提高剪枝效率的。 它通过维护着 法历史，每当遇到好的着法，就给其历史得分一个相 应的增量，使其具有更高的优先被搜索的权利。 历史启发是一种基于经验的择序标准，它克服 了基于知识择序存在的知识不足的缺点，使得算法 的择序具有很强的动态适应性。 ３）杀手启发［６１］ 杀手启发可以看作是历史启发的特例。 它把同 层中引发剪枝最多的节点称为杀手，当下次搜索到 同一层时，如果杀手移动是合法的话，就优先搜索杀 手。 杀手启发可以对着法进行动态重排序，且提高 了置换表的使用效率。 ４．２．５ 迭代深化［６２］ 迭代深化也称为遍历深化，是一种常用的蛮力 搜索机制，经常使用在深度优先搜索中。 迭代深化 最初是作为控制时间的机制而提出的，通过对博弈 树进行多次遍历，并逐渐提高搜索深度，一直到指定 的时间停止。 迭代深化利用 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝算法对子节点排 序敏感的特点，使用上次迭代后得到的博弈值，作为 当前迭代的搜索窗口估值，以此为启发式信息计算 当前迭代的博弈值。 另外，它利用时间控制遍历次 数，只要时间一到，搜索立即停止。 在关键的开局和 残局，由于分支较少，可以进行较深层次的搜索。 Ａｌｐｈａ⁃Ｂｅｔａ 剪枝经过一系列技术如置换表、历史启 发、迭代深化等增强后，其性能可大幅提高。 ４．２．６ 最佳优先算法 最佳优先的搜索算法，不受节点排序的影响，其 搜索空间小于深度优先的最小树，理论上应该优于 深度优先。 实际上，最佳优先算法仍处于理论研究 阶段。 最佳优先算法分为两类：采用极大极小算法 取值的 ＳＳＳ ∗ ［６３－６４］算法和 ＤＵＡＬ ∗ 算法，不采用极大 极小方法取值的 Ｂ ∗ ［６５］和 ＰＢ ∗ ［６６］算法。 １）ＳＳＳ ∗和 ＤＵＡＬ ∗算法［６３－６４］ ＳＳＳ ∗ 和 ＤＵＡＬ ∗ 算 法 都 属 于 状 态 空 间 搜 索 （Ｓｔａｔｅ Ｓｐａｃｅ Ｓｅａｒｃｈ），把极大极小树看成状态图，在 不同的分支上展开多条路径，并且维护一个关于状 态图的全局信息表。 这两种算法是两个操作相反的 过程，前者在搜索深度为偶数的极大极小搜索中表 现较佳，后者则在深度为奇数搜索中较佳。 ＳＳＳ ∗和 ＤＵＡＬ ∗算法都过于复杂，难于理解，且时 间和空间开销较大，在计算机博弈中实际应用较少。 ２）Ｂ ∗和 ＰＢ ∗算法［６５－６６］ Ｂ ∗算法用一个乐观值和一个悲观值来评价节点。 当根节点的一个孩子的悲观值不比所有其他节点的乐 观值差的时候，Ｂ ∗算法就结束了。 算法搜索控制的关 键是尽快找到终止条件。 由于它对局面估值的依赖性 太强，估值的可信度将直接影响最终结果。 ＰＢ ∗算法就是基于概率的 Ｂ ∗算法，这个算法对 概率的准确估计比较敏感，实现困难。 ４．２．７ 随机搜索 随机搜索有两种算法：拉斯维加斯算法和蒙特 卡罗算法。 采样越多，前者越有机会找到最优解，后 者则越接近最优解。 通常，要根据问题的约束条件来确定随机算法， 如果对采样没有限制，但必须给出最优解，则采用拉 斯维加斯算法。 反之，如果要求在有限采样内求解， 但不要求是最优解，则采用蒙特卡罗算法。 计算机博弈中，每步着法的运算时间、堆栈空间 都是有限的，且仅要求局部优解，适合采用蒙特卡罗 算法。 由于非完备信息博弈也具有不确定性博弈的 一些特征，所以蒙特卡罗算法也适用于非完备信息 ·７９２· 智 能 系 统 学 报 第 １１ 卷
第6期 王亚杰，等：计算机博弈的研究与发展 ·793. 博弈。 面、越准确，获胜的机率就会越高。但是，博弈有个 l)蒙特卡罗搜索(MCTS,Monte Carlo Tree 很重要的约束条件就是时间。评估中考虑的问题越 Search)【6-0 全面细致，则耗费的时间就越多，搜索的深度和速度 在人工智能的问题中，蒙特卡罗搜索是一种最 必然受到影响。另外，随着搜索深度加深，信息处理 优决策方法，它结合了随机模拟的一般性和树搜索 量也会大幅提升。 的准确性。由于海量搜索空间、评估棋局和落子行 设计评估函数需要考虑诸多因素，在完全信息 为的难度，围棋长期以来被视为人工智能领域最具 博弈中双方的子力、领地、位置、空间、机动性、拍节 挑战的经典游戏。近年来，MCTS在类似计算机围 威胁、形状、图案都可以作为评估参数，非完备信息 棋等完备信息博弈、多人博弈以及其他随机类博弈 博弈中除了己方已知参数外，还要猜测对手的情况 难题上的成功应用而受到快速关注。理论上， 并通过量化后加权组合而成。 MCTS可以被用在以{状态，行动}定义并用模拟预 国内外有不少学者在计算机博弈评估方面做了 测输出结果的任何领域。 大量深入研究[。针对不同棋种的特点，学者们提 基本的MCTS算法根据模拟的输出结果，按照 出了各种不同的方式进行评估与优化：通过博弈记 节点构造博弈树，其过程如图3所示，包括路径选择 录来评估博弈树搜索[]：针对六子棋应用遗传算法 (Selection)、节点扩展(Expansion)、模拟实验(Simu- 进行寻优处理，优化机器博弈评估函数[：在中国 lation)、反向传播(Backpropagation)4个步骤。 象棋里，把自适应遗传算法引入评估函数中，通过锦 多次重复 标赛算法对评估函数中的参数组合进行自动调整和 优化]：根据棋子的数量、移动范围、攻击范围、子 路径 节点 摸拟 反向 选择 扩展 实验 传播 力攻击力、盘面分值和占弧价值等对苏拉卡尔塔棋 局面评估函数进行了研究[0]：根据亚马逊棋领地」 图3构造MCTS博弈树的过程 位置和机动性等特征在不同阶段的重要程度及权重 Fig.3 Process of constructing the MCTS game tree 值，给出一个分阶段的评估函数[，4]。 MCTS算法适用于有较大分支因子的博弈程 提高计算机博弈能力不能单纯依靠加大搜索深 序，如AlphaGo就是采用MCTS算法进行搜索)。 度，还需要将必要的相关博弈知识引人到相应的博 2)UCT算法[13,25】 弈搜索中，只有协调搜索算法与评估函数，博弈系统 UCT算法，即上限置信区间算法，是一种基于 才能发挥有效作用。 MCTS发展的博弈树搜索算法，该算法通过扩展 UCB(upper confidence bound)到极大极小树搜索， 6综合优化技术 将MCTS方法与UCB公式结合。 计算机博弈中，目前应用较多的综合优化技术 UCB计算方法如公式1所示，在向下遍历博弈 主要有并行计算、遗传算法和基于神经网络的深度 树时，通过选择最大化该值来实现节点的选择。 学习。 In N 6.1并行计算 UCB=U:+C× 并行计算4，]是为了提高计算速度，把博弈树 (1) 动态分开，发挥计算机多CPU强大的并行处理能 式中：v:是节点i估计的值，n:是节点i被访问的次 力，同时执行多个指令的算法。它不裁剪和缩小博 数，而N是其父节点已被访问的总次数，C是可调参 弈树的规模，通过提高搜索速度，而进行优化系统。 数。相对于传统的搜索算法，UCT时间可控，具有 并行计算有两种体系，单机体系SMP(Symmet- 更好的鲁棒性，可以非对称动态扩展博弈树，在超大 ric Multiprocessor)和分布式体系Cluster(计算机集 规模博弈树的搜索过程中，表现出时间和空间方面 群)，对应多线程并行和多机并行。两者最大的区 的优势。目前，UCT在搜索规模较大的完备信息博 别是，前者可以共享存储器（并且共享同一地址的 弈、复杂的多人博弈、非完备信息博弈以及随机类博 存储单元)，后者则必须通过网络来交换数据。由 弈项目中，表现出色[)。 于博弈搜索通常需要用到置换表，所以适合以SMP 的方式多线程并行处理，但随着大数据、云计算等技 5局面评估 术的成熟与完善，计算机集群技术将被越来越多地 在计算机博弈系统中，对博弈局面评估得越全 运用到计算机博弈中
博弈。 １） 蒙 特 卡 罗 搜 索 （ ＭＣＴＳ， Ｍｏｎｔｅ Ｃａｒｌｏ Ｔｒｅｅ Ｓｅａｒｃｈ） ［６７－７０］ 在人工智能的问题中，蒙特卡罗搜索是一种最 优决策方法，它结合了随机模拟的一般性和树搜索 的准确性。 由于海量搜索空间、评估棋局和落子行 为的难度，围棋长期以来被视为人工智能领域最具 挑战的经典游戏。 近年来，ＭＣＴＳ 在类似计算机围 棋等完备信息博弈、多人博弈以及其他随机类博弈 难题上的成功应用而受到快速关注［７１］ 。 理论上， ＭＣＴＳ 可以被用在以｛状态，行动｝定义并用模拟预 测输出结果的任何领域。 基本的 ＭＣＴＳ 算法根据模拟的输出结果，按照 节点构造博弈树，其过程如图 ３ 所示，包括路径选择 （Ｓｅｌｅｃｔｉｏｎ）、节点扩展（Ｅｘｐａｎｓｉｏｎ）、模拟实验（Ｓｉｍｕ⁃ ｌａｔｉｏｎ）、反向传播（Ｂａｃｋｐｒｏｐａｇａｔｉｏｎ）４ 个步骤。 图 ３ 构造 ＭＣＴＳ 博弈树的过程 Ｆｉｇ．３ Ｐｒｏｃｅｓｓ ｏｆ ｃｏｎｓｔｒｕｃｔｉｎｇ ｔｈｅ ＭＣＴＳ ｇａｍｅ ｔｒｅｅ ＭＣＴＳ 算法适用于有较大分支因子的博弈程 序，如 ＡｌｐｈａＧｏ 就是采用 ＭＣＴＳ 算法进行搜索［３］ 。 ２）ＵＣＴ 算法［ １３，２５ ］ ＵＣＴ 算法，即上限置信区间算法，是一种基于 ＭＣＴＳ 发展的博弈树搜索算法，该算法通过扩展 ＵＣＢ（ ｕｐｐｅｒ ｃｏｎｆｉｄｅｎｃｅ ｂｏｕｎｄ） 到极大极小树搜索， 将 ＭＣＴＳ 方法与 ＵＣＢ 公式结合。 ＵＣＢ 计算方法如公式 １ 所示，在向下遍历博弈 树时，通过选择最大化该值来实现节点的选择。 ＵＣＢ ＝ ｖｉ ＋ Ｃ × ｌｎ Ｎ ｎｉ （１） 式中： ｖｉ 是节点 ｉ 估计的值，ｎｉ 是节点 ｉ 被访问的次 数，而 Ｎ 是其父节点已被访问的总次数，Ｃ 是可调参 数。 相对于传统的搜索算法，ＵＣＴ 时间可控，具有 更好的鲁棒性，可以非对称动态扩展博弈树，在超大 规模博弈树的搜索过程中，表现出时间和空间方面 的优势。 目前，ＵＣＴ 在搜索规模较大的完备信息博 弈、复杂的多人博弈、非完备信息博弈以及随机类博 弈项目中，表现出色［７１］ 。 ５ 局面评估 在计算机博弈系统中，对博弈局面评估得越全 面、越准确，获胜的机率就会越高。 但是，博弈有个 很重要的约束条件就是时间。 评估中考虑的问题越 全面细致，则耗费的时间就越多，搜索的深度和速度 必然受到影响。 另外，随着搜索深度加深，信息处理 量也会大幅提升。 设计评估函数需要考虑诸多因素，在完全信息 博弈中双方的子力、领地、位置、空间、机动性、拍节、 威胁、形状、图案都可以作为评估参数，非完备信息 博弈中除了己方已知参数外，还要猜测对手的情况， 并通过量化后加权组合而成。 国内外有不少学者在计算机博弈评估方面做了 大量深入研究［７２］ 。 针对不同棋种的特点，学者们提 出了各种不同的方式进行评估与优化：通过博弈记 录来评估博弈树搜索［７３］ ；针对六子棋应用遗传算法 进行寻优处理，优化机器博弈评估函数［４０］ ；在中国 象棋里，把自适应遗传算法引入评估函数中，通过锦 标赛算法对评估函数中的参数组合进行自动调整和 优化［１９］ ；根据棋子的数量、移动范围、攻击范围、子 力攻击力、盘面分值和占弧价值等对苏拉卡尔塔棋 局面评估函数进行了研究［４０］ ；根据亚马逊棋领地、 位置和机动性等特征在不同阶段的重要程度及权重 值，给出一个分阶段的评估函数［４７，７４］ 。 提高计算机博弈能力不能单纯依靠加大搜索深 度，还需要将必要的相关博弈知识引入到相应的博 弈搜索中，只有协调搜索算法与评估函数，博弈系统 才能发挥有效作用。 ６ 综合优化技术 计算机博弈中，目前应用较多的综合优化技术 主要有并行计算、遗传算法和基于神经网络的深度 学习。 ６．１ 并行计算 并行计算［１４，７５］ 是为了提高计算速度，把博弈树 动态分开，发挥计算机多 ＣＰＵ 强大的并行处理能 力，同时执行多个指令的算法。 它不裁剪和缩小博 弈树的规模，通过提高搜索速度，而进行优化系统。 并行计算有两种体系，单机体系 ＳＭＰ（ Ｓｙｍｍｅｔ⁃ ｒｉｃ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ）和分布式体系 Ｃｌｕｓｔｅｒ（计算机集 群），对应多线程并行和多机并行。 两者最大的区 别是，前者可以共享存储器（并且共享同一地址的 存储单元），后者则必须通过网络来交换数据。 由 于博弈搜索通常需要用到置换表，所以适合以 ＳＭＰ 的方式多线程并行处理，但随着大数据、云计算等技 术的成熟与完善，计算机集群技术将被越来越多地 运用到计算机博弈中。 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７９３·
.794 智能系统学报 第11卷 6.2遗传算法 方法来增强传统学习算法的性能，提升计算机博弈 遗传算法]是人工智能领域的关键技术，它是 水平，仍是今后研究的重点。 一种非数值、并行、随机优化、搜索启发式的算法，通 过模拟自然进化过程随机化搜索最优解。它采用概 策略网络 价值网络 率化的寻优方法，能自动获取和指导优化的搜索空 P(als) vAs) ● 间，自适应地调整搜索方向，不需要确定的规则，同 时具有内在的隐并行性和更好的全局寻优能力。 遗传算法是解决搜索问题的一种通用算法，在 计算机博弈中，遗传算法通常被用于搜索、自适应调 整和优化局面评估参数。它的基本思想是将博弈树 看作遗传操作的种群，博弈树中由根节点到叶子节 点组成的所有子树为种群中的个体。根据优化目标 设计评估函数，计算种群中每个个体的适应度函数 值，依据适应度函数值的大小确定初始种群，让适应 性强（适应度函数值大）的个体获得较多的交叉、遗 传机会，生成新的子代个体，通过反复迭代，可得到 图4 AlphaGo神经网络体系结构原理图 Fig.4 Schematic representation of the neural network 满意解。 architecture used in AlphaGo 采用遗传算法优化局面估值时，可根据博弈程 序与其他程序对弈的结果，检验某一组参数获胜的 面临的问题与展望 机率。经过多次试验，通常可以找到较好的估值参 数。传统的算法一般只能维护一组最优解，遗传算 近年来，计算机博弈给人工智能带来了很多重 法可以同时维护多组最优解。在实践中，遗传算法 要的方法和理论，在二人零和完备信息博弈研究方 被引入了中国象棋、国际象棋、亚马逊等棋搜索与评 面，其知识结构系统层次清晰，已经取得了许多惊人 估优化中，效果还是很明显的」 的成果，其中，关于基于神经网络深度学习技术的研 6.3深度学习 究与运用，已经达到新的高度。在中国象棋、围棋等 深度学习是基于多层网络结构的一种机器学习 完全信息的计算机博弈中，尽管状态空间和搜索树 方法，它逐层提取抽象特征，通过多层非线性传输， 复杂度都较大，但经过大量学习与训练，结合大规模 完成复杂的目标函数系统逼近。深度学习领域典型 搜索算法，计算机占尽优势[)。 的网络模型包括卷积神经网络(convolutional neural 另一个方面，对于军棋、麻将、桥牌、扑克等非完 networks,CNN)、深层玻尔兹曼机(deep boltzmann 备信息博弈，以及具有模糊性和随机性的不确定性 machine,DBM)和堆叠自动编码器(stacked auto-en- 博弈，虽然在基于案例的策略研究方面有了一定进 coder,SAE)等76J。 展，但因其相关理论研究还不成熟，相应的程序智力 近几年，基于人工神经网络的深度学习技术逐 有限，仍难以战胜人类真正的高手。因此，在非完备 渐被应用于计算机博弈中3,9】，人工智能围棋程序 信息和不确定性机器博弈方面，具有高效学习与抽 AlphaGo是其典型代表[)。AlphaGo成功的关键在 象思维能力的博弈技术还有待进一步研究。另外， 于拥有两个大脑一落子选择器(move picker)和棋 在计算机博弈平台方面的研究投入相对较少，对计 局评估器(position evaluator)。分别基于两种不同 算机博弈技术的发展也有所制约。 的深度神经网络一策略网络(policy network)和价 可以预见，在不远的将来，计算机博弈技术将融 值网络(value network),如图4所示。前者用于学 入各个领域的应用中，具体体现在如下几点： 习高水平棋手的棋谱，获得如何在盘面落子的棋感： 1)计算机博弈研究的内容将不断拓宽，处理的 后者通过机器的增强型学习，获得形势判断的棋感。 问题复杂程度越来越高，信息量将越来越大。为解 这两个棋感通过蒙特卡罗搜索的技术进行验证，使 决某类特定问题，技术方法将集成化，计算机博弈技 AlphaGo实现了技术突破。 术将与并行计算、大数据技术等相关技术结合。 2)计算机博弈软件与使件的结合越来越密切！ 尽管深度学习技术在围棋方面取得了前所未有 固化博弈系统的智能硬件产品将越来越多地出现在 的成功，但在拓展应用方面，如何合理利用深度学习 人们的生活中，典型的应用包括：有博弈思维能力机
６．２ 遗传算法 遗传算法［１５］是人工智能领域的关键技术，它是 一种非数值、并行、随机优化、搜索启发式的算法，通 过模拟自然进化过程随机化搜索最优解。 它采用概 率化的寻优方法，能自动获取和指导优化的搜索空 间，自适应地调整搜索方向，不需要确定的规则，同 时具有内在的隐并行性和更好的全局寻优能力。 遗传算法是解决搜索问题的一种通用算法，在 计算机博弈中，遗传算法通常被用于搜索、自适应调 整和优化局面评估参数。 它的基本思想是将博弈树 看作遗传操作的种群，博弈树中由根节点到叶子节 点组成的所有子树为种群中的个体。 根据优化目标 设计评估函数，计算种群中每个个体的适应度函数 值，依据适应度函数值的大小确定初始种群，让适应 性强（适应度函数值大）的个体获得较多的交叉、遗 传机会，生成新的子代个体，通过反复迭代，可得到 满意解。 采用遗传算法优化局面估值时，可根据博弈程 序与其他程序对弈的结果，检验某一组参数获胜的 机率。 经过多次试验，通常可以找到较好的估值参 数。 传统的算法一般只能维护一组最优解，遗传算 法可以同时维护多组最优解。 在实践中，遗传算法 被引入了中国象棋、国际象棋、亚马逊等棋搜索与评 估优化中，效果还是很明显的［１９］ 。 ６．３ 深度学习 深度学习是基于多层网络结构的一种机器学习 方法，它逐层提取抽象特征，通过多层非线性传输， 完成复杂的目标函数系统逼近。 深度学习领域典型 的网络模型包括卷积神经网络（ ｃｏｎｖｏｌｕｔｉｏｎａｌ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ，ＣＮＮ）、深层玻尔兹曼机（ ｄｅｅｐ ｂｏｌｔｚｍａｎｎ ｍａｃｈｉｎｅ，ＤＢＭ）和堆叠自动编码器（ ｓｔａｃｋｅｄ ａｕｔｏ⁃ｅｎ⁃ ｃｏｄｅｒ，ＳＡＥ）等［７ ６ ］ 。 近几年，基于人工神经网络的深度学习技术逐 渐被应用于计算机博弈中［３ ，２９ ］ ，人工智能围棋程序 ＡｌｐｈａＧｏ 是其典型代表［３］ 。 ＡｌｐｈａＧｏ 成功的关键在 于拥有两个大脑———落子选择器（ｍｏｖｅ ｐｉｃｋｅｒ）和棋 局评估器（ ｐｏｓｉｔｉｏｎ ｅｖａｌｕａｔｏｒ）。 分别基于两种不同 的深度神经网络———策略网络（ｐｏｌｉｃｙ ｎｅｔｗｏｒｋ）和价 值网络（ ｖａｌｕｅ ｎｅｔｗｏｒｋ），如图 ４ 所示。 前者用于学 习高水平棋手的棋谱，获得如何在盘面落子的棋感； 后者通过机器的增强型学习，获得形势判断的棋感。 这两个棋感通过蒙特卡罗搜索的技术进行验证，使 ＡｌｐｈａＧｏ 实现了技术突破。 尽管深度学习技术在围棋方面取得了前所未有 的成功，但在拓展应用方面，如何合理利用深度学习 方法来增强传统学习算法的性能，提升计算机博弈 水平，仍是今后研究的重点。 图 ４ ＡｌｐｈａＧｏ 神经网络体系结构原理图 Ｆｉｇ．４ Ｓｃｈｅｍａｔｉｃ ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｏｆ ｔｈｅ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ａｒｃｈｉｔｅｃｔｕｒｅ ｕｓｅｄ ｉｎ ＡｌｐｈａＧｏ ７ 面临的问题与展望 近年来，计算机博弈给人工智能带来了很多重 要的方法和理论，在二人零和完备信息博弈研究方 面，其知识结构系统层次清晰，已经取得了许多惊人 的成果，其中，关于基于神经网络深度学习技术的研 究与运用，已经达到新的高度。 在中国象棋、围棋等 完全信息的计算机博弈中，尽管状态空间和搜索树 复杂度都较大，但经过大量学习与训练，结合大规模 搜索算法，计算机占尽优势［７８］ 。 另一个方面，对于军棋、麻将、桥牌、扑克等非完 备信息博弈，以及具有模糊性和随机性的不确定性 博弈，虽然在基于案例的策略研究方面有了一定进 展，但因其相关理论研究还不成熟，相应的程序智力 有限，仍难以战胜人类真正的高手。 因此，在非完备 信息和不确定性机器博弈方面，具有高效学习与抽 象思维能力的博弈技术还有待进一步研究。 另外， 在计算机博弈平台方面的研究投入相对较少，对计 算机博弈技术的发展也有所制约。 可以预见，在不远的将来，计算机博弈技术将融 入各个领域的应用中，具体体现在如下几点： １）计算机博弈研究的内容将不断拓宽，处理的 问题复杂程度越来越高，信息量将越来越大。 为解 决某类特定问题，技术方法将集成化，计算机博弈技 术将与并行计算、大数据技术等相关技术结合。 ２）计算机博弈软件与硬件的结合越来越密切， 固化博弈系统的智能硬件产品将越来越多地出现在 人们的生活中，典型的应用包括：有博弈思维能力机 ·７９４· 智 能 系 统 学 报 第 １１ 卷
第6期 王亚杰，等：计算机博弈的研究与发展 .795. 器人、智能决策控制系统的无人驾驶汽车和无人机。 [6]SHANNON C E.Programming a computer for playing chess 3)计算机博弈技术将与其他学科进一步融合， [J].Philosophical magazine,1950,41(314):2562275. 越来越紧密地应用经济、生活、军事等领域，注重实 [7]BERNSTEIN A,ARBUCKLE T,DE V ROBERTS M,et al. 际工程应用，解决实际问题。在虚拟现实仿真方面， A chess playing program for the IBM 704[C]//Proceedings 特别是游戏与教育方面拥有广阔的应用前景。 of the May 6-8,1958,Western Joint Computer Confer- 4)计算机博弈技术将呈现高度智能化趋势，通 ence:Contrasts in Computers.New York,NY,USA: ACM.1958:157-159 过与遗传算法、人工神经网络、类脑思维等人工智能 [8]SAMUEL A L.Some studies in machine learning using the 技术进一步融合，类似基于神经网络深度学习的智 game of checkers.Il;recent progress[J].IBM journal of re- 能技术将大量涌现，使得计算机博弈程序的类脑智 search and development,1967,11(6):601-617. 能越来越高。 [9]FULLER S H,GASCHNIG J G,GILLOGLY J J.Analysis 5)合理拓展现有的博弈技术，深入研究更加智 of the alpha-beta pruning algorithm[R].Carnegie:Carnegie 能的普适算法，构建一个通用的计算机博弈系统，也 Mellon University,1973. 将成为未来计算机博弈研究的重点。 [10]KORF R E.Depth-first iterative-deepening:an optimal ad- missible tree search[].Artificial intelligence,1985,27 8结束语 (1):97-109. 伴随着人工智能科学发展的60周年，计算机博 [11]ROIZEN I,PEARL J.A minimax algorithm better than al- 弈也经历了起步、发展、成熟、飞跃4个阶段。依托 pha-beta?Yes and No[J].Artificial intelligence,1983, 21(1/2):199-220. 各种形式的竞赛，极大地促进了学术交流，检验了新 [12]RUMELHART D E,HINTON G E.WILLIAMS R J. 技术，推动了博弈的研究与发展。当前完备信息博 Learning representations by back-propagating errors[J]. 弈技术相对比较成熟，非完备信息博弈和随机类博 Nature.1986,323(6088):533-536. 弈技术还需进一步发展。深度学习算法在AlphaGo [13]GELLY S,SILVER D.Combining online and offline 围棋计算机博弈中的成功应用，引发了世界范围内 knowledge in UCT[C]//Proceedings of the 24th Interna- 对人工智能技术的高度关注，调动了更多的专家学 tional Conference on Machine Learning.New York,USA: 者开展深入研究的积极性。尽管在计算机博弈领域 ACM,2007:273-280. 还存在着各种各样的问题，许多工作还需要向更广 [14]李之棠，陈华民.博弈树并行搜索算法[J].小型微型 领域和更深层次推进，但是随着研究人员的不断增 计算机系统，1998,19(10)：53-56. 加以及计算机博弈技术在各个领域的广泛应用，将 LI Zhitang,CHEN Huamin.Parallel game-tree search[J]. 会产生越来越多的研究成果。计算机博弈是一个颇 Mini-micro systems,1998,19(10):53-56. 有发展前途的研究领域。 [15]DAVID-TABIBI O,KOPPEL M,NETANYAHU N S.Ge- netic algorithms for automatic search tuning[J].ICGA 参考文献： journal,2010,33(2):67-79. [16]HINTON G E,SALAKHUTDINOV RR.Reducing the di- [1]徐心和，邓志立，王骄，等.机器博弈研究面临的各种 mensionality of data with neural networks[J].Science, 挑战[J].智能系统学报，2008,3(4)：288-293. 2006,313(5786):504-507 XU Xinhe,DENG Zhili,WANG Jiao,et al.Challenging is- [17]WU I C,CHANG H C.Threat-based proof search for Con- sues facing computer game research[J].CAAl transactions nect 6[R].Taiwan,China:National Chiao Tung Universi- on intelligent systems,2008,3(4):288-293. y,2006. [2]徐心和.计算机博弈一对于人类思维的挑战[J].中国 [18]徐心和，王骄.中国象棋计算机博弈关键技术分析[刀 科技博览，2009(34)：194-195. 小型微型计算机系统，2006,27(6)：961-969 [3]SILVER D,HUANG Ajia,MADDISON C J,et al.Maste- XU Xinhe,WANG Jiao.Key technologies analysis of Chi- ring the game of Go with deep neural networks and tree nese chess computer game[J].Mini-micro systems,2006, search[J].Nature,2016,529(7587):484-489 27(6):961-969. [4]BENCH-CAPON T J M,DUNNE P E.Argumentation in ar- [19]王骄，王涛，罗艳红，等.中国象棋计算机博弈系统评 tificial intelligence[J].Artificial intelligence,2007,171 估函数的自适应遗传算法实现[J].东北大学学报：自 (10/15):619-641. 然科学版.2005,26(10)：949-952. [5]PENNISI E.Breakthrough of the year:human genetic varia- WANG Jiao,WANG Tao,LUO Yanhong,et al.Imple- tion[J].Science,2007,318(5858):1842-1843 mentation of adaptive genetic algorithm of evaluation func-
器人、智能决策控制系统的无人驾驶汽车和无人机。 ３）计算机博弈技术将与其他学科进一步融合， 越来越紧密地应用经济、生活、军事等领域，注重实 际工程应用，解决实际问题。 在虚拟现实仿真方面， 特别是游戏与教育方面拥有广阔的应用前景。 ４）计算机博弈技术将呈现高度智能化趋势，通 过与遗传算法、人工神经网络、类脑思维等人工智能 技术进一步融合，类似基于神经网络深度学习的智 能技术将大量涌现，使得计算机博弈程序的类脑智 能越来越高。 ５）合理拓展现有的博弈技术，深入研究更加智 能的普适算法，构建一个通用的计算机博弈系统，也 将成为未来计算机博弈研究的重点。 ８ 结束语 伴随着人工智能科学发展的 ６０ 周年，计算机博 弈也经历了起步、发展、成熟、飞跃 ４ 个阶段。 依托 各种形式的竞赛，极大地促进了学术交流，检验了新 技术，推动了博弈的研究与发展。 当前完备信息博 弈技术相对比较成熟，非完备信息博弈和随机类博 弈技术还需进一步发展。 深度学习算法在 ＡｌｐｈａＧｏ 围棋计算机博弈中的成功应用，引发了世界范围内 对人工智能技术的高度关注，调动了更多的专家学 者开展深入研究的积极性。 尽管在计算机博弈领域 还存在着各种各样的问题，许多工作还需要向更广 领域和更深层次推进，但是随着研究人员的不断增 加以及计算机博弈技术在各个领域的广泛应用，将 会产生越来越多的研究成果。 计算机博弈是一个颇 有发展前途的研究领域。 参考文献： ［１］徐心和， 邓志立， 王骄， 等． 机器博弈研究面临的各种 挑战［Ｊ］． 智能系统学报， ２００８， ３（４）： ２８８－２９３． ＸＵ Ｘｉｎｈｅ， ＤＥＮＧ Ｚｈｉｌｉ， ＷＡＮＧ Ｊｉａｏ， ｅｔ ａｌ． Ｃｈａｌｌｅｎｇｉｎｇ ｉｓ⁃ ｓｕｅｓ ｆａｃｉｎｇ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｒｅｓｅａｒｃｈ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００８， ３（４）： ２８８－２９３． ［２］徐心和． 计算机博弈———对于人类思维的挑战［Ｊ］． 中国 科技博览， ２００９（３４）： １９４－１９５． ［３］ＳＩＬＶＥＲ Ｄ， ＨＵＡＮＧ Ａｊｉａ， ＭＡＤＤＩＳＯＮ Ｃ Ｊ， ｅｔ ａｌ． Ｍａｓｔｅ⁃ ｒｉｎｇ ｔｈｅ ｇａｍｅ ｏｆ Ｇｏ ｗｉｔｈ ｄｅｅｐ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ａｎｄ ｔｒｅｅ ｓｅａｒｃｈ［Ｊ］． Ｎａｔｕｒｅ， ２０１６， ５２９（７５８７）： ４８４－４８９． ［４］ＢＥＮＣＨ⁃ＣＡＰＯＮ Ｔ Ｊ Ｍ， ＤＵＮＮＥ Ｐ Ｅ． Ａｒｇｕｍｅｎｔａｔｉｏｎ ｉｎ ａｒ⁃ ｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００７， １７１ （１０ ／ １５）： ６１９－６４１． ［５］ＰＥＮＮＩＳＩ Ｅ． Ｂｒｅａｋｔｈｒｏｕｇｈ ｏｆ ｔｈｅ ｙｅａｒ： ｈｕｍａｎ ｇｅｎｅｔｉｃ ｖａｒｉａ⁃ ｔｉｏｎ［Ｊ］． Ｓｃｉｅｎｃｅ， ２００７， ３１８（５８５８）： １８４２－１８４３． ［６］ＳＨＡＮＮＯＮ Ｃ Ｅ． Ｐｒｏｇｒａｍｍｉｎｇ ａ ｃｏｍｐｕｔｅｒ ｆｏｒ ｐｌａｙｉｎｇ ｃｈｅｓｓ ［Ｊ］． Ｐｈｉｌｏｓｏｐｈｉｃａｌ ｍａｇａｚｉｎｅ， １９５０， ４１（３１４）： ２５６２２７５． ［ ７］ＢＥＲＮＳＴＥＩＮ Ａ， ＡＲＢＵＣＫＬＥ Ｔ， ＤＥ Ｖ ＲＯＢＥＲＴＳ Ｍ， ｅｔ ａｌ． Ａ ｃｈｅｓｓ ｐｌａｙｉｎｇ ｐｒｏｇｒａｍ ｆｏｒ ｔｈｅ ＩＢＭ ７０４［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｍａｙ ６ － ８， １９５８， Ｗｅｓｔｅｒｎ Ｊｏｉｎｔ Ｃｏｍｐｕｔｅｒ Ｃｏｎｆｅｒ⁃ ｅｎｃｅ： Ｃｏｎｔｒａｓｔｓ ｉｎ Ｃｏｍｐｕｔｅｒｓ． Ｎｅｗ Ｙｏｒｋ， ＮＹ， ＵＳＡ： ＡＣＭ， １９５８： １５７－１５９． ［８］ＳＡＭＵＥＬ Ａ Ｌ． Ｓｏｍｅ ｓｔｕｄｉｅｓ ｉｎ ｍａｃｈｉｎｅ ｌｅａｒｎｉｎｇ ｕｓｉｎｇ ｔｈｅ ｇａｍｅ ｏｆ ｃｈｅｃｋｅｒｓ． ＩＩ： ｒｅｃｅｎｔ ｐｒｏｇｒｅｓｓ［Ｊ］． ＩＢＭ ｊｏｕｒｎａｌ ｏｆ ｒｅ⁃ ｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， １９６７， １１（６）： ６０１－６１７． ［９］ＦＵＬＬＥＲ Ｓ Ｈ， ＧＡＳＣＨＮＩＧ Ｊ Ｇ， ＧＩＬＬＯＧＬＹ Ｊ Ｊ． Ａｎａｌｙｓｉｓ ｏｆ ｔｈｅ ａｌｐｈａ⁃ｂｅｔａ ｐｒｕｎｉｎｇ ａｌｇｏｒｉｔｈｍ［Ｒ］． Ｃａｒｎｅｇｉｅ： Ｃａｒｎｅｇｉｅ Ｍｅｌｌｏｎ Ｕｎｉｖｅｒｓｉｔｙ， １９７３． ［１０］ＫＯＲＦ Ｒ Ｅ． Ｄｅｐｔｈ⁃ｆｉｒｓｔ ｉｔｅｒａｔｉｖｅ⁃ｄｅｅｐｅｎｉｎｇ： ａｎ ｏｐｔｉｍａｌ ａｄ⁃ ｍｉｓｓｉｂｌｅ ｔｒｅｅ ｓｅａｒｃｈ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８５， ２７ （１）： ９７－１０９． ［１１］ＲＯＩＺＥＮ Ｉ， ＰＥＡＲＬ Ｊ． Ａ ｍｉｎｉｍａｘ ａｌｇｏｒｉｔｈｍ ｂｅｔｔｅｒ ｔｈａｎ ａｌ⁃ ｐｈａ⁃ｂｅｔａ？ Ｙｅｓ ａｎｄ Ｎｏ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８３， ２１（１ ／ ２）： １９９－２２０． ［１２］ ＲＵＭＥＬＨＡＲＴ Ｄ Ｅ， ＨＩＮＴＯＮ Ｇ Ｅ， ＷＩＬＬＩＡＭＳ Ｒ Ｊ． Ｌｅａｒｎｉｎｇ ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ ｂｙ ｂａｃｋ⁃ｐｒｏｐａｇａｔｉｎｇ ｅｒｒｏｒｓ ［ Ｊ］． Ｎａｔｕｒｅ， １９８６， ３２３（６０８８）： ５３３－５３６． ［１３ ］ ＧＥＬＬＹ Ｓ， ＳＩＬＶＥＲ Ｄ． Ｃｏｍｂｉｎｉｎｇ ｏｎｌｉｎｅ ａｎｄ ｏｆｆｌｉｎｅ ｋｎｏｗｌｅｄｇｅ ｉｎ ＵＣＴ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２４ｔｈ Ｉｎｔｅｒｎａ⁃ ｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ． Ｎｅｗ Ｙｏｒｋ， ＵＳＡ： ＡＣＭ， ２００７： ２７３－２８０． ［１４］李之棠， 陈华民． 博弈树并行搜索算法［ Ｊ］． 小型微型 计算机系统， １９９８， １９（１０）： ５３－５６． ＬＩ Ｚｈｉｔａｎｇ， ＣＨＥＮ Ｈｕａｍｉｎ． Ｐａｒａｌｌｅｌ ｇａｍｅ⁃ｔｒｅｅ ｓｅａｒｃｈ［Ｊ］． Ｍｉｎｉ⁃ｍｉｃｒｏ ｓｙｓｔｅｍｓ， １９９８， １９（１０）： ５３－５６． ［１５］ＤＡＶＩＤ⁃ＴＡＢＩＢＩ Ｏ， ＫＯＰＰＥＬ Ｍ， ＮＥＴＡＮＹＡＨＵ Ｎ Ｓ． Ｇｅ⁃ ｎｅｔｉｃ ａｌｇｏｒｉｔｈｍｓ ｆｏｒ ａｕｔｏｍａｔｉｃ ｓｅａｒｃｈ ｔｕｎｉｎｇ ［ Ｊ ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２０１０， ３３（２）： ６７－７９． ［１６］ＨＩＮＴＯＮ Ｇ Ｅ， ＳＡＬＡＫＨＵＴＤＩＮＯＶ Ｒ Ｒ． Ｒｅｄｕｃｉｎｇ ｔｈｅ ｄｉ⁃ ｍｅｎｓｉｏｎａｌｉｔｙ ｏｆ ｄａｔａ ｗｉｔｈ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ ［ Ｊ］． Ｓｃｉｅｎｃｅ， ２００６， ３１３（５７８６）： ５０４－５０７． ［１７］ＷＵ Ｉ Ｃ， ＣＨＡＮＧ Ｈ Ｃ． Ｔｈｒｅａｔ⁃ｂａｓｅｄ ｐｒｏｏｆ ｓｅａｒｃｈ ｆｏｒ Ｃｏｎ⁃ ｎｅｃｔ ６［Ｒ］． Ｔａｉｗａｎ， Ｃｈｉｎａ： Ｎａｔｉｏｎａｌ Ｃｈｉａｏ Ｔｕｎｇ Ｕｎｉｖｅｒｓｉ⁃ ｔｙ， ２００６． ［１８］徐心和， 王骄． 中国象棋计算机博弈关键技术分析［ Ｊ］． 小型微型计算机系统， ２００６， ２７（６）： ９６１－９６９． ＸＵ Ｘｉｎｈｅ， ＷＡＮＧ Ｊｉａｏ． Ｋｅｙ ｔｅｃｈｎｏｌｏｇｉｅｓ ａｎａｌｙｓｉｓ ｏｆ Ｃｈｉ⁃ ｎｅｓｅ ｃｈｅｓｓ ｃｏｍｐｕｔｅｒ ｇａｍｅ［Ｊ］． Ｍｉｎｉ⁃ｍｉｃｒｏ ｓｙｓｔｅｍｓ， ２００６， ２７（６）： ９６１－９６９． ［１９］王骄， 王涛， 罗艳红， 等． 中国象棋计算机博弈系统评 估函数的自适应遗传算法实现［ Ｊ］． 东北大学学报： 自 然科学版， ２００５， ２６（１０）： ９４９－９５２． ＷＡＮＧ Ｊｉａｏ， ＷＡＮＧ Ｔａｏ， ＬＵＯ Ｙａｎｈｏｎｇ， ｅｔ ａｌ． Ｉｍｐｌｅ⁃ ｍｅｎｔａｔｉｏｎ ｏｆ ａｄａｐｔｉｖｅ ｇｅｎｅｔｉｃ ａｌｇｏｒｉｔｈｍ ｏｆ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃ⁃ 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７９５·
.796. 智能系统学报 第11卷 tion in Chinese chess computer game system[J].Journal of tion Processing Systems,vol 19.Cambridge:MIT Press, northeastern university:natural science,2005,26(10): 2007:153-160. 949-952. [30]COULOM R.Computing "Elo ratings"of move patterns in [20]魏钦刚，王骄，徐心和，等.中国象棋计算机博弈开局 the game of go[J].ICGA journal,2007,30(4):198- 库研究与设计[J].智能系统学报，2007,2(1)：85- 208. 89. [31]FERREIRA D R.Determining the strength of chess players WEI Qingang,WANG Jiao,XU Xinhe,et al.A study and based on actual play[J].ICGA journal,2012,35(1):3- design of opening-book of computer Chinese Chess[J]. 19. CAAI transactions on intelligent systems,2007,2(1):85 [32]NIJSSEN J A M,WINANDS M H M.Search policies in -89. multi-player games1[J].ICGA journal,2013,36(1):3- [21]徐长明，南晓斐，王骄，等.中国象棋机器博弈的时间 21. 自适应分配策略研究[J].智能系统学报，2006,1(2)： [33]LEIFKER D B,KANAL L N.A hybrid SSS'/Alpha-Beta 39-43. algorithm for parallel search of game trees[C]//Proceed- XU Changming,NAN Xiaofei,WANG Jiao,et al.Adap- ings of the 9th International Joint Conference on Artificial tive time allocation strategy in computer game of Chinese Intelligence.San Francisco,CA,USA:ACM,1985,2: Chess[]]CAAI transactions on intelligent systems,2006, 1044-1046. 1(2):39-43. [34]PLAAT A,SCHAEFFER J,PIJLS W,et al.Best-first [22]LIU Zhiqing.DOU Qing.Automatic pattern acquisition fixed-depth game-tree search in practice[C]//Proceedings from game records in GO[J.The journal of China univer- of the 14th International Joint Conference on Artificial In- sities of posts and telecommunications,2007,14(1): telligence.San Francisco,CA,USA:ACM,1995,1: 100-105. 273-279. [23]LIU Zhiqing,DOU Qing,LI Wenhong,et al.Automatic [35 BURNS E,LEMONS S,ZHOU Rong,et al.Best-first acquisition of pattern collocations in GO[J].The journal heuristic search for multi-core machines[C]//Proceedings of China universities of posts and telecommunications, of the 21st International Jont Conference on Artifical Intel- 2008,15(1):61-67. ligence.San Francisco,CA,USA:ACM,2009:449- [24]马骁，王轩，王晓龙.一类非完备信息博弈的信息模型 455. [J].计算机研究与发展，2010,47(12)：2100-2109. [36]王骄，徐心和.计算机博弈：人工智能的前沿领域一 MA Xiao,WANG Xuan,WANG Xiaolong.The informa- 全国大学生计算机博弈大赛[J].计算机教育，2012 tion model for a class of imperfect information game[J]. (7):14-18. Journal of computer research and development,2010,47 [37]邱虹坤.全国计算机博弈大赛网站[EB/0L].[2016-04 (12):2100-2109. -22].2013.http://www.caaigames.net. [25]ZHANG Jiajia,WANG Xuan,LIN Jing,et al.UCT algo- 「38]张利群.实现苏拉卡尔塔棋网络博弈平台的吃子算法 rithm in imperfect information multi-player military chess [J].计算机工程与应用，2016,52(7)：62-66. game[C]//Proceedings of the 11th Joint Conference on ZHANG Liqun.Realization of capture algorithm about Information Sciences.Atlantis Press,2008:1-9. Surakarta chess network battle platform in computer game [26]WANG X,XU Zhaoyang,MA X.TD (A)optimization of [J].Computer engineering and applications,2016,52 imperfect information game's evaluation function[R].Ja- (7):62-66. pan:WCCGC,2007. [39]张小川，陈光年，张世强，等.六子棋博弈的评估函数 [27]XIA Zhengyou,ZHU Yongping,LU Hui.Using the loopy [J].重庆理工大学学报：自然科学版，2010,24(2)： belief propagation in Siguo[J].ICGA journal,2007,30 64-68. (4):209-220. ZHANG Xiaochuan,CHEN Guangnian, ZHANG [28]XIA Zhengyou,ZHU Yongping,LU Hui.Evaluation func- Shiqiang,et al.Research on evaluation functions for com- tion for siguo game based on two attitudes[C]//Proceed- puter game of conneet 6[].Journal of Chongqing univer- ings of the Third International Conference on Fuzzy Systems sity of technology:natural science,2010,24(2):64-68. and Knowledge Discovery.Berlin Heidelberg:Springer, [40]李淑琴，李静波，韩裕华，等.苏拉卡尔塔博弈系统中 2006:1322-1331. 评估函数的研究[J].北京信息科技大学学报，2012， [29]BENGIO Y,LAMBLIN P,POPOVICI D,et al.Greedy 27(6):42-45,61. layer-wise training of deep networks M]//SCHOLKOPF LI Shuqin,LI Jingbo,HAN Yuhua,et al.The assessment B,PLATT J,HOFMANN T.Advances in Neural Informa- function in the Surakarta game system[J].Journal of Bei-
ｔｉｏｎ ｉｎ Ｃｈｉｎｅｓｅ ｃｈｅｓｓ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｓｙｓｔｅｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｎｏｒｔｈｅａｓｔｅｒｎ ｕｎｉｖｅｒｓｉｔｙ： ｎａｔｕｒａｌ ｓｃｉｅｎｃｅ， ２００５， ２６（ １０）： ９４９－９５２． ［２０］魏钦刚， 王骄， 徐心和， 等． 中国象棋计算机博弈开局 库研究与设计［ Ｊ］． 智能系统学报， ２００７， ２（ １）： ８５－ ８９． ＷＥＩ Ｑｉｎｇａｎｇ， ＷＡＮＧ Ｊｉａｏ， ＸＵ Ｘｉｎｈｅ， ｅｔ ａｌ． Ａ ｓｔｕｄｙ ａｎｄ ｄｅｓｉｇｎ ｏｆ ｏｐｅｎｉｎｇ⁃ｂｏｏｋ ｏｆ ｃｏｍｐｕｔｅｒ Ｃｈｉｎｅｓｅ Ｃｈｅｓｓ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００７， ２（１）： ８５ －８９． ［２１］徐长明， 南晓斐， 王骄， 等． 中国象棋机器博弈的时间 自适应分配策略研究［Ｊ］． 智能系统学报， ２００６， １（２）： ３９－４３． ＸＵ Ｃｈａｎｇｍｉｎｇ， ＮＡＮ Ｘｉａｏｆｅｉ， ＷＡＮＧ Ｊｉａｏ， ｅｔ ａｌ． Ａｄａｐ⁃ ｔｉｖｅ ｔｉｍｅ ａｌｌｏｃａｔｉｏｎ ｓｔｒａｔｅｇｙ ｉｎ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｏｆ Ｃｈｉｎｅｓｅ Ｃｈｅｓｓ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓｔｅｍｓ， ２００６， １（２）： ３９－４３． ［２２］ ＬＩＵ Ｚｈｉｑｉｎｇ， ＤＯＵ Ｑｉｎｇ． Ａｕｔｏｍａｔｉｃ ｐａｔｔｅｒｎ ａｃｑｕｉｓｉｔｉｏｎ ｆｒｏｍ ｇａｍｅ ｒｅｃｏｒｄｓ ｉｎ ＧＯ［Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎａ ｕｎｉｖｅｒ⁃ ｓｉｔｉｅｓ ｏｆ ｐｏｓｔｓ ａｎｄ ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００７， １４ （ １）： １００－１０５． ［２３］ ＬＩＵ Ｚｈｉｑｉｎｇ， ＤＯＵ Ｑｉｎｇ， ＬＩ Ｗｅｎｈｏｎｇ， ｅｔ ａｌ． Ａｕｔｏｍａｔｉｃ ａｃｑｕｉｓｉｔｉｏｎ ｏｆ ｐａｔｔｅｒｎ ｃｏｌｌｏｃａｔｉｏｎｓ ｉｎ ＧＯ［ Ｊ］． Ｔｈｅ ｊｏｕｒｎａｌ ｏｆ Ｃｈｉｎａ ｕｎｉｖｅｒｓｉｔｉｅｓ ｏｆ ｐｏｓｔｓ ａｎｄ ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２００８， １５（１）： ６１－６７． ［２４］马骁， 王轩， 王晓龙． 一类非完备信息博弈的信息模型 ［Ｊ］． 计算机研究与发展， ２０１０， ４７（１２）： ２１００－２１０９． ＭＡ Ｘｉａｏ， ＷＡＮＧ Ｘｕａｎ， ＷＡＮＧ Ｘｉａｏｌｏｎｇ． Ｔｈｅ ｉｎｆｏｒｍａ⁃ ｔｉｏｎ ｍｏｄｅｌ ｆｏｒ ａ ｃｌａｓｓ ｏｆ ｉｍｐｅｒｆｅｃｔ ｉｎｆｏｒｍａｔｉｏｎ ｇａｍｅ ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｃｏｍｐｕｔｅｒ ｒｅｓｅａｒｃｈ ａｎｄ ｄｅｖｅｌｏｐｍｅｎｔ， ２０１０， ４７ （１２）： ２１００－２１０９． ［２５］ＺＨＡＮＧ Ｊｉａｊｉａ， ＷＡＮＧ Ｘｕａｎ， ＬＩＮ Ｊｉｎｇ， ｅｔ ａｌ． ＵＣＴ ａｌｇｏ⁃ ｒｉｔｈｍ ｉｎ ｉｍｐｅｒｆｅｃｔ ｉｎｆｏｒｍａｔｉｏｎ ｍｕｌｔｉ⁃ｐｌａｙｅｒ ｍｉｌｉｔａｒｙ ｃｈｅｓｓ ｇａｍｅ［ Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １１ｔｈ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｃｉｅｎｃｅｓ． Ａｔｌａｎｔｉｓ Ｐｒｅｓｓ， ２００８： １－９． ［２６］ＷＡＮＧ Ｘ， ＸＵ Ｚｈａｏｙａｎｇ， ＭＡ Ｘ． ＴＤ （Λ） ｏｐｔｉｍｉｚａｔｉｏｎ ｏｆ ｉｍｐｅｒｆｅｃｔ ｉｎｆｏｒｍａｔｉｏｎ ｇａｍｅ’ ｓ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎ［Ｒ］． Ｊａ⁃ ｐａｎ： ＷＣＣＧＣ， ２００７． ［２７］ＸＩＡ Ｚｈｅｎｇｙｏｕ， ＺＨＵ Ｙｏｎｇｐｉｎｇ， ＬＵ Ｈｕｉ． Ｕｓｉｎｇ ｔｈｅ ｌｏｏｐｙ ｂｅｌｉｅｆ ｐｒｏｐａｇａｔｉｏｎ ｉｎ Ｓｉｇｕｏ［ Ｊ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２００７， ３０ （４）： ２０９－２２０． ［２８］ＸＩＡ Ｚｈｅｎｇｙｏｕ， ＺＨＵ Ｙｏｎｇｐｉｎｇ， ＬＵ Ｈｕｉ． Ｅｖａｌｕａｔｉｏｎ ｆｕｎｃ⁃ ｔｉｏｎ ｆｏｒ ｓｉｇｕｏ ｇａｍｅ ｂａｓｅｄ ｏｎ ｔｗｏ ａｔｔｉｔｕｄｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ Ｔｈｉｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ ａｎｄ Ｋｎｏｗｌｅｄｇｅ Ｄｉｓｃｏｖｅｒｙ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ， ２００６： １３２２－１３３１． ［２９］ ＢＥＮＧＩＯ Ｙ， ＬＡＭＢＬＩＮ Ｐ， ＰＯＰＯＶＩＣＩ Ｄ， ｅｔ ａｌ． Ｇｒｅｅｄｙ ｌａｙｅｒ⁃ｗｉｓｅ ｔｒａｉｎｉｎｇ ｏｆ ｄｅｅｐ ｎｅｔｗｏｒｋｓ ［ Ｍ］ ／ ／ ＳＣＨÖＬＫＯＰＦ Ｂ， ＰＬＡＴＴ Ｊ， ＨＯＦＭＡＮＮ Ｔ． Ａｄｖａｎｃｅｓ ｉｎ Ｎｅｕｒａｌ Ｉｎｆｏｒｍａ⁃ ｔｉｏｎ Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍｓ， ｖｏｌ １９． Ｃａｍｂｒｉｄｇｅ： ＭＩＴ Ｐｒｅｓｓ， ２００７： １５３－１６０． ［３０］ＣＯＵＬＯＭ Ｒ． Ｃｏｍｐｕｔｉｎｇ “Ｅｌｏ ｒａｔｉｎｇｓ” ｏｆ ｍｏｖｅ ｐａｔｔｅｒｎｓ ｉｎ ｔｈｅ ｇａｍｅ ｏｆ ｇｏ［ Ｊ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２００７， ３０（ ４）： １９８ － ２０８． ［３１］ＦＥＲＲＥＩＲＡ Ｄ Ｒ． Ｄｅｔｅｒｍｉｎｉｎｇ ｔｈｅ ｓｔｒｅｎｇｔｈ ｏｆ ｃｈｅｓｓ ｐｌａｙｅｒｓ ｂａｓｅｄ ｏｎ ａｃｔｕａｌ ｐｌａｙ［Ｊ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２０１２， ３５（１）： ３－ １９． ［３２］ＮＩＪＳＳＥＮ Ｊ Ａ Ｍ， ＷＩＮＡＮＤＳ Ｍ Ｈ Ｍ． Ｓｅａｒｃｈ ｐｏｌｉｃｉｅｓ ｉｎ ｍｕｌｔｉ⁃ｐｌａｙｅｒ ｇａｍｅｓ１［Ｊ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２０１３， ３６（１）： ３－ ２１． ［３３］ＬＥＩＦＫＥＲ Ｄ Ｂ， ＫＡＮＡＬ Ｌ Ｎ． Ａ ｈｙｂｒｉｄ ＳＳＳ ∗ ／ Ａｌｐｈａ⁃Ｂｅｔａ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐａｒａｌｌｅｌ ｓｅａｒｃｈ ｏｆ ｇａｍｅ ｔｒｅｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄ⁃ ｉｎｇｓ ｏｆ ｔｈｅ ９ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＣＡ， ＵＳＡ： ＡＣＭ， １９８５， ２： １０４４－１０４６． ［３４］ ＰＬＡＡＴ Ａ， ＳＣＨＡＥＦＦＥＲ Ｊ， ＰＩＪＬＳ Ｗ， ｅｔ ａｌ． Ｂｅｓｔ⁃ｆｉｒｓｔ ｆｉｘｅｄ⁃ｄｅｐｔｈ ｇａｍｅ⁃ｔｒｅｅ ｓｅａｒｃｈ ｉｎ ｐｒａｃｔｉｃｅ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ １４ｔｈ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃｉａｌ Ｉｎ⁃ ｔｅｌｌｉｇｅｎｃｅ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＣＡ， ＵＳＡ： ＡＣＭ， １９９５， １： ２７３－２７９． ［３５］ ＢＵＲＮＳ Ｅ， ＬＥＭＯＮＳ Ｓ， ＺＨＯＵ Ｒｏｎｇ， ｅｔ ａｌ． Ｂｅｓｔ⁃ｆｉｒｓｔ ｈｅｕｒｉｓｔｉｃ ｓｅａｒｃｈ ｆｏｒ ｍｕｌｔｉ⁃ｃｏｒｅ ｍａｃｈｉｎｅｓ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ２１ｓｔ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ａｒｔｉｆｉｃａｌ Ｉｎｔｅｌ⁃ ｌｉｇｅｎｃｅ． Ｓａｎ Ｆｒａｎｃｉｓｃｏ， ＣＡ， ＵＳＡ： ＡＣＭ， ２００９： ４４９ － ４５５． ［３６］王骄， 徐心和． 计算机博弈： 人工智能的前沿领域——— 全国大学生计算机博弈大赛［ Ｊ］． 计算机教育， ２０１２ （７）： １４－１８． ［３７］邱虹坤． 全国计算机博弈大赛网站［ＥＢ／ ＯＬ］． ［２０１６－０４ －２２］． ２０１３． ｈｔｔｐ： ／ ／ ｗｗｗ．ｃａａｉｇａｍｅｓ．ｎｅｔ． ［３８］张利群． 实现苏拉卡尔塔棋网络博弈平台的吃子算法 ［Ｊ］． 计算机工程与应用， ２０１６， ５２（７）： ６２－６６． ＺＨＡＮＧ Ｌｉｑｕｎ． Ｒｅａｌｉｚａｔｉｏｎ ｏｆ ｃａｐｔｕｒｅ ａｌｇｏｒｉｔｈｍ ａｂｏｕｔ Ｓｕｒａｋａｒｔａ ｃｈｅｓｓ ｎｅｔｗｏｒｋ ｂａｔｔｌｅ ｐｌａｔｆｏｒｍ ｉｎ ｃｏｍｐｕｔｅｒ ｇａｍｅ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１６， ５２ （７）： ６２－６６． ［３９］张小川， 陈光年， 张世强， 等． 六子棋博弈的评估函数 ［Ｊ］． 重庆理工大学学报： 自然科学版， ２０１０， ２４（２）： ６４－６８． ＺＨＡＮＧ Ｘｉａｏｃｈｕａｎ， ＣＨＥＮ Ｇｕａｎｇｎｉａｎ， ＺＨＡＮＧ Ｓｈｉｑｉａｎｇ， ｅｔ ａｌ． Ｒｅｓｅａｒｃｈ ｏｎ ｅｖａｌｕａｔｉｏｎ ｆｕｎｃｔｉｏｎｓ ｆｏｒ ｃｏｍ⁃ ｐｕｔｅｒ ｇａｍｅ ｏｆ ｃｏｎｎｅｃｔ ６［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｈｏｎｇｑｉｎｇ ｕｎｉｖｅｒ⁃ ｓｉｔｙ ｏｆ ｔｅｃｈｎｏｌｏｇｙ： ｎａｔｕｒａｌ ｓｃｉｅｎｃｅ， ２０１０， ２４（２）： ６４－６８． ［４０］李淑琴， 李静波， 韩裕华， 等． 苏拉卡尔塔博弈系统中 评估函数的研究［ Ｊ］． 北京信息科技大学学报， ２０１２， ２７（６）： ４２－４５， ６１． ＬＩ Ｓｈｕｑｉｎ， ＬＩ Ｊｉｎｇｂｏ， ＨＡＮ Ｙｕｈｕａ， ｅｔ ａｌ． Ｔｈｅ ａｓｓｅｓｓｍｅｎｔ ｆｕｎｃｔｉｏｎ ｉｎ ｔｈｅ Ｓｕｒａｋａｒｔａ ｇａｍｅ ｓｙｓｔｅｍ［ Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｂｅｉ⁃ ·７９６· 智 能 系 统 学 报 第 １１ 卷
第6期 王亚杰，等：计算机博弈的研究与发展 .797. jing information science and technology university,2012, 2015,38(1):47-53. 27(6):42-45.61 [53]VAN DER HERIK H J.UITERWIJK J W H M,VAN RI- [41]TANG Pingzhong,LIN Fangzhen.Discovering theorems in JSWIJCK J.Games solved:now and in the future[J].Ar- game theory:two-person games with unique pure Nash e- tificial intelligence,2002,134(1/2):277-311 quilibrium payoffs[J].Artificial intelligence,2011,175 [54]KAINDL H,SHAMS R,HORACEK H.Minimax search (14/15)：2010-2020. algorithms with and without aspiration windows[].IEEE [42]RUBIN J,WATSON I.Case-based strategies in computer transactions on pattern analysis and machine intelligence, poker[]].AI communications,2012,25(1):19-48. 1991,13(12):1225-1235. [43]FLESCH J.KUIPERS J,SCHOENMAKERS G,et al. [55]LU Hui,XIA Zhengyou.AWT:aspiration with timer Subgame-perfection in free transition games[J].European search algorithm in Siguo[C//Proceedings of the 6th In- journal of operational research,2013,228(1):201-207. ternational Conference on Computers and Games.Berlin [44]GILPIN A,SANDHOLM T.Lossless abstraction of imper- Heidelberg:Springer-Verlag,2008:264-274. fect information games[J].Journal of the ACM,2007,54 [56]邹竞.基于MTD(f)的中国象棋人机博弈算法的设计与 (5):25. 优化[J].计算机与数字工程，2008,36(9)：38-43. [45]何大华，陈传波.关于桥牌的取胜策略[J].华中科技 ZOU Jing.Chinese chess algorithm design and optimize 大学学报：自然科学版，2004,32(7)：13-15. based on MTD(f)[J].Computer digital engineering, HE Dahua,CHEN Chuanbo.The strategy for winning 2008,36(9):38-43. bridge game[J].Journal of Huazhong university of science [57]张明亮，李凡长.一种新的博弈树搜索方法[J].山东 technology:nature science edition,2004,32(7):13- 大学学报：工学版，2009,39(6)：1-8. 15. ZHANG Mingliang,LI Fanzhang.A new search method for [46]CHEN Bonian,LIU Pangfeng,HSU S C,et al.Aggrega- a game tree[J].Journal of Shandong university:engineer- ting consistent endgame knowledge in Chinese Chess[J]. ing science,2009,39(6):1-8. Knowledge-based systems,2012,34:34-42. [58]焦尚彬，刘丁.博弈树置换表启发式算法研究[J].计 [47]郭琴琴，李淑琴，包华.亚马逊棋机器博弈系统中评估 算机工程与应用.2010.46(6)：42-45. 函数的研究[J刀].计算机工程与应用，2012,48(34)： JIAO Shangbin,LIU Ding.Research on translation table 50-54 heuristic algorithm[].Computer engineering and applica- GUO Qingin,LI Shugin,BAO Hua.Research on evalua- tions,2010,46(6):42-45. tion function computer game of Amazon[J.Computer en- [59]DONKERS HH L M,UITERWIJK J W H M,VAN DER gineering and applications,2012,48(34):50-54. HERIK H J.Probabilistic opponent-model search[J].In- [48]SCHADD M P D,WINANDS M H M.Best reply search formation sciences,2001,135(3/4):123-149. for multiplayer games[J].IEEE transactions on computa- [60]SCHAEFFER J.The History heuristic and alpha-beta tional intelligence and Al in games,2011,3(1):57-66. search enhancements in practice[J.IEEE transactions [49]李学俊，王小龙，吴蕾，等.六子棋中基于局部“路”扫 on pattern analysis and machine intelligence,1989,11 描方式的博弈树生成算法[J].智能系统学报，2015， (11):1203-1212. 10(2):267-272. [61]SAKUTA M,HASHIMOTO T,NAGASHIMA J,et al.Ap- LI Xuejun,WANG Xiaolong,WU Lei,et al.Game tree plication of the killer-tree heuristic and the lambda-search generation algorithm based on local-road scanning method method to lines of action[J].Information sciences,2003, for connect 6[J].CAAI transactions on intelligent sys- 154(3/4):141-155. tems,2015,10(2):267-272. [62]REINEFELD A,MARSLAND T A.Enhanced iterative- [50]ETESSAMI K,LOCHBIHLER A.The computational com- deepening search[].IEEE transactions on pattern analy- plexity of evolutionarily stable strategies[J].International sis and machine intelligence,1994,16(7):701-710. journal of game theory,2008,37(1):93-113. [63]MARSLAND T A.REINEFELD A,SCHAEFFER J.Low [51]高强，徐心和.时间复杂性和空间复杂性研究[J].智 overhead alternatives to SSS[].Artificial intelligence, 能系统学报，2014,9(5)：529-535. 1987,31(2):185-199. GAO Qiang,XU Xinhe.Research on time complexity and [64]PLAAT A,SCHAEFFER J,PIJLS W,et al.SSS'al- space complexity[J.CAAl transactions on intelligent sys- pha-beta +TT[J].Computer Science,2014,8(1):25. tems,2014,9(5):529-535. [65]BERLINER H.The B'tree search algorithm:a best-first [52]GAO Qiang,XU Xinhe.Research on the computational proof procedure[].Artificial intelligence,1979,12(1): complexity of n x n Chinese chess J].ICGA journal, 23-40
ｊｉｎｇ ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅ ａｎｄ ｔｅｃｈｎｏｌｏｇｙ ｕｎｉｖｅｒｓｉｔｙ， ２０１２， ２７（６）： ４２－４５， ６１． ［４１］ＴＡＮＧ Ｐｉｎｇｚｈｏｎｇ， ＬＩＮ Ｆａｎｇｚｈｅｎ． Ｄｉｓｃｏｖｅｒｉｎｇ ｔｈｅｏｒｅｍｓ ｉｎ ｇａｍｅ ｔｈｅｏｒｙ： ｔｗｏ⁃ｐｅｒｓｏｎ ｇａｍｅｓ ｗｉｔｈ ｕｎｉｑｕｅ ｐｕｒｅ Ｎａｓｈ ｅ⁃ ｑｕｉｌｉｂｒｉｕｍ ｐａｙｏｆｆｓ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２０１１， １７５ （１４ ／ １５）： ２０１０－２０２０． ［４２］ＲＵＢＩＮ Ｊ， ＷＡＴＳＯＮ Ｉ． Ｃａｓｅ⁃ｂａｓｅｄ ｓｔｒａｔｅｇｉｅｓ ｉｎ ｃｏｍｐｕｔｅｒ ｐｏｋｅｒ［Ｊ］． ＡＩ ｃｏｍｍｕｎｉｃａｔｉｏｎｓ， ２０１２， ２５（１）： １９－４８． ［ ４３］ ＦＬＥＳＣＨ Ｊ， ＫＵＩＰＥＲＳ Ｊ， ＳＣＨＯＥＮＭＡＫＥＲＳ Ｇ， ｅｔ ａｌ． Ｓｕｂｇａｍｅ⁃ｐｅｒｆｅｃｔｉｏｎ ｉｎ ｆｒｅｅ ｔｒａｎｓｉｔｉｏｎ ｇａｍｅｓ［Ｊ］． Ｅｕｒｏｐｅａｎ ｊｏｕｒｎａｌ ｏｆ ｏｐｅｒａｔｉｏｎａｌ ｒｅｓｅａｒｃｈ， ２０１３， ２２８（１）： ２０１－２０７． ［４４］ＧＩＬＰＩＮ Ａ， ＳＡＮＤＨＯＬＭ Ｔ． Ｌｏｓｓｌｅｓｓ ａｂｓｔｒａｃｔｉｏｎ ｏｆ ｉｍｐｅｒ⁃ ｆｅｃｔ ｉｎｆｏｒｍａｔｉｏｎ ｇａｍｅｓ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ ｔｈｅ ＡＣＭ， ２００７， ５４ （５）： ２５． ［４５］何大华， 陈传波． 关于桥牌的取胜策略［ Ｊ］． 华中科技 大学学报： 自然科学版， ２００４， ３２（７）： １３－１５． ＨＥ Ｄａｈｕａ， ＣＨＥＮ Ｃｈｕａｎｂｏ． Ｔｈｅ ｓｔｒａｔｅｇｙ ｆｏｒ ｗｉｎｎｉｎｇ ｂｒｉｄｇｅ ｇａｍｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｈｕａｚｈｏｎｇ ｕｎｉｖｅｒｓｉｔｙ ｏｆ ｓｃｉｅｎｃｅ ＆ ｔｅｃｈｎｏｌｏｇｙ： ｎａｔｕｒｅ ｓｃｉｅｎｃｅ ｅｄｉｔｉｏｎ， ２００４， ３２（７）： １３－ １５． ［４６］ＣＨＥＮ Ｂｏｎｉａｎ， ＬＩＵ Ｐａｎｇｆｅｎｇ， ＨＳＵ Ｓ Ｃ， ｅｔ ａｌ． Ａｇｇｒｅｇａ⁃ ｔｉｎｇ ｃｏｎｓｉｓｔｅｎｔ ｅｎｄｇａｍｅ ｋｎｏｗｌｅｄｇｅ ｉｎ Ｃｈｉｎｅｓｅ Ｃｈｅｓｓ［ Ｊ］． Ｋｎｏｗｌｅｄｇｅ⁃ｂａｓｅｄ ｓｙｓｔｅｍｓ， ２０１２， ３４： ３４－４２． ［４７］郭琴琴， 李淑琴， 包华． 亚马逊棋机器博弈系统中评估 函数的研究［ Ｊ］． 计算机工程与应用， ２０１２， ４８（ ３４）： ５０－５４． ＧＵＯ Ｑｉｎｑｉｎ， ＬＩ Ｓｈｕｑｉｎ， ＢＡＯ Ｈｕａ． Ｒｅｓｅａｒｃｈ ｏｎ ｅｖａｌｕａ⁃ ｔｉｏｎ ｆｕｎｃｔｉｏｎ ｃｏｍｐｕｔｅｒ ｇａｍｅ ｏｆ Ａｍａｚｏｎ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎ⁃ ｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａｔｉｏｎｓ， ２０１２， ４８（３４）： ５０－５４． ［４８］ＳＣＨＡＤＤ Ｍ Ｐ Ｄ， ＷＩＮＡＮＤＳ Ｍ Ｈ Ｍ． Ｂｅｓｔ ｒｅｐｌｙ ｓｅａｒｃｈ ｆｏｒ ｍｕｌｔｉｐｌａｙｅｒ ｇａｍｅｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｃｏｍｐｕｔａ⁃ ｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ ａｎｄ ＡＩ ｉｎ ｇａｍｅｓ， ２０１１， ３（１）： ５７－６６． ［４９］李学俊， 王小龙， 吴蕾， 等． 六子棋中基于局部“路”扫 描方式的博弈树生成算法［ Ｊ］． 智能系统学报， ２０１５， １０（２）： ２６７－２７２． ＬＩ Ｘｕｅｊｕｎ， ＷＡＮＧ Ｘｉａｏｌｏｎｇ， ＷＵ Ｌｅｉ， ｅｔ ａｌ． Ｇａｍｅ ｔｒｅｅ ｇｅｎｅｒａｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｌｏｃａｌ⁃ｒｏａｄ ｓｃａｎｎｉｎｇ ｍｅｔｈｏｄ ｆｏｒ ｃｏｎｎｅｃｔ ６ ［ Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓ⁃ ｔｅｍｓ， ２０１５， １０（２）： ２６７－２７２． ［５０］ＥＴＥＳＳＡＭＩ Ｋ， ＬＯＣＨＢＩＨＬＥＲ Ａ． Ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍ⁃ ｐｌｅｘｉｔｙ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｉｌｙ ｓｔａｂｌｅ ｓｔｒａｔｅｇｉｅｓ［ Ｊ］． Ｉｎｔｅｒｎａｔｉｏｎａｌ ｊｏｕｒｎａｌ ｏｆ ｇａｍｅ ｔｈｅｏｒｙ， ２００８， ３７（１）： ９３－１１３． ［５１］高强， 徐心和． 时间复杂性和空间复杂性研究［ Ｊ］． 智 能系统学报， ２０１４， ９（５）： ５２９－５３５． ＧＡＯ Ｑｉａｎｇ， ＸＵ Ｘｉｎｈｅ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｉｍｅ ｃｏｍｐｌｅｘｉｔｙ ａｎｄ ｓｐａｃｅ ｃｏｍｐｌｅｘｉｔｙ［Ｊ］． ＣＡＡＩ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｉｎｔｅｌｌｉｇｅｎｔ ｓｙｓ⁃ ｔｅｍｓ， ２０１４， ９（５）： ５２９－５３５． ［５２］ ＧＡＯ Ｑｉａｎｇ， ＸＵ Ｘｉｎｈｅ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｈｅ ｃｏｍｐｕｔａｔｉｏｎａｌ ｃｏｍｐｌｅｘｉｔｙ ｏｆ ｎ ｘ ｎ Ｃｈｉｎｅｓｅ ｃｈｅｓｓ ［ Ｊ］． ＩＣＧＡ ｊｏｕｒｎａｌ， ２０１５， ３８（１）： ４７－５３． ［５３］ＶＡＮ ＤＥＲ ＨＥＲＩＫ Ｈ Ｊ， ＵＩＴＥＲＷＩＪＫ Ｊ Ｗ Ｈ Ｍ， ＶＡＮ ＲＩ⁃ ＪＳＷＩＪＣＫ Ｊ． Ｇａｍｅｓ ｓｏｌｖｅｄ： ｎｏｗ ａｎｄ ｉｎ ｔｈｅ ｆｕｔｕｒｅ［Ｊ］． Ａｒ⁃ ｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， ２００２， １３４（１ ／ ２）： ２７７－３１１． ［５４］ ＫＡＩＮＤＬ Ｈ， ＳＨＡＭＳ Ｒ， ＨＯＲＡＣＥＫ Ｈ． Ｍｉｎｉｍａｘ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍｓ ｗｉｔｈ ａｎｄ ｗｉｔｈｏｕｔ ａｓｐｉｒａｔｉｏｎ ｗｉｎｄｏｗｓ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９１， １３（１２）： １２２５－１２３５． ［５５］ ＬＵ Ｈｕｉ， ＸＩＡ Ｚｈｅｎｇｙｏｕ． ＡＷＴ： ａｓｐｉｒａｔｉｏｎ ｗｉｔｈ ｔｉｍｅｒ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ ｉｎ Ｓｉｇｕｏ［Ｃ］ ／ ／ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ６ｔｈ Ｉｎ⁃ ｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｃｏｍｐｕｔｅｒｓ ａｎｄ Ｇａｍｅｓ． Ｂｅｒｌｉｎ Ｈｅｉｄｅｌｂｅｒｇ： Ｓｐｒｉｎｇｅｒ⁃Ｖｅｒｌａｇ， ２００８： ２６４－２７４． ［５６］邹竞． 基于 ＭＴＤ（ｆ）的中国象棋人机博弈算法的设计与 优化［Ｊ］． 计算机与数字工程， ２００８， ３６（９）： ３８－４３． ＺＯＵ Ｊｉｎｇ． Ｃｈｉｎｅｓｅ ｃｈｅｓｓ ａｌｇｏｒｉｔｈｍ ｄｅｓｉｇｎ ａｎｄ ｏｐｔｉｍｉｚｅ ｂａｓｅｄ ｏｎ ＭＴＤ（ ｆ） ［ Ｊ］． Ｃｏｍｐｕｔｅｒ ＆ ｄｉｇｉｔａｌ ｅｎｇｉｎｅｅｒｉｎｇ， ２００８， ３６（９）： ３８－４３． ［５７］张明亮， 李凡长． 一种新的博弈树搜索方法［ Ｊ］． 山东 大学学报： 工学版， ２００９， ３９（６）： １－８． ＺＨＡＮＧ Ｍｉｎｇｌｉａｎｇ， ＬＩ Ｆａｎｚｈａｎｇ． Ａ ｎｅｗ ｓｅａｒｃｈ ｍｅｔｈｏｄ ｆｏｒ ａ ｇａｍｅ ｔｒｅｅ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｎｄｏｎｇ ｕｎｉｖｅｒｓｉｔｙ： ｅｎｇｉｎｅｅｒ⁃ ｉｎｇ ｓｃｉｅｎｃｅ， ２００９， ３９（６）： １－８． ［５８］焦尚彬， 刘丁． 博弈树置换表启发式算法研究［ Ｊ］． 计 算机工程与应用， ２０１０， ４６（６）： ４２－４５． ＪＩＡＯ Ｓｈａｎｇｂｉｎ， ＬＩＵ Ｄｉｎｇ． Ｒｅｓｅａｒｃｈ ｏｎ ｔｒａｎｓｌａｔｉｏｎ ｔａｂｌｅ ｈｅｕｒｉｓｔｉｃ ａｌｇｏｒｉｔｈｍ［Ｊ］． Ｃｏｍｐｕｔｅｒ ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ ａｐｐｌｉｃａ⁃ ｔｉｏｎｓ， ２０１０， ４６（６）： ４２－４５． ［５９］ＤＯＮＫＥＲＳ Ｈ Ｈ Ｌ Ｍ， ＵＩＴＥＲＷＩＪＫ Ｊ Ｗ Ｈ Ｍ， ＶＡＮ ＤＥＲ ＨＥＲＩＫ Ｈ Ｊ． Ｐｒｏｂａｂｉｌｉｓｔｉｃ ｏｐｐｏｎｅｎｔ⁃ｍｏｄｅｌ ｓｅａｒｃｈ［ Ｊ］． Ｉｎ⁃ ｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００１， １３５（３ ／ ４）： １２３－１４９． ［ ６０ ］ ＳＣＨＡＥＦＦＥＲ Ｊ． Ｔｈｅ Ｈｉｓｔｏｒｙ ｈｅｕｒｉｓｔｉｃ ａｎｄ ａｌｐｈａ⁃ｂｅｔａ ｓｅａｒｃｈ ｅｎｈａｎｃｅｍｅｎｔｓ ｉｎ ｐｒａｃｔｉｃｅ ［ Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８９， １１ （１１）： １２０３－１２１２． ［６１］ＳＡＫＵＴＡ Ｍ， ＨＡＳＨＩＭＯＴＯ Ｔ， ＮＡＧＡＳＨＩＭＡ Ｊ， ｅｔ ａｌ． Ａｐ⁃ ｐｌｉｃａｔｉｏｎ ｏｆ ｔｈｅ ｋｉｌｌｅｒ⁃ｔｒｅｅ ｈｅｕｒｉｓｔｉｃ ａｎｄ ｔｈｅ ｌａｍｂｄａ⁃ｓｅａｒｃｈ ｍｅｔｈｏｄ ｔｏ ｌｉｎｅｓ ｏｆ ａｃｔｉｏｎ［Ｊ］． Ｉｎｆｏｒｍａｔｉｏｎ ｓｃｉｅｎｃｅｓ， ２００３， １５４（３ ／ ４）： １４１－１５５． ［６２］ ＲＥＩＮＥＦＥＬＤ Ａ， ＭＡＲＳＬＡＮＤ Ｔ Ａ． Ｅｎｈａｎｃｅｄ ｉｔｅｒａｔｉｖｅ⁃ ｄｅｅｐｅｎｉｎｇ ｓｅａｒｃｈ［Ｊ］． ＩＥＥＥ ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ ｐａｔｔｅｒｎ ａｎａｌｙ⁃ ｓｉｓ ａｎｄ ｍａｃｈｉｎｅ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９９４， １６（７）： ７０１－７１０． ［６３］ＭＡＲＳＬＡＮＤ Ｔ Ａ， ＲＥＩＮＥＦＥＬＤ Ａ， ＳＣＨＡＥＦＦＥＲ Ｊ． Ｌｏｗ ｏｖｅｒｈｅａｄ ａｌｔｅｒｎａｔｉｖｅｓ ｔｏ ＳＳＳ ［ Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９８７， ３１（２）： １８５－１９９． ［６４］ＰＬＡＡＴ Ａ， ＳＣＨＡＥＦＦＥＲ Ｊ， ＰＩＪＬＳ Ｗ， ｅｔ ａｌ． ＳＳＳ ∗ ＝ ａｌ⁃ ｐｈａ⁃ｂｅｔａ ＋ ＴＴ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２０１４， ８（１）： ２５． ［６５］ＢＥＲＬＩＮＥＲ Ｈ． Ｔｈｅ Ｂ ∗ ｔｒｅｅ ｓｅａｒｃｈ ａｌｇｏｒｉｔｈｍ： ａ ｂｅｓｔ⁃ｆｉｒｓｔ ｐｒｏｏｆ ｐｒｏｃｅｄｕｒｅ［Ｊ］． Ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ， １９７９， １２（１）： ２３－４０． 第 ６ 期 王亚杰，等：计算机博弈的研究与发展 ·７９７·