摘要
提出了人工智能博弈树搜索ＳＳＳ＊算法的两种改进算法ＢＳ＊和ＤＳ＊算法，给出了ＢＳ＊和ＤＳ＊搜索博弈树端结点的充分必要条件，由此证明了，如果能估计一个合适的上界，则ＢＳ＊算法优于ＳＳＳ＊算法．同时还证明了ＤＳ＊算法优于α－β算法．论述了ＤＳ＊算法搜索深度为奇数的博弈树时，在一般情况下也优于ＳＳＳ＊算法，且这两种算法都降低了存储开销．
Two improved versions for the intelligent game tree search SSS' algorithm arepresented,they are called BS' and DS. respectively. This paper gives the'necessary andsufficient conditions for BS' and DS' to search a terminal node of a game tree,and proves that DS' is superior over SSS' if a proper upper bound can be estimated.Simultaneously,this paper proves DS' algorithm is superior over α-β algorithm and DS'is generally superior over SSS' when searching a game tree with odd depth. These twoalgorithms decrease the storage requirement.
出处
《山东大学学报（自然科学版）》
CSCD
1994年第2期162-172,共11页
Journal of Shandong University(Natural Science Edition)
基金
国家自然科学基金
山东省自然科学基金
关键词
博弈树
与或树
人工智能
搜索算法
game tree lAND/OR tree
minimax value
SSS ￣* algorithm
α-β algorithm
best-first search
branch and bound
