(12)发明专利申请
(10)申请公布号 CN 107622092 A(43)申请公布日 2018.01.23
(21)申请号 201710733645.X(22)申请日 2017.08.24
(71)申请人 河海大学
地址 211100 江苏省南京市江宁开发区佛
城西路8号(72)发明人 连晓颖 张雪洁 王乐进 杨泽
朱云 (74)专利代理机构 南京经纬专利商标代理有限
公司 32200
代理人 姜慧勤(51)Int.Cl.
G06F 17/30(2006.01)A63F 3/02(2006.01)
权利要求书1页 说明书7页 附图3页
(54)发明名称
中国象棋基于多重优化、迭代加深剪枝的搜索方法(57)摘要
本发明公开了中国象棋基于多重优化、迭代加深剪枝的搜索方法，该方法是在传统的Alpha-Beta剪枝搜索算法的基础上叠加了一系列优化搜索的方法，极大地提升了传统Alpha-Beta算法的剪枝效率和搜索准确率。包括：（1）设计的迭代加深搜索技术可充分利用计算资源，增大剪枝几率；（2）加入开局库使系统在棋局的一开始便具有了专业的走棋风格；（3）构建状态机搜索机制，优化了各方法的执行顺序，使机器的思考更加具有条理性；（4）得到的优秀走法记录到历史表中使系统具备较强的学习能力。本发明算法与优化机制保证人工智能（Artificial Intelligent，AI）算法能智能地进行人机对战，且资源空间占用小，操作简单便捷，是一种具备高效AI算法的轻量级的人工智能中国象棋搜索方法。
CN 107622092 ACN 107622092 A
权 利 要 求 书
1/1页
1.中国象棋基于多重优化、迭代加深剪枝的搜索方法，其特征在于，包括如下步骤：步骤1，针对当前局面，清空置换表、杀手走法表以及历史表，初始化控制落子时间的计时器；
步骤2，搜索对局开始前设置的开局库，若在开局库中搜索到当前局面的对应走法，则根据搜索结果进行落子，并结束搜索；否则进入下一步；
步骤3，根据象棋规则得出当前局面的所有走法，并判断走法是否唯一，若唯一，则按照唯一走法进行落子，并结束搜索；否则进入下一步；
步骤4，设定迭代加深搜索的水平线i＝1，极限深度为32，从深度1到深度i进行迭代加深搜索；
步骤5，将搜索时遇到的Beta截断或者Alpha截断的局面校验码、深度、标志、分值、走法记录在置换表中；搜索置换表，若在置换表中找到当前局面，判断深度是否和当前深度一致，若一致，则采用置换表中的走法虚拟落子形成新的局面，转步骤8，否则进入下一步；
步骤6，将当前深度对应的所有走法中最优秀的两个走法作为杀手走法并记录在杀手走法表中，判断当前深度对应的杀手走法是否有效，若有效则采用杀手走法虚拟落子，转步骤8，否则进入下一步；
步骤7，对当前局面生成所有的走法，排除掉置换表中的走法和杀手走法，按照历史表中的分值对剩余走法进行排序，按照排序第一的走法进行虚拟落子，进入下一步；
步骤8，判断搜索的深度是否到达本次迭代加深搜索的水平线i，若是，则转步骤9，否则转步骤10；
步骤9，当迭代加深搜索的深度到达水平线i时，进行静态搜索，当静态搜索结束后，判断水平线i是否到达极限深度，若是则转步骤14，否则，i＝i+1，并返回步骤4；
步骤10，判断是否生成重复局面，若无重复局面，进入下一步；步骤11，尝试空步裁剪，并进入下一步；步骤12，判断是否已经杀棋，若已经杀棋则停止本次迭代加深搜索，返回步骤4，开始下一次迭代加深搜索，否则进入下一步；
步骤13，将步骤5到步骤7中找到的走法记录到置换表和历史表中，判断水平线i是否到达极限深度，若到达则搜索结束，转步骤14；否则i＝i+1，分别尝试步骤5到步骤7中找到的走法虚拟落子或执行步骤11中的空步裁剪，虚拟交换走子方，进行递归走棋，返回步骤4；
步骤14，整个搜索过程结束，按最终搜索结果落子，并交换走子方，到玩家落子。2.根据权利要求1所述中国象棋基于多重优化、迭代加深剪枝的搜索方法，其特征在于，步骤2所述开局库由Zobrist局面校验码、走法描述、走法分值组成，且一个局面对应唯一一个Zobrist局面校验码。
3.根据权利要求1所述中国象棋基于多重优化、迭代加深剪枝的搜索方法，其特征在于，步骤5所述分值由局面评价函数计算得到。
4.根据权利要求1所述中国象棋基于多重优化、迭代加深剪枝的搜索方法，其特征在于，步骤5所述Beta截断为对于对方来说最坏的值。
5.根据权利要求1所述中国象棋基于多重优化、迭代加深剪枝的搜索方法，其特征在于，步骤5所述Alpha截断为搜索到的最好值。
2
CN 107622092 A
说 明 书
中国象棋基于多重优化、迭代加深剪枝的搜索方法
1/7页
技术领域
[0001]本发明涉及中国象棋基于多重优化、迭代加深剪枝的搜索方法，属于Alpha-Beta剪枝搜索技术领域。
背景技术
[0002]计算机诞生的同时也孕育了人工智能技术的产生，而人工智能技术最初就是从象棋程序当中实践摸索而来的，因此谈到人工智能技术，必然会让人想到象棋。智能象棋便作为了人们研究人工智能的重要载体，其研究价值不亚于生物界的果蝇，而如何使得象棋系统更加智能化、高效化便是人们研究的目标。目前智能的中国象棋系统在下棋过程中往往反应较慢，而且传统的搜索算法效率较低，耗费资源量大，无法高效的给出棋子的下子走法，急需一种高效的轻量级搜索算法来提升系统的处理效率。[0003]Alpha-Beta算法，是常用的博弈类搜索算法，主要通过是Alpha剪枝和Beta剪枝对博弈树进行搜索。根据上一层已经得到的当前最优结果，决定目前的搜索是否要继续下去。这种算法具有实现容易、精度高等优点，但该算法严重依赖于走法的寻找顺序。如果你总是先去搜索最坏的着法，那么Beta截断就不会发生，因此该算法就如同最小-最大一样，效率非常低，最终可能会找遍整个博弈树。综上，设计一种基于Alpha-Beta剪枝搜索算法，利用位棋盘表示，开局库、历史表、置换表优化搜索算法等技术的人工智能中国象棋搜索方法，是当前我们需要解决的问题。
发明内容
[0004]本发明所要解决的技术问题是：提供中国象棋基于多重优化、迭代加深剪枝的搜索方法，克服了传统Alpha-Beta剪枝搜索算法的缺点，具有搜索效果好、反应速度快、成本低、易扩展等特点。
[0005]本发明为解决上述技术问题采用以下技术方案：[0006]中国象棋基于多重优化、迭代加深剪枝的搜索方法，包括如下步骤：[0007]步骤1，针对当前局面，清空置换表、杀手走法表以及历史表，初始化控制落子时间的计时器；
[0008]步骤2，搜索对局开始前设置的开局库，若在开局库中搜索到当前局面的对应走法，则根据搜索结果进行落子，并结束搜索；否则进入下一步；[0009]步骤3，根据象棋规则得出当前局面的所有走法，并判断走法是否唯一，若唯一，则按照唯一走法进行落子，并结束搜索；否则进入下一步；[0010]步骤4，设定迭代加深搜索的水平线i＝1，极限深度为32，从深度1到深度i进行迭代加深搜索；[0011]步骤5，将搜索时遇到的Beta截断或者Alpha截断的局面校验码、深度、标志、分值、走法记录在置换表中；搜索置换表，若在置换表中找到当前局面，判断深度是否和当前深度一致，若一致，则采用置换表中的走法虚拟落子形成新的局面，转步骤8，否则进入下一步；
3
CN 107622092 A[0012]
说 明 书
2/7页
步骤6，将当前深度对应的所有走法中最优秀的两个走法作为杀手走法并记录在
杀手走法表中，判断当前深度对应的杀手走法是否有效，若有效则采用杀手走法虚拟落子，转步骤8，否则进入下一步；[0013]步骤7，对当前局面生成所有的走法，排除掉置换表中的走法和杀手走法，按照历史表中的分值对剩余走法进行排序，按照排序第一的走法进行虚拟落子，进入下一步；[0014]步骤8，判断搜索的深度是否到达本次迭代加深搜索的水平线i，若是，则转步骤9，否则转步骤10；[0015]步骤9，当迭代加深搜索的深度到达水平线i时，进行静态搜索，当静态搜索结束后，判断水平线i是否到达极限深度，若是则转步骤14，否则，i＝i+1，并返回步骤4；[0016]步骤10，判断是否生成重复局面，若无重复局面，进入下一步；[0017]步骤11，尝试空步裁剪，并进入下一步；[0018]步骤12，判断是否已经杀棋，若已经杀棋则停止本次迭代加深搜索，返回步骤4，开始下一次迭代加深搜索，否则进入下一步；[0019]步骤13，将步骤5到步骤7中找到的走法记录到置换表和历史表中，判断水平线i是否到达极限深度，若到达则搜索结束，转步骤14；否则i＝i+1，分别尝试步骤5到步骤7中找到的走法虚拟落子或执行步骤11中的空步裁剪，虚拟交换走子方，进行递归走棋，返回步骤4；
[0020]步骤14，整个搜索过程结束，按最终搜索结果落子，并交换走子方，到玩家落子。[0021]作为本发明的一种优选方案，步骤2所述开局库由Zobrist局面校验码、走法描述、走法分值组成，且一个局面对应唯一一个Zobrist局面校验码。[0022]作为本发明的一种优选方案，步骤5所述分值由局面评价函数计算得到。[0023]作为本发明的一种优选方案，步骤5所述Beta截断为对于对方来说最坏的值。[0024]作为本发明的一种优选方案，步骤5所述Alpha截断为搜索到的最好值。[0025]本发明采用以上技术方案与现有技术相比，具有以下技术效果：[0026]本发明在Alpha-Beta搜索算法的基础上，结合位棋盘表示，开局库、历史表、置换表优化算法等技术以及多重优化的思想，大大提高了算法找到最优解的效率；同时利用迭代加深搜索，使得每一层的搜索中都可以利用上一层搜索对走法的排序结果，进而大大增加剪枝的效率，避免陷入严重依赖于着法的寻找顺序的僵局。这些改进使得改进后的Alpha-Beta能够有效的跳出依赖着法顺序的僵局，克服了Alpha-Beta算法本身的缺点，在智能象棋领域上取得了良好的成效。
附图说明
[0027]图1是本发明基于多重优化、迭代加深剪枝的搜索方法的流程图。[0028]图2是棋盘存储表示图。
[0029]图3是本发明算法金字塔结构图。[0030]图4是状态机示意图。
具体实施方式
[0031]下面详细描述本发明的实施方式，所述实施方式的示例在附图中示出。下面通过
4
CN 107622092 A
说 明 书
3/7页
参考附图描述的实施方式是示例性的，仅用于解释本发明，而不能解释为对本发明的限制。[0032]现有技术：我们在人工智能(Artificial Intelligent，AI)算法搜索中传递两个值，第一个值是Alpha，即搜索到的最好值，任何比它更小的值就没用了，因为策略就是知道Alpha的值，任何小于或等于Alpha的值都不会有所提高。第二个值是Beta，即对于对手来说最坏的值。这是对手所能承受的最坏的结果，因为我们知道在对手看来，他总是会找到一个对策不比Beta更坏的。如果搜索过程中返回Beta或比Beta更好的值，那就够好的了，走棋的一方就没有机会使用这种策略了。[0033]在搜索着法时，每个搜索过的着法都返回跟Alpha和Beta有关的值，它们之间的关系非常重要，或许意味着搜索可以停止并返回。[0034]如果某个着法的结果小于或等于Alpha，那么它就是很差的着法，因此可以抛弃。因为在这个策略中，局面对走棋的一方来说是以Alpha为评价的。[0035]如果某个着法的结果大于或等于Beta，那么整个结点就作废了，因为对手不希望走到这个局面，而它有别的着法可以避免到达这个局面。因此，如果我们找到的评价大于或等于Beta，就证明了这个结点是不会发生的，因此剩下的合理着法没有必要再搜索。[0036]如果某个着法的结果大于Alpha但小于Beta，那么这个着法就是走棋一方可以考虑的走法，除非以后有所变化。因此Alpha会不断增加以反映新的情况。有时候可能一个合理着法也不超过Alpha，这在实战中是经常发生的，此时这种局面是不予考虑的，因此为了避免这样的局面，我们必须在博弈树的上一层局面选择另外一个着法。[0037]本发明改进技术：[0038]第一步，棋盘的设定。我们采用位棋盘表示以位运算为基本操作，大大降低AI响应的时间。[0039]第二步，迭代加深搜索技术。假如我们设定AI的预测深度是32步，迭代加深的搜索方式便是用for循环把搜索的深度由1一直递增到32来进行搜索，这么做的好处是，在每一层的搜索中都可以利用上一层搜索对走法的排序结果，进而大大增加剪枝的效率。在搜索的过程中，还采用了静态搜索，检查重复局面和空步裁剪等技术，使得AI思考得更为深远的同时完善了象棋规则体系。在搜索中用到局面评估函数计算公式为：
[0040]
[0041][0042]
Vnow＝|Vblack-Vwhite|+Vaduanced[0043]其中，Vblack和Vwhite分别是红方和黑方的局势评估值，PieceValuei,j是棋子所处位置和棋子类型所决定的子力价值，Vadvanced是先行权分值，Vncw是当前局面的局势评分。[0044]第四步，加入开局库——一个存储了对应局面较好走法的信息库。在搜索决策树之前，如果能在开局库中找到了好的走法，便可以省下很多的搜索时间，同时开局库也保证了AI在棋局的一开始就具有了专业的走棋风格。[0045]第五步，使用状态机——按照规定的顺序进行搜索。执行顺序是：首先是置换表里
5
CN 107622092 A
说 明 书
4/7页
搜索，如果找到了对应的局面就采用对应局面的走法。置换表中没有，就尝试杀手走法一、杀手走法二，如果上述走法都不好，便对当前局面生成全部走法，选择剩余走法中最好的那个。[0046]第六步，使用置换表。在下棋的时候虽然走法不同，但很多走法的最终导致的局面可能是相同的，置换表便是记录了这些对应局面的走法，当发现了相同的局面便可以直接采用置换表中的走法。[0047]第七步，记录两个杀手走法，便是AI在搜索决策树的过程中，同一层节点里比较好的走法，由于这样的走法比较容易成为好的走法，所以也把这些走法记录了下来。[0048]通过以上步骤的优化，可得到最佳走法，改进的Alpha-Beta剪枝搜索算法流程图如图1所示。
[0049]图1描述的是AI算法的在某一局面下的搜索流程，即当前局面轮到AI落子时AI的思考过程，本流程的结束代表AI做出了落子决策。
[0050]本流程建立于Alpha-Beta剪枝搜索的基础上，在搜索过程中会形成决策树，决策树的根节点代表当前局面；根节点通过双方不断落子(AI思考假设落子，并非真的落在了棋盘上)成为新的棋局状态，每种落子会在根节点下形成新的子节点；落子的步数相当于该决策树的层数，同一层的节点称为兄弟节点。
[0051]AI思考的极限深度即搜索到达了设定的决策树的层数(最终目标层)；AI算法采用迭代加深搜索，并非一次性搜索到极限深度，而是经过多次搜索，每次搜索的水平线都递加一层，因此水平线(不是最终目标层，但是本次搜索的目标层)代表AI一次搜索的最大层数。层数也称深度。具体步骤如下：[0052]步骤1，清空历史表，清空杀手走法表，清空置换表，初始化计时器(控制AI的思考时间，在搜索过程中判断是否超时，后文省略超时判断的描述)。[0053]步骤2，搜索开局库，开局库在用户点击开始对局的时候就已经载入，本流程仅是“在某一局面下的搜索流程”，因此不需要每次搜索都载入开局库。开局库包括局面校验码(对应某一局面独一无二的编码，后文不再解释)，对应走法，走法分值，通过他人博弈落子经验建立，走法都很优秀，因此搜索开局库的目的是以很小的搜索量换取可信度较高的搜索结果。搜索量小是因为开局库用局面校验码作为HASH函数值，对于同一局面的不同走法按照分值排序便于二分搜索，HASH搜索加上二分搜索使得开局库搜索代价小。在开局库中搜到结果，则直接落子，退出搜索，没搜到结果则进入下一步。[0054]步骤3，根据象棋规则得出当前局面的所有走法，并判断走法是否唯一，若唯一则结束并按照唯一走法进行走棋，若不唯一则进入下一步。[0055]步骤4，搜索层数就是落子的步数，每落一子形成一个新的子节点(新的局面)，距离根节点相同步数的子节点称为处于同一层的兄弟节点。在决策树中，搜索层数就表现为当前局面是从根节点走了多少步(即搜了多少层)。进行迭代加深搜索，设搜索的水平线从1一直递增到32，之后的步骤，描述的是在某一次迭代加深搜索中的步骤，即水平线为x时的步骤。搜索到达极限深度会停止搜索，根据搜索过程中得到的最佳走法落子(水平线，极限深度的意思见前文第三段)。进入下一步(之后为一次迭代加深搜索过程的描述，一次迭代加深搜索是一个Alpha-Beta剪枝递归过程)。[0056]步骤5，搜索置换表，置换表中记录了某一局面的局面校验码，深度，标志(标志用
6
CN 107622092 A
说 明 书
5/7页
于标记该置换表项是一个Beta截断产生，还是一个Alpha截断产生的，设表项中记录的分值为s，Beta截断标志表明该节点的分值至少是s，而Alpha截断标志表明该节点的分值至多是s)，分值，最佳走法，若在置换表中找到当前局面，判断深度是否和当前深度一致，如果一致，可以直接采用置换表中的走法落子(并非真的落子，这里是AI的在思考中的虚拟落子，迭代加深搜索过程中的落子都是虚拟落子)形成新的局面，转步骤8，否则进入下一步。[0057]步骤6，判断当前层数对应的杀手走法是否有效，杀手走法是兄弟节点中产生Beta截断的走法，每一层最优秀的两个走法成为杀手走法(记录采用更新的方式，新走法的分值大于杀手走法一的，把杀手走法一赋值给杀手走法二，新走法赋值给杀手走法一，完成一次更新；若新走法分值小于杀手走法一但大于杀手走法二，则新走法复制给杀手走法二，完成一次更新)，如果杀手走法符合走法规则(即杀手走法有效)，则采用杀手走法落子(虚拟落子)，转步骤8，否则进入下一步。[0058]步骤7，对当前局面生成所有的走法，按照历史表中的分值排序。历史表的下标是走法(走法由一个数值表示)，历史表的值是每次加上该走法对应的深度平方。历史表的分值越大，表明这种走法价值越大。排除掉之前置换表中的走法和杀手走法，照历史表中的排序走剩余走法，每种走法都将生成一个新的局面(虚拟落子，由上可知，从步骤5到步骤7一定落了一子，即形成了新的局面，决策树拓展了一层，搜索的层数增加了一层，出现了新的一层子节点)，进入下一步。[0059]步骤8，判断搜索的深度是否到达本次迭代加深搜索的水平线，若是，则转步骤9，否则转步骤10。[0060]步骤9，尝试静态搜索，即到达水平线后再用局面评估函数(子力价值表中每种棋子所处位置的分值累加得到，用于静态评估当前局势状况)配合Alpha-Beta剪枝往下搜索几步(不超过极限深度，也未必和到达极限深度，因为可能在到达极限深度前停止)，目的是为防止在上述步骤中得到的走法看错局势，比如现在只能搜索到吃一个子的走法，但同时也可以选择不吃，通过静态搜索可以发现吃子后局势的优劣。静态搜索结束后表明一次迭代加深搜索过程的结束，判断是否到达的极限深度，若未达则转步骤4，进入下一次迭代加深搜索；否则转步骤14。[0061]步骤10，判断是否生成了重复局面，防止遇到“解将还将”的情况，导致搜索无止境地进行下去，用于程序进行单方面长将判负以及和棋的判断。若无重复局面，进入下一步。[0062]步骤11，尝试空步裁剪，之前的步骤中是一定要找到一个走法继续递归走棋，但还没有尝试过这一步不走的方式，如果这步不走直接让对手落子，对手仍然无法击倒自己，此时无形中节省了搜索的时间，可以在规定时间里(之前说过有定时器)使搜索的深度增加1到2层，进入下一步。[0063]步骤12，判断是否已经杀棋，若已经杀棋则停止本次迭代加深搜索，回到步骤4，开始下一次迭代加深搜索，否则进入下一步。[0064]步骤13，将步骤5到步骤7中找到的走法记录到置换表和历史表中(在此处更新了置换表和历史表，在搜索过程中，历史表和置换表就是这样产生并不断更新的)，交换走子方，继续本次迭代加深搜索的Alpha-Beta剪枝递归走棋流程，即分别尝试走步骤5到步骤7产生的走法或按照步骤11中的空步裁剪进行走棋(虚拟走棋)。递归前先判断是否到达了极限深度，若到达则搜索结束，转步骤14；否则开始递归，交换走子方(还是AI的思考过程，并
7
CN 107622092 A
说 明 书
6/7页
非棋局真的交换了走子方)，回到步骤4。[0065]步骤14，整个搜索过程结束，AI走一步棋(这回是真的在棋盘上走了一步棋，之前都是AI在思考的过程中的虚拟落子)，交换走子方，到玩家落子。[0066]其中，步骤4到步骤13是迭代加深搜索的全过程，每次迭代加深搜索都是一次Alpha-Beta剪枝的递归过程。步骤5到步骤13是一次Alpha-Beta剪枝的递归过程，也是一次迭代加深搜索过程。从开局库到生成全部走法这一系列的搜索方案的顺序称为状态机。[0067]如图2所示，是棋盘存储表示图。采用长度为256的字节数组对整个棋盘进行存储，使得棋盘可以通过位运算迅速获取到一个棋子在数组中的下标，很好的实现了棋盘操作和位运算的映射关系；此外，棋子的类型也可以通过位运算区别开来，红方棋子为8～14，黑方棋子为16～22。
[0068]规则数组显示了每种棋子可以移动到的位置在256数组中的下标；规则数组为判断走法是否合法，判断将军等其它函数提供了更加方便的操作。[0069]子力价值表显示了各种不同的棋子在不同位置的价值分，每一种棋子都有对应的256长度的子力价值表，子力价值表在估计算局势分值上起到了至关重要的作用。[0070]Zobrist校验码为当前局面的标识，每往棋盘上增加或删除一个棋子都要进行一次校验码计算。校验码初值由RC4密码流生成器生成，棋子有变动时对Zobrist校验码进行Xor操作，使得每个局面的校验码唯一。Zobrist校验码作为置换表的键值和开局库的查找依据，为加快AI搜索算法做出了莫大贡献；此外Zobrist校验码可以解决一些规则问题，比如长将、长捉判负，和棋的判定等。[0071]历史表以走法为下标，存储了搜索深度的平方，方便在遍历所有当前的走法时从历史表中的最优走法开始遍历。[0072]置换表以Zobrist Key％HASH_SIZE作为索引值，置换表中存储的内容有：深度、标志、分值、最佳走法等信息。许多不同的走法可能对应了同一个最终的棋局局面，置换表便是通过置换相同的局面来进一步简化Alpha-Beta搜索过程。[0073]如图3所示，AI算法可以用一个金字塔来描述，算法的基础是Alpha-Beta剪枝搜索算法，在这基础之上叠加了多层优化技术和学习方式。金字塔由底至顶，体现了AI的执行流程和AI思维细化的过程。
[0074]首先是算法的根基——Alpha-Beta剪枝搜索算法，它的作用是在庞大的决策树中剪去没有搜索价值的分支，减小搜索的工作量。在搜索算法的根基上，我们采取了一系列优化搜索效率的方法，也就是金字塔的中间部分。[0075]第一层优化方法是迭代加深搜索技术，迭代加深就是把搜索深度逐步增加到预定值，比如AI设定思考到32层停止，那么在搜索的时候不是直接把深度定到32，而是从1开始递增到32。这么做的好处就是在搜索时可以利用上一层搜索的结果，增大决策树的剪枝几率，节省计算资源。[0076]第二层优化方法是开局库，开局库是整理了他人对象棋开局的研究生成的走法库，使AI在棋局的一开始就能具有专业的走棋风格。开局库的实现依赖于Zobrist校验码技术，校验码给了每个局面独一无二的编码，方便走法信息的记录，也为AI的学习功能奠定了基础。[0077]第三层优化方法是状态机，它规定了AI采用左边各方法的优先级，从上到下优先
8
CN 107622092 A
说 明 书
7/7页
级依次递减，使各方法协调运作，AI的思考也更加具有条理性。[0078]至此，通过这一系列的优化搜索，AI一定能得到一个走法，如果这个走法足够好，就会把这个走法记录到历史表中。历史表的作用是暂存了本局中学习到的经验。[0079]迭代加深搜索就是把搜索的深度逐步增加到预定值以节省计算资源，提升搜索的精确度和效率。在迭代加深搜索技术中，主要用到了静态搜索和空步裁剪技术来克服水平线效应，使得在某些情况搜索得以进一步延伸。[0080]静态搜索采用局面估计函数，类似于Alpha-Beta搜索算法，并依据MVV/LVA分值对搜索到的吃子算法进行排序，MVV/LVA是一个应用上非常简单的着法排序技巧，从而最先搜索最好的吃子着法。这个技术假设最好的吃子是吃到最大的子。如果不止一个棋子能吃到最大的子，那么假设用最小的子去吃是最好的。
[0081]空步裁剪运用可能忽视重要路线的冒险策略，使得象棋搜索时的分枝因子锐减，它导致搜索深度的显著提高，因为大多数情况下它明显降低了搜索的数量。它的工作原理是裁剪大量无用着法而只保留好的着法。
[0082]开局库中存储了在棋局刚开始时对应局面的一些比较好的走法，使得程序在棋局刚开始时不用Alpha-Beta搜索也可以很快给出灵活多变的可靠走法，这极大地减少了搜索的时间和复杂性。
[0083]杀手走法就是兄弟节点中产生Beta截断的走法，在Alpha-Beta搜索过程中，将得到的最好走法和次好走法作为杀手走法存储起来，由于杀手走法往往是比较容易产生Beta截断的走法，因而杀手走法也能够大大降低搜索的复杂性。[0084]如图4所示，构造一个状态机，来描述走法顺序的若干阶段，搜索顺序按照图示顺序进行优化，即先搜索开局库中的走法，再搜索置换表中的走法，接着尝试两个杀手走法，只有在上述走法的搜索都没有结果的时候才会采取生成所有走法的方式来根据历史表选择最佳走法。
[0085]在对局过程中，经历过的局面会被记录到置换表中，优秀的走法会被记录到历史表中。
[0086]历史表中记录了能产生Beta截断的走法或者不能产生Beta截断，但它是所有PV走法(vl>vlAlpha)中最好的走法。历史表在程序中定义为nHistoryTable[mv]+＝nDepth*nDepth；AI算法搜索时如果发现历史表中的走法即可发生截断，因为历史表中记录的这个走法足够好便可以省去大量的搜索时间。
[0087]置换表依据Zobrist校验码记录了各种局面的深度、标志、分值和最佳走法，其基本思想是不同的走法可能得到相同的局面，通过对相同局面的置换，可以降低Alpha-Beta搜索的复杂性，提高搜索效率。
[0088]以上实施例仅为说明本发明的技术思想，不能以此限定本发明的保护范围，凡是按照本发明提出的技术思想，在技术方案基础上所做的任何改动，均落入本发明保护范围之内。
9
CN 107622092 A
说 明 书 附 图
1/3页
图1
10
CN 107622092 A
说 明 书 附 图
2/3页
图2
图3
11
CN 107622092 A
说 明 书 附 图
3/3页
图4
12
因篇幅问题不能全部显示，请点此查看更多更全内容