B∗ probability based search

摘要

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.(1) stopping when one alternative is clearly better than all the others, and2.(2) focusing the search on the place where the most progress can likely be made toward stopping.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. The upper bound is its optimistic value, based on some measure of unexplored potential. This provides an I-have-optimism-that-needs-to-be-investigated attitude that is an excellent guiding force. Uncertainty is represented by probability distributions. The search develops those parts of the tree where moving existing bounds would be most likely to succeed and would 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.The B∗ probability based search algorithm has been implemented on the chess machine Hitech. En route we have developed effective techniques for: •• producing viable optimistic estimates to guide the search,•• producing cheap probability distribution estimates to measure goodness,•• dealing with independence of alternative moves, and•• dealing with the graph history interaction problem. The report describes the implementation, and the results of tests including games played against brute-force programs. Test data indicate that B∗ Hitech is better than any searcher that expands its whole tree based on selectivity. Further, analysis of the data indicates that should additional power become available, the B∗ technique will scale up considerably better than brute-force techniques.