UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Bootstrapping from game tree search

Veness, J; Uther, W; Blair, A; Silver, D; (2009) Bootstrapping from game tree search. In: Advances in Neural Information Processing Systems 22 - Proceedings of the 2009 Conference. (pp. 1937 - 1945).

Full text not available from this repository.


In this paper we introduce a new algorithm for updating the parameters of a heuristic evaluation function, by updating the heuristic towards the values computed by an alpha-beta search. Our algorithm differs from previous approaches to learning from search, such as Samuel's checkers player and the TD-Leaf algorithm, in two key ways. First, we update all nodes in the search tree, rather than a single node. Second, we use the outcome of a deep search, instead of the outcome of a subsequent search, as the training signal for the evaluation function. We implemented our algorithm in a chess program Meep, using a linear heuristic function. After initialising its weight vector to small random values, Meep was able to learn high quality weights from self-play alone. When tested online against human opponents, Meep played at a master level, the best performance of any chess program with a heuristic learned entirely from self-play.

Type:Proceedings paper
Title:Bootstrapping from game tree search
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record