会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

   首页 人人文库网 > 资源分类 > DOC文档下载

中国象棋软件设计与实现论文.doc

  • 资源星级:
  • 资源大小:339.00KB   全文页数:17页
  • 资源格式: DOC        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
2:本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3:本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

中国象棋软件设计与实现论文.doc

1中国象棋对弈程序专业计算机科学与技术小组成员孙忱、周俊、施聪聪、周理想指导老师陈宇、蒋德茂(苏州大学计算机学院)作品类别学术论文计算机程序【摘要】人机博弈是人工智能研究的经典课题之一。凭借设计优良的算法和计算机的快速运算能力,计算机可以在人机对弈中表现出相当高的智能。通常,一款象棋程序的实现可以被分为下棋引擎(人工智能)和外壳(界面及程序辅助)两大部分。本文将介绍如何实现一款中国象棋对弈程序。【关键词】中国象棋人工智能博弈树AlphaBeta搜索历史启发界面多线程计时器列表框MFC。AbstractManmachineGameisaclassictopicinArtificialIntelligence.Relyingonfinedesignedalgorithmsandthefastoperationability,computerscandisplayhighintelligenceinplayingchess.Usually,therealizationofachessprogramcanbedecomposedintotwomajorpartstheChessEngineArtificialIntelligenceandtheShellUserInterfaceProgramAssist.ThispaperwillintroducehowtorealizeaChineseChessprogram.KeywordsChineseChessArtificialIntelligenceAIGameTreeAlphaBetaSearchHistoryHeuristicUserInterfaceMultithreadedTimerListBoxMFC.一、前言我们的目标是实现一款有着一定下棋水平且交互友好的中国象棋人机对弈程序。该程序功能包括人机对弈盲棋模式(注此功能为创新功能)搜索深度设定(电脑棋力选择)棋子、棋盘样式选择悔棋、还原着法名称显示下棋双方计时整个程序的实现可分为两大部分一、人工智能部分(计算机下棋引擎)该部分实现了如何让计算机下中国象棋,其中涉及人机博弈的基本理论及思想,是该程序的核心部分,同时也是本项目研究的重点所在。二、界面及程序辅助部分2光有下棋引擎尚不能满足人机交互的基本要求,因此我们还需要一个框架(界面)来作为引擎的载体,同时提供一些诸如悔棋,计时之类的附属功能(程序辅助)来为程序增色添彩。下面分别介绍各部分实现。由于界面及程序辅助部分涉及内容宽泛而又繁琐,因而本文只介绍其中重点部分以及我们在开发过程中曾经遇到过困难的地方。二、人工智能部分(计算机下棋引擎)1、概述程序的基本框架从程序的结构上讲,大体上可以将引擎部分划分为四大块棋局表示着法生成搜索算法局面评估。程序的大概的思想是首先使用一个数据结构来描述棋局信息,对某一特定的棋局信息由着法生成器生成当前下棋方所有合法的着法并依次存入着法队列。然后通过搜索算法来逐一读取着法并调用局面评估函数对该着法所产生的后继局面进行评估打分,从中选出一个最有可能导致走棋方取胜的着法。在搜索的过程中还可以采用一些辅助手段来提高搜索的效率。其过程如下图所示下面将分别介绍各个部分。32、棋局表示计算机下棋的前提是要让计算机读懂象棋。所谓读懂,即计算机应该能够清楚地了解到棋盘上的局面(棋盘上棋子的分布情况)以及下棋方所走的每一种着法。因而首先我们需要有一套数据结构来表示棋盘上的局面以及着法。对于棋盘局面的表示我们采用了最传统的同时也是最为简单的棋盘数组。即用一个910的数组来存储棋盘上的信息,数组的每个元素存储棋盘上相应位置是何种棋子。这种表示方法简单易行(缺点是效率不是很高)。按此方法棋盘的初始情形如下所示BYTECChessBoard910{R,0,0,P,0,0,p,0,0,r,H,0,C,0,0,0,0,c,0,h,E,0,0,P,0,0,p,0,0,e,A,0,0,0,0,0,0,0,0,a,K,0,0,P,0,0,p,0,0,k,A,0,0,0,0,0,0,0,0,a,E,0,0,P,0,0,p,0,0,e,H,0,C,0,0,0,0,c,0,h,R,0,0,P,0,0,p,0,0,r}其中0表示无棋子,大写字母表示红方棋子,小写字母表示黑方棋子(所有这些大小写字母都是用宏定义的整数)。具体如下R表示红车H表示红马E表示红相A表示红仕K表示红帅C表示红炮P表示红兵。r表示黑车h表示黑马e表示黑象a表示黑士k表示黑将c表示黑炮p表示黑卒。此外这个数组也表明了我们对棋盘进行了如右图所示的编号,并约定红方棋子总处于棋盘的下方。对于着法的表示,我们直接借用棋盘数组的下标来记录着法的起点和目标点。至于是什么棋子在走,以及是否吃子、吃的是什么子,我们在着法结构中并不记录。这些信息由外部读取棋盘上起点、终点的数据获得。着法结构定义如下,其中还包含了对着法的历史得分的记录项,以供后面要讲到的历史启发所用。typedefstruct_cchessmove{POINTptFrom//起点POINTptTo//目标点intnScore//该走法的历史得分}CCHESSMOVE//走法结构有了对棋盘局面和着法的表示之后,程序才能够完成以下操作1、生成所有合法着法2、执行着法、撤销着法3、针对某一局面进行评估。因而,棋局表示好比是整个程序(计算机下棋引擎部分)的地基,之后所有的操作都将建4立在其基础上。3、着法生成我们的程序需要让计算机在轮到它走子的时候能够执行一步它认为对它最有利的着法,那前提就是它要有诸多(也可能是唯一)可供选择的着法,提供所有候选着法的清单就是我们的着法生成器所要完成的。之后用搜索函数来搜索清单,并用局面评估函数来逐一打分,最后就可以选择出最佳着法并执行了。在着法生成器中,我们采用的基本思想就是遍历整个棋盘(一个接一个地查看棋盘上的每个位置点),当发现有当前下棋方的棋子时先判断它是何种类型的棋子,然后根据其棋子类型而相应地找出其所有合法着法并存入着法队列。这里谈到的合法着法包括以下几点1、各棋子按其行子规则行子。诸如马跳日字、象走田字、士在九宫内斜行等等(这里需要特别注意的是卒(兵)的行子规则会随其所在位置的不同而发生变化过河后可以左右平移)。2、行子不能越出棋盘的界限。当然所有子都不能走到棋盘的外面,同时某些特定的子还有自己的行棋界限,如将、士不能出九宫,象不能过河。3、行子的半路上不能有子阻拦(除了炮需要隔一个子才能打子之外)以及行子的目的点不能有本方棋子(当然不能自己吃自己了)。4、将帅不能碰面(本程序中只在生成计算机的着法时认为将帅碰面是非法的,而对用户所走的导致将帅碰面的着法并不认为其非法,而只是产生败局罢了)。产生了着法后要将其存入着法队列以供搜索之用,由于搜索会搜索多层(即考虑双方你来我往好几步,这样才有利于对局面进行评估以尽可能避免目光短浅),所以在把着法存入着法队列的时候还要同时存储该着法所属的搜索层数。因此我们将着法队列定义为二维数组MoveList1280,其中第一个数组下标为层数,第二个数组下标为每一层的全部着法数。关于搜索层数,我将数组下标设定为12,实际使用的是1到11(在界面中我又将其限定为110)。搜索层数的增加会显著提高电脑的下棋水平(当然计算机的棋力在很大程度上也依赖于局面评估)。在我的迅驰1.5,736M内存的笔记本上最多只能搜索5层,再多将导致搜索时间达到令人无法容忍的地步(这里还需要特别说明的是,搜索的速度也和着法生成的效率以及局面评估的复杂度有关,因为每分析一个结点都要执行这两种操作)。对于每一层的着法数,也就是当前下棋方针对当前局面的所有可选的合法着法,据有关数据统计在象棋实战中一般最多情况下也就五六十种。定义第二个数组下标为80,应当可以保证十分的安全。着法生成为搜索部分提供了原料,接下来的任务就交给搜索和局面评估了。4、搜索算法搜索算法对于整个下棋引擎来说都是至关重要的。它如同程序的心脏,驱动着整个程序。搜索算法的好坏直接影响着程序执行的效率(从某种角度上,它影响着计算机的下棋水平。因为,计算机必须在有限的时间内完成思考,搜索速度快意味着在相同的时间内程序可以看得更远,想的更多)。关于棋类对弈程序中的搜索算法,经前人的努力已形成了非常成熟的AlphaBeta搜索算法1以及其它一些辅助增强算法(还有众多基于AlphaBeta算法的派生、变种算法)。鉴于目前我们的知识储备、时间、精力等均达不到推陈出新、另开炉灶的要求,再1Alphabeta算法,该算法是由匹兹堡大学的三位科学家Newell,ShawandSimon于1958年提出的。

注意事项

本文(中国象棋软件设计与实现论文.doc)为本站会员(网游小王子)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网([email protected]),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5