AlphaGo对弈李世石，人工智能登场 - iDoNews
> AlphaGo对弈李世石，人工智能登场
AlphaGo对弈李世石，人工智能登场
1996年，电脑深蓝与卡斯帕罗夫展开激战。2016年，人工智能与人类的博弈由国际象棋转向了围棋。
不久之后，韩国首尔四季酒店对弈的黑白两方，是围棋高手李世石与人工智能“阿尔法围棋”。
韩国著名围棋九段棋手李世石与谷歌人工智能“阿尔法围棋”(AlphaGo)的5盘对决将于3月9日、10日、12日、13日和15日在首尔举行。比赛用时为每方两小时，一分钟读秒3次，比赛采用中国围棋规则。这场对决的胜者将获得100万美元奖金，如果阿尔法围棋获胜，奖金将捐给联合国儿童基金会和STEM教育以及围棋相关公益团体。
关于围棋，王安石曾经有诗云：“莫将戏事扰真情，且可随缘道我赢。战罢两奁分白黑，一枰何处有亏成。”
下棋的胜负，王安石看的很淡，所以才有“战罢两奁分白黑，一枰何处有亏成”之说。但是“阿尔法围棋”与李世石对弈，似乎并没有那么恬淡。我想将王荆公的诗反过来，这样说：“战罢两奁分白黑，一枰处处有亏成”。
因为，人工智能与人类在围棋上的博弈，意义很大。不是没有“亏成”，而是处处有“亏成”。
关于这次对弈，笔者一直在思索这样几个问题。相信，这几个问题也是很多普通人关心的问题。这些问题是：第一，人工智能在围棋方面探索的原理是什么;
第二，此次人工智能与围棋高手的对抗与当年的深蓝有何区别;第三，如果人工智能赢了，有什么意义;第四，如果人工智能输了，李世石赢了，能代表什么;第五，不论输赢的话，人工智能在围棋方面的探索，对人工智能的发展有何意义;第六，在我的心目中，围棋代表着哲学，人工智能在围棋方面的造诣，是否意味着人工智能已经具备了哲学方面的思考能力;第七，人工智能与围棋高手对抗，是不是意味着机器人威胁论又进了一步?第八，前面几个问题，是我从非专业角度思考的，从专业的角度，那些人工智能企业、科学家不知如何看待这个事件。
针对这几个问题，笔者以 iDoNews专栏签约作者的身份，向北京图灵机器人联合创始人、技术负责人韦克礼先生请教，请他回答了这几个问题。
以下，是韦克礼先生的回答。
第一，人工智能在围棋方面探索的原理。
人工智能在棋类的研究基本方法本质都是把棋子可能的走法构建成搜索树，计算能得到最优值的落子选择。目前这种方法在其他很多棋类(中国象棋、国际象棋等)中都能战胜人类的顶尖选手，但在围棋上还是一个挑战。19路围棋的复杂度是10^170，国际象棋的才是10^47，策略变化也更复杂，要计算出初始盘面的最优值(蛮力做法)，即使按照现在硬件的计算能力也难以达到。
由于计算围棋盘面最优值的时间随着该盘面到终盘之间的步数呈指数级增长，而围棋程序的运算时间有限，理论上无法得到最优值，从而引入了蒙特卡洛树搜索方法。蒙特卡洛是一类随机方法，特点是在随机采样上计算得到近似结果，采样越多，得到结果的越接近最优解;即在有限的采样中，必须要给出一个解的条件下，蒙特卡洛方法能给出一个靠近最优解的结果。所以在比赛时间受限的情况下，利用蒙特卡洛树搜索仍然可以给出一个“好的选择”。
AlphAgo(阿尔法围棋，笔者注)基于蒙特卡洛树搜索，在选择策略中加入更多的围棋方法的专家知识，使系统的水平不断提高;同时AlphAgo充分利用深度学习和大数据的优势，并与改进的搜索树算法结合，通过自我对局的结果训练使棋力一直在进步。
第二，此次人工智能与围棋高手的对抗与当年深蓝有何区别。
1、挑战的难度不同，围棋复杂度10^170，国际象棋10^47，围棋困难很多。2、神经网络的能力的再次体现，随着硬件计算能力的提高，神经网络在图像、机器翻译等领域的应用已经得到了很好的效果，AlphaGo的深度神经网络包含数百万的神经元，12个不同的网络层，训练后预测对手下步棋的正确率达到了57%(之前记录44%)。3、自我强化学习，除了学习已有的历史棋谱，AlphaGo还通过自我对局，可以无限量增长的对局来评价每步棋子的落子策略，而深蓝是依赖于人工定义的目标函数，相比而言，AlphaGo的自我学习更接近于人类。
第三，如果人工智能赢了，有什么意义。
如果人工智能获胜，更多的应该还是依靠计算能力和稳定性发挥来取胜，说明机器的计算智能又有了进一步的进步。
第四，如果人工智能输了，李世石赢了，能代表什么。
如果人工智能输了，主要原因应该还是训练量不够，相信给人工智能一定的时间进行训练，总有一天会超过人类的，而且这个时间不会超过几年。
第五，不论输赢的话，人工智能在围棋方面的探索，对人工智能的发展有何意义。
无论是否输赢(即使这次不赢，在很短的时间内也会战胜人类顶尖选手)，这都可能成为人工智能的一个里程碑。当1997年深蓝战胜了国际象棋冠军的时候，围棋计算机同一般的业余选手都还有不小的距离，因为其复杂性，很多人认为电脑围棋想要战胜人类，至少要等四十年。然而随着AI的发展，在部分领域计算机已经能达到甚至超过人类，如机器在图像识别方面的能力已经超过了人眼识别。而在围棋这样更具深度与挑战的领域，能做到如此重大的突破，相信在其他之前认为只有人类能够完成的领域，例如无人驾驶、智能对话等领域，在不久的将来，人工智能也能逐渐取代人类。
第六，在我的心目中，围棋代表着哲学。人工智能在围棋方面的造诣，是否意味着人工智能已经具备了哲学方面的思考能力。
人工智能的棋艺我更觉得是一种计算能力，因此还谈不上哲学方面的思考能力。
第七，人工智能与围棋高手对抗，是不是意味着机器人威胁论又进了一步?
去年我们组织了一个中关村AI相关的讨论会，其中有一个话题就是关于机器人威胁论的。当时在场大都是偏工程领域的，所以大家达成非常一致的结论是现在业界中的产品更多体现的是IA(智能增强)，还没有达到消费者希望的AI(人工智能)的地步，而这个AI的发展的时间也还很长，因此机器人威胁论离我们还很远。对于人工智能与围棋高手对抗，我个人感觉更多还是体现在计算智能的进步，还未达到所期望的认知智能，因为AlphaGo
的进步依赖于海量的自我对局数目，这当然是它的长处，但也恰好说明它并未真正掌握人类的学习能力，因此暂时也谈不上威胁了。
第八，从专业的角度，你们怎么看这个事件。
不论结果如何，这次的事件都可能会成为人工智能的一个里程碑之一。但是AlphaGo
和一切神经网络一样，本质上还只是个大黑盒，我们能观察到它表现出的巨大能力，但对它究竟是如何“思考”的这件事依然所知甚少。在工程上，这是个伟大的胜利。但在科学上，人类所具有的思维、意识等等能力还需要人工智能去进行进一步的挖掘。
在感谢图灵机器人，感谢韦克礼先生解答我困惑的同时，我又想起了纪晓岚关于围棋的两句诗：“局中局外两沉吟，犹是人间胜负心。”我想，这次李世石与阿尔法围棋的对弈，已经不简单是胜负之心了，而是我前面所说的：“战罢两奁分白黑，一枰处处有亏成”。
作者：姜伯静 &| 来源：iDoNews 专栏
正在加载......国际象棋,最全面的国际象棋文章 - 电子工程世界网
在电子工程世界为您找到如下关于“国际象棋”的新闻
国际象棋资料下载
个人开发的国际象棋源代码，可以进行人－人对战，人－机对战，机－机对战。同时可以进行网络连接对战。用java开发，可以很方便地放到网络上。...
一个人工智能的国际象棋游戏，用VC写的，完全采用的win32 API，而没有用MFC。英文介绍为：The Genius is a chess engine that uses AI techniques to play against humans。...
一个国际象棋的小游戏算法，可以通过在原来基础上提高一下改进...
一个简单的国际象棋游戏源码，编程环境是java。...
问题描述：按照国际象棋的规则，车可以攻击与之处在同一行或同一列上的棋子。指南车是有方向的车。横向指南车可以攻击与之处在同一行上的棋子。纵向指南车可以攻击与之处在同一列上的棋子。指南车问题要求在m×n格的棋盘上放置指南车，并确定各指南车的攻击方向，使棋盘上不受指南车攻击的方格数最多。编程任务：对于给定的m×n格的棋盘和2 个整数x 和y。整数x 表示棋盘上有x个规定方格应放置指南车，但攻击方向未定...
Horse Riding.rar计算国际象棋马的行走路线...
在一个8×8国际象棋盘上，有8个皇后，每个皇后占一格；要求皇后间不会出现相互“攻击”的现象，即不能有两个皇后处在同一行、同一列或同一对角线上。问共有多少种不同的方法。...
EVC4.0开发的国际象棋的元代码，编译通过了的...
用8051实现的一个国际象棋的源代码,很值得学习研究....
用数组来解决关于国际象棋马踏棋盘问题已经调试无错误...
国际象棋相关帖子
90年 代初，如果你能上网的话，应该知道当年颇负盛名的 Usenet 讨论组。该讨论组创立伊始是为了国际象棋，然而随后讨论话题便围绕着软件、色情文学或是某些《龙与地下城》或者科幻小说衍生来的话题。我之所以知道这个是因为我曾也在讨论组中。虽然对于一个 8 岁的小孩来说，出现在那种地方可能不太合适，但这没什么。
暂且不管他们的话题内容，这些早期的极客先驱者有一套极佳的合作方案。他们以开放存取、相互协作为...
1996年，IBM公司开发的深蓝计算机与国际象棋大师卡斯帕罗夫进行了一场比赛，最后深蓝计算机取得了胜利。当时这引起了社会各界的巨大轰动，甚至有人认为人工智能将取代人脑。此后，智能技术的发展并没有想象中的那样快，但是最近几年，智能技术在为机器赋予了人类感觉和思考能力方面取得了长足进步，将在2016年呈现十大发展趋势。
一、信息系统集成化
推动智能技术重大突破
由于各类信息系统的集成...
：“人工智能是尚未实现的任何事情。”人们称之为“人工智能效应”。怀疑者贬低人工智能程序的性能，认为人工智能不是真正的智能，不过是计算和算法的蛮力。
这个批评有一定道理。尽管计算机击败了国际象棋大师和“危险边缘”智力竞赛的选手，还学会和我们对话和开车，但Siri和微软小娜仍有缺点并会惹人生气。
不过，情况即将改变，就连怀疑者都要说人工智能已经到来。“深度学习”神经网络有了重大进展，它们通过摄取大量...
8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后）技术面试都这德行……当年他们让我翻转一个链接列表，当时我的灵魂就已逃离了那个房间。
——@0xeb1997 年他们面试了我 6 个小时，最后一个问题是「为什么我们要聘用你？」我的回答是：你们 TM 自己想吧。最后我拿到了 offer
——@daniel_bilar如果是我，我会当场把那个白板翻过来然后说「看，我完...
、情感、判断力与决定权，但是它却有着它的优势成功。roboteasy机器人e资讯了解，国际象棋专家表示即使计算机很强大，但是最为出色的棋手则是人类和智能的合体。然而目前的社会领域各行各业也是正在进行人机合作这种趋势走向。医学中使用仪器进行高分效的检测，使用手机智能进行语音识别为使用者提供多钟语音翻译服务。人工智能渗入至生活各角，为人类的生活带来影响力。
其实并不是所有的人工智能，都能带来显着性的影响...
制造产品”，因此他坚信个性化生产将颠覆大规模制造业。
　　Neil教授认为，自2011年IBM超级计算机“沃森”打败两名人类国际象棋世界冠军，到2014年计算机首次通过图灵测试，这都标志着人工智能时代已经来临。人工智能技术不仅仅是能撬动整个地球的杠杆，它还能增强机器人、合成生物和纳米等指数式技术的影响力。
霍金等呼吁在人工智能创新方面采取安全措施
日下午消息，史蒂芬·霍金...
= LCD12864_PowerOn;
　　　至于剩下的，大家伙就自己看程序吧。程序还很简单，只是一个画国际象棋的demo函数。
　　　过后我要在这个基础上，写一个 多级菜单界面，当然那就是另一回事了，敬请期待。
昨天晚上...
直接定义为 LCD12864。
这里有一个”历史原因“。
我最初写这个12864驱动的时候，我只写了串行方式，我曾答应给 卖给我这个12864屏的朋友一套我自己写的例程。
所以我打算发给她的时候，她问我，是否还有并行的驱动，我说还没，我写完就给你吧。
然后我发现，由于我这种封装驱动的方式，导致我需要重新写一次 诸如 在屏上画 国际象棋棋盘&&这样的画屏函数
使用免费软件，用简单的命令建立有机模式。
约翰·埃德加·帕克
上载：美丽的笔刷
用画笔工具创建简单的图形。
查尔斯·普拉特
摄像机新选择
操作简单的视频拍摄可能性越来越大。
查尔斯·普拉特
1+2+3：制作风触发灯笼
一个发光二级管、一片羽毛和一片弹簧。
莫特·斯科格力
1+2+3：机械图复制图
Cy·蒂姆尼
本帖最后由 平湖秋月 于
10:55 编辑
我看到有些坛友谈到，说什么自己用基于寄存器的开发模式比采样
基于固件的开发模式，得出的代码占用资源更少！！这句花语法当然
是对的，不过，想过没有，就我们国内工程师目前的编程水平，怎么能
跟TI的软件工程师pk呢!就像人和电脑下国际象棋，能搞定电脑的也只有
老毛子的那几个国际大师在不犯错误的情况下，才可能出现“胜”的可能性...
国际象棋视频
国际象棋创意
你可能感兴趣的标签
热门资源推荐中国象棋博弈树搜索算法研究与实现--《沈阳工业大学》2012年硕士论文
中国象棋博弈树搜索算法研究与实现
【摘要】：计算机博弈是人工智能的一个传统研究领域。计算机博弈为人工智能提供一个实验平台,将人工智能的一些理论与方法应用于计算机博弈,可通过博弈水平的高低来检验这些理论与方法的有效性,研究计算机博弈所得到的成果也可推广至人工智能的其他领域。二者相辅相成,相互促进。国际象棋计算机博弈已经比较成熟,历史悠久的中国象棋计算机博弈很多技术还不够成熟,随着对人工智能的深入研究,对中国象棋博弈的研究成为人工智能研究的热点之一。
本文对中国象棋博弈树搜索算法以及博弈系统进行研究,介绍了中国象棋计算机博弈的关键技术,分析了数据结构设计和评估函数在系统中所起的作用。深入研究博弈树的特性以及基于α-β剪枝的博弈树搜索算法的改进策略,包括窗口原则、历史表法、置换表法、空着搜索等,结合不同的改进策略得到不同的搜索引擎,对这些引擎的性能进行测试,验证它们的剪枝效率。研究了静态搜索,在静态搜索中加入吃子走法排序和将军延伸,解决了博弈树搜索的水平效应。
实现一个人机博弈系统,实现生成并显示棋谱,统计搜索引擎每次搜索的叶节点和所用的时间,结合不同的优化策略得到不同的搜索引擎,通过实验证明综合多种改进策略的搜索算法的剪枝效率得到了提高。选取剪枝效率较高的搜索引擎结合静态搜索提高棋力,让这些新的搜索引擎对弈,证明了剪枝效率最高的PVSHNTIQ搜索算法的棋力也最高。
【关键词】：
【学位授予单位】：沈阳工业大学【学位级别】：硕士【学位授予年份】：2012【分类号】：TP391.3【目录】：
摘要5-6Abstract6-9第一章 绪论9-13 1.1 课题的研究背景9 1.2 国内外研究现状9-11
1.2.1 国外研究现状9-10
1.2.2 国内研究现状10-11 1.3 论文结构11-13第二章 数据结构设计13-20 2.1 棋局状态表示13-16
2.1.1 棋盘表示13-15
2.1.2 棋子表示15-16 2.2 走法生成16-18
2.2.1 走法表示17
2.2.2 走法生成17-18 2.3 棋局辅助信息18-20第三章 局面评估函数20-24 3.1 局面评估函数组成部分20-22
3.1.1 固定子力价值20-21
3.1.2 棋子的位置价值21
3.1.3 其它评估因素21-22 3.2 局面评估函数与博弈系统的关系22-24第四章 博弈树搜索算法研究24-48 4.1 博弈树搜索24-26
4.1.1 搜索24-25
4.1.2 中国象棋博弈树25-26 4.2 基本的搜索算法26-35
4.2.1 极大极小值算法26-29
4.2.2 α-β剪枝算法29-33
4.2.3 α-β剪枝算法的性能分析33-35 4.3 基于窗口原则的改进策略35-40
4.3.1 Fail-Soft alpha-beta算法35-36
4.3.2 渴望搜索36-38
4.3.3 极小窗口搜索38-39
4.3.4 基于窗口原则搜索算法小结39-40 4.4 博弈树节点排序40-42
4.4.1 吃子走法启发40-41
4.4.2 杀手启发41
4.4.3 历史表启发41-42 4.5 置换表42-44 4.6 迭代加深44-45 4.7 水平效应与静态搜索45-46 4.8 裁剪算法46-48
4.8.1 无害裁剪46
4.8.2 空着裁剪46-48第五章 系统实现与实验分析48-66 5.1 走法生成与局面评估函数48-50 5.2 优化策略实现50-57
5.2.1 历史表实现50
5.2.2 置换表实现50-52
5.2.3 迭代加深实现52-55
5.2.4 静态搜索实现55-57 5.3 系统实现57-63
5.3.1 系统功能介绍57-59
5.3.2 综合搜索算法59-63 5.4 实验分析63-66第六章 结论66-67参考文献67-69在学研究成果69-70致谢70
欢迎：、、)
支持CAJ、PDF文件格式
【参考文献】
中国期刊全文数据库
岳金朋;冯速;;[J];北京师范大学学报(自然科学版);2009年02期
李红;吴粉侠;刘小豫;;[J];长春工程学院学报(自然科学版);2007年02期
王骄,王涛,罗艳红,徐心和;[J];东北大学学报;2005年10期
鲍鹏;高珩;王伟;;[J];电脑学习;2009年05期
舒晓苓;;[J];电脑知识与技术;2008年09期
张振;顾治华;;[J];电脑知识与技术;2008年24期
许景婷;;[J];工业技术经济;2006年11期
周玮;王水涛;孙旸;;[J];计算机工程与应用;2006年35期
张聪品;刘春红;徐久成;;[J];计算机工程与应用;2008年16期
焦尚彬;刘丁;;[J];计算机工程与应用;2010年06期
中国硕士学位论文全文数据库
王一非;[D];哈尔滨工程大学;2007年
危春波;[D];昆明理工大学;2008年
谢艳茹;[D];西安理工大学;2008年
谢国;[D];西安理工大学;2008年
毕津滔;[D];哈尔滨理工大学;2009年
【共引文献】
中国期刊全文数据库
谢招犇;刘万蓉;谢静如;;[J];安徽农业科学;2011年36期
黄杰;陈雪;吴渊;;[J];兵工自动化;2008年07期
惠一楠;朱华勇;沈林成;;[J];兵工自动化;2009年01期
陈易;王晶;;[J];北京化工大学学报(自然科学版);2009年05期
李擎,宋顶立,张双江,李哲,刘建光,王志良;[J];北京科技大学学报;2005年03期
熊翱,孟洛明;[J];北京邮电大学学报;2004年S2期
余兵;廖宗凡;;[J];变频器世界;2006年02期
陈丹;刘月兰;;[J];北京工商大学学报(自然科学版);2006年06期
李久熙;王春山;赵树朋;高喜银;叶振合;;[J];包装工程;2005年06期
王同喜;孙淑霞;;[J];成都理工大学学报(自然科学版);2007年04期
中国重要会议论文全文数据库
冯闻捷;彭力;;[A];第二十七届中国控制会议论文集[C];2008年
王非凡;李文亚;;[A];第十六次全国焊接学术会议论文摘要集[C];2011年
王兰莎;张国英;;[A];图像图形技术研究与应用(2010)[C];2010年
赵斌宁;王帅;周庆忠;;[A];全国ISNBM学术交流会暨电脑开发与应用创刊20周年庆祝大会论文集[C];2005年
谢晓霞;倪文桥;;[A];2007北京地区高校研究生学术交流会通信与信息技术会议论文集（上册）[C];2008年
胡松峰;彭显刚;;[A];武汉(南方九省)电工理论学会第22届学术年会、河南省电工技术学会年会论文集[C];2010年
王洪岩;朱峰;张雪峰;李玉倩;安爽;徐心和;;[A];2007中国控制与决策学术年会论文集[C];2007年
朱峰;张雪峰;徐心和;;[A];2007中国控制与决策学术年会论文集[C];2007年
;[A];Proceedings of the 2011 Chinese Control and Decision Conference（CCDC）[C];2011年
李楚刚;吴唏;郭石军;;[A];海浪海啸与实用航海技术[C];2006年
中国博士学位论文全文数据库
丁和艳;[D];华中科技大学;2010年
周国雄;[D];中南大学;2010年
赵晓东;[D];河北工业大学;2011年
张谆;[D];大连理工大学;2011年
何涛;[D];南京邮电大学;2011年
徐长明;[D];东北大学;2010年
谢健文;[D];广东工业大学;2004年
黄群星;[D];浙江大学;2005年
石跃祥;[D];中南大学;2005年
王家忠;[D];吉林大学;2006年
中国硕士学位论文全文数据库
王真;[D];郑州大学;2010年
蔡磊;[D];辽宁工程技术大学;2009年
赵慧静;[D];沈阳理工大学;2010年
马超;[D];北京交通大学;2011年
方晓汾;[D];浙江大学;2011年
张恩海;[D];沈阳大学;2011年
余庆平;[D];西安电子科技大学;2011年
王伟东;[D];北京交通大学;2011年
宋宏宇;[D];吉林大学;2011年
李梅;[D];大连海事大学;2011年
【二级参考文献】
中国期刊全文数据库
赵志诚;蔡安妮;;[J];北京邮电大学学报;2007年05期
王骄,王涛,罗艳红,徐心和;[J];东北大学学报;2005年10期
王兴伟;江南;王家林;黄敏;;[J];东北大学学报;2006年07期
吴华波;钱春来;;[J];单片机与嵌入式系统应用;2006年08期
杜娟,汪小燕;[J];电气电子教学学报;2004年01期
陈心浩;[J];电子技术;2003年10期
徐玉,韩波,李平;[J];工业控制计算机;2004年11期
蒋学勤;[J];贵州大学学报(自然科学版);2005年01期
王健强;程汀;;[J];合肥工业大学学报(自然科学版);2008年07期
熊光明;赵涛;龚建伟;高峻峣;;[J];机床与液压;2007年03期
中国硕士学位论文全文数据库
王骐;[D];浙江大学;2006年
张赜;[D];东北大学;2006年
张杰;[D];南京理工大学;2008年
谢艳茹;[D];西安理工大学;2008年
【相似文献】
中国期刊全文数据库
尹宏伟;;[J];科技浪潮;2006年08期
;[J];每周电脑报;1998年50期
杨水元;[J];发明与革新;2001年07期
王炳晨;;[J];微电脑世界;2006年10期
闵波;许家珆;;[J];西南民族大学学报(自然科学版);2010年03期
;[J];科技浪潮;2006年07期
;[J];收藏界;2008年01期
燕铭;;[J];每周电脑报;2006年31期
;[J];中国计算机用户;2006年33期
林健;黄鸿;刘进长;;[J];机器人技术与应用;2006年05期
中国重要会议论文全文数据库
支成秀;梁正友;;[A];广西计算机学会2006年年会论文集[C];2006年
常新杰;李言俊;;[A];1998年中国智能自动化学术会议论文集（上册）[C];1998年
李玉;侯媛彬;;[A];第十七届全国煤矿自动化学术年会、中国煤炭学会自动化专业委员会学术会议论文集[C];2007年
蔡阳波;邓一贵;王康;;[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年
张国亮;郑方;吴文虎;;[A];第六届全国人机语音通讯学术会议论文集[C];2001年
张晓玲;钟诚;李智;李锦;张尊国;;[A];2007年全国开放式分布与并行计算机学术会议论文集(上册)[C];2007年
李金;蒋国平;;[A];2007中国控制与决策学术年会论文集[C];2007年
李亮;路世豹;于广明;;[A];结构及多学科优化工程应用与理论研讨会’2009（CSMO-2009）论文集[C];2009年
孙文彬;赵学胜;邹仁贵;;[A];第四届海峡两岸GIS发展研讨会暨中国GIS协会第十届年会论文集[C];2006年
徐波;黄泰翼;;[A];第五届全国人机语音通讯学术会议论文集[C];1998年
中国重要报纸全文数据库
利国;[N];今日信息报;2006年
钱晞;[N];四川日报;2008年
刘乾胜;[N];围棋报;2009年
记者　 孙永杰;[N];中国电子报;2006年
葛会忠;[N];中国体育报;2006年
张艳蕊;[N];中国企业报;2005年
苏迅;[N];安阳日报;2006年
记者 何屹;[N];科技日报;2005年
胡国民 通讯员
陈明喜;[N];黄冈日报;2007年
邓润青;[N];衡阳日报;2007年
中国博士学位论文全文数据库
周晖;[D];东华大学;2010年
阎兴頔;[D];华东理工大学;2013年
刘孝男;[D];吉林大学;2010年
吴昊;[D];合肥工业大学;2013年
岳鹏;[D];西南大学;2007年
王吉;[D];中国科学技术大学;2006年
常珊;[D];北京工业大学;2009年
张映玉;[D];华中科技大学;2011年
郝亮;[D];清华大学;2010年
刘国乐;[D];北京邮电大学;2013年
中国硕士学位论文全文数据库
宋兴亮;[D];沈阳工业大学;2012年
郭峰;[D];河北大学;2009年
王志水;[D];中国石油大学;2007年
李小舟;[D];华南理工大学;2010年
郭秀丽;[D];河北大学;2010年
王友政;[D];东北大学;2008年
刘婉;[D];武汉科技大学;2013年
任建敏;[D];燕山大学;2012年
裴祥豪;[D];河北大学;2009年
王一非;[D];哈尔滨工程大学;2007年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号中国象棋计算机博弈关键技术分析
中国象棋计算机博弈关键技术分析
【摘要】机器博弈被认为是人工智能领域最具挑战性的研究方向之一．国际象棋的计算机博弈已经有了很长的历史，并且经历了一场波澜壮阔的“搏杀”，“深蓝”计算机的胜利也给人类留下了难以忘怀的记忆．中国象棋计算机博弈的难度绝不亚于国际象棋，不仅涉足学者太少，而且参考资料不多．在国际象棋成熟技术的基ak_L，结合在中国象棋机器博弈方面的多年实践，总结出一套过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库与残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的热点与方向．
【关键词】人工智能；中国象棋计算机博弈；机器博弈过程建模；着法生成；评估函数；博弈树搜索
Key Techno1ogie Analysis of
Chinese Chess Computer Game
【Abstract】ComputergameisoneOfthemostchallengingtopmsinthefieldOfartificialintelligence．Chesscomputergamehasalonghistory，andcomethroughtoughresearch．Finally,DeepBlue`svictorystartledthewholeworld．Chinesechesscomputergameismorecomplexthanchesscomputergame，andthefewerresearchersandfewerreferencesleadthelagintheheld．BasedOnaseriesO{technologiesOfchesscomputergameandyearspracticeOfChinesechess，asetOfschemesandmethodsareproposed，suchastheprocessmodeling，staterepresentation，movegeneration，evaluationfunction，searchinggametree，openingbook，endgamedatabase，systemtestandparameteroptimization，etc．Hottopmsandtasksarealsoproposedattheend．
【Keywords】artificialintelligence(A1)；Chinesechesscomputergame；processmodelingOfcomputergame；movegeneration；e―valuationfunction；searchinggametree
博弈问题无所不在，小到孩童的游戏与争论、各种场合下的讨价还价，大到商家的竞争、各种突发事件(恐怖、灾害)的应急处理、国家的外交、流血的和不流血的战争，只要局中的双方主体存在某种利益冲突，博弈便成为矛盾表现和求解的一种方式．博弈与对策将成为一类智能系统研究的焦点问题．
象棋是从两军对阵中抽象出来的一种智力游戏，因此它是博弈的一个标准问题．下棋的双方无时不在调动自己的一切智能，充分发挥逻辑思维、形象思维和灵感思维的能力．所以，在人工智能领域始终将棋类的机器博弈作为最具挑战性的研究方向之一．
早在半个多世纪之前，信息论的创始人C．E香侬教授就提出了为象棋博弈编程的方案，成为机器博弈的创始人．半个世纪以来，国际象棋的计算机博弈十分活跃，而且确实经历了一场惊心动魄的激烈搏杀
1958年，IBM704成为第一台能同人下棋的计算机，名为“思考”，思考速度每秒200步．到了60年代中期，科学家德里夫斯依然断言，计算机将无法击败一位年仅10岁的棋手．
1973年，CHESS4．0被B．SlateandAtkin开发出来，成为未来程序的基础．1979年，国际象棋软件4．9达到专家级水平．
1981年，CRAYBLITZ新的超级计算机拥有特殊的集成电路，预言可以在1995年击败世界棋王．
1983年，KenThompson开发了国际象棋硬件BEI．LE，达到了大师水平．
80年代中期，美国的卡内基梅隆大学开始研究世界级的国际象棋计算机程序――“深思”．1987年，“深思”首次以每秒钟75万步的思考速度露面，它的水平相当于拥有国际等级分为2450的棋手．1988年，“深思”击败丹麦特级大师拉尔森．
1989年，“深思”已经有6台信息处理器，每秒思考速度达200万步，但在与世界棋王卡斯帕罗夫进行的“人机大战”中，以0比2败北．
1993年，“深思”二代击败了丹麦国家队，并在与世界优秀女棋手小波尔加的对抗中获胜．
1995年，IBM&深蓝”更新程序，新的集成电路将其思考速度提高到每秒300万步．1996年，“深蓝”在向卡斯帕罗夫的挑战赛中，以2比4败北．
1997年，由1名国际特级大师，4名电脑专家组成的“深蓝”小组研究开发出“更深的蓝”，它具有更加高级的“大脑”，通过安装在RS／6000S大型计算机上的256个专用处理芯片，可以在每秒钟计算2亿步，并且存储了百年来世界顶尖棋手的10亿套棋谱，最后“超级深蓝”以3．5比2．5击败了卡斯帕罗夫．卡斯帕罗夫要求重赛，但没有得到回应．
时至今日，尽管新的硬件、软件系统层出不穷，但国际象棋的机器博弈和人机大战仍然持续不断．因为人们总在不断地挑战自我，况且计算机在人机大战中仍然没有占据绝对优势．卡斯帕罗夫也仅仅输给“超级深蓝”那一次．
中国象棋是世界上历史最为悠久的棋类，早在2000多年前的战国时代就已经有了关于象棋的记载．然而中国象棋的计算机博弈却开展的不尽人意，成了“被爱情遗忘的角落”．缺少学者的关注，寥寥无几的参与者，匮乏的参考文献，沉寂的计算机博弈氛围，使得中国象棋的计算机博弈在中国大陆难有作为，只是成为一些商家的游戏软件和教学载体．这便是当前我们所面临的艰难局面．
国际象棋棋盘8行8列总计64格，中国象棋lo行9列总计90个交点，显然中国象棋的运子空间更大．相比之―厂，中国象棋的着法更为特殊(如蹩马脚、压象眼等)，棋局变化也更加复杂，这都是对中国象棋的计算机博弈提出的困难和挑战．
随着计算机博弈在Othello、Checker和国际象棋三种棋类上的成功，全世界的学者又把目光投到更为复杂的中国象棋(ChineseChess)、日本将棋(Shogi)、围棋(Go)上面．几种棋类遍历搜索的复杂度对比见表1―2，表中的数字为复杂度的自然对数值．显然，这更是对中国学者提出的严峻挑战．
面对如此富于挑战性的局面，东北大学人工智能与机器人研究所从2003年便开始了中国象棋计算机博弈课题的研究．在认真借鉴国际象棋开发成果的基础上，突破了系列关键技术，开发出具有相当棋力的博弈软件系统，并在2004年成立了“棋天大圣”代表队，准备在中象机器博弈领域开创新的局面。本文便是针对系列关键技术的总结和归纳．接下来的各节分别论述了过程建模、状态表示、着法生成、棋局评估、博弈树搜索、开局库建立、残局库开发、系统测试与参数优化等核心技术要点，最后提出了当前研究的难点．
象棋博弈过程建模
人工智能的先驱者们曾认真地表明：如果能够掌握下棋的本质，也许就掌握了人类智能行为的核心；那些能够存在于下棋活动中的重大原则，或许就存在于其它任何需要人类智能的活动中．
在各种棋牌博弈当中，象棋是一种完全知识博弈(Gamesofcompleteinformation)，即参与双方在任何时候都完全清楚每一个棋子是否存在，位于何处．
象棋博弈具有如下基本特征：
(1)规则简单明确，成功与失败的判定标准简单，不包含任何机会或偶然性；
(2)问题的状态(即局面)数量在数学意义上是有限的；
(3)问题的解决在认识意义上不需要过多的知识．
为了深入探讨机器博弈的原理与方法学问题，尤其要从系统论和博弈沦的角度研究问题的规律与求解方法，有必要分析象棋对弈的演化过程，建立相应的数学模型．图1给出了象棋博弈状态演化过程图．图中表明棋局状态是在着法算子作用下进行演化的，其对应的状态转移方程可以写成式中为象棋的初始局面，为第n+1步的着法算子，而S。+：为走完第n-I-1步后的棋局．于是，不难写出式中S，为终局，或红胜，或黑胜，或和棋．显然，着法序列Q＝&Q~q2q3…Q／}便是记载博弈过程的棋谱，其中单数项序列Q+＝{Qlg…)为红方系列着法，而偶数项序列Q。＝{Q：Q4…}便是黑方的系列着法．
着法便是弈棋者的决策．尽管每次只能走出一步，但弈棋者可能考虑过全部有价值的走法，并且通过前瞻若干步，才形成弈棋者的当前决策．图2便以状态演化流程框图的形式展示了计算机应该如何实现这样的“思维”过程．
在这里全部可能的走法是通过着法生成器给出的，由它生成了第j步的A种可行着法，根据状态演化方程(1)，在算子g㈠，j＝1…是的作用下所形成的第i步后的棋局便不是一个，而同样是是个紧后棋局状态，即S，．j，／＝1…是．显然，这便是决策树，亦称为博弈树的展开过程．弈棋者按照这样的思维方式，必然展开一棵规模庞大的、根在上而叶在下的博弈树，如图3所示．它与一般决策树的不同点则在于它的决策主体不是一方，而是相互对立的双方，即红方和黑方．图中方节点代表轮到红方走棋的状态(棋局)，圆节点代表轮到黑方走棋的状态．显然，方、圆节点间的连线便对应于一个个着法．如果说，一个优秀棋手可以前瞻四步，则表示在他的脑海中的是将这棵博弈树展开4层(D叩th)．
博弈树上的每一个节点都代表一个棋局，棋手就是要在众多的叶子节点上挑选一个最佳的局面作为自己的选择，从而反推到当前的着法．
中国象棋博弈树的庞大是可以想象的．如果按照每一步平均有45种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，则要考虑45’*匀10’‘*种局面。据说这一天文数字要比地球上原子数目还要多，即使用世界上最快的计算机进行计算，直到地球毁灭也无法算出第一步的着法．
棋局状态的表示
要让计算机下棋首先需要解决的就是棋盘和棋局的数字表示。棋盘上面有9路10行形成90个交叉点，它很容易用109的棋盘数偶矩阵M。表示与坐标的对应关系．
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
要表示棋局则首先要给棋子编码．应该说编码的方法是任意的，只要能够满足棋局表示的唯一性和可区分性，都是可行的编码．如果考虑和追求棋局处理的节俭与快捷，那么在编码上还是具有研究的余地．
“棋天大圣”的兵种(Arms)编码在表2中给出．红方和黑方兵种编码仅相差一个负号，这为棋局评估红黑双方保持对称性提供了方便．
仅有兵种的编码是不够的．为了跟踪棋子的挪动与拼杀，还需要进行棋子编码．我们的做法如表3所示．由此便可以根据棋局给出兵种状态矩阵S‘和棋子状态矩阵S”．式(3)(4)便给出了中象初始局面(图4)对应的状态矩阵．
为了避免从棋子状态矩阵中提取某棋子实时位置的搜索过程，还需要直接给出棋子位置矩阵：PM=[PMi，j]2*32,矩阵中第一行PM1，j表示编号为j的棋子在棋盘矩阵中的行号，矩阵中第2行PM2，j表示编号为j的棋子在棋盘矩阵中的列(路)号．对应于S俨则有初始棋子位置矩阵为
在着法生成过程中，时常只关心棋子的分布，而不关心是什么棋子，这时可以用比特棋盘表示棋局的某种状态，它其实是棋盘状态矩阵5的布尔表示．比特棋盘的定义为
根据计算过程的需要，还可以定义其它含义的各种单项比特矩阵或比特向量．如：红棋比特矩阵，中路比特向量等．通常我们使用状态集合S。来表示n时刻的棋局状态．
棋手都知道中国象棋着法的表示方法，如：炮八平五，马8进?等等．看得出，这种着法是和当时的棋局有着不可分割的联系．我们称其为相对着法，用／来表示．而在机器博弈中所说的着法g，都是绝对着法，它由提―动―落―吃4部分内容组成．即
式中from为“提址”，即此着的出发位置，moved
(chessman moved)为“动子”，即走动哪个棋子；to为“落址”，即着法的到达位置；killed (chessman
killed)为“吃子”，即吃掉哪个棋子．显然，落址处有对方棋子，则形成吃子；落址处没有棋子，则“吃空”，仅走不吃；落址处为本方棋子，则为非法着法．
着法生成方法一般有棋盘扫描法、模板匹配法和预置表法，时常还结合使用．
4．1 棋盘扫描法
根据象棋规则，定义可行区域，如棋盘有效区域A={(i,j)|11}，红方半区AR={(i,j)|61}，黑方九宫APB={(i,j)|14}等。在已知提址和动子的情况下，根据各兵种的行棋规则，计算合法落址．有时还要考虑制约条件．表4给出了马的着法规则．其它动子以此类推．
虽然在着法的表达上，棋盘扫描法最为直观，但在着法生成的过程中需要在棋盘上反复扫描有效区域、制约条件和落址状况，时间开销巨大，实战意义不强．
4．2 模板匹配法
当动子确定之后，其落址与提址的相对关系便被固定下来．于是可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址．图5给出了走马的匹配模板．当将马字对准提址，Х表示蹩马腿的制约条件，○表示符合“走日”规则的落址，根据X的具体分布，很容易判断可能的落址．再通过单项比特矩阵比对，实现“本方子则止，对方子则吃”，完成“提―动―落―吃”内容的确定．
比较适合使用模板的动子为马和相(象)．
4．3 预置表法
预置表法是使用最为经常的着法生成方法．它的基本思想就是用空间换时间．为了节省博弈过程中的生成着法的扫描时间，将动子在棋盘任何位置(提址)、针对棋子的全部可能分布，事先给出可能的吃子走法和非吃子走法．
以图6炮的一个行着法预置表为例，炮的提址为某行的第6列，该行考虑的棋子分布为C]布尔向量形式．不难得出，此时炮的非吃子着法的落址为[)，而可能的吃子着法的落址为C]．将这样的输入(炮的列号，该行棋子的布尔分布)和输出(吃子落址和非吃子落址的布尔表示)关系写入一个预置表中，在使用时通过查表，便很快可以得到可行的着法．而且还可以区分开吃子着法和非吃子着法，必然有利于搜索路径的选择(先吃，后不吃)．
这样的预置表的规模是比较大的．对炮而言(车也是这样)，就每一行棋子的可行排列数恰好对应于9位二进制数(有子为l，无子为0)，即29=512种情况(项)．考虑到炮的9种可能位置，预置表的规模即为9*512项．再分开吃子和非吃子，还要考虑各列的全部情况，所以表的总规模为：2*9*512+2*10*项。如果假设每一项需要4个字节，那存放炮的着法预置表就需要116k内存空间．应该说还是可以接受的，因为它可以将着法生成的速度提高几个数量级．
棋局评估函数
棋局评估就是给棋局打分．由于在较少的步数内，一般难以将对方将死．在难以判断输赢的情况下识别棋局的好坏，可行的办法就是对局面进行量化，通过数值评判棋局的好坏．由于评估需要大量的象棋知识，仁者见仁，智者见智，评估函数的设计便成为机器博弈中最为人性化的部分．目前对于评估函数取得共识的观点，应该包括如下部分
棋子价值评估值(e1)
简单说就是评估双方都有哪些棋子在棋盘上．如设定：车―1000；马―450，炮―450，仕―170，相-160，兵―60，将帅―无穷大，红方为正值，黑方为负值．
棋子位置评估值(e2)
同样一个棋子，处在棋盘的不同位置上其价值大不相同，式(9)给出了兵的位置评估值．可见过河兵，尤其是逼近和进入九宫的兵身价倍增．根据设计者的经验，各个兵种在其可行位置上都应该给出位置评估矩阵，以方便计算其位置评估值．而总的棋子位置评估值f。则为全部盘上棋子评估值之和．
棋子灵活度评估值(e3)
对各兵种而言，每多一个可走位置就加上一定分值．如设定：兵―15，士―1，象―l，车―6，马―12，炮―6，将―0．
棋子配合评估值(e4)
重点是车马炮的配合与牵制．过河兵牵手可加200分．连环马、担子炮、霸王车等都可以考虑加分．
将帅安全评估值(e5)
此项多从盘势上加以考虑．如多子归边、空头炮、当头炮、沉底炮、将帅位置等，都要给出一定数量、有正有负的评估值．
我方总的棋局评估值便是求取各项评估值之和不仅要计算本方的，还要计算对方的．本方为正值，对方为负值，其代数和即为当前局面评估值．显然，总值为正对我方有利，负值对对方有利．绝对值的大小说明双方棋势的差距．
不难看出，评估函数中涉及到的权值系数可能多达上千个，都需要认真选择与权衡．困难之处在于，至今还有许多盲点，或者认识不到，或者说不出好坏，有待进一步研究与开发．可能还需要引进“自适应”与“自学习”功能．
博弈树搜索
本文第2节已经为象棋博弈问题建立了状态空间显示图，亦即博弈树图模型(见图3)．搜索法是求解此类图模型的基本方法．前面提到，我们无法搜索到最终的胜负状态，于是搜索的目标便成为如何在有限深度的博弈树中找到评估值最高而又不剧烈波动的最佳状态(棋局)，于是从当前状态出发到达最佳状态的路径便为最佳路径(Principalcontinuation)，它代表着理智双方精彩对弈的系列着法．而最佳路径上的第1步棋便成为当前局面的最佳着法(Thebestmove)．所谓“不剧烈波动”就是说最佳棋局不是在进行子力交换与激烈拼杀的过程当中．
需要注意的是博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树．在图3中，红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，即实行“Max搜索”．而其应对方――黑方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，即实行&Min搜索”．香侬(ClaudeShannon)教授早在1950年首先提出了“极大―极小算法”(MinimaxAlgori―thm)03，从而奠定丁计算机博弈的理论基础．
在搜索策略上，一般可以分为以下三种：
A类――穷尽搜索(Exhaustive search)
B类――选择性搜索(Selective search)
C类――目标导向搜索(Goal oriented
会下棋的人都知道“一着不慎，满盘皆输”的道理．于是，看得远(搜索的深)，看得准(真正找到指定深度内的最佳的平稳棋局)，便成为搜索算法的基本着眼点．显然穷尽搜索成为人们首选的搜索策略．原始的蛮力搜索(Brutesearch)一般采用广度优先搜索(Breadth―firstsearch)[63，一层层展开，一层层搜索，因为“穷尽”而没有风险，不会漏掉展开深度内的最优解．但是，在给定的时间内搜索的节点数是基本固定的，当考虑到博弈树的平均分枝数(分枝因子B＝40～50)，搜索深度也是基本固定的．假设计算机搜索节点速率为1M／秒，中国象棋B＝45，表5给出了在不同的给定时间T内达到的搜索层数D．
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
由于完整的博弈树过于庞大，盲目搜索所能达到的层数十分有限，在象棋博弈中几乎没有实用价值．
若想在指定时间内将搜索深度加以提高，一方面需要优化硬件和程序代码，提高单位时间内搜索的节点数；另一方面就需要像人类棋手一样有选择性地进行搜索，即对博弈树进行必要的裁剪(cut―off／pruning)．
6．1 a-β搜索
a-β剪枝搜索是一种基于o―卢剪枝(a-卢cut―off)[s]的深度优先搜索(Depth―firstsearch)．为了表述方便，我们不妨将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；而将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法．
在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得。以“落实”的着法最佳值，记为oD显然此。值可作为MAX方着法指标的下界．在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合(2步棋)之后评估值变差，即孙节点评估值低于下界。值，则便可以剪掉此枝(以该子节点为根的子树)，即不再考虑此“软着”的延伸．此类剪枝称为。剪枝。图7给出了搜索和剪枝过程，最后得到如粗箭头所示的最佳路径片断．
同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的钳制值，记为A显然此卢值可作为MAX方可能实现着法指标的上界．在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界夕值，则便可以剪掉此枝，即不再考虑此“软着”的延伸．此类剪枝称为卢剪枝．图8给出了搜索和剪枝过程，最后得到如粗箭头所示的最佳路径片断．
需要指出的是，a-β剪枝是根据极大―极小搜索规则的进行的，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。剪枝技巧的发现，一下便为博弈树搜索效率的提高开创了崭新的局面co]．1975年Knuth和Moore给出了a-β算法正确性的数学证明．a-β剪枝算法的效率与子节点扩展的先后顺序相关．在最理想情况下(极小树)，其生成的节点数目为
其中D为搜索深度，B为分枝因子(Branchingfactor)．在不使用a-β剪枝时，需要搜索的节点数是ND＝BD，即极大树．所以最理想情况下a-β算法搜索深度为D的节点数相当于搜索深度为D／2的不做任何剪枝节点数。
如何才能得到极小树?不难看出，如果最左路的分枝就是最佳路径，亦即理智双方最为精彩的对弈着法序列，那么就可以将右路各分枝陆续剪掉，从而使搜索的节点数仅为极大树的
为了得到最好的节点扩展顺序，许多搜索算法在着法(节点扩展的分枝)排序上给予特别的关注．比如在着法生成(节点扩展)时，先生成吃子着法，尤其先生成吃分值高的“大子”着法，因为由此产生着法更有可能是最佳的．
围绕着法排序，已经出现许多优秀的搜索算法与举措．如：同形表法(Transposition
table)、吃子走法的SEE排序、杀手走法(Killer heuristic)、未吃子走法的历史启发排序(Historic
heuristic)、类比法(Method of analogies)等．
有人将a-β剪枝作用延伸到多千回合之后，于是又出现了深层a-β剪枝(Deepn―pcut―off)算法．也取得很好效果．
a-β窗口搜索
从a-β剪枝原理中得知，a值可作为MAX方可实现着法指标的下界，而夕值(应对方的钳制值)便成为MAX方可实现着法指标的上界，于是由。和夕可以形成一个MAX方候选着法的窗口．围绕如何能够快速得到一个尽可能小而又尽可能准确的窗口，也便出现了各种各样的o』窗口搜索算法．如Fail-Soft
Alpha-Beta、Aspiration Search(渴望搜索)、Minimal Window
Search(最小窗口搜索)、Principal Vari―able Search (PVS搜索)／Negascout搜索、宽容搜寻(Tol―eranceSearch)等．
迭代深化搜索
不难想像，深度为D―1层的最佳路径，最有可能成为深度为D层博弈树的最佳路径。Knuth和Moore分析表明r叫，对于分枝因子为B博弈树，利用o-卢剪枝搜索D层所需时间大约是搜索D―1层所需时间的倍．如果国象取B＝36，每多搜一层就要花上原先的6倍时间．于是CHESS4．6和DUCHENSS课题组开始采用逐层加深搜索算法．先花1／6的时间做D―l层的搜索，找到最佳路径，同时记载同形表、历史启发表、杀手表等有价值信息，以求达到D层最好的剪枝效果，可谓“磨刀不误砍柴功”．
目前几乎所有高水平的博弈程序都采用迭代深化算法，并在不断改进．如PV记录(Principal
Variation)，以及和渴望窗口搜索(Aspiration Windows
Search)的结合，都会对走法排序产生非常好的效果．另外，逐层加深的搜索算法比固定深度搜索算法更适合于对弈过程的时间控制．
启发式搜索(Heuristic search)
具体问题的领域决定了初始状态、算符和目标状态，进而决定了搜索空间．因此，具体问题领域的信息常常可以用来简化搜索．此种信息叫做启发信息，而把利用启发信息的搜索方法叫做启发性搜索方法．
利用象棋的领域知识(启发信息)设计博弈搜索的启发式算法或方法，在着法排序中就有许多成功的应用．这里需要特别提及的则是平静搜索、空着搜索和兑子搜索等．
平静搜索(Quiescent Search)．a-β夕搜索使用的是给定深度搜索，当局面变化剧烈的时候，虽然已经达到搜索的最大深度，但此时评估函数的返回值并不能准确地表示当前局面的情况．举个简单的例子，某个叶节点上红车吃掉了黑炮，但是下一步红车会被黑方吃掉．如果在此叶节点调用评估函数，返回值肯定对红方十分有利，但会引起判断失误．平静搜索判断局面是否剧烈振荡的准则是走棋方是否还有吃子走法，一直延伸到走棋方无吃子走法，也就是相对平静的局面．
将军延伸(Check Extension)，是指当本方受到对方将军时所进行的扩展．由于逃避对方对本帅攻击的解将着法不多，所以我们可以对当前节点的搜索深度增加一层，以更准确地评估攻击的危险性．
唯一着法延伸(One―Reply Extension)．当本方受对方将军的时候，并且解将着法只有一步，这时候由于搜索量不大，我们在将军延伸之外，还要对其进行额外的延伸．
兑子延伸(Recapture Extension)．搜索过程中，如果出现A棋子吃掉对方的B棋子，随即A棋子又被对方吃掉，那么也要对这样的局面进行延伸，以保证对兑子进行准确的评估．
空着搜索(NullMove)是在1993年由Chrilly Donninger最先提出的NullMove的思想是放弃本方的走棋权利，让对方连续走棋，如果得到的分值还大于原先的9值，说明对方没有“硬着”可施，于是在此分枝下搜索的意义已经不大，免于搜索．NullMove危险性比较小，实现较为简单，剪枝效果明显，现已被棋类博弈广泛采用．
负极大值算法
前面谈到博弈树的搜索是一种“变性”搜索．在偶数层进行&Max搜索”，而在奇数层进行&Min搜索”．这无疑给算法的实现带来一大堆麻烦．
Knuth和Moore充分利用了“变性”搜索的内在规律，在1975年提出了意义重大的负极大值算法．它的思想是：父节点的值是各子节点值的变号极大值，从而避免奇数层取极小而偶数层取极大的尴尬局面．
F(v)=max{-F(v1),-F(v2),…,-F(vn)}&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
其中v1，v2…vn为v的子节点.
此时需要特别注意的则是，如果口十节点是红方(走棋方)走棋，评估函数返回RedValue―BlackValue，如果是黑方(应对方)走棋，则返回BlackVahte―RedValue．另外，由于负极大值计算等价于&Min搜索”，所以这里只进行夕剪枝，非常有利于编程实现和提高搜索速度．
从以上有限的介绍不难看出，博弈树的搜索算法丰富多彩，改革、重组与创新的余地很大，一定会成为“兵家必争之地”，成为机器博弈研究的重点．
开局库与残局库
7．1 开局库设计
象棋博弈一般分为三大阶段：开局、中局、残局．虽然有时在中局就已经决出了胜负而没有残局，但所有的对局都必须有开局，只不过长短不同．
中国象棋的开局是指棋局从初始状态开始的10～20个回合之内，对战双方各自展开子力，占据棋盘的有利位置．中国象棋讲究的是快速出动子力，各棋子协调作战，并且尽早占据中心位置．如果让搜索引擎从棋局一开始就进行搜索，那么搜索引擎能够看到的至多十几层之内的变化，很容易在战略上犯错误．因为电脑往往为了局部很小的利益而忽视全局的发展．中国象棋棋谱上记载的是经过干锤百炼的开局着法，这些着法公认是对全局的发展大有裨益的．如果把一些公认为最佳的开局存储在计算机中，在开局时用查询取代搜索和评估，那么会大大提高计算机在开局的对弈水平．达到这个目标的途径就是开发和利用开局库．
开局库中存放了数以十万计甚至更多的棋局，如何能够快速准确地搜索到当前对应的棋局成为开局库设计的关键技术之一．本文第3节给出的棋局状态描述方式显然无法适应此项需要．国际象棋的成功经验表明，开局库最好是采用Z。brist哈希技术加以实现．
将棋局转换为哈希数，即哈希技术的基本原理是将盘上双方棋子的兵种代码(见表2)和坐标位置(5式)作为64位随机数发生器(Random64)的输入变量，将盘上全部棋子的对应的随机数异或求和，这个64位的哈希数和便作为给定棋局的索引值，用作棋局的存储与查询．哈希数的最大优点就在于它求的是64位数的异或和，当在着法(提―动―落―吃)的作用下，棋局发生了变化，只要将相应变化棋子的哈希数再异或一次，便可以转变成新局面对应的哈希数．亦即存在与(2―1)式相似的哈希值转移方程
Hn+1=Hn?qn+1,H0=H(0)&&&&&&&&&&&&&&&&&&&&&&&&&&&&
开局库中与棋局索引值相联系的便是可以采用的着法，常常不止一个，每个着法都对应有输赢统计比率、作者偏好权重等，以便使用时选择．一般还应该具有自学习的功能，将新的对弈结果补充进来，并且不断自行调整比率与权重值．
7．2 残局库设计
残局是指由少数残余子力所构成并进入决定胜负阶段的对峙局面．残局阶段的任务是，如何巩固和扩大既得的优势而赢得对手，或者在已处于劣势的情况下如何力争求和．在残局阶段，象棋大师的知识、人类的直觉与灵感往往能够战胜程序的搜索能力．因此，一般计算机在残局阶段是不占优势的．
提高残局阶段的棋力，比较常用的是残局库技术．在国际象棋中通常使用回溯法(Retrogradealgorithm)构造残局库．把成熟的残局着法信息事先存储在残局局面的数据库文件中，当进入残局时只要存在与该局面相同的残局数据库文件，就可以从残局库中直接提取处理，这时不仅节省大量的评估和搜索时间，而且其走法策略都是完美的．
国际象棋残局库有3种[：2)：赢／平局／输(win／draw／loss)残局库，将杀步数(distance―to―conversion)残局库，变换步数(distanee-to-conversion)残局库．各有特长，尚无定论．
鉴于残局库信息量庞大，对残局数据库的索引方案和存储压缩，都是不容忽视的任务．另外，残局阶段对于象棋规则的考虑应该给与特别的关注。比如对于“长将”的评判，还有60步规则(60-move―rule)等，如果给与忽略，在实际的对战中就可能判负．
系统开发、测试与参数优化
系统开发与实现
目前比较有水平的象棋博弈软件的程序规模都比较庞大，源程序少则几万条，多则数十万条．从头开发是软件工程领域的艰巨任务．只有认真掌握了全部算法，认真做好总体设计和详细设计，才有成功的希望．
幸好，目前已经出现一些国象和中象的开源软件．借助已有的人机界面和搜索引擎不断消化、改造、完善和奉富，从而形成具有自己特色和知识产权的博弈软件，应该说是最为现实的开发方案．
这里对于系统开发需要格外提出的几个问题是：
(1)本文为了将博弈原理表述清楚，几乎所有的表达式都是采用矩阵形式，亦即二维数组．在程序运行过程中，二维数组的计算要比一维数组更多地耗时，因此都要转为一维数组进行编程．
(2)由于博弈树展开的规模十分庞大，一般中局搜索的节点数可达千万个，因此节点信息的存储内容与方式便要非常讲究，否则内存空间危机将成为程序运行的薄弱环节．
(3)相对运行空间而言，恐怕运行时间的矛盾更为突出，它是影响搜索深度和质量的瓶颈．如何以空间换时间，是各种算法研究的焦点问题．本文在着法生成一节中介绍的预置表法，便是解决此类问题的典型范例．
(4)探讨人类博弈的认知过程，结合象棋对弈过程中出现的实际问题，研究新型的启发式搜索算法，将是机器博弈获得升华的不竭动力．
(5)就国内而言，中国象棋残局库的开发基本还是空白．
系统测试与参数优化
系统测试的重要性是不言而喻的．系统测试除了要检查系统需求定义的功能、排除编程中的错误、保证系统在对弈过程中顺利运行之外，更重要的是参数的优化与棋力的提高．前面提到在评估函数中就有成百上千个参数，在搜索过程中也有一系列的预置参数，都需要在调试和实际对弈过程中不断改进．
测试的最好办法是通过对战平台，可以是自己对自己，也可以是与其它象棋软件自动对阵．每当程序作了较大的修改，都需要通过对战检查会否发生死机或出现新的问题．
为了做到参数优化需要给出相当数量的测试棋局．由于事先知道棋局正解(最佳着法)，检查被测软件是否找到了正解，研究为什么出现了偏离．一般出现偏离原因或是在评估中缺少了什么，或是权值给的不好．软件调试的办法，就是设法调出正确结果．然而常常是“按下去葫芦又起来了瓢”，因此参数优化是一个非常需要耐心、又非常需要象棋专业知识的细活，聘请象棋高手和象棋大师参加工作是必不可少的．
总体来说，中国象棋的机器博弈还处在起步阶段，许多关键技术的研究还不够成熟，许多国际象棋成熟的做法我们还需要结合中国象棋的特点加以完善．不过，挑战中国象棋大师、特级大师和冠军的时刻指日可待．
需要特别指出的是，真正应用系统论、控制论和博弈论的方法来探讨象棋博弈问题就是在国际上也不多见．如何通过形式化和模型化来提升象棋博弈问题的研究，如何将象棋机器博弈的研究成果应用到社会安全与军事博弈当中，都是既有理论意义又有应用前景的科研项目．离散事件动态系统、模糊逻辑、神经网络、模式识别、参数估计、离散优化、数据挖掘等在机器博弈这一崭新领域大有用武之地．
文章选自《小型微型计算机系统》（2006.6）