Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Fine-Grained Decision-Theoretic Search Control
Stuart Russell
Abstract:
Decision-theoretic control of search has previously used as its basic unit. of computation the generation and evaluation of a complete set of successors. Although this simplifies analysis, it results in some lost opportunities for pruning and satisficing. This paper therefore extends the analysis of the value of computation to cover individual successor evaluations. The analytic techniques used may prove useful for control of reasoning in more general settings. A formula is developed for the expected value of a node, k of whose n successors have been evaluated. This formula is used to estimate the value of expanding further successors, using a general formula for the value of a computation in game-playing developed in earlier work. We exhibit an improved version of the MGSS* algorithm, giving empirical results for the game of Othello.
Keywords:
Pages: 436-442
PS Link:
PDF Link: /papers/90/p436-russell.pdf
BibTex:
@INPROCEEDINGS{Russell90,
AUTHOR = "Stuart Russell ",
TITLE = "Fine-Grained Decision-Theoretic Search Control",
BOOKTITLE = "Proceedings of the Sixth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-90)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "1990",
PAGES = "436--442"
}


hosted by DSL   •   site info   •   help