UCL logo

UCL Discovery

UCL home » Library Services » Electronic resources » UCL Discovery

Non-linear Monte-Carlo search in civilization II

Branavan, SRK; Silver, D; Barzilay, R; (2011) Non-linear Monte-Carlo search in civilization II. In: (pp. pp. 2404-2410).

Full text not available from this repository.


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 10 21 joint 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
ISBN-13: 9781577355120
DOI: 10.5591/978-1-57735-516-8/IJCAI11-401
URI: http://discovery.ucl.ac.uk/id/eprint/1347378
Downloads since deposit
Download activity - last month
Download activity - last 12 months
Downloads by country - last 12 months

Archive Staff Only

View Item View Item