【作者】 张明亮；

【导师】 李凡长；

【作者基本信息】 苏州大学 ， 计算机应用技术， 2007， 硕士

【摘要】 机器博弈是人工智能研究领域的一大热点,博弈树搜索则是机器博弈的引擎。本文在博弈树搜索算法和博弈树优化技术等方面做了深入研究,将理论和实践紧密结合,取得了以下的主要创新成果:⑴提出并成功验证了一种新的博弈树搜索算法:基于广度优先的接力式空窗探测搜索算法。实验证实该方法在实际应用中的平均搜索效率,高于目前公认搜索效率最高、也是最流行的PVS和MTD(f)搜索方法;在迭代深化搜索中,该方法也具有相对优势;并且该算法的最小搜索极限小于极小树。因此,该方法具有广阔的应用前景。⑵给出了一种新的博弈树优化技术—“子树复用”技术。该技术在几乎不需要额外时间开销的情况下,就能使深层博弈树搜索的效率提高10%以上,并随着搜索深度的加大,效率提高得愈多。“子树复用”技术在限定用时或必胜局面的对弈中还具有额外的实用价值,因而“子树复用”技术无疑具有极好的应用价值。⑶给出了极小搜索树叶结点数定理的新的证明方法,指出了以前的有关证明的缺陷。针对很多人对极小树的不准确理解,以及对窗口搜索效率的有关误解,给出了正确的结论。⑷开发了高水平的五子棋人机对弈系统,该系统在估值函数设计上,探索了不同颗粒度估值函数的应用效果,证实粗颗粒度估值函数在深度搜索中可以具有更好的综合效果;部分局面下的估值函数延伸评估技巧,同样可以替代搜索,来减少地平线效应;这些为同行提供了很好的借鉴。证实借助棋类知识的走法生成函数,在五子棋对弈系统中具有很好的效果。在博弈树优化方面,挖掘出极小极大值搜索算法的优势,应用收到了良好的效果。更多还原

【Abstract】 Computer game is a very popular field in AI, Game-tree search is the key core of computer game. This paper gives profound research is game-tree search algorithm and game-tree optimization technique. The author combines theory and practice presents the following results:⑴It puts forward a new game-tree search algorithms which based on breadth-first continuously null-window test method. Experiments have proved that the efficiency of this algorithm out-performs the popular algorithms such as PVS and MTD(f) which are considered as having most high efficiencies. The new method also has some advantages in iterative-deepening search, and the search limit of this algorithm is smaller than minimal game-tree. Thus a wide application can be promised by this algorithm.⑵It gives a new technique of optimizing game tree: sub-game-tree reuse. This technique can improve deep search efficiency by 10 percent and more with deeper depth but no extra expenditure. The sub-game-tree reuse technique has added effect in limit time game or must victory phase. Of course, it has a better application value.⑶It gives a new proof of the theory about the number bottom-nodes of minimal game-tree, and points out the deficiency of old method. It also clarifies the misunderstanding concepts of minimal tree and window searching efficiency and gives the correct conclusion.⑷In this paper a high level human-machine playing gobang system is developed, and the author proves that by using evaluation function of rough value the better whole effect in depth searching can acquire, and the extending evaluating technique of the evaluation function also can reduce the horizon effect. The author also testifies that with the help of playing gobang knowledge, the move-generation function can produce good results in human-computer play gobang system. The author also extends use of minimax search algorithm in the optimizing game-tree area and achieves good result. With all these ideas and experiments, the paper provides a good reference to fellow researchers.更多还原