摘要
通过对机器博弈主要搜索算法的深入分析和实践,提出了在博弈树一层结点中以广度优先方式,运用接力式空窗探测技术反复淘汰到只剩一个结点的新搜索方法.该方法面向应用,搜索过程易控,理论上的最小搜索极限小于极小博弈树.对比实验表明,该算法平均搜索效率高于PVS搜索和MTD(f)方法,并且使用该方法的迭代深化对博弈树优化效果最佳,从而使迭代深化搜索应用范围更加广泛.
A new search method was given for a game-tree with breadth-first in the first layer nodes and continuously minimal window test by deep analysis on game-tree search algorithms. It was good for the application and the process of search was easier for control, and may build a smaller search tree than the minimal game-tree in theory. Comparison experiments indicate that the efficiency of this technique outperforms the PVS and MTD（f） method. Another speriority is to optimize a game-tree by an itera- tive-deepening search, and to make the overall efficiency of iterative-deepening exceed a one-off game tree search.
出处
《山东大学学报（工学版）》
CAS
北大核心
2009年第6期1-7,23,共8页
Journal of Shandong University（Engineering Science）
基金
国家自然科学基金资助项目(60775045)
关键词
博弈树
极小树
空窗探测
迭代深化
广度优先
五子棋
game-tree
minimal tree
null window search
iterative-deepening search
breadth-first
gobang
