[computer-go] icml2007: Learning to solve game trees

[Rémi Coulom]

Hi,

Interesting paper, in case you did not notice:
http://www.machinelearning.org/proceedings/icml2007/papers/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