博弈树搜索算法设计和分析

THE DESIGN AND ANALYSIS OF GAME TREE SEARCHALGORITHMS

本文提出了博弈树搜索SSS~*算法的两种改进算法BS~*和DS~*算法,给出了BS~*和DS~*搜索博弈树端结点的充分必要条件,并由此证明了,如果能估计一个合适的上界,则BS~*算法优于SSS~*算法,同时还证明了DS~*算法优于α-β算法,论述了DS~*算法搜索深度为奇数的博弈树时,在一般情况下也优于SSS~*算法,且这两种算法都降低了存储开销。

This paper presents two improved versions of the game tree search algorithm SSS* ,called BS* and DS* respectively,gives the necessary and sufficient conditions for BS* and DS* to search a terminal node of a game tree,and proves that BS* is superior over SSS* if a proper'upper bound can be estimated.Simultaneously,this paper proves that DS* is superior over α-β algorithm and DS* is generally superior over SSS* when searching a game tree with odd depth.These two algorithms decrease the storage requirement.