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

Research on translation table heuristic algorithm

作　　者：焦尚彬[1] 刘丁[1] 

机构地区：[1]西安理工大学信息与控制工程研究中心,西安710048

出　　处：《计算机工程与应用》2010年第6期42-45,共4页Computer Engineering and Applications

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

关 键 词：计算机博弈 博弈树 置换表启发 alpha—beta算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]