Neural Comp. NEW Faster Access
HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
QUICK SEARCH:   [advanced]


     

This Article
Right arrow Full Text
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Download to citation manager
Right arrow reprints & permissions
Citing Articles
Right arrow Citing Articles via Google Scholar
Google Scholar
Right arrow Articles by Baum, E. B.
Right arrow Articles by Smith, W. D.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Baum, E. B.
Right arrow Articles by Smith, W. D.

Neural Computation, Vol 11, 215-227, Copyright © 1999 by The MIT Press

LETTERS

Propagating Distributions Up Directed Acyclic Graphs

Eric B. Baum and Warren D. Smith

In a previous article, we considered game trees as graphical models. Adopting an evaluation function that returned a probability distribution over values likely to be taken at a given position, we described how to build a model of uncertainty and use it for utility-directed growth of the search tree and for deciding on a move after search was completed. In some games, such as chess and Othello, the same position can occur more than once, collapsing the game tree to a directed acyclic graph (DAG). This induces correlations among the distributions at sibling nodes. This article discusses some issues that arise in extending our algorithms to a DAG. We give a simply described algorithm for correctly propagating distributions up a game DAG, taking account of dependencies induced by the DAG structure. This algorithm is exponential time in the worst case. We prove that it is #P complete to propagate distributions up a game DAG correctly. We suggest how our exact propagation algorithm can yield a fast but inexact heuristic.




HOME HELP FEEDBACK SUBSCRIPTIONS ARCHIVE SEARCH TABLE OF CONTENTS
J COGNITIVE NEUROSCIENCE NEURAL COMPUTATION MIT PRESS JOURNALS
Copyright © 1999 by The MIT Press.