Phased state space search
T.A. Marsland, N. Srimani · 1986
PS*, a newsequential tree searching algorithm based on the State Space Search (SSS*), is presented. PS*(k) divides each MAX node of a game tree into k partitions, which are then searched in sequence. By this means twomajor disadvantages of SSS*, storage demand and maintenance overhead, are significantly reduced, and yet the corresponding increase in nodes visited is not so great eveninthe random tree case. The performance and requirements of PS* are compared on both theoretical and experimental grounds to the well known and SSS* algorithms. The basis of the comparison is the storage needs and the average count of the bottom positions visited.