Catalogue of Artificial Intelligence Techniques
Keywords: evaluation function, games, heuristic search
Author(s): Maarten van Someren
B* is a heuristic search method that can be applied to both adversary and non-adversary problems, but only when the search has an iterative character. It computes the best next step toward the solution on the basis of an evaluation function. An evaluation function assigns two values to each node, a pessimistic and an optimistic value, (cf. Minimax) on the basis of evaluation of the descendants. In non-adversary search this is done according to the following rules:
- Evaluate the descendants of a node in arbitrary order. If one of the descendants of a node has a pessimistic value greater than the pessimistic value of its parent, then raise the pessimistic value of the parent to the value of this daughter. If a node has an optimistic value that is higher than that of any daughter, then lower it to the maximal optimistic value of its daughters.
- Terminate when a daughter of the root of the search tree has a pessimistic value that is not lower than the optimistic value of all other daughters. The arc to that daughter is the best step to take.
In the case of adversary search (e.g., game playing), B* is the same as Alpha/Beta search, except that it stops once it has found the best next move. Best-first or Heuristic Search may be implemented in this manner. B* is claimed to be a good model of the search of chess masters.
- Berliner, H., The B* tree search algorithm: a best-first proof procedure Artificial Intelligence 12 (1979) no.1, 23--40, also appears in Readings in Artificial Intelligence
(Webber, B.L., ed.) Tioga Publishing, 1981, pp. 79--88