“理治棋壮”中国象棋计算机博弈引擎开发总结

2006-08-12

“理治棋壮”中国象棋计算机博弈引擎作为北京理工大学2004级软件基础实习项目,自2006年7月初启动以来,在黄鸿、黄远灿、陈朔鹰、汤建平、李凌等领导和老师的关怀指导下,由开发小组林健、高然、应张彬、武斌四位成员分工合作,完成了基础但完整的程序编码,撰写了详细的书面说明与程序文档,并成功参加了全国首届中国象棋计算机博弈锦标赛,获得“新秀奖”。

计算机博弈是人工智能领域公认的最具挑战性的科研课题之一,中国象棋是一个标准的博弈问题。但中国内地计算机博弈研究起步较晚,理论成果和成熟产品少。小组成员在接到这个项目后积极收集资料,检索到该领域先驱的一些论文,借阅了《PC游戏编程(人机博弈)》等相关书籍,下载过数个开源的中国象棋与国际象棋软件。通过一周的学习研究,我们了解了计算机博弈的基本理论和博弈程序的经典架构,以及业界的一些标准与常见象棋软件的使用习惯。

考虑到对现有资源的充分利用及项目将来的持续开发问题,我们决定将此项目做成遵循GPL许可的开源项目。在决定程序现实方式时,我们有两种选择:一是独立开发界面、核心在内的所有功能,二是开发算法引擎,协同第三方象棋界面程序工作。考虑到参赛时间因素,我们选择了后者。这也体现了我们本次软件基础实习项目以提高数据结构和算法设计能力为核心目的。而在引擎协议方面,我们选择了简单易懂但功能强大、诞生刚刚2年而蓬勃发展的UCCI协议。从后来的锦标赛上18个队伍中有7个使用UCCI协议引擎看来,我们的这个选择是正确的。通用的协议使我们的引擎可以与强大的界面程序配合进行功能测试和性能调试;可以与他人开发的引擎进行自动化对战,便于比较分析,改进算法。

小组成员根据个人特长和实际能力进行了分工:林健有一定的项目开发经验,负责设计程序架构,编写博弈树搜索模块,管理文档;应张彬和武斌算法分析能力强,负责编写着法生成模块、局面评估模块等,并进行单元测试;高然象棋知识丰富,负责整体黑盒测试,局面评估值审定和测试用例管理。

依小组成员普遍掌握的技能和程序效率需要,我们决定使用GNU C++语言编码。我们对程序进行迭代开发,持续完善。在搭建基础框架后首先与界面程序进行命令行方式的通信实验,保证通信畅通。在完成着法生成模块后立即编写测试程序及测试用例,并连接界面程序进行随机走棋实验。有了搜索和评估模块后,程序便可以正常运行并马虎地与人对弈了,此时我们一方面用一系列典型的局面测试添加新的代码后棋力的变化,一方面将程序交给小组外的同学试用,收集意见与建议。之后我们添加了静态搜索、迭代深化搜索、置换表、开局库、局势变化策略、时间分配策略等增强型功能,在添加每一段代码后,都要将原有的测试用例运行一遍,检验新功能的效果,同时避免bug的引入。

比赛前夕,我们又特别针对参赛用计算机的性能优化了搜索参数,并根据比赛章程的要求改善了时间分配策略。在比赛当日凌晨,连夜运行测试用例,保证了最后参赛版本的稳定性。

终因实力悬殊,我们以2胜7负1和积5分的预赛战绩,在18支队伍中名列第15名,失去了出线机会。但小组成员没有因此而气馁。参加比赛是本着学习的态度和交流的精神,利用比赛的机会提高自身的算法水平与象棋技艺。总结比赛失利原因,客观方面由于我们时间仓促,从设计到实现仅用一个月的时间,中途还不能放松其它课程的学习。主观方面我们没有深入理解某些核心算法,将一些既有理论简单撮合,不能充分发挥棋力。

通过比赛与交流,我们找到了程序总体改进方向。我们需要重新审核核心算法,将算法优化整合;加入完善的调试输出,随时掌控机器思路;编写辅助程序实现大量局面自动化连续测试,自动分析测试结果;使用神经网络、遗传算法等自学习技术调整评估函数,节约人力。比赛之后,我们将程序源代码发布在了UCCI电脑象棋联赛的网站,同时商议了将源代码挂靠在sourceforge.net便于持续开发的事宜。

总结小组成员一个月以来的学习、开发、参赛过程,总体而言,达到了软件基础实习的课程要求。小组成员体会了多人合作开发的苦与乐,巩固了数据结构基础知识,提高了算法分析与设计能力,实践了软件工程与OOAD基本思想。通过相互协作,取长补短,提高了每个人的团队合作精神和学习创新能力。

合作开发过程中,小组内部也出现过一些问题。例如开会的守时问题。参赛程序版本的定夺问题等,都曾引起过小组成员的争论,但我们均以大局为重,团结协商,妥善解决。

在本次项目开发过程中,我们要感谢指导老师黄鸿的关怀指导。她实时关注开发进度,帮我们联系开发交流场所与校内象棋高手,并安排了参赛相关事宜,准备了参赛用的高性能计算机等。为我们提供了这次与高手过招、学习交流的机会。

同时我们要感谢软件学院2003级学长赵陈翔。我们在学习计算机博弈理论的时候得到了他的帮助指导。在开局库筛选和局面评估值审定方面,他给出了不少可行的建议,并实地参与了调试。“理治棋壮”这一名称也是项目启动之初由赵陈翔所取。

我们还要特别感谢UCCI协议制定者、上海格尔软件工程师黄晨。我们的程序参考并引用了他的部分开源代码。这次比赛他也参加了。比赛期间,我们与他进行了广泛的交流,向他请教了一些技术和非技术问题,都得到了满意的答复。

比赛虽已结束,但我们的脚步没有停止。我们已与指导老师沟通,希望将计算机博弈项目在我校坚持下去,建立持续的开发团队与良好的学习氛围,争取在不久的将来为校争光!