B* Probability Based Search
Abstract
We describe a search algorithm for two-player games that relies on selectivity rather than brute-force to achieve success. The key ideas behind the algorithm are: (1) Stopping when one alternative is clearly better than all the others; and (2) Focusing the search on the place where the most progress can likely be made toward being able to stop. Critical to this process is identifying uncertainty about the ultimate value of any move. The lower bound on uncertainty is the best estimate of the real value of a move, while the upper bound is its optimistic value, based on some measure of unexplored potential. Uncertainty is represented as probability densities. The search develops those parts of the tree where moving existing bounds would be most likely to succeed and make the most progress toward terminating the search. Termination is achieved when the established real value of the best move is so good that the likelihood of this being achieved by any other alternative is minimal
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 27, 1994
- Accession Number
- ADA282551
Entities
People
- Chris Mcconnell
- Hans J. Berliner
Organizations
- Carnegie Mellon University