Accession Number:

ADA282551

Title:

B* Probability Based Search

Descriptive Note:

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1994-06-27

Pagination or Media Count:

54.0

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

Subject Categories:

  • Operations Research
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE