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

THE DESIGN AND ANALYSIS OF GAME TREE SEARCHALGORITHMS

作　　者：孙伟[1] 马绍汉[1] 

机构地区：[1]山东大学计算机科学系,济南250100

出　　处：《计算机学报》1993年第5期361-369,共9页Chinese Journal of Computers

基　　金：国家自然科学基金;山东省自然科学基金

摘　　要：本文提出了博弈树搜索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.

关 键 词：博弈树 SSS算法 数据结构 

分 类 号：TP311.12[自动化与计算机技术—计算机软件与理论]