“理治棋壮”中国象棋计算机博弈引擎关键算法分析与设计

《“理治棋壮”中国象棋计算机博弈引擎关键算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、“理治棋壮”中国象棋计算机博弈引擎关键算法分析与设计“理治棋壮”中国象棋计算机博弈引擎开发小组在《程序架构设计与主要算法概述》一文中，我们阐述了中国象棋计算机博弈涉及的主要算法。下面就其中的关键算法进行深入分析，并说明其设计实现方法。一、核心搜索算法1、PrincipalVariableSearch搜索算法是计算机博弈程序的核心算法。如何选择适合的搜索算法，配以合理的剪枝条件，是决定搜索效率的关键所在。博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。应对这类问题，香农(ClaudeShannon)教授早在1950年提出了极大-极小

2、算法（MinimaxAlgorithm）。这种算法常以一种形式上的改进——负极大值算法出现：记我方节点值为正，对方节点值为负，双方在每一节点分别选择其子节点中绝对值最大的一个。递归深度优先遍历有限层次的树，找到使起始节点绝对值最大的一个叶子节点，然后回溯找到形成这一叶子节点的第一层子节点，作为最优解。可以在博弈树深度优先搜索过程中记录2个附加值，α：我方搜索到的最好值，任何比它更小的值就没用了；β：对于对手来说最坏的值。在搜索算法中，如果某个节点的结果小于或等于α，那么它就可以抛弃；如果某个着法的结果大于或等于β，那么整个结点就作废了，因为对手不希望走

3、到这个局面。如果某个节点值大于α但小于β，那么这个节点就是可以考虑走。这便是所谓的α-β剪枝搜索。1由α和β可以形成一个节点预选窗口。如何能够快速得到一个尽可能小而又尽可能准确的窗口？有不少窗口搜索算法被设计出来解决这个问题，如：AspirationSearch、PrincipalVariableSearch、ToleranceSearch等。目前大多数国际象棋与中国象棋的算法核心青睐速度快而不会出现错误剪枝的PrincipalVariableSearch，它的原理是第一个分枝以完整窗口搜索，产生一个解v，后继分枝则以一个极小窗口(v,v+1)搜索之，

4、旨在建立高效的、极小的搜索树。本质上，极小窗口搜索依赖于后继节点的值对于前驱节点值微小变化的猜测。如果猜测被证明不准确，就要以(v+1,β)为窗口重新进行搜索。2、迭代深化搜索博弈树的庞大是可以想象的。对于中国象棋，如果按照每一步平均有45种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，则要考虑的局面种数比地球上的原子数目还要多，无法完全计算，因此只能对有限层次展开分析。那么应该搜索多少层为佳呢？如果设定一个搜索截止层数，则搜索的时间会随局面上可行着法数量的变化产生显著变化。一个更好的方案是限定搜索截止时间，让程序在有限的时间内尽可能深地搜

5、索。用伪代码表示为：depth=0;while(time

6、估函数，返回值肯定对红方有利，但会引发无用的兑子。因此有必要加入静态局面搜索，将叶子节点继续展开一直延伸到相对静态（没有吃子）的局面。2静态搜索实现起来比较简单，直接用静态搜索函数替代叶子节点的评估函数即可。在实际应用中多采用选择性延伸，即只对有重要威胁的叶子节点（将军、唯一着法、兑子等）进行展开，忽略次要的非静态叶子节点。4、循环检测中国象棋规则中禁止连续三回合以上的循环着法，比如“长将”和“长不变”要判负或判和。如果仅使用普通的搜索和剪枝规则，电脑很可能会死守一个对其有利的局面不放，不断地用循环的着法与对手周旋，最终被判负或判和。因此我们有必要在搜

7、索中记录一个节点所有上级节点的情况，如果它与某个上级节点完全相同，则应避免这个着法（但不可以就此剪枝，因为有时不得不因为只有一条路可走而走两个回合的循环着法）。在具体实现时，不可能记录一个节点（即局面）的全部信息，那样既浪费空间，又难以高效地查找和匹配。通常采用节点的哈希数进行记录和查找匹配。记录的长度应与搜索深度相同。综合以上算法，我们实现了博弈树搜索模块。请参考源文件searcher.cpp。二、局面评估函数局面评估就是给棋局打分，识别棋局的好坏，以便在博弈树搜索时作为路径选择条件寻找最佳着法。可行的办法就是对局面进行量化，通过数值评判棋局的好坏。

8、由于评估需要大量的象棋知识，仁者见仁，智者见智，评估函数的设计便成为计算机博弈中最为人性化的部