UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Non-linear Monte-Carlo search in civilization II

Branavan, SRK; Barzilay, R; Silver, D; (2011) Non-linear Monte-Carlo search in civilization II. In: IJCAI International Joint Conference on Artificial Intelligence. (pp. 2404 - 2410).

Full text not available from this repository.

Abstract

This paper presents a new Monte-Carlo search algorithm for very large sequential decision-making problems. We apply non-linear regression within Monte-Carlo search, online, to estimate a stateaction value function from the outcomes of random roll-outs. This value function generalizes between related states and actions, and can therefore provide more accurate evaluations after fewer rollouts. A further significant advantage of this approach is its ability to automatically extract and leverage domain knowledge from external sources such as game manuals. We apply our algorithm to the game of Civilization II, a challenging multiagent strategy game with an enormous state space and around 10joint actions. We approximate the value function by a neural network, augmented by linguistic knowledge that is extracted automatically from the official game manual. We show that this non-linear value function is significantly more efficient than a linear value function, which is itself more efficient than Monte-Carlo tree search. Our non-linear Monte-Carlo search wins over 78% of games against the built-in AI of Civilization II.

Type:Proceedings paper
Title:Non-linear Monte-Carlo search in civilization II
DOI:10.5591/978-1-57735-516-8/IJCAI11-401
UCL classification:UCL > School of BEAMS > Faculty of Engineering Science > Computer Science

Archive Staff Only: edit this record