Tree exploration with uncertainty

Any topic that does not fit elsewhere
Post Reply
luke_g
Posts: 29
Joined: Sun Feb 17, 2008 9:52 am

Tree exploration with uncertainty

Post by luke_g » Wed Nov 05, 2008 9:16 am

I've been thinking about (best-first) exploration of trees, taking into account uncertainties in the evaluation function. Basically, choosing a node to expand based not only on its evaluation, but also the reliability or uncertainty of the evaluation. A couple examples: One is in UCT where less-explored, and therefore less reliably evaluated, nodes get higher priority. Second, quiescent search for chess in situations with capturable pieces, where the evaluation function is likely to be unstable.

It should be possible to take these ideas into a general framework, where in addition to an evaluation function, one also has an "uncertainty" function.

Does anyone know some good resources (papers, articles) about this? It seems like an interesting topic and I'd like to know what's already out there.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Tree exploration with uncertainty

Post by Rémi Coulom » Wed Nov 05, 2008 9:36 am

The idea of using probability distributions or confidence intervals instead of just a value for the evaluation function is not new. Here are some paper:

@article{
Berliner-1995a,
author = "Hans J. Berliner and Chris McConnell",
title = "{B}$^*$ Probability-Based Search",
journal = "Artificial Intelligence",
volume = 86,
number = 1,
pages = "97--156",
year = 1995
}

@article{
Berliner-1979a,
author = "Hans Berliner",
title = "The {B}$^*$ Tree-Search Algorithm: A Best-First Proof Procedure",
journal = "Artificial Intelligence",
volume = 12,
number = 1,
pages = "23--40",
year = 1979
}

@techreport{
Baum-1993a,
author = "Eric B. Baum and Warren D. Smith",
title = "Best Play for Imperfect Players and Game Tree Search",
institution = "{NEC} Research Institute",
address = "Princeton, NJ",
year = 1993
}

@article{
Baum-1997a,
author = "Eric B. Baum and Warren D. Smith",
title = "A {B}ayesian Approach to Relevance in Game Playing",
journal = "Artificial Intelligence",
volume = 97,
number = "1--2",
pages = "195--242",
year = 1997
}

Rémi

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Tree exploration with uncertainty

Post by Rémi Coulom » Wed Nov 05, 2008 9:38 am

Also:

@book{
Palay-1984a,
author = "Andrew J. Palay",
title = "Searching with Probabilities",
publisher = "Pitman",
year = 1984
}

Rémi

luke_g
Posts: 29
Joined: Sun Feb 17, 2008 9:52 am

Re: Tree exploration with uncertainty

Post by luke_g » Sun Nov 09, 2008 10:29 am

Perfect, thank you!

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Tree exploration with uncertainty

Post by Rémi Coulom » Sun Nov 09, 2008 11:59 am

Hi,

I forgot another important recent paper:

http://www.machinelearning.org/proceedi ... rs/394.pdf

Title: Learning to solve game trees

Authors: David Stern, Ralf Herbrich, Thore Graepel

Abstract: We apply probability theory to the task of proving whether a
goal can be achieved by a player in an adversarial game. Such problems
are solved by searching the game tree. We view this tree as a graphical
model which yields a distribution over the (Boolean) outcome of the
search before it terminates. Experiments show that a best-first search
algorithm guided by this distribution explores a similar number of nodes
as Proof-Number Search to solve Go problems. Knowledge is incorporated
into search by using domain-specific models to provide prior
distributions over the values of leaf nodes of the game tree. These are
surrogate for the unexplored parts of the tree. The parameters of these
models can be learned from previous search trees. Experiments on Go show
that the speed of problem solving can be increased by orders of
magnitude by this technique but care must be taken to avoid over-fitting.

Rémi

Post Reply