vc中国象棋软件（程序+源码+论文）.doc

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