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 signi?cant 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 1021 joint actions. We approximate the value function by a neural network, augmented by linguistic knowledge that is extracted automatically from the of?cial game manual. We show that this non-linear value function is signi?cantly more ef?cient than a linear value function, which is itself more ef?cient than Monte-Carlo tree search. Our non-linear Monte-Carlo search wins over 78% of games against the built-in AI of Civilization II. 1