|
SSS * is a search algorithm, introduced by George Stockman in 1979, that conducts a state space search traversing a game tree in a best-first fashion similar to that of the A * search algorithm. SSS * is based on the notion of solution trees. Informally, a solution tree can be formed from any arbitrary game tree by pruning the number of branches at each MAX node to one. Such a tree represents a complete strategy for MAX, since it specifies exactly one MAX action for every possible sequence of moves might be made by the opponent. Given a game tree, SSS * searches through the space of partial solution trees, gradually analyzing larger and larger subtrees, eventually producing a single solution tree with the same root and Minimax value as the original game tree. SSS * never examines a node that alpha-beta pruning would prune, and may prune some branches that alpha-beta would not. Stockman speculated that SSS * may therefore be a better general algorithm than alpha-beta. However, Igor Roizen and Judea Pearl have shown that the savings in the number of positions that SSS * evaluates relative to alpha/beta is limited and generally not enough to compensate for the increase in other resources (e.g., the storing and sorting of a list of nodes made necessary by the best-first nature of the algorithm). However, Aske Plaat, Jonathan Schaeffer, Wim Pijls and Arie de Bruin have shown that a sequence of null-window alpha-beta calls is equivalent to SSS * (i.e., it expands the same nodes in the same order) when alpha-beta is used with a transposition table, as is the case in all game-playing programs for chess, checkers, etc. Now the storing and sorting of the OPEN list were no longer necessary. This allowed the implementation of (an algorithm equivalent to) SSS * in tournament quality game-playing programs. Experiments showed that it did indeed perform better than Alpha-Beta in practice, but that it did not beat NegaScout. The reformulation of a best-first algorithm as a sequence of depth-first calls prompted the formulation of a class of null-window alpha-beta algorithms, of which MTD-f is the best known example. ==Algorithm== There is a priority queue OPEN that stores states or the nodes, where - node identificator (Dewey's notation is used to identify nodes, is a root), - state of the node (L - the node is live, which means it's not solved yet and S - the node is solved), - value of the solved node. Items in OPEN queue are sorted descending by their value. If more than one node has the same value of , a node left-most in the tree is chosen. OPEN := while (true) // repeat until stopped pop an element p=(J,s,h) from the head of the OPEN queue if J == e and s == S STOP the algorithm and return h as a result else apply Gamma operator for p operator for is defined in the following way: if s == L if J is a terminal node (1.) add (J,S,min(h,value(J))) to OPEN else if J is a MIN node (2.) add (J.1,L,h) to OPEN else (3.) for j=1..number_of_children(J) add (J.j,L,h) to OPEN else if J is a MIN node (4.) add (parent(J),S,h) to OPEN remove from OPEN all the states that are associated with the children of parent(J) else if is_last_child(J) // if J is the last child of parent(J) (5.) add (parent(J),S,h) to OPEN else (6.) add (parent(J).(k+1),L,h) to OPEN // add state associated with the next child of parent(J) to OPEN 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SSS*」の詳細全文を読む スポンサード リンク
|