Tree exploration with uncertainty

[luke_g]

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]

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]

Also:

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

Rémi

[luke_g]

Perfect, thank you!

[Rémi Coulom]

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