计算机工程与应用 ›› 2010, Vol. 46 ›› Issue (6): 42-45.DOI: 10.3778/j.issn.1002-8331.2010.06.012

• 研究、探讨 • 上一篇    下一篇

博弈树置换表启发式算法研究

焦尚彬,刘 丁   

  1. 西安理工大学 信息与控制工程研究中心,西安 710048
  • 收稿日期:2008-09-19 修回日期:2008-12-10 出版日期:2010-02-21 发布日期:2010-02-21
  • 通讯作者: 焦尚彬

Research on translation table heuristic algorithm

JIAO Shang-bin,LIU Ding   

  1. Xi’an University of Technology,Xi’an 710048,China
  • Received:2008-09-19 Revised:2008-12-10 Online:2010-02-21 Published:2010-02-21
  • Contact: JIAO Shang-bin

摘要: 博弈树搜索对于计算机博弈至关重要。优秀的搜索算法通过搜索较少的节点就可以获得最佳路径,从而提高计算机的博弈水平。论文以中国象棋计算机博弈作为背景,在alpha-beta基本搜索算法上,详细阐述了置换表启发算法的原理和哈希冲突,引进了双层置换表的概念及其替换策略,增强了引擎的搜索效率。实验结果表明了该算法的有效性。

关键词: 计算机博弈, 博弈树, 置换表启发, alpha-beta算法

Abstract: Searching is essential for computer-game of board games.And excellent search algorithm may obtain the optimal path by searching few nodes,and improve the competitive level of computer game.This paper sets Chinese chess computer game as background,and on the basis of alpha-beta algorithm,it makes a detailed description about the principle of translation table heuristic algorithm and hash collision,and the replacement schemes of two-level transposition table is proposed,enhancing the efficiency of searing engine.At last,the experiment results verify the effectiveness of the methods.

Key words: computer game, searching tree, translation table heuristic, alpha-beta algorithm

中图分类号: