作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (17): 186-188. doi: 10.3969/j.issn.1000-3428.2012.17.051

• 人工智能及识别技术 • 上一篇    下一篇

五子棋中Alpha-Beta搜索算法的研究与改进

程 宇,雷小锋   

  1. (中国矿业大学计算机科学与技术学院,江苏 徐州 221008)
  • 收稿日期:2011-10-21 修回日期:2011-12-26 出版日期:2012-09-05 发布日期:2012-09-03
  • 作者简介:程 宇(1987-),男,硕士研究生,主研方向:机器学习;雷小锋,副教授、博士

Research and Improvement on Alpha-Beta Search Algorithm in Gobang

CHENG Yu, LEI Xiao-feng   

  1. (School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221008, China)
  • Received:2011-10-21 Revised:2011-12-26 Online:2012-09-05 Published:2012-09-03

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

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

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

中图分类号: