基于ＦＰＧＡ的中国象棋博弈系统董思维，段勇，何浩，徐一华，贾云得北京理工大学１０００８１ｓｉｄｏｎ９１９８５．ｓｔｕｄｅｎｔ＠ｓｉｎａ．ｔｏｍ摘要：计算机博弈有着近５０年的发展历史，其中国际象棋的博弈研究已经取得了巨大的成功。中国象棋的博弈研究起步较晚，特别是硬件博弈系统。本文给出了一种采用并行处理的博弈专用硬件系统，包括一块以ＦＰＧＡ为主处理芯片的硬件板卡和一台计算机。ＦＰＧＡ板卡完成大部分博弈处理计算，计算机完成人机交互界面处理。目前初步的实现结果已经表明，本文系统能够显著提升博弈处理的速度。关键词：中国象棋博弈硬件博弈系统ＦＰＧＡＡｎＦＰＧＡ－ｂａｓｅｄＣｈｉｎｅｓｅＣｈｅｓｓＧａｍｅＳｙｓｔｅｍＤｏｎｇＳｉｗｅｉ，ＤｕａｎＹｏｎｇ，ＨｅＨａｏ，ＸｕＹｉｈｕａ，ＪｉａＹｕｎｄｅＢｅｉｊｉｎｇＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ１０００８１，ｓｉｄｏｎ９１９８５．ｓｔｕｄｅｎｔ＠ｓｉｎａ．ｃｏｍＡｂｓｔｒａｃｔ：Ｗｉｔｈｔｈｅｄｅｖｅｌｏｐｍｅｎｔｏｆｃｏｍｐｕｔｅｒｇａｍｅｉｎｒｅｃｅｎｔ５０ｙｅａｒｓ，ｒｅｓｅａｒｃｈｏｆｃｈｅｓｓｈａｓａｃｈｉｅｖｅｄａｇｒｅａｔＳｕｃｃｅｓｓ．ＢｕｔｔｈｅｒｅｉｓｌｉａｌｅｗｏｒｋｏｎｒｅｓｅａｒｃｈｏｆＣｈｉｎｅｓｅｃｈｅｓｓ，ｅｓｐｅｃｉａｌｌｙｏｎｔｈｅｈａｒｄｗａｒｅｓｙｓｔｅｍ．Ｔｈｉｓｐａｐｅｒｐｒｅｓｅｎｔｓａｈａｒｄｗａｒｅｓｙｓｔｅｍｓｐｅｃｉａｌｌｙｄｅｓｉｇｎｅｄｆｏｒｃｏｍｐｕｔｅｒｇａｍｅ．ＩｔｉｎｃｌｕｄｅｓａｈａｒｄｗａｒｅｂｏａｒｄｕｓｉｎｇａｎＦＰＧＡａｓｍａｉｎｐｒｏｃｅｓｓｉｎｇａｎｄａｃｏｍｐｕｔｅｒ．ＴｈｅＦＰＧＡｂｏａｒｄｒｅａｌｉｚｅｓｍｏｓｔｃｏｍｐｕｔａｔｉｏｎｆｏｒｇａｍｅ，ａｎｄｔｈｅｃｏｍｐｕｔｅｒｐｒｏｖｉｄｅｓｔｈｅｕｓｅｒｉｎｔｅｒｆａｃｅ．ＰｒｅｌｉｍｉｎａｒｙｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｓｙｓｔｅｍＣａｌｌｓｉｇｎｉｆｉｃａｎｔｌｙｉｍｐｒｏｖｅｔｈｅｇａｍｅｐｅｒｆｏｒｍａｎｃｅ．ＫｅｙＷｏｒｄｓ：Ｃｈｉｎｅｓｅｃｈｅｓｓｇａｍｅ：ｇａｍｅｈａｒｄｗａｒｅｓｙｓｔｅｍ；ＦＰＧＡ１．引言计算机博弈发展了将近５０年。微处理器性能的提高以及博弈算法的进步，使得计算机平台上的博弈水平得到了很大提升。与此同时，一些研究者也在研究设计专门用于博弈的硬件系统，通过高性能的硬件处理能力来提高系统的博弈水平。１９９７年“深蓝”的成功，说明了高性能硬件系统在博弈中的重要性。目前在国际象棋领域的硬件博弈系统还有Ｂｒｕｔｕｓ和Ｈｙｄｒａ等。中国象棋计算机博弈研究起步较晚，在这方面的硬件博弈系统的实际开发还比较少。目前大部分的象棋博弈系统是基于个人计算机实现的，博弈算法的进步使得这些象棋软件的水平得到了很大提升。从１９５０年Ｓｈａｎｎｏｎ在他的著作中提出两种博弈搜索策略（向前裁剪和向后裁剪）开始【ｌ】，已经有越来越多优秀的数据结构与算法被提了出来。１９９３年，ＣｈｒｉｌｌｙＤｏｎｎｉｇｅｒ提出了空着裁剪，基本可以使搜索增加一到两层１２】。９０年代中期，ＡｓｋｅＰｌａａｔ提出ＭＴＤ（ｆ）搜索算法，效率很高，并善于做并行计算。“深蓝”小组提出了“单步延伸”的概念，如果在搜索中某步看上去比其他变化好很多，它就会加深这步搜索以确认里边没有陷阱【３１。近几年国内的博弈算法研究也有了很大进展。比如“纵马奔流”１０３２程序的作者涂志坚就提出了新的位行、位列数据结构实现以及置换表存储的ＦａｉｌＬｏｗ修正算法【４】。算法研究是必不可少的，还应该结合专用高速的硬件系统。“．深蓝”是由许峰雄等人研发的一台专门用于国际象棋博弈的计算机【５Ｊ。它包含３０个处理器，每个处理器采用３２位ＰＯＷＥＲ２超级：签片（Ｐ２ＳＣ），其中２８个处理器的主频为１２０ＭＨｚ，剩下２个的主频为１３５ＭＨｚ。每个处理器都配有１６个专门用于国际象棋的ＡＳＩＣ芯片。整个系统共使用了４８０个这样的专用芯片。在１９９７年与人类冠军卡斯帕罗夫交战时，使用ＡＩＸ４．２操作系统，搜索速度因局面而异。对于较为平静的局面，平均每秒能够处理２亿个局面。平均搜索深度为１２．２层。深蓝最终以３．５．２．５的比分战胜卡斯帕罗夫，震惊了世界。Ｂｒｕｔｕｓ由ＣｈｒｉｓｔｉａｎＤｏｎｎｉｎｇｅｒ开发，被认为是一种“微型的深蓝”［６１０Ｂｒｕｔｕｓ在系统中使用了ＦＰＧＡＶ＇ｎ－ｔｅｘＶ４０５Ｅ的芯片，它将部分搜索以及局面评估放在这块芯片上来实现，其最大的优势就在于为其设计的程序比在Ｐｅｎｔｉｕｍ或Ａｔｈｌｏｎ这些通用芯片上运行的快的多。此外，ＦＰＧＡ芯片不仅显著提高了搜索模块的速度，而且向局面评估函数中添加新的知识时并不会降低搜索的速度，然而软件上实现博弈程序是要以牺牲搜索速度为代价的。Ｈｙｄｒａ是继“深蓝”之后又一专门用于国际象棋博弈的超级计算机【７】。它使用６４个ＩｎｔｅｌＸｅｏｎ３．０６ＧＨｚ处理器，每个处理器都配有一个专门用于国际象棋的ＦＰＧＡ芯片作为辅助。它每秒钟大概可以处理２亿个局面，与深蓝类似，但却比深蓝有更强的全局计算能力。它的平均搜索深度为１８层，与深蓝平均搜索深度１２层相比，多出的几层主要是因为搜索时采用了向前裁剪的Ｂ策略。在２００４年举办的ＩＰＣＣＣ中Ｈｙｄｒａ获得了冠军。以上介绍的都是国际象棋硬件博弈系统，它们为中国象棋博弈的发展提供了很好的参考。目前基于高速硬件开发的中国象棋计算机博弈系统还不是太多。东北大学的杜玉远等人设计了棋天大圣博弈硬件系统【８】。该系统基于ＤＳＰ和ＦＰＧＡ，采用松散耦合型的多处理器博弈硬件体系结构，每个多处理器子系统包括８个ＤＳＰ最小系统，各ＤＳＰ最小系统之间相对独立工作，通过总线仲裁器和数据传输接口实现与主机之间的数据传输。ＦＰＧＡ在这里的主要作用是实现集中式总线仲裁器，并未用于处理关键运算。本文设计了一种基于ＦＰＧＡ的中国象棋博弈系统。系统在一块ＦＰＧＡ板卡上实现了中国象棋博弈程序的全部关键功能，包括着法产生、搜索算法、评估函数等。该板卡采用ＰＣＩ结构实现与计算机的通信，计算机负责实现中国象棋博弈的交互界面绘制等。２．基于ＦＰＧＡ的博弈系统概述本文的中国象棋博弈系统采用ＦＰＧＡ作为主处理芯片，采用ＰＣＩ结构实现ＦＰＧＡ板卡与计算机的通信。ＦＰＧＡ板卡用来实现博弈系统所有的计算和搜索功能，可以更大程度的发挥硬件的并行优势，而计算机只用于绘制人机交互的图形界面，并通过调用底层ＡＰＩ函数与ＦＰＧＡ进行通信。典型的博弈系统一般由三大功能模块组成：着法生成、估值函数、搜索引擎。着法生成根据当前局面计算出所有可行着法；估值函数应用中国象棋的棋类知识通过为局面赋值的方式来评估局面的好坏；搜索引擎控制博弈树的展开和搜索过程。其中在搜索过程中常常使用ａｌｐｈａ．ｂｅｔａ剪枝、极小窗口搜索（ＰＶＳ）和ｉｖｒｎ＞（ｆ）等算法，并且为了提高搜索深度，加快搜索速度，专业的博弈系统还往往加入置换表、历史表等进行优化。但因为计算机使用的串行执行方式，搜索节点越多计算量越大，所花费的时间往往越长，所以这三个模块的速度受到多方面因素的限制，如评估局面时所考虑的因素数目，着法生成时棋盘上的棋子数，以及博弈树的规模等。而ＦＰＧＡ芯片在这方面就有很大优势，它可以使用并行执行的方式，通过增加处理单元来抵消所增加的额外时间开销，克服了计算机的不足。１０３３＝＝。．。…～一“…一＝：，．。？黑…翻１ＦＰＧＡ开发板３．磋件平台本文使用的ＦＰＧＡ开发扳基于ＡｌｔｅｒａＳｔｒａｔｉｘＩＩ设备，包含多个功能模块，为硬件系统设计提供了一个完善的开发平台，如图２所示。在搏弈系统中使用的主要设备有ＦＰＧＡ芯片，ＣＰＬＤ芯片，ＤＤＲ设备，ＰＣＩ芯片。其中功能强大的ＦＰＧＡ芯片连接了板＃上大部分器件，同时支持了］ＴＡＧ、ＡＳ等多种配置方法，内部集成２４７１６ＡＬＭ，２５４４１９２位片内存储器和３６个ＤＳＰ块，完全可以作为博弈程序的运算核心．满足系统数据处理的需要；ＣＰＬＤ为配置芯片，根据需要编写配置程序，并可以对工作模式进行调节；ＤＤＲ等存储设备具有高达１Ｇ的存储空间．可以用来存放博奔数据库，并且该板还提供了ＳＤ告控制器，连接ＳｒｍｆｉｘＨ设备用户管脚，可供用户操作；ＰＣＩ用于与ＰＣ进行数据通讯，可以让系统独立或者协同ＰＣ＿＿：｜二作。它到总线数据传输率可达１３３ＭＢ／ｓ：除此之外充足的扩展接口也为后续开发留下了很大的空间。图２开发板功能模块４ＦＰＧＡ博弈系统实现本文使用ｖｅｒｉｌｏｇ硬忭描述语言对ＦＦＧＡ芯片进行编程ｎＦＰＧＡ芯片内部聚用ｒ逻辑单元阵列ＬＣＡ（Ｌｏ百ｃＣｅｌｌＡ“ａｙ）这样一个概念，它是由可配置逻辑模块ＣＬＢ（ＣｏｎｆｉｇｕｒａｂｌｅＬｏｇｉｃＢＩｔｘ＇ｋＪ、辅入输出模块ＩＯＢｆＩｎｐｕｌＯｕｔｐｕｔＢｌｏｃｋｊ和内部琏线ｆＩｎｔｅｒｃｏｎｎｅｃｔＪ这－二部分组成．对睦编稃的过样就垲模块搭建Ｉ）９过稃，所咀硬件编程与软¨帕址上小川是．它小存在“训用”，每卟功能模块就足个尘体，是实际存在ｒ芯片上的结构．它们都有自己的功能并且打‘个与其它模块通信ｆｆＪ接ｕ，所有逻辑单元都在同时且连缕坷：断地执行。为了保证站粜们“教性，必颓ｉ“格安排所宵逻楫单儿的时序共系。奉土乳体结台ＦＰＧＡ蚱行执行、模块实制他的特点，以典型博布系统们＝大功能模块为基础，将博奔系统具体分为以下几个模块：粒据传输模块，棋盘表．搜索控制机．参数拽，指针栈，估值函数，着法生成器等，如图３所示。其中数据传输模块岫目的是能够快速将数据在扳ｐ与操作系统之间进行传输，这样便可将太带的预置表和开局库残局卑中的数据快述地存入扳＃的存储殴备中：棋盘袭用来存储当前棋｛；；；｝状态：搜索控制机结台参数技指针投进行深度优先搜索，控制博奔树的搜索过程：着法乍成器根据当前局面产生棋局的所有可能着法；估值卤数是用既有帕棋类知识对当前局面进行计估。图３结构框图４．１数据传输扳＃上擐主要的存储设备足ＤＤＲ，操作系统中的预置表和开局库残局库等需要通过ＰＣＩ接ｕ传入扳卡卜的存储设备中，所以本文在ＦＰＧＡｑＪ专门设立了相应模块对传输＿：ｌｒ式和传输过程进行控制调度，分为两种不同的操作类型：恃通ＩＯ方式和ＤＭＡ方式。图４传输控制图烨迎【０斤式｝！｜Ｊｌｉ符止Ａ，徘次列Ｊｐｊ』、个３２忡数刮州ｌ衄的奇行嚣．等待结ｔ托咀后冉ｏｉ入ｒ十。优ｔ’ｉ是控制简ｔ弘．便Ｊｊ、坦．…肚＾的吓址足传输速Ｊ４¨＊慢，下利Ｊ人：Ａ数据的ｆ々输。川博弈乐缱中怕颇。爵表、丌局ｆ１。、址ｆ。Ⅲ。书数拈ｊ最庞，、，所以小迅Ｊ用将通ＩＯ＾式，肢此种，ｊ式用十控制匍夸的输＾输出。木文存ＦＰＧＡ中吐置了１６个寄存嚣，川ｊｒ传输醉通ＩＯ山式ｆ．：』数据，埘ｍ的存储地＾Ｉ为０ｘ００垒０ｘＯｆ。其ｔＩｔ０ｘ“Ｊ至０Ｘ０７寄存器作为状鸯街存器，ＰＣＩｊ＿＿，只能读聪；Ｏｘ０８至０ｘｏｆ作为配嚣奇＿『『器，ＰＣ力只能写入。状态寄存器，ｐ前两十抖ｊｊ返同‘≮前的传输状态ｒ队列是爵满或空ｊ．配髓寄存嚣ｃｐ最后一个ｊ＿｝ｊＪ控制白々的输入，县泉的州枉捌需要ｎ由配健。经过史骑榆测普通ＩＯ方式的传输迎牢可选到３００ｋｂ居‘删泼文什火小为２００ＭｂＪ。ＤＭＡ方式叫奎续存珏１ｃ的斤式．根措，；八ｆｈ阵地址及长度．ＰＣｒｑＬｌ玎：同断的读取或者写入数据。其优点是传输速度怍常快．此种儿式适Ｊ＝｜｛ｒ将大爷数据输入到ＤＤＲ设备、或从ＤＤＲ设务输出．所以预霄表和歼局库残局痒数据ｆ由写入即可采用此种＾式，但是它的控制方式比较麻烦，本文教置了阿个先进先出队列．分别用』‘输入和输出。每个队列长度为１０２４Ｂｉｔ，对应ｔ二ＰＣ程序‘｝１设置ｒ１０２４Ｂｉｔ传输缓冲。喇为ＰＣＩ传输频率为３３ＭＨｚ，而ＤＤＲ设备的｛专辅频率为１３３ＭＨｚ，所咀通过记录每个队列的传输状态ｍ调两边船工作速度。经过实验检测ＤＭＡ方式的传输速率可以达到２０Ｍｂ／ｓｆ测试文件大小为２００Ｍｂ）。４，２搜索控髑控索足博弈系统中的关键技术，搜索散率的高低直接影响着搜索的速度．它是整个系统棋力高低的决定嘲桑。在此过程一扣我们用到的上要葬法为极大极小值算法，并采用固定深度的深度优先搜索，递加入了Ａｌｐｈａ—Ｂｅｔａ剪枝算法来进行优化，神：生成节点曲过程中对节点进行估值，井根据一定的前提条件剪去一砦没用的分技，咀达到提高搜索效率的目的。彦敏拽监标盘找擎数掩如，忐战目５搜索拧制在汁葬机Ｌ找们一般使Ⅲ递门调用的疗式来史现搜索算法。闻为它可以通过一个不断递归调朋自身的过程把一个人犁复杂旧搏弈树层层转化为一个与原问题相似的规模较小的树束求解，直到深度等ｒ开始注定的最，：深度为止，虽后冉层层返回到初始节．“。运样就保证，在搜索过程。｝ｊ任何时候只蛰５７．存与其深度相同的节点个数，仅牛成将要挫索的仙Ｊ＿，搜索完成的竹＾¨Ｔ蚍，Ｚ捌删去以节省空间。但㈨为ＦＰＧＡ其何模块实例化的特ｔ々．不存ｎ递归ｉＩ爿用，所有模块都在同时执行．所以我们选用栈配以搜索控制机来生现软什Ｌ旧建归功能。搜索状态机是整个系统的控制中心，它盯］束控制壮伊ｆ｜图象棋博弈系统的机器搜索过程，Ｊｉ协训所有于模块的调度。｝｛＿【扣命夸的发送．数据的传输等时序关系更需鐾状态机米严格控制。栈用来存储递归调用时传递的参数和返回值，令栈的层数等于树的深度，并另外设立一个指针表明当前的深度，每当博弈树的深度加～，指针就向下移一层。由于每个节点都有多个子节点，所以每层中的节点数不止一个，我们需要另外设一个标志栈表明我们搜索到当前层的第几个节点。其中指针要同时指向两个栈的相同位置，以保持同步。４．３着法生成器与估值函数着法生成器和估值函数在系统中被重复调用，是整个系统的重要组成部分。着法生成器是将棋盘上所有可能的走法罗列出来，这与棋类的规则有关，就中国象棋来说对于不同的棋子有不周的规则。估值函数用来评估当前局面，但在进行全局量化评估前都要生成棋子间的相关位置，对棋子问｛｛ｌ勺相互关系进行评判，即判断它们是否具有保护或者威胁的关系，而相关位置生成与着法生成器的唯一区别是它允许目标地址为本方棋子，除此之外其它的生成方法完全一致。所以着法产生的快慢对博弈系统的搜索效率有着巨大的影响，它不仅是博弈搜索的依据，更在估值模块中占据了举足轻重的地位。博弈系统硬件设备最主要的任务就是提高系统的运行效率，实现的方法有两种：一种为提高各模块的计算速度，减少对钟周期数；第二种为提高各模块的并行程度。因为着法生成在整个系统搜索过程中被频繁调用，占据了大量的时钟周期，所以可以应用上面的两种方法进行改善。首先本系统采用了预置表法和模板匹配法，在系统初始化时将预置表和模板通过数据传输模块预先存入板卡的存储设备中，进行着法生成时只需根据不同的棋盘位置和棋子分布读取不同的模板和预置表数据，再判断生成走法的目的地址是本方棋子还是对方棋子即可，节省了大量的逐位扫描时间，提高了每个棋子的着法产生效率。根据博弈系统中各位置着法生成任务的并行性和相对独立性特点我们还将着法生成分别从着法生成器和估值函数中独立出来；并分配到Ｎ个不同模块中并行执行，这样就相当于Ｎ个着法生成模块同时执行，可以将速度提高到原来的将近Ｎ倍（额外的调度需要花费一些时钟周期），如图６所示。经测试，当搜索深度为３，Ｎ为４时，电脑每走一步棋所需的搜索时间可缩短到原来的３／５。图６着法生成５．性能评估本实验将基于个人计算机的博弈程序和基于ＦＰＧＡ的中国象棋博弈系统进行速度对比测试。我们令两者在程序中采用相同的局面评估方法，相同的着法生成，以及相同的搜索算法（均采用未加入排序的Ａｌｐｈａ．Ｂｅｔａ算法＞，搜索层数设为５层。为了能够对比出ＦＰＧＡ的速度优势，我们未加入任何优化搜索，只在基于ＦＰＧＡ系统中的着法生成器和估值函数相关位置生成中使用了四个模块并行运行的处理方式，其它部分均未采用任何并行措施。基于ＦＰＧＡ的博弈系统所使用的ＦＰＧＡ板卡基于ＡｌｔｅｒａＳｔｒａｔｉｘ／／设备，测试时对钟频率设定为６６ＭＨｚ；测试博弈程序所用的计算机ＣＰＵ为２．４ＧＨｚｂｌｔｅｌＰｅｎｔｉｕｍ４处理器，内存为５１２Ｍ，操作系统为ＷｉｎｄｏｗｓＸＰ。我们任意选取～种局面，在此局面的基础上连续走棋４步，两个系统在人方走棋时采用相同的着法，使它们每次能够对相同的局面进行搜索，两个系统每走一步棋所用时间如表ｌ所示。１０３７表１速度测试对比次数每走一步所花费的时间／ｍｓ基于ＰＣ的博弈程序基于ＦＰＧＡ的博弈程序ｌ１９３８６４００２２２５０３７５１８３３２４４８３５２０１４３７１０２７０３４从以上测试结果可以看出，虽然仅在基于ＦＰＧＡ的中国象棋博弈系统中采用了一小部分并行处理的方式，但它的速度已经是普通ＰＣ上实现的博弈程序的５倍。如果我们提高这一小部分的并行度，并且在系统中的其它部分如搜索控制等模块中加入大量优化以及并行处理方式，那么整个系统的速度将有更大的提升。６．结语本文介绍了基于ＦＰＧＡ的中国象棋计算机博弈系统的整体结构及实现方案，并对一些细节问题进行了阐述。这是我们在中国象棋计算机博弈领域的一次大胆尝试，并且通过与ＰＣ平台对应软件的效率进行比较，看到了基于专用硬件平台的博弈系统在速度提升上的极大优势。当然，目前我们构造的硬件博弈系统尚未在算法上加入大量的优化，ＦＰＧＡ芯片的时钟频率也不够高，在经过大量优化后，该系统的博弈水平应当会比当前有更大的提升。致谢本文所使用的ＦＰＧＡ板卡由微软亚洲研究院研发设计并无偿提供，在此表示特别感谢！同时感谢微软亚洲研究院的许峰雄博士对本文博弈系统研究工作的重要指导和建议，感谢蔡雄飞研究员对本文ＦＰＧＡ板卡开发工作所提供的技术指导和支持。参考文献【１】ＣｌａｕｄｅＥ．Ｓｈａｎｎｏｎ．ＰｒｏｇｒａｍｍｉｎｇａＣｏｍｐｕｔｅｒｆｏｒＰｌａｙｉｎｇＣｈｅｓｓ【Ｊ】．ＰｈｉｌｏｓｏｐｈｉｃａｌＭａｇａｚｉｎｅ，１９５０，４１（４）：２５６．－２７５【２】ＢｒｕｃｅＭｏｒｅｌａｎｄ．Ｎｕｌｌ－ＭｏｖｅＦｏｒｗａｒｄＰｒｕｎｉｎｇ［ＥＢＩＯＬ］．：ｓｃａｎｅｔ．ｃｏｍ，２００２：４－１１【３】Ｌａｒａｍｉｅ．ＡｄｖａｎｃｅｄＳｅａｒｃｈ［ＥＢＩＯＬ］．：ｇａｍｅｄｅｖ．ｎｅｔ，２０００．【４】涂志坚．电脑象棋的设计与实现【Ｄ】．广州：中山大学，２００４．【５】ＭｕｒｒａｙＣａｍｐｂｅｌｌ，Ａ．ＪｏｓｅｐｈＨｏａｎｅＪｒ．，Ｆｅｎｇ—ｈｓｉｕｎｇＨｓｕ．ＤｅｅｐＢｌｕｅ【Ｊ１．ＡｒｔｉｆｉｃｉａｌＩｎｔｅｌｌｉｇｅｎｃｅ，２００２，１３４（１）：５７—８３【６】ＷｈａｔｉｓＢｒｕｔｕｓ［ＥＢ／ＯＬ］．：ｃｈｅｓｓｂａｓｅ．ｅｏｍ，２００２－３－２０【７】ａｂｏｕｔＨｙｄｒａ［ＥＢ／ＯＬ］．：ｈｙｄｒａｅｈｅｓｓ．ｃｏｒｎ【８】杜玉远，徐心和．一种基于ＤＳＰ和ＦＰＧＡ的博弈硬件方案实现【Ｊ】．小型微型计算机系统，２００６，２７（６）：９７０－９７４１０３８基于FPGA的中国象棋博弈系统
作者：作者单位：
董思维， 段勇， 何浩， 徐一华， 贾云得北京理工大学 100081
1.会议论文 陆慧.朱勇平.夏正友 基于两种态度的四国军棋评价函数的实验与分析 2007
四国军棋是人机对弈的一个新兴领域,它为不确定信息下的人工智能研究提供了一块新的平台。而评价函数是任何人机博弈程序的重要组成部分,它是决定人机博弈程序棋力的重要因素。本文针对四国军棋提出基于不同态度的两种评价函数——乐观评价函数和悲观评价函数。并通过实验比较在同一局面下,机器方在不同的评价函数和搜索深度下找到的最佳走法以及对应的得分。
2.学位论文 罗丽 基于Brew平台的人机对弈系统设计与实现 2008
人们追求交流和自由的脚步从未停止过，互联网技术的出现，打破了时空交流上的限制，成为人类追求并获得自由的一个重要里程碑；而移动终端则让人们摆脱线的约束，能随时随地进行沟通。应用于移动终端的开发技术除了WAP和I-Mode外，还有Brew与J2ME技术。目前，市场上存在很多手机应用开发平台，其中高通公司的Brew是最有影响力的平台之一。Brew由于其主要基于C/C++语言，有速度快，节省内存空间等优势，所以得到广大的推广应用。Brew平台的广泛应用应该能伴随3G时代的到来而不可避免。所以我们现在进行基于Brew平台的研究和开发是相当具有现实意义的。
比如将人工智能应用到基于Brew平台的手机上，目前这就是一个比较新的研究方向。人工智能是探索和模拟人(人类)的感觉和思维过程的规律的学科。同时经过近些年的研究，人工智能的研究取得了很大的发展，也细化出很多不同的方向。其中人机对弈就是其中之一。如何将人机对弈应用到Brew平台上，这正是这篇论文要探讨的问题。因为Brew平台有别于PC，所以我们对基于Brew平台的人机对弈的研究不是对PC上人机对弈的简单重复和照搬。我们必须充分考虑到手机内存小、运算速度没有PC快这两个先天不足，对基于Brew平台的人机对弈的算法进行有针对性的精简和优化。比如代码的精简、代码设计如何使Brew的内存利用率最高等多方面考虑。
本论文首先介绍了什么是Brew，因为对人机对弈算法而言，内存消耗和需要的运算速度是两个很重要需要考虑的指标，所以其中重点介绍了Brew的内存管理机制、堆栈的用法、优化内存。接下来介绍了人工智能和人机对弈目前的研究情况。在第五章里，以象棋为例，从棋盘表示、走法产生、基本搜索技术、估值基础四个方面阐述了基于Brew平台的人机对弈。为了追求人机对弈具有更好的性能，同时充分考虑到Brew平台本身的特点，文章继续讨论了搜索算法的改进和估值核心的优化问题。
3.会议论文 黄鸿.林健.任雪梅 中国象棋计算机博弈局面评估技术研究 2007
以博弈树搜索为核心的人机对弈系统中,局面评估是决定程序智能水平的关键。本研究基于对近年来相对成熟的中国象棋软件的研究,将各类局面评估方法分为了四类：静态单子型、未来局势型、象棋知识型及局面附加信息。文章阐述了各类方法的原理、实现策略、优化方法及其与相关博弈模块的关系，指出了近期的研究趋势并对其发展前景进行了展望。
4.学位论文 许云春 基于Brew平台的人工智能的研究 2006
随着通信和计算机技术的日益进步，游戏不再仅仅可以在台式计算机上玩。手机硬件技术的进步，使手机也逐渐成为一个好的游戏平台。目前，市场上存在很多手机应用开发平台，其中高通公司的Brew是最有影响力的平台之一。Brew由于其主要基于C／C++语言，有速度快，节省内存空间等优势，所以得到广大的推广应用；但是Brew又是高通公司的专利，通用性不够，这个是Brew平台推广中遇到的一个重要障碍。不过总的来说，Brew平台的广泛应用应该能伴随3G时代的到来而不可避免。所以，本文进行基于Brew平台的研究和开发是具有现实意义的。
目前，将人工智能应用到基于Brew平台的手机上，这是一个比较新的研究方向。人工智能是探索和模拟人(人类)的感觉和思维过程的规律的学科。同时经过近些年的研究，人工智能的研究取得了很大的发展，也细化出很多不同的方向，其中人机对弈就是其中之一。如何将人机对弈应用到Brew平台上，这正是这篇论文要探讨的问题。因为Brew平台有别于PC，所以我们对基于Brew平台的人机对弈的研究不是对PC上人机对弈的简单重复和照搬。我们必须充分考虑到手机内存小、运算速度没有PC快这两个先天不足，对基于Brew平台的人机对弈的算法进行有针对性的精简和优化。比如代码的精简、代码设计如何使Brew的内存利用率最高等多方面考虑。
本文介绍了Brew，因为对人机对弈算法而言，内存消耗和需要的运算速度是两个很重要需要考虑的指标，所以重点介绍了Brew的内存管理机制、堆栈的用法和优化内存，以及目前人工智能和人机对弈的研究情况。在第四章里，以象棋为例，从棋盘表示、走法产生、基本搜索技术和估值基础四个方面，阐述了基于Brew平台的人机对弈。为了追求人机对弈具有更好的性能，充分考虑到Brew平台本身的特点，讨论了搜索算法的改进和估值核心的优化问题。
5.会议论文 陆慧.朱勇平.夏正友 基于2种策略的四国军棋评价函数的实验与分析 2007
四国军棋是人机对弈的一个新兴领域，它为不确定信息下的人工智能研究提供了一块新的平台。而评价函数是任何人机博弈程序的重要组成部分，它是决定人机博弈程序棋力的重要因素。针对四国军棋提出基于不同态度的2种评价函数——乐观评价函数和悲观评价函数。并通过实验比较在同一局面下，机器方在不同的评价函数和搜索深度下找到的最佳走法以及对应的得分(PAYOFF)。
6.学位论文 潘璐 基于增强学习的博弈主体的研究 2007
目前，以人工智能为中心的游戏受到人们的普遍青睐。本文针对中国跳棋游戏，将人工智能领域中的增强学习技术应用到其中，构建了一个具有智能决策和自主学习能力的多人跳棋博弈系统。系统的体系结构不同于传统的跳棋游戏，它是一种基于传统游戏模式的扩展型系统。
系统按功能界面划分为三个部分：测试子系统、机器自学习子系统和人机对弈子系统。在博弈系统建立的初期，为了阶段性地了解系统的构建过程中各组件之间的协调工作情况，一个测试子系统被首先建立起来。机器自学习子系统主要进行博弈主体的自主学习，通过对弈的交互过程不断积累经验，提高下棋的能力。机器自学习子系统实现了机器自对弈训练模式和人机对弈训练模式。通过在人机对弈训练模式中观察人的开局方式，系统建立了一个开局策略知识库并在对弈过程中综合运用。基于增强学习和反向传播算法的原理，机器的自对弈训练模式通过自对弈的在线学习方式不断提高利用神经网络实现的非线性棋局评估函数的准确度，进而完善自身的对弈能力。人机对弈界面主要利用机器自学习子系统中学习到的不同等级的对弈模型来实现多游戏者的人机对弈。
在系统的设计方面，主要讨论了棋盘和博弈主体的设计思想。在棋盘设计中，给出了一个棋盘的构造模型，提出了棋盘分区的概念和游戏运行阶段的定义。在博弈主体的设计中，确定了主体的慎思结构，提出了一个主体的智能决策学习模型并详细讨论了各主要部件的功能，给出了神经网络棋局评估学习器的网络结构和训练过程中可选取的棋盘特征。在系统的实现方面，利用VC++的MFC并基于面向主体的编程思想构建了一个的多文档类型的应用程序。
在文章的最后，针对中国跳棋游戏的特点，从思考人对弈的角度出发，探讨一个有限理性的慎思主体如何能够通过交互下棋过程观察并学习人类对手的行棋模式，进而综合运用它来指导博弈过程的可扩展原型。整个原型构成了一个初步的可进一步深入研究的框架，并在阐述的过程中提到了一些有针对性的问题以供参考和探究。提出了一个博弈主体用于决策的布阵图模型，并概述了其利用布阵图进行决策的步骤。
7.会议论文 李一波.安涌.乔志华 人工神经网络在六子棋机器博弈中的应用 2007
人工神经网络具有自学习的特性,本研究利用这个特性,提出将人工神经网络与机器学习结合起来应用于六子棋机器博弈的方法,以提高博弈程序的智能性。通过应用该方法的六子棋程序与一般的六子棋程序的比较,表明该方法在某些方面具有一定的优越性,为人工神经网络在军事、经济等方面的应用提供了有价值的依据。
8.学位论文 罗涛 中国象棋博弈·局面评估研究 2009
计算机博弈是博弈领域长期的奋斗目标，也是人工智能学科极具挑战性的研究课题之一。凭借计算机的高速运算能力和设计严谨的算法，计算机可
以在人机对弈中表现出相当高的“智能”。
国际象棋已经有了“深蓝”这样震惊世界的成果，更加复杂的中国象棋计算机博弈水平却远远落后。
一款象棋博弈程序的实现主要被分为两大部分：界面(程序辅助)+引擎(人工智能)。本文将介绍如何实现一款中国象棋博弈程序。其中包括：搜索算法、局面评估、哈希表、历史启发、局面库以及中盘研究；打谱；复盘等功能的实现。
9.学位论文 蒋峥峻 graphplan扩展与中国象棋 2004
planning技术是人工智能中的一项核心技术，可以应用于工业，太空系统，软件工程，机器人，教育与娱乐等各个领域。
首先，本文对graphplan做详细的介绍。Graphplan最先由AvrimL.Blum提出，以其高效性而成为一种主流方法。Graphplan是当前两大处理经典规划的方法之一，另外一个是启发状态搜索方法。然后介绍实时minimax过程与AltAlt分析系统的实现与评测。AltAlt是stan与hsp-r的优势互补的综合实现的分析系统。然后是本文的主要工作：结合带有启发信息graphplan与实时minimax过程并使之应用于象棋对弈辅助中。
针对目前象棋软件的一些缺陷，本文尝试应用与扩展graph-planning方法使之处理对弈问题。目前有人人对弈、人机对弈、人机相辅，而人机相辅中有一种情况没有实现：对弈中，人可以给出一个目标，让机器以这个目标来寻求解法。综合minimax过程与带有启发信息的graph-planning方法，可以在较小的空间中进行搜索，快速地得到解法。
本文最后对planning的当前发展状况作一介绍。
10.期刊论文 魏宁 人机对弈体现了机器具有智能吗 -中国信息技术教育2008,\"\"(10)
\"人工智能之父\"图灵在1950年曾说:\"下棋是很抽象的活动,是机器可以和人竞争的纯智能领域之一.\"自此之后的半个世纪中,人机对弈就成了人工智能研究的热门领域.在地图版和教科版高中信息技术必修教材中的人工智能部分,就以大篇幅介绍了\"更深的蓝\"与卡斯帕罗夫的人机大战.这次世纪对决确实是人工智能历史上一次里程碑式的事件,其影响深远且意义非凡,那么,人机对弈究竟意味着什么呢?它是否真正体现了机器具有智能呢?下面我们就来探索人机对弈过程中的奥秘.
本文链接：http://d.g.wanfangdata.com.cn/Conference_6492740.aspx
授权使用：燕山大学(ysdx)，授权号：9e5b2f98-5777-4512-8cbd-9e5900960322
下载时间：2010年12月27日