基于JAVA的中国象棋（程序+任务书+说明书+外文翻译+演示文稿）

i基于JAVA的中国象棋摘要近年来，现代化的人工智能以及先进的计算机技术迅猛发展，基于此基础的电脑象棋程序，其下棋水平也得到了进一步的提升。然而，早在二十世纪的六十年代初期，来此美国麻省理工学院的约翰麦卡锡就提出了修剪算法“alpha-beta”。在该算法提出以前，通常计算机下棋程序在决定每一步走步时，所需的棋盘状态空间的搜索量都是指数级别的，而该算法则将这一搜索量的数量级减少为指数的平方根，这极大程度地提高了电脑下棋程序的水平。而随后IBM公司推出的超级计算机“DeepBlue”，则是一个不择不扣的神话，这一耗资上千万，耗时8年所建造出的世界上最强大的国际象棋“棋手”，着实为广大棋迷们所神往。本文内容根据以往国内外象棋程序在设计上所取得的一些成功案例及经验，为中国象棋设计其基本的思路和算法。关键词：中国象棋，位棋盘，alpha-beta搜索，Zobrist键值，置换表ChineseChessbasedonJAVAAbstractInrecentyears,modernartificialintelligenceaswellastherapiddevelopmentofadvancedcomputertechnology,computerchessprogrambasedonthisfoundation,itslevelofchessalsogotfurtherimprovement.However,asearlyastheearly60softhe20thcentury,totheUnitedStatesattheMassachusettsinstituteoftechnology,JohnMcCarthywasproposedpruningalgorithm-alphaandbeta.Beforethealgorithmisputforward,thecomputerchessprogramsusuallyeverystepindecidingwhenwalking,theboardofstatespacesearchvolumeindexlevel,whilethealgorithmreducesthesearchquantityofanorderofmagnitudeastheindextothesquarerootofthedrasticallyincreasedthelevelofcomputerchessprogram.AndthenIBMsupercomputerDeepBlue,isamyth,notchoosethetravelthisatacostoftensofmillions,spenteightyearsbuiltbytheworldsmostpowerfulchesschessplayer,isbythemassesofchessenthusiasts.Thisarticlecontentbasedonpreviouschessprogramsathomeandabroadinthedesignofsomesuccessfulcasesandexperience,designthebasictrainofthoughtforChinesechessandalgorithms.Keywords:ChineseChess,bitboard,alpha-betasearch,zobristkeys,transpositiontable目录摘要.iAbstract.ii目录.1引言.11概述.21.1棋盘的标记.21.1.1纵线方式.21.1.2坐标方式.21.2棋子的名称.31.3棋谱的记录方法.31.4历史局面的表示及存储.41.5棋谱记录文件的格式.41.5.1标签部分.41.5.2棋谱记录部分.51.5.3XML格式.52基本数据结构位棋盘.72.1什么是位棋盘.72.2位棋盘的作用.72.3位棋盘的基本运算.92.4Java中位棋盘的实现.92.4.1位棋盘类的实现.92.4.2位棋盘的初始化.102.4.3位棋盘的更新.103基本数据结构Zobrist键值.113.1比较局面的方法.113.2Zobrist键值的实现方法.113.3Zobrist键值的工作原理及用途.113.3.1Zobrist键值的工作原理.113.3.2Zobrist键值的用途.123.4Java中实现Zobrist键值.124着法生成.144.1伪合法着法的生成.144.1.1数组及其下标的含义.144.1.2算法示例车炮的伪合法着法生成.164.2合法着法的生成.185搜索算法.215.1最小-最大搜索.215.1.1基于最小-最大的评价函数.215.1.2最小-最大搜索.215.1.3负值最大函数.235.2Alpha-Beta搜索.235.2.1最小-最大搜索算法的问题.235.2.2Alpha-Beta修剪.245.2.3Alpha-Beta修剪算法的实现.255.2.4可能的弱点.265.3迭代加深.265.4置换表.275.4.1置换表的实现.275.4.2替换策略.296局面评价函数.306.1评价函数的实现方法.306.1.1算法设计思路.306.1.2评价要素的组合.316.2评价函数所需的信息.317程序的设计及实现.347.1搜索引擎的实现（engine包）.347.2信息传输机制（message包）.347.3棋子（pieces包）.357.4主控模块（main包）.35参考文献.36致谢.37外文文献.380引言计算机象棋水平的发展，依赖的是计算机软硬件技术的不断提高。国际象棋对弈平台有两个非常好的典范，即WinBoard和ChessBase。前者是作为一个国际象棋对弈平台的同时，又可以直接对象棋的棋谱进行编辑。后者则是国际象棋的一个商业数据库和象棋对弈软件。他们都为国际象棋爱好者以及研究人员大开方便之门。国际象棋软件作为一种新兴产业，它有着自己十分成功的商业运作。与此相对的，中国象棋在计算机上的运用实则刚刚起步，由于缺乏必要的基础工作，尽管国内有相当一部分制作计算机中国象棋的专业网站与专业软件，但是，计算机技术在中国象棋上的应用优势仍然无法清晰明朗地体现出来。在中国象棋的软件设计过程中，国际象棋软件有很多优秀的思想以及成功经验值得我们来借鉴。例如，微软公司的程序设计师B.Moreland，业余时间用来进行国际象棋引擎软件Ferret的研究开发，他写的关于国际象棋程序设计的文章非常值得其他棋类程序设计人员借鉴。虽然如此，中国象棋也仍然与国际象棋存在着巨大的差异，因此国际象棋的某些成熟技术，无法直接应用于中国象棋，需要对其加以改进和创新。本文针对中国象棋程序设计的一系列问题，总结出一些搜索引擎的设计方法，并给出java语言的实现。11概述中国象棋是由两人下的。一方称为红方（或白方），一方称为黑方。对局时由红方先走，黑方后走，一次一着，双方轮流走棋，直到对局结束为止。棋子的走法及详细规则见中国象棋竞赛规则，本章只描述计算机实现象棋对弈程序时所涉及的一些概念及相关的表示方法。1.1棋盘的标记象棋的着法表示，简而言之就是某个棋子从什么位置走到什么位置。通常，表示方法可以分为“纵线方式”和“坐标方式”两种，现在作简要说明。1.1.1纵线方式这是中国象棋常用的表示方法，即棋子从棋盘的哪条线走到哪条线。中国象棋规定，对于红方来说的纵线从右到左依次用“一”到“九”表示，黑方则是“1”到“9”(如图1.1(左)所示)，这种表示方式体现了古代中国象棋研究者的智慧。1.1.2坐标方式这是套用国际象棋中的表示方法，即把每个格子按坐标编号(如图1.1(右)所示)，只要知道起始格子和到达格子，就确定了着法，这种表示方式更方便也更合理，而且还可以移植到其他棋类游戏中。采用这种方法来表示，棋盘的纵线从左到右(红方)依次为abcdefghi，横线从下到上(红方)依次为0123456789(如图1.1(右)所示)。九八七六五四三二一aBcdefghi99887766554433221100aBcdefghi（左）（右）图1.1中国象棋与国际象棋常用表示方法21.2棋子的名称为方便表示，中国象棋的棋子名称除了用汉字以外，还可以用字母，字母可从国际象棋中稍加改动得到，而数字是为了方便着法的输入(以便用在数字小键盘上)(见表1.2)：表1.2中国象棋中英文名称对照表格红方黑方字母英文单词数字帅将KKing1仕士AAdvisor2相象BBishop3马马NKnight4车车RRook5炮炮CCannon6兵卒PPawn71.3棋谱的记录方法现以如下局面为例说明各种记谱方法对于右图图1.3的局面，记法如下：1.炮二平五炮平2.炮五进四士进3.马二进三马进4.炮八平五马进5.前炮退二车平图1.3象棋记谱方法示例图3坐标格式包括：棋子的名称、起点和终点的位置（起点和终点用-连接），对上面的走法，记录如表1.3.1（省略了吃子、将军等信息）：表1.3.1棋子走步记录法1、Ch2-e2(炮二平五)Ch7-e7(炮平)2、Ce2-e6(炮五进四)Ad9-e8(士进)3、Nh0-g2(马二进三)Nh9-g7(马进)4、Cb2-e2(炮八平五)Nb9-c7(马进)5、Ce6-e4(前炮退二)Ri9-h9(车平)1.4历史局面的表示及存储中国象棋的一个局面可以用一个“FEN格式串”来表示。FEN格式串是由4段ASCII字符串组成的代码(彼此3个空格隔开)，这4段代码的意义依次是：(1)棋盘上的棋子，这是FEN格式串的主要部分；(2)当前局面轮到哪一方走子；(3)最近一次吃子或者进兵后棋局进行的步数(半回合数)，用来判断“50回合自然限着”；(4)棋局的回合数。现以最初局面为例详细说明如下：rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNRw01第一部分(w前面的字符)：表示棋盘布局，小写表示黑方棋子，大写表示红方棋子。例如前九个字母rnbakabnr表示棋盘第一行的棋子分别为黑方的“车马象士将士象马车”，“/”为棋盘行与行之间的分割；数字“9(5,1)”表示该行从该位置起连续9(5，1)个位置无棋子。第二部分(w)：表示轮到哪一方走棋，如果是w表示轮到红方(白方)走，是b表示轮到黑方走。第三部分(w后的数字0)：表示自然限着。第四部分(w后的数字1)：表示当前局面的回合数。1.5棋谱记录文件的格式存放棋谱的文件分为两个部分：标签部分和棋谱部分，现分述如下：1.5.1标签部分有如下标签：1、Event：比赛名；2、Site：比赛地点；3、Date：比赛日期，格式统一为yyyy.mm.dd；4、Red：红方棋手；5、Black：黑方棋手；6、Result：比赛结果，“红先胜”用“1-0”表示，“黑先胜”用“0-1”表示，和棋用“1/2-1/2”7、FenStr：起始局面。如果空缺，表示起始局面是最初局面。41.5.2棋谱记录部分棋谱记录部分必须在标签部分的后面，棋谱部分当中不能插入标签；每一回合都由“回合数”、“红方着法”和“黑方着法”三部分组成，回合数后面要跟“.”(句点)，三者之间用两个分隔符隔开(回合数后面的句点也不例外)，回合之间也用分隔符隔开。现举一个例子如下：例1：Event第19届五羊杯全国象棋冠军邀请赛Date1998.12.09Site广州Red徐天红Black许银川Result1/2-1/21.炮二平五马进2.马二进三车平3.车一平二马进4.兵七进一卒进5.车二进六炮平6.车二平三炮退7.马八进九车进8.兵五进一马退9.炮八进四炮平10.马九进七炮平例2：Event全国象棋冠军邀请赛Date1999.12.15Site广州Red吕钦Black许银川FEN3k1ab2/4a4/8b/6NPP/9/4n1P2/6p2/4B4/4A4/2BAK4w-046Result1-046.兵一进一卒进47.兵一平二卒进48.前兵平三卒平49.马三退五马退50.兵二平三马进51.马五退六1.5.3XML格式全国象棋冠军邀请赛5广州1999.12.09许银川聂卫平rnbakabnr/9/1c5c1/p1p1p1p1p/9/9/9/1C5C1/9/RN2K2NRr-011-0炮八平五炮平62基本数据结构位棋盘2.1什么是位棋盘在中国象棋中，棋盘有90个交叉点。位棋盘其实就是一个长度为90位的变量，每个位对应一个交叉点，用来记录棋盘上的某些布尔值。在Java中，用3个int类型数据（每个32位，共96位多余的6位不用）表示一个位棋盘。2.2位棋盘的作用位棋盘的作用，可从回答下面的问题开始：“哪些格子上面有棋子？”“哪些格子上面有白棋（黑棋）棋子？”“哪些格子上面有车（马，炮等）？”“哪些格子受到a7格上的棋子的攻击？”(不用管格子上是否有棋子或是什么颜色的棋子。)“如果有马在a3格上，哪些格子会受到它的攻击？”通过回答上面的问题，可设置如下一些位棋盘1、记录所有棋子位置的位棋盘AllPieces。AllPieces告诉我们棋盘上哪些格子有棋子，哪些没有。当棋子处于最初位置的时候，“AllPieces”看上去是这个样子的(以下描述中，格子的下标从0开始，坐标的图示见第一章“棋盘的标记”):(Hi,89,a9)111111111000000000101010101000000000000000000101010101000000000010000010000000000111111111(Low,0,i0)其最高位对应第89格(a9格,左上角)，最低位对应第0格(a8格，右下角)。这样显示位棋盘可能更形象一点：黑棋111111111000000000010000010101010101000000000000000000101010101000000000010000010000000000111111111红棋2、记录所有黑棋棋子初始位置的位棋盘BlackPieces如下(记录红棋棋子初始位置的位棋盘RedPieces与此类似，在此不再列出)11111111100000000001000001071010101010000000000000000000000000000000000000000000000000000003、记录各兵种如红棋车的初始位置的位棋盘“redRooks”如下：0000000000000000000000000000000000000000000000000000000000000000000000000000000001000000014、假如我们创建了一个位棋盘数组knight90，用“knight0”位棋盘记录当马在0格(即i0格)时，棋盘上所有受到它攻击的格子，knight89记录当马在第89格(a9格)时，棋盘上所有受到它攻击的格子，那么，“knight20”就是这个样子的（为了直观，用“x”标记出马的位置，实际上该位置是“0”）：000000000000000000000000000000000000000000000000001010000010001000000x000000100010000010105、用另外一个位棋盘数组HorseLeg90记录蹩马腿位置的位棋盘。与Knight20对应的HorseLeg20如下(在实际系统中，根据马的行走方向单独设置只有一个蹩腿位的位棋盘，knight数组更改为knight908)：0000000000000000000000000000000000000000000000000000000000001008000001x100000001000000000006、建立全局数组“BitBoardbitMask90”，用来屏蔽或设置位棋盘中的某位。bitMask0是这样的：000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001mask89是这样的：1000000000000000000000000000000000000000000000000000000000000000000000000000000002.3位棋盘的基本运算1、与(&)2、或(|)3、异或()4、取补()010101010101a=0001100110011001a=11100001110111002.4Java中位棋盘的实现2.4.1位棋盘类的实现Java中，位棋盘用3个int型的数据表示，最高六位不用。Java中“与、或、非、异或、左位移，右位移（注意，位棋盘的右位移是无符号位移）”分别是“&、|、”。代码摘要及相关说明如下：publicclassBitBoardprivateintLow,Mid,Hi/用3个int字段表示位棋盘，最高位Hi的高/6位不用9publicBitBoard(intArg1,intArg2,intArg3)/构造函数Low=Arg1;Mid=Arg2;Hi=Arg3;publicstaticBitBoardopAnd(BitBoardarg1,BitBoardarg2)/位棋盘的“与”操作，保存结果。intlow=arg1.Lowintmid=arg1.Midinthi=arg1.HireturnnewBitBoard(low,mid,hi);publicstaticBitBoardopOr(BitBoardarg1,BitBoardarg2)/位棋盘的“或”操作，保存结果。publicstaticBitBoardopXor(BitBoardarg1,BitBoardarg2)/位棋盘的“异或”操作，保存结果。publicstaticintcount(BitBoardarg)/计算位棋盘中非零位的个数publicstaticBitBoardduplicate(intarg)/复制位棋盘publicstaticbooleanequals(BitBoardarg1,BitBoardarg2)/位棋盘是否相等（所有90位对应的位相同即/为相等）publicstaticBitBoardleftShift(BitBoardarg,intnum)/位棋盘arg左位移num位publicstaticrightShift(BitBoard,intnum)/位棋盘右位移num位publicstaticintLSB(BitBoardArg)/位棋盘最低非0位的位置（从0开始计数）publicstaticintMSB(BitBoardArg)/位棋盘最高非0位的位置（从0开始计数）publicstaticbooleannotZero(BitBoardArg)/是否非“0”。当90位中有非0位时返回true。2.4.2位棋盘的初始化某些位棋盘从程序开始运行到结束都不会改变。例如上面所述的那个位棋盘数组“knight90”。(他实际上记录了当马在任意格子上时，它下一步可以走的格子。)这个数组将在程序开始执行的时候被初始化并且不再改变。其余的位棋盘将不断变化。例如“AllPieces”位棋盘。当中国象棋棋盘变化时，它也跟着变化。然而，他们的初始化方式相同。对于诸如knight90这样不变化的位棋盘的初始化，将在“伪着法生成”章节详述。此处叙述走棋过程中随棋局变化的诸多位棋盘的初始化及相关操作。2.4.3位棋盘的更新当棋盘局面变动后，某些位棋盘就需要被更新。例如记录白子所在位置的“WhitePieces”位棋盘。假如我们把h2格的红炮移动到h9格（炮二进七），吃掉黑棋的一个马，需要更新如下位棋盘：allPieces，redPieces，redCannons，blackpieces，blackKnights首先，把redPieces，redCannons位棋盘的“h2”位清零，然后把他们的“h9”位置1。最后我们要将blackPieces和blackKnights位棋盘的h9位清除，因为那里的黑马被吃掉10了。3基本数据结构Zobrist键值3.1比较局面的方法在写中国象棋程序时，需要比较两个局面看它们是否相同。如果比较每个棋子的位置，或许不需要花很多时间，但是实战中每秒种需要做成千上万次比较，因此这样会使比较操作变成瓶颈的。另外，需要比较的局面数量多得惊人，要存储每个棋子的位置，需要占用非常大的空间。一个解决方案是建立一个标签，通常是64位。由于64位不足以区别每个局面，所以仍然存在冲突的标签，但实战中这种情况非常罕见。3.2Zobrist键值的实现方法Zobrist散列(也称为Zobrist键或Zobrist签名)是一个散列函数构造中使用计算机程序的抽象的棋盘游戏,比如国际象棋和围棋,实现换位表,一种特殊的哈希表,由董事会的位置索引,用来避免多次分析相同的位置。Zobrist散列以其发明者的名字命名,阿尔伯特林赛Zobrist。它也被应用作为识别的方法置换合金配置模拟晶体材料。Zobrist散列开始通过随机生成bitstrings为每个可能的棋盘游戏的元素,即每一块和一个位置(在国际象棋的游戏,这是12件64板位置,或14如果国王可能仍城堡和一个棋子,捕获顺道分别处理)。现在任何董事会配置可分为独立片/位置组件,映射到生成随机bitstrings早些时候。最后Zobrist散列计算这些bitstrings使用位XOR相结合。实现Zobrist必须从多维的64位数组开始，每个数组含有一个随机数。在Java中，“rand.nextLong()”函数返回一个64位的随机数值。这个函数用来填满一个long型（64位）的三维数组：棋子的类型、棋子的颜色和棋子的位置：longzobristpcMAXcoMAXsqMAX;程序启动时就把这个数组用随机数填满。要为一个局面产生Zobrist键值，首先把键值设成零，然后找棋盘上的每个子，并且让键值跟“zobristpccosq”做异或(通过“”运算符)运算。如果局面由白方走，那么别去动它，如果是黑方走，你还要在键值上异或一个64位的随机常数。3.3Zobrist键值的工作原理及用途3.3.1Zobrist键值的工作原理用Zobrist技术产生的键值，表面上跟局面没什么关系。如果一个棋子动过了，就会得到完全不同的键值，所以这两个键值不会挤在一块儿或者冲突。当把它们用作散列表键值的时候会非常有效。另一个优点在于，键值的产生是可以逐步进行的。例如，红马在e5格，那么键值里一定异或过一个“zobristKNIGHTREDE5”。如果再次异或这个值，那么根据异或的工作原理，这个马就从键值里删除了。11这就是说，如果有当前局面的键值，并且需要把红马从e5移到f7，你只要异或一个“红马在e5”的键值，把马从e5格移走，并且异或一个“红马在f7”的键值，把红马放在f7上。比起从头开始一个个棋子去异或，这样做可以得到同样的键值。如果要改变着子的一方，只要异或一个“改变着子方”的键值就可以了。用这种方法，可以在搜索根结点的时候构造一个Zobrist键值，在搜索时通过走子函数“MakeMove()”来更新键值，一直让它保持和当前局面同步。3.3.2Zobrist键值的用途Zobrist键值通常用在散列键值当中，而散列键值在象棋程序里有以下几个作用：1、用Zobrist键值来实现置换表。置换表是一个巨大的散列表，来保存以前搜索过的局面，这样可以节省很多搜索的时间。如果需要对某个局面搜索9层，可以从置换表中查找该局面，如果它已经搜索过9层，那么不必去重复搜索。置换表的另一个并不起眼的作用是，它可以帮助我们改善着法的顺序。2、可以用Zobrist键值制造一个很小的散列表，来检测当前着法路线中有没有重复局面，以便发现长将或其他导致和局的着法。3、可以用Zobrist键值创建支持置换的开局库。3.4Java中实现Zobrist键值本系统使用一个key和一个lock结合来区分每个局面，这样发生冲突（即两个局面对应的key和lock一样）的概率几乎为0。示例代码及相关说明如下1、填充数组。上述的三维数组现在改变为二维（将颜色与棋子兵种类型合并）publicstaticlongZobristKeyPlayer;/改变走子方的keypublicstaticlongZobristLockPlayer;/改变走子方的lockpublicstaticlongZobristKeyTable=newlong1490;publicstaticlongZobristLockTable=newlong1490;staticzobristGen();publicstaticvoidzobristGen()inti,j;Randomrand=newRandom();longRandSeed;RandSeed=1;rand.setSeed(RandSeed);ZobristKeyPlayer=rand.nextLong();for(i=0;i=0;k-)if(j&(1=0;k-)if(j&(1=0;k-)if(j&(1=0;k-)if(j&(1Move.Dst,退if(Attack&(Player!=0?16:32)!=0)returnMove.dst=PreMoves.FileCannonCapMinyBitWord+Bottomx;elsereturnMove.dst=PreMoves.FileNonCapMinyBitWord+Bottomx;else/与目标位置的列位置不同，也就是“平”BitWord=BitRanksy;/行位棋盘数值，9位二进制数if(Move.src=PreMoves.RankNonCapMinxBitWord+y;以上对炮伪合法着法的合法性判断。File90和Rank90保存的是格子对应的列和行，这比“%、/”（取余和除法）的运算速度快。BitFiles9和BitRanks10分别保存的是位棋盘中9列（每列共10位）和10行（每行共9位）的二进制值。2、合法着法的生成代码如下：publicvoidmove(StringmoveStr)src=(char)(ChessPosition.BottommoveStr.charAt(0)-a+moveStr.charAt(1)-0);dst=(char)(ChessPosition.BottommoveStr.charAt(2)-a+moveStr.charAt(3)-0);if(src=90|dst=90)/invalidmovesrc=dst=-1;MoveStruct是着法的数据结构，src和dst分别是移动前后的位置（格子）publicvoidGenMoves(finalChessPositionPosition,finalintHistTab)GenKingMoves(Position,HistTab);/帅将GenAdvisorMoves(Position,HistTab);/仕士GenBishopMoves(Position,HistTab);/相象GenKnightMoves(Position,HistTab);/马GenRookMoves(Position,HistTab);/车GenCannonMoves(Position,HistTab);/炮GenPawnMoves(Position,HistTab);/兵GenMoves根据当前局面（作为参数的finalChessPositionPosition）生成合法着法，并保存在一个数组MoveStructmoveListMAX_MOVENUM中，同时也将每个着法的局面评价值存入数组intvalueListMAX_MOVENUM中，这样以便对着法进行排序，在搜索算法中提高算法的效率。GenKnightMoves(ChessPositionPosition,HistTab)for(all马的伪合法着法)if(ChessPosition.LeagalMove(其中一个着法)ChessPosition.MakeMove();/If(走子方不是处于被“将”状态)saveToMoveList;ChessPosition.UnMove();205搜索算法5.1最小-最大搜索在中国象棋里，双方棋手都知道每个棋子在哪里，他们轮流走并且可以走任何合理的着法。下棋的目的就是将死对方，或者避免被将死，或者有时争取和棋是最好的选择。中国象棋程序通过使用“搜索”函数来寻找着法。搜索函数获得棋局信息，然后寻找对于程序一方来说最好的着法。一个浅显的搜索函数用“树状搜索”(Tree-Searching)来实现。一个中国象棋棋局通常可以看作一个很大的n叉树(“n叉树”意思是树的每个结点有任意多个分枝通向其他结点)，棋盘上目前的局面就是“根局面”(RootPosition)或“根结点”(RootNode)。从根局面走一步棋，局面就到达根局面的“分枝”(Branch)，这些局面称为“后续局面”(SuccessorPosition)或“后续结点”(SuccessorNodes)。每个后续局面后面还有一系列分枝，每个分枝就是这个局面的一个合理的着法。中国象棋的树非常庞大(通常每个局面有45个分枝)，又非常深。每盘棋局都是一棵巨大的n叉树，如果能通过树状搜索找到棋局中对双方来说都最好的着法就好了。这个浅显的算法在这里称为“最小-最大搜索”(Min-maxSearch)。用最小-最大搜索来解诸如井字棋的简单棋局是可行的(即完全了解每一种变化)。井字棋的博弈树既不烦琐也不深，所以整个树可以遍历，棋局的所有变化都可以知道，任何局面都可以保证找到一步最佳着法。数学上用这种方法处理中国象棋也是可以的，但是目前和不久的将来用计算机去实现，却是不可行的。即便如此，我们仍然可以用基于最小-最大搜索的程序来下象棋。相比最小-最大地搜索整个树，在一个给定的局面下搜索前几步则是可能的。由于叶子结点的局面没能搜索出杀棋或和棋，所以要用一个称为“评价”(Evaluate)的启发函数给这些局面赋值。5.1.1基于最小-最大的评价函数评价函数首先应该返回局面的准确值，在没办法得到准确值的情况下，如果可能的话启发值也可以。它可以由两种方法来决定：1、如果黑方被将死了，那么评价函数返回一个充分大的正数；如果红方被将死了，那么返回一个充分大的负数；如果棋局是和棋，那么返回一个常数，通常是零或接近零。如果不是棋局结束局面，那么它返回一个启发值。确定启发值，子力平衡是首先要考虑的(如果红方盘面上多子的话，这个值就大)，而其他位置上的考虑(帅、将的安全性，重要的子力的位置等等)也需要加上。如果红方是赢棋或者很有希望赢，那么启发函数21通常会返回正数；如果黑方是赢棋或者很有希望赢，那么返回负数；如果棋局是均势或者是和棋，那么返回在零左右的数值。2、这个函数的工作原理跟第一个一样，只是如果当前局面要走子的一方优势，那么它返回正数，反之是负数。5.1.2最小-最大搜索最小-最大搜索是一对几乎一样的函数，或者说两个逻辑上重复的函数。纯粹的(不完美的)最小-最大函数，代码如下：intMinMax(intdepth)if(SideToMove()=RED)/红方是“最大”者returnMax(depth);else/黑方是“最小”者returnMin(depth);intMax(intdepth)intbest=-INFINITY;if(depthbest)best=val;returnbest;intMin(intdepth)intbest=INFINITY;/注意这里不同于“最大”算法if(depthbest)best=val;returnbest;在这个函数里，当走子一方改变时就要对返回值取负值，以反映当前局面评价的更改。就根结点是红先走的情况，如果没有剩下的层数，那么“评价”返回的值是就红方而言的，如果有剩下的层数，就产生后续局面，函数对这些局面逐一做递归，每个23次递归都得到就黑方而言的评价，黑方走得越好值就越大。当评价值返回时，它们被取负数，变成就白方而言的评价。该函数在遍历时结点的顺序同“最小-最大”搜索的函数是一样的，产生的返回值也一样。它的代码更短，同时减少了移植代码时出错的可能，代码维护起来也比较方便。5.2Alpha-Beta搜索5.2.1最小-最大搜索算法的问题Alpha-Beta同“最小-最大”非常相似，事实上只多了一条额外的语句。“最小-最大”运行时要检查整个博弈树，然后尽可能选择最好的线路。这是非常好理解的，但效率非常低。每次搜索更深一层时，树的大小就呈指数式增长。通常一个中国象棋局面平均都有45个左右的合理着法（有效分支因子），所以用最小-最大搜索来搜索一层深度，就有45个局面要检查，如果用这个函数来搜索两层，就有452个局面要搜索，搜索局面的数量一指数级增长，非常迅速。要想通过检查搜索树的前面几层，并且在叶子结点上用启发式的评价，那么做尽可能深的搜索是很重要的。最小-最大搜索无法做到很深的搜索，因为有效的分枝因子实在太大了。5.2.2Alpha-Beta修剪Alpha-Beta修剪算法可以有效地减少分支因子，它是建立在这样一个思想之上：如果你已经有一个不太坏的选择了，那么当你要作别的选择并知道它不会更好时，你没有必要确切地知道它有多坏。有了最好的选择，任何不比它更好的选择就是足够坏的，因此你可以撇开它而不需要完全了解它。只要你能证明它不比最好的选择更好，你就可以完全抛弃它。Alpha-Beta对搜索树有两种修剪1、浅的修剪假设用最小-最大搜索(前面讲到的)来搜索下面的树：图5.2.2-1搜索树的浅修剪当搜索到F，发现子结点的评价分别是11、12、7和9，在这层是棋手甲走，我们希望他选择最好的值，即12。所以，F的最小-最大值是12。24现在开始搜索G，并且第一个子结点就返回15。一旦如此，就知道G的值至少是15，可能更高(如果另一个子结点比G更好)。这就意味着我们不指望棋手乙走G这步了，因为就棋手乙看来，F的评价12要比G的15(或更高)好，因此我们知道G不在主要变例上。我们可以裁剪(Prune)结点G下面的其他子结点，而不要对它们作出评价，并且立即从G返回，因为对G作更好的评价只是浪费时间。一般来说，像G一样只要有一个子结点返回比G的兄弟结点更好的值(对于结点G要走棋的一方而言)，就可以进行裁剪。2、深的裁剪我们来讨论更复杂的可能裁剪的情况。例如在同一棵搜索树中，我们评价的G、H和I都比12好，因此12就是结点B的评价。现在我们来搜索结点C，在下面两层我们找到了评价为10的结点N：图5.2.2-2搜索树的深修剪我们能用更为复杂的路线来作裁剪。我们知道N会返回10或更小(轮到棋手乙走棋，需要挑最小的)。我们不知道J能否返回10或更小，也不知道J的哪个子结点会更好。如果从J返回到C的是10或者更小的值，那么我们可以在结点C上作裁剪，因为它比兄弟结点B要好。因此在这种情况下，继续找N的子结点就毫无意义。考虑其他情况，J的其他子结点返回比10更好的值，此时搜索N也是毫无意义的。所以我们只要看到10，就可以放心地从N返回。5.2.3Alpha-Beta修剪算法的实现Alpha