| Description |
The alpha-beta strategy is a widely used method for economizing on the size of game trees. Heretofore, its application has been limited to depth-first tree growth in recursive search functions. However, many modern game players use retentive (i.e. coroutine-based) control to achieve greater attention mobility in the game tree, e.g. for heuristically guided "best-first" searching. This paper reformulates the alpha-beta strategy for this generalized control setting. Algorithms are provided (in complete PASCAL code) for the following operations on appropriate nodes arbitrarily selected from a game tree: terminal node expansion, resumption of heuristically suspended move generation, tree re-rooting (i.e. top-level move selection), subtree redevelopment to satisfy a new search thoroughness condition, including restart of nodes that were cut-off but may no longer be. empirical results are presented indicating that, in addition to heuristic freedom, this method typically offers trees with fewer terminal nodes than in the recursive case, due to best-first descendant ordering, and the availability on the average of greater tree context for node cutting. |
