黎利辉

【摘 要】中国象棋的基础搜索——Alpha-Beta 算法的剪枝过程对搜索节点的排序顺序依赖很大，当搜索顺序的排列为最差情况时，该算法基本上不能实现剪枝。搜索过程其实会出现很多重复的节点，利用哈希表的思想，把以前搜索过的节点保存起来，这样在搜索某一节点之前，先到哈希表里去查找以前是否搜索过，如果以前搜索过，则直接返回哈希表里保存的局面评估值；如果没有，则采用正常的Alpha-Beta算法进行搜索。通过实现可知当搜索层次大于5层时，改进后的算法比Alpha-Beta算法在搜索节点数量和时间有都有很大的优化。

【关键词】中国象棋；置换表；哈希表；博弈树搜索

0 引言

在中国象棋的人机博弈的研究中，局面搜索算法是核心，中国象棋的博弈过程中，针对某一局面，平均着法达到60步，故减少搜索的节点，提高搜索的速度和节省搜索过程中内存开销，就成了中国象棋搜索研究一个终极目标。Alpha-Beta搜索算法是人机博弈的一个基本算法，但是该算法在搜索过程中，存在大量的冗余[1]。本文即在这一基本算法的基础上，加入置换表技术和Hash table技术，以提高搜索速度。

1 Alpha-Beta搜索算法

如图1所示，结点下面的数字为该节点所代表的局面评估值。在左图中，节点B的值为18，节点D的值为16，因为C节点要取其子节点的最小值，故可以判定节点C的值将小于或者等16，而A节点的值为B节点和C节点的最大值，这样无论E节点和F节点的值为多少，都不影响A节点的取值，因为A节点此时肯定会取B节点的值18，这样将节点D的后继节点减去称Alpha剪枝。……