数。在这一方走棋的时候，选择价值最大的子节点走法，即实行“Max搜索”，另一方走棋则选择价值最小的子节点走法，即实行“Min搜索”，这就是象棋博弈中的一个极大极小过程。例如，如果红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，实行“Max搜索”，称为MAX方，而其敌对方即黑方在奇数层的着法选择则是在其全部子节点中要找到评估值最小的一个，实行“Min搜索”，称为MIN方。图2.4表示了一个极大极小搜索过程，粗箭头为最佳路径片段。
图 2.4 极大极小值算法示意图
由于完整的博弈树过于庞大，程序不能也没有必要搜索整棵博弈树的所有节点，而需要像人类棋手一样有选择性地进行搜索，对于一些已经确定不佳的走步可以将以它根节点的子树剪掉(cut-off/pruning)，以提高单位时间内搜索的节点数。
上述极大极小值搜索过程中，遍历了整个的博弈树，这样的搜索算法效率低，搜索量非常大，如果要减少搜索量，又可能影响搜索效果。但假如将叶节点的评估计算与树的展开同时进行，然后对博弈树进行必要的裁剪，就可能大量减少所需搜索的节点数目，并且保持搜索效术叫α-β剪枝搜于α-β搜索的深所有剪枝算法的极大极小搜索规和图2.6给出两
MAX
果不变。这个技索。它是一种基度优先搜索，是基础，它是根据则进行的。图2.5个剪枝示意图：
MIN MAX
图 2.5 α剪枝示意图
MIN
MAX
MIN
图2.6 β剪枝示意图
在图2.5所示的极大极小树片段中，按照极大极小值搜索规则，从左路分枝的叶节点倒推得到第一层MAX节点的值为5，可表示此时的着法最佳值，记为α，显然此α值可作为MAX方着法指标的下界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最小值，即取M州(8，3，“□”)，而无论“□”中为何值，都不会比5大(最大为3)，故可以将“□”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，也可以进行剪枝操作。此类剪枝称为α-剪枝。图2.5中通过剪枝，最后得到如粗箭头所示的最佳路径片断。
图2.6所示的极大极小树片段中，由左路分枝的叶节点倒推得到第一层MIN节点的值为n，可表示此时对方着法的钳制值，记为β。显然此β值可作为MIN方可能实现着法指标的上界。在搜索中路分枝时，因为第二层着法的选择是取第三层节点的最大值，即取MAX(5，12，“○”)，而无论“○”中为何值，都不会比11小(至少为12)，故可以将“○”表示的节点及其后继节点剪掉，不再考虑此节点的延伸。同理搜索右路分枝，进行剪枝操作。此类剪枝称为β-剪枝。图2.7中通过剪枝，最后得到如粗箭头所示的最佳路径片断。
α-β剪枝搜索能够让我们省略许多节点的搜索，不只是节点本身，而且包括节点下面的子树，这样α-β剪枝搜索需要遍历的节点数远少于极大极小算法所遍历的节点，也就节省了大量的时间开销，并且仍不失为穷尽搜索的本性，但α-β剪枝的剪枝效果即搜索节点数与博弈树节点的搜索次序密切相关。
2.4.2 高级搜索算法
极大极小值搜索是所有搜索算法的基础，而α-β剪枝搜索是所有剪枝算法的基础。但在实际的博弈系统设计中，要提高程序的搜索速度和搜索深度，还必须利用搜中得到的一些启发式信息来加快搜索，目前己经有很多对基本搜索算法的增强算法。
在α-β剪枝搜索中，剪枝效率几乎完全取决于节点的排列顺序，如何调整待展开的走法的顺序，是提高搜索效率的关键。在搜索的过程中，往往有一些启发性的信息可以利用，如果利用这些信息在相似的局面下对走法进行优化排序，或者对相同的局面不再搜索，而直接返回以前搜索的结果，都会对搜索产生明显的加速作用。围绕着法排序，己经出现了许多优秀的搜索算法与举措，例如历史启发，杀手启发，置换表等等。
历史启发(History Heuristic)实际上就是记录搜索过的好的走法，并在后续着法中优先搜索。根据经验，一些以前经过搜索认为最佳的走法，其后续走法仍然有很大可能成为最优的走法。在搜索过程中，每找到一个好的着法，就将与该走法相应的历史得分作一增量，一个多次被搜索并确认为好的走法的历史记录分值会较高，当搜索中间节点时，将走法根据其历史得分排序，以获得较佳的排列顺序。
杀手启发(Killer Heuristic)是基于这样的思想:在搜索过程中，有许多走法一经搜索就引发了剪枝，且这些走法通常是同一个走法，这样，为每一层记录引发剪枝最多的走法即杀手走法，当下一次搜索到同样的深度时，如果杀手走法是该局的一个合法走法，就优先搜索杀手走法。杀手启发是一种特殊的历史启发，它不依赖于人类的知识，具有普遍性。
置换表 (TransposilionTable)是用一张表把搜索过的信息记录下来，在后续的搜索中，察看记录在表中的这些信息，如果将要搜索的某个节点已经有记录，就直接利用记录下来的结果引入到当前的搜索中，以减少搜索。置换表不同于历史启发表和杀手表，不必在每次搜索之前都清空，而是一直维持这些数据，作为以后搜索的信息。
另外，空着搜索(Null Move)也是搜索算法中一种很有效的搜索策略，它的思想是放弃本方的走棋权利，让对方连续走棋，如果得到的分数还大于原来的β值，就可以简单地返回β值，在此分枝下的搜索意义不大，免于搜索。空着搜索明显降低了搜索的数量，导致搜索深度显著提高，并且危险性比较小，实现较为简单。
2.5 开局库设计
中国象棋的开局变化极多，每一种走法都能产生出一种新的变化，单就中炮对屏风马、中炮对反宫马、中炮对左三步虎等数十种变化，其格个开局又都有自身的变化，这些开局都遵循开局的规律:“明车”，即车路要通;“活马”，即马与兵阵的配合合理，使马能有活动的空间;“好炮位”，即炮要占住子力疏密适中的要点，封锁对方进攻路线，配合其他子力展开进攻。另外当进行快棋赛时，棋手还会选择一些冷门开局，使局面很快“脱谱”，迅速进入到中、残局。所以中国象棋开局阶段是整个对弈过程中变化最多的阶段，开局的好坏对之后的中、残局意义重大。
2.5.1 开局库的作用
象人们记住开局招数一样，博弈程序使用一个数据库，里面储存了开局谱着和局面，于是当对局（开局）中的棋步在开局库中能找到时，它就可以立即取出来走，不用计算。无庸多说，这对于程序节省思考时间有重大帮助。这对于整个博弈系统来说有三点好处：一是防止战略性错误；二是形成较为稳妥和有利的局面；三是节省了大量的搜索时间。但另一方面，如果开局库本身不好或部分不好，程序也可能被盲目引到劣势的局面甚至很快失利。所以如何设置一个比较好的开局库，就成了程序设计中不可或缺的部分。 2.5.2 实现开局库的主要方法
实现开局库的方法一般有两种：一种是用FEN的形式表示的开局库；另一种是哈希值表示的开局库。
用FEN串表示开局库的方法比较简单，该方法仅仅是将开局库中的存储的棋盘状态与当前棋盘的状态进行比较，若相同，则程序根据库中的走法走一步。下面我们来看看什么是fen串。
(1) FEN
FEN就是“福斯夫-爱德华兹记号法”（Forsyth-Edwards Notation），这是一种使用ASCII码字符描述国际象棋局面的标准。FEN是建立在19世纪由报社记者S·D·福斯夫设计的记录局面的标准基础上的。后来为了适合象棋软件的需要，由爱德华兹对此做了少许修改。一份标准的局面记号对需要大量交换共享局面数据的国际象棋程序设计等工作具有尤其重要的作用。
(2) 结构描述
一个FEN记录使用长度可不同的一行来表示，由六个区域组成。单纯的FEN记录文件后缀应该是“.fen”，比如:kk-1.fen，在中国象棋开局库的fen串形式的开局库文件后缀为.DAT。FEN描述了:棋子位置、轮走棋方、易位可行性、吃过路兵目标格、半步计数、以及总回合数。所有这一切用一行文字符号表示就行了而且非常容易读。 看看一个FEN的五个区域及其含义，以中国象棋为例：
Rnbakabnr/9/1C5C1/P1P1P1P1P/9/9/P1P1P1P1P/1C5C1/9/RNBAKABNR w—0 1 这就是每盘常规对局的最初局面，一个子都没有动，如图2.7：
图 2.7 象棋初始局面
(3) 棋子位置数值区域（Piece placement data）
就是表示双方棋子各在棋盘哪个格子上的。规则是从第10横线开始顺序数到第1横线(红方在下，从上数到下)，从a线开始顺次数到h线；红方棋子以大写字母 \\“RNBAKABNR\\”功表示，黑方棋子以小写\\“rnbakabnr\\”表示，这是英文表示法，每个字母代表的意义与常规规定相同。数字代表一个横线上的连续空格，反斜杠\\“∧”表示结束一个横线的描述。
上面的那P1PlP1PlP，就是表示黑方在第7横线上排有5只兵；后面那两个数字9， 就是表示从第6到第5横线，双方一个棋子都不在，是空格；9个反斜杠\\“∧”将第一区域分成8段，因为棋盘有10条横线；其它的照着图完全可以类推。 (4) 轮走棋方（Active Color）
表示目前局面谁该走棋。小写\\“w\\”表示红方走棋；小写\\“b\\”表示黑方走棋；因为起初局面是红先，所以上面就是\\“w\\”. (5) 吃过路兵目标格（En Passant Target Square）