基于置换表技术的中国象棋搜索算法研究

摘要

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