Abstract: This paper researches Alpha-Beta search algorithm. According to the characteristics of Gobang, it proposes a local search method, thereby directly reducing the search node branch number; combined with the fact that Alpha-Beta algorithm efficiency is highly relevant to the child node order, this paper proposes the static evaluation heuristic and iterative deepening methods for optimization of move ordering. Experimental results show that this method enhances the efficiency of Alpha-Beta search algorithm.

Key words: Gobang, Alpha-Beta search algorithm, local search, static evaluation heuristic, iterative deepening, move ordering

摘要： 对五子棋中Alpha-Beta搜索算法进行研究。依据五子棋的特点，提出一种局部搜索的算法，该算法可直接减少搜索的平均分枝因子。结合Alpha-Beta搜索算法效率与子节点着法顺序高度相关的特点，给出静态评价启发以及迭代深化的方法优化着法顺序。实验结果表 明，该方法能提升Alpha-Beta搜索算法的效率。

关键词: 五子棋, Alpha-Beta搜索算法, 局部搜索, 静态评价启发, 迭代深化, 着法顺序

CLC Number: 

• TP311