资源描述:
《中国象棋对弈软件的设计论文》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、中国象棋对弈软件的设计论文中国象棋对弈软件的设计中国象棋对弈软件的设计摘要:随着人工智能及计算机硬件的发展,计算机象棋程序的下棋水平也不断地得到提高。20世纪60年代初,麦卡锡提出了alpha-beta修剪算法,把为决定下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根,大大地提高了机器下棋的水平。IBM的超级计算机“DeepBlue”更是一个神话,让棋迷们神往。本文根据国际象棋程序设计的一些成功经验,提出中国象棋程序设计的一些思路和方法。关键词:中国象棋,位棋盘,Zobrist键值,alpha-beta搜索,置换
2、表,局面评价Abstract:AlongwiththedevelopmentoftheArtificialIntelligenceandcomputerhardware,thecapabilityofcomputerchessprogramhaveadvancedcontinually.Atthebeginningof60s,20thcentury,McCaxibroughtforwordalpha-betapruningalgorismwhichmadethechessprogramadvancedmorebyreducin
3、gtheorderofmagnitudeofthenumberofsearchingnodesdecidingnextstep,named“StateSpace”fromOXntoOXn/2.IBM’ssuper-computer“DeepBlue”ismorelikeamythforallcomputerchessfans.Inmyarticle,IwilldescribesomeideasandmethodsofdesigningChineseChessprogramalongwithsomesuccessfulexper
4、iencesandcasesoftheChess.Keywords:ChineseChess,bitboard,zobristkeys,alpha-betasearch,transpositiontable,Evaluation目录引言3第一章概述41.1棋盘的标记41.2棋子的名称51.3棋谱的记录方法51.4历史局面的表示及存储71.5棋谱记录文件的格式8第二章基本数据结构??位棋盘102.1什么是位棋盘102.2位棋盘的作用102.3位棋盘的基本运算122.4Java中位棋盘的实现13第三章基本数据结构??Zobrist
5、键值173.1比较局面的方法173.2Zobrist键值的实现方法173.3Zobrist键值的工作原理及用途173.4Java中实现Zobrist键值18第四章着法生成204.1伪合法着法的生成204.2合法着法的生成25第五章搜索算法295.1最小-最大搜索295.2Alpha-Beta搜索335.3迭代加深365.4置换表375.5其他策略41第六章局面评价函数476.1评价函数的实现方法486.2评价函数所需的信息48第七章程序的设计及实现517.1搜索引擎的实现(engine包)517.2信息传输机制(message
6、包)527.3棋子生成(pieces包)527.4主控模块(main包)52附件1:搜索算法主程序SearchMove.java55附件2:程序运行界面及功能说明74引言象棋水平的发展是需要靠信息技术来推动的,国际象棋有两个很好的范例,一个是象棋棋谱编辑和对弈程序的公共平台??WinBoard平台,另一个是商业的国际象棋数据库和对弈软件??ChessBase,他们为国际象棋爱好者和研究者提供了极大的便利。国际象棋软件有着成功的商业运作,已发展成一种产业。然而,电脑在中国象棋上的运用还刚刚起步,尽管国内涌现出一大批中国象棋的专业
7、网站和专业软件,但是由于缺乏必要的基础工作,电脑技术在中国象棋上的应用优势还无法体现出来。在设计中国象棋软件过程中,国际象棋软件有很多值得借鉴的成功经验和优秀的思想。例如B.Moreland,微软Microsoft的程序设计师,业余从事国际象棋引擎Ferret的开发,他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。然而,中国象棋与国际象棋存在着很大的差异,因此国际象棋的某些成熟技术,无法直接应用于中国象棋,需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题,总结出一些搜索引擎的设计方法,并给出j
8、ava语言的实现。第一章概述中国象棋是由两人下的。一方称为红方(或白方),一方称为黑方。对局时由红方先走,黑方后走,一次一着,双方轮流走棋,直到对局结束为止。棋子的走法及详细规则见《中国象棋竞赛规则》,本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。1.1