The B* Algorithm

[Steven J. Edwards]

A good write-up on the B* search algorithm can be found in the paper
by Hans Berliner titled "The B* Tree Search Algorithm: A Best-First
Proof Procedure". It appears in _Readings in Artifical Intelligence_
edited by Webber and Nilsson (Tioga 1981, ISBN 0-935382-03-8). This
book also has a copy of Wilkins' "Using Patterns and Plans in Chess"
which discusses PARADISE, a program that can solve a mate-in-10 while
generating a search tree with only 109 nodes. (The test position is
BWTC.0031 in pub/chess/Tests/BWTC.epd.gz at ics.onenet.net; Spector
can solve this problem but generates about 3.8 million nodes in the
process.)

One of the interesting aspects of B* compared to traditional depth
first searching is its ability to re-transverse portions of the search
tree with different "strategies" based on earlier analysis. To do
this it keeps the entire tree available, unlike traditional depth
first which doesn't keep around much more than the current path from
the root position. Also, B* does not guarantee an exact evaluation of
the selected move; rather, it "proves" that the value of the selected
move is better than that of any of the alternatives.

B* relies on the existence of evaluation functions that can give
accurate estimates of the pessimistic and optimistic values of a
position. Berliner writes that these are hard to do and I am unaware
of further progress. Each node with descendents gets both a
pessimistic and an optimistic evaluation and these are dynamically
backed-up during the search. If the functions are chosen properly,
the claim is that the search will terminate "naturally" and not suffer
combinatoric explosion.

I am in the early stages of an investigation into AQ*, an algorithm
that is in some ways similar to B* except that is uses backed-up
measures of quiescence (anti-quiescence, actually) combined with
traditional material plus positional factor evaluations. The entire
tree remains accessible during the search and multiple transversals
can be performed. A linked list of frontier nodes is kept and the
search progresses by iteratively selecting the "most interesting"
frontier node to expand while time remains. A lot of work remains to
be done, but there are a lot of opportunities to incorporate other AI
techniques (expert systems, neural networks, analogical reasoning, and
machine learning) into the node selector.

-- Steven (s...@mv.mv.com)