文档介绍：中山大学硕士学位论文电脑象棋的设计与实现姓名:涂志坚申请学位级别:硕士专业:计算机软件与理论指导教师:姜云飞20040601摘要计算机软件与理论论文题闩:电脑象棋的设计与实现专业:硕士生:涂志坚指导老师:姜云飞教授计算机博弈是人工智能领域中的一个重要主题,而当前对中国象棋博弈的研究也在不断地发展着,本文通过对象棋程序“纵马奔流”〉昧说届象棋软件金牌氖萁峁埂⑺阉魉惴ㄓ肫兰酆拿枋觯约岸运采用的数据结构、搜索方法进行基于测试数据集的分析和检验,阐述了一个可达人类大师水平的象棋程序的设计及实现的原理、方法。且在当中提出了新的数据结构实现以及存储的拚惴ǎ计算机博弈,电脑象棋,启发式搜索有效地提高了实际搜索运算的效率。关键字:中山大学硕上论文一—盔堂婴圭堕型篏篊:坐堕墨垡堕丝生量塞丝枷,甅——篋:.琀,.,瑂.,瓸啊Ⅱ第一章引言象棋程序“纵马奔流”电脑象棋简介在人类文明发展的初期,人们便开始进行棋类博弈的游戏了。到了近年前,随着电子计算机的诞生,科学家们开始通过电脑模拟人的智能逐步向人类智能发起挑战,香农与图灵提出了对棋类博弈程序的描述,随着电脑硬件和软件的高速发展,从开始,电脑博弈便开始逐渐大规模地向人的智能发起了挑战,到年,兜缒訢世界冠军卡斯帕罗夫,成为了人工智能挑战人类智能发展的一个重要旅程碑。而在空间复杂度以及搜索复杂度比国际象棋更高的中国象棋韵录虺葡棋矫妫鼻暗难芯恳舱畈5胤⒄棺牛揭惨徊讲降靥岣撸⒊鱿至瞬簧优秀的象棋程序,包括台湾大学许舜钦教授及其团队的⒚拦馊筒┦康拿入神机、台湾郑明政的象棋世家、法国的等,出现了研究和竞技百家争鸣的好景象。随着研究的深入以及电脑硬件速度的增长,在不远的将来,象棋程序将会向顶尖人类高手发起强而有力的挑战。搜索树复杂【国际象棋中园象棋电脑象棋的研究常常通过比赛对弈的方式来验证各自研究的成果,当前的主要比赛包括:由每年举办的,以及从年起在台湾成功大学举办的世界电脑象棋争霸赛。击败了当时国际象棋空间复杂度黑白棋本文将会介绍象棋程序“纵马奔流”韵录虺芞的设计原理与实现度【围棋表髦制謇喔丛佣缺冉电脑象棋的设计与实现中大学硕畚‘本文架构方法。从年月份开始编写,其主要由开局知识库、搜索引擎、评价函数以及一系列的知识学习机制组成,主要的特点包括快速的数据结构设计实保持高速的搜索速度与深度,做到知识’俣鹊木狻4月开始,⒂略诎碌乩窭染傩械的取得了电脑象棋的第一章将会阐述计算机博弈发展以及电脑象棋介绍、电脑象棋的状态空间复第二章首先描述了电脑象棋表示的一些基本数据结构,然后提出了所采用的双向映射数组的盘面表达方法,以及优化的快速运算数据结构⋯一纳杓剖迪衷怼第三章将重点讲述博奔树的搜索方法,包括博弈树构建、算法介、拚惴ǎ詈蠖哉逅阉骺蚣芙凶芙帷最后,第五章是全文的总结及展望。现、以及高效率的搜索,这些机制保证了在应用大量领域知识的同时能大师凶远诵械牟馐裕甑兹〉每炱迮琶谝唬⑶昕J杂度以及文章架构。、选择性剪枝和延伸,以及提出新的娲⒌腇第四章主要描述的评价函数架构,包括子力分数、子力灵活度评价、棋盘控制以及一些重要特征的计算。年世界冠军。绍、惴ㄓ隡、,有效地对研究目标构架一个好的数据结构表示,既能快速断根据当前棋盘,生成可行移动,然后进行搜索树的扩展;同时评价函数也是根在本人编写的中国象棋程序中,采用了是一个棋盘数组和棋子数组双向映射棋盘坐标是指对棋盘建立坐标系,通过坐标标示棋盘上每一点的方法。便于搜索地进行,更能大大提高搜索的效率。而在中国象棋博弈的研究中,显然怎样很好的表示棋盘,也是决定搜索效率的关键之一,一般来说,博弈运算的时间耗费主要在搜索和评价中。搜索时,不据当前棋盘情况进行相关特征的计算和估价。因此,好的棋盘数据结构的表示,能大大提高以上这两个部分的运行效率。表的形式。以下首先说说一些辅助知识:,表示比较直观,譬如棋盘横坐标从左开始,纵坐标从上到下为的话,棋盘左上角的点就是銎迮套暧肂】来定义,这样表示比较真观。一维坐标,举个例子,棋盘第一行,,,,诙,,,,,,,,,如此类推,阁一维数缀表示坐标。计算棋盘上某个点的横坐标纵雀标,只需作和计算便可。比较两种方式,由于在搜索、评价时,访问用一维数组的方式访问棋盘比用二维数组的方式快倭艘淮蔚刂菲撇僮,采用的一维数组有速度上的优势。冗余辅助点:当进行树扩展时┤缙遄映担恚冢等生成可移动步时,举个例子,车的向左移动,每次都要和左边界进行比较,看当前坐标是否已经超出棋盘,浪费了效