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.
Tree exploration with uncertainty
-
- Posts: 122
- Joined: Tue Feb 12, 2008 8:31 pm
- Contact:
Re: Tree exploration with uncertainty
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
@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
-
- Posts: 122
- Joined: Tue Feb 12, 2008 8:31 pm
- Contact:
Re: Tree exploration with uncertainty
Also:
@book{
Palay-1984a,
author = "Andrew J. Palay",
title = "Searching with Probabilities",
publisher = "Pitman",
year = 1984
}
Rémi
@book{
Palay-1984a,
author = "Andrew J. Palay",
title = "Searching with Probabilities",
publisher = "Pitman",
year = 1984
}
Rémi
Re: Tree exploration with uncertainty
Perfect, thank you!
-
- Posts: 122
- Joined: Tue Feb 12, 2008 8:31 pm
- Contact:
Re: Tree exploration with uncertainty
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
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