合肥工业大学毕业论文.doc

《合肥工业大学毕业论文.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、合肥工业大学毕业论文（计算机及其应用专业）中国象棋对弈软件的设计姓名葛标学科专业计算机及其应用专业指导老师李琳二零零五年九月-75-中国象棋对弈软件的设计摘要：随着人工智能及计算机硬件的发展，计算机象棋程序的下棋水平也不断地得到提高。20世纪60年代初，麦卡锡提出了alpha-beta修剪算法，把为决定下一个走步而需对棋盘状态空间的搜索量从指数级减少为指数的平方根，大大地提高了机器下棋的水平。IBM的超级计算机“DeepBlue”更是一个神话，让棋迷们神往。本文根据国际象棋程序设计的一些成功经验，提出中国象棋程序设计的一些思路和方法。关键词：中国象棋，位棋盘，Zobrist键值，

2、alpha-beta搜索，置换表，局面评价Abstract：AlongwiththedevelopmentoftheArtificialIntelligenceandcomputerhardware,thecapabilityofcomputerchessprogramhaveadvancedcontinually.Atthebeginningof60s,20thcentury,McCaxibroughtforwordalpha-betapruningalgorismwhichmadethechessprogramadvancedmorebyreducingtheorderofm

3、agnitudeofthenumberofsearchingnodesdecidingnextstep,named“StateSpace”fromO(Xn)toO(Xn/2).IBM’ssuper-computer“DeepBlue”ismorelikeamythforallcomputerchessfans.Inmyarticle,IwilldescribesomeideasandmethodsofdesigningChineseChessprogramalongwithsomesuccessfulexperiencesandcasesoftheChess.Keywords:C

4、hineseChess,bitboard,zobristkeys,alpha-betasearch,transpositiontable,Evaluation-75-目录引言4第一章概述51.1棋盘的标记51.2棋子的名称61.3棋谱的记录方法61.4历史局面的表示及存储81.5棋谱记录文件的格式8第二章基本数据结构——位棋盘112.1什么是位棋盘112.2位棋盘的作用112.3位棋盘的基本运算132.4Java中位棋盘的实现14第三章基本数据结构——Zobrist键值173.1比较局面的方法173.2Zobrist键值的实现方法173.3Zobrist键值的工作原理及用途173

5、.4Java中实现Zobrist键值18第四章着法生成204.1伪合法着法的生成204.2合法着法的生成25第五章搜索算法295.1最小-最大搜索295.2Alpha-Beta搜索325.3迭代加深365.4置换表365.5其他策略40第六章局面评价函数466.1评价函数的实现方法476.2评价函数所需的信息47第七章程序的设计及实现507.1搜索引擎的实现（engine包）507.2信息传输机制（message包）517.3棋子生成（pieces包）517.4主控模块（main包）51附件1：搜索算法主程序SearchMove.java55附件2：程序运行界面及功能说明74-7

6、5-引言象棋水平的发展是需要靠信息技术来推动的，国际象棋有两个很好的范例，一个是象棋棋谱编辑和对弈程序的公共平台——WinBoard平台，另一个是商业的国际象棋数据库和对弈软件——ChessBase，他们为国际象棋爱好者和研究者提供了极大的便利。国际象棋软件有着成功的商业运作，已发展成一种产业。然而，电脑在中国象棋上的运用还刚刚起步，尽管国内涌现出一大批中国象棋的专业网站和专业软件，但是由于缺乏必要的基础工作，电脑技术在中国象棋上的应用优势还无法体现出来。在设计中国象棋软件过程中，国际象棋软件有很多值得借鉴的成功经验和优秀的思想。例如B.Moreland，微软(Microsoft

7、)的程序设计师，业余从事国际象棋引擎Ferret的开发，他的一系列关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。然而，中国象棋与国际象棋存在着很大的差异，因此国际象棋的某些成熟技术，无法直接应用于中国象棋，需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题，总结出一些搜索引擎的设计方法，并给出java语言的实现。-75-第一章概述中国象棋是由两人下的。一方称为红方（或白方），一方称为黑方。对局时由红方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止