University of Cambridge > Talks.cam > Inference Group > Coherent Inference on Optimal Play in Games

Coherent Inference on Optimal Play in Games

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Emli-Mari Nel.

The search for an optimal path through a game tree is one of the oldest problems in computer science. Over the past years, Monte Carlo tree search has emerged as a surprisingly effective approach to this problem. I will present a probabilistic generative model for game trees that explains why MC tree search works at all. I will then move on to derive an approximate inference algorithm for this model, which can infer beliefs over the value of any node in the tree under optimal play, using random roll-out data from other parts in the tree. Somewhat surprisingly, this inference algorithm is of linear complexity, even though the exact search problem has exponential cost.

The work presented in this talk has just been published as P. Hennig, D. Stern, T. Graepel: “Coherent Inference on Optimal Play in Game Trees”, J Machine Learning Research, W&CP 9 (2010), 326-333.

See http://jmlr.csail.mit.edu/proceedings/papers/v9/hennig10a/hennig10a.pdf

This talk is part of the Inference Group series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity