Learning to solve game trees
Learning to solve game trees
复制标题
学习解决博弈树
DOI：
10.1145/1273496.1273602
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
T. Graepel
中科院分区：
文献类型：
--
作者：
David H. Stern;R. Herbrich;T. Graepel
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.
