Learning to Win by Reading Manuals in a Monte-Carlo Framework

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 268–277, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Learning to Win by Reading Manuals in a Monte-Carlo Framework S.R.K. Branavan David Silver * Regina Barzilay Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology {branavan, regina}@csail.mit.edu * Department of Computer Science University College London d.silver@cs.ucl.ac.uk Abstract This paper presents a novel approach for lever- aging automatically extracted textual knowl- edge to improve the performance of control applications such as games. Our ultimate goal is to enrich a stochastic player with high- level guidance expressed in text. Our model jointly learns to identify text that is relevant to a given game state in addition to learn- ing game strategies guided by the selected text. Our method operates in the Monte-Carlo search framework, and learns both text anal- ysis and game strategies based only on envi- ronment feedback. We apply our approach to the complex strategy game Civilization II us- ing the official game manual as the text guide. Our results show that a linguistically-informed game-playing agent significantly outperforms its language-unaware counterpart, yielding a 27% absolute improvement and winning over 78% of games when playing against the built- in AI of Civilization II. 1 1 Introduction In this paper, we study the task of grounding lin- guistic analysis in control applications such as com- puter games. In these applications, an agent attempts to optimize a utility function (e.g., game score) by learning to select situation-appropriate actions. In complex domains, finding a winning strategy is chal- lenging even for humans. Therefore, human players typically rely on manuals and guides that describe promising tactics and provide general advice about the underlying task. Surprisingly, such textual infor- mation has never been utilized in control algorithms despite its potential to greatly improve performance. 1The code, data and complete experimental setup for this work are available at http://groups.csail.mit.edu/rbg/code/civ. The natural resources available where a population settles affects its ability to produce food and goods. Build your city on a plains or grassland square with a river running through it if possible. Figure 1: An excerpt from the user manual of the game Civilization II. Consider for instance the text shown in Figure 1. This is an excerpt from the user manual of the game Civilization II.2 This text describes game locations where the action “build-city” can be effectively ap- plied. A stochastic player that does not have access to this text would have to gain this knowledge the hard way: it would repeatedly attempt this action in a myriad of states, thereby learning the characteri- zation of promising state-action pairs based on the observed game outcomes. In games with large state spaces, long planning horizons, and high-branching factors, this approach can be prohibitively slow and ineffective. An algorithm with access to the text, however, could learn correlations between words in the text and game attributes – e.g., the word “river” and places with rivers in the game – thus leveraging …

Content truncated to 500 words