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

S. R. K. Branavan; David Silver; Regina Barzilay

Source-linked AI summary

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

S. R. K. Branavan, David Silver, Regina Barzilay

arXiv:1401.5390v1Jan 18, 2014cs.CLcs.AIcs.LG

TL;DR

The paper asks how textual domain knowledge can be grounded automatically in a complex control task without manually encoding it or collecting extensive annotations. It integrates partial language analysis into a feedback-trained Monte-Carlo Search policy and reports substantially higher Civilization II win rates than language-unaware baselines. The method’s practical scope is limited by the computation-time trade-off introduced by its non-linear model.

Problem
Control algorithms typically require human effort to encode domain knowledge, while manuals and guides had not been automatically used to improve control performance.
Method
The method jointly learns text grounding and game control from simulated-game feedback, extracting state-relevant text and predicate structure as latent features in a non-linear action-value model.
Results
65.4% full-game win rate versus 31.5% for the best text-unaware baseline shows substantially stronger Civilization II performance with language-aware Monte-Carlo Search.
Takeaways & Limitations
Deeper linguistic analysis further improves game play, and acquired textual knowledge sustains good performance even when the number of simulations is reduced.
Takeaways & Limitations
The non-linear model requires more computation for parameter estimation, creating a trade-off between model complexity and the number of roll-outs possible in fixed time.

Abstract

from arXiv · show

Domain knowledge is crucial for effective performance in autonomous control systems. Typically, human effort is required to encode this knowledge into a control algorithm. In this paper, we present an approach to language grounding which automatically interprets text in the context of a complex control application, such as a game, and uses domain knowledge extracted from the text to improve control performance. Both text analysis and control strategies are learned jointly using only a feedback signal inherent to the application. To effectively leverage textual information, our method automatically extracts the text segment most relevant to the current game state, and labels it with a task-centric predicate structure. This labeled text is then used to bias an action selection policy for the game, guiding it towards promising regions of the action space. We encode our model for text analysis and game playing in a multi-layer neural network, representing linguistic decisions via latent variables in the hidden layers, and game action quality via the output layer. Operating within the Monte-Carlo Search framework, we estimate model parameters using feedback from simulated games. We apply our approach to the complex strategy game Civilization II using 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 34% absolute improvement and winning over 65% of games when playing against the built-in AI of Civilization.

1. Introduction

The paper develops automatic language grounding for control applications, using text-derived domain knowledge to guide game play without manual encoding. It addresses this through joint text analysis and control learning, evaluated in Civilization II against language-unaware baselines.

Motivation: The paper aims to ground document content in control applications by automatically using textual knowledge to improve situation-appropriate action selection.The motivation is that manuals describe promising tactics, but such information had not been used in control algorithms.
Challenges: The approach must learn mappings between guide text and states or actions, so relevant advice can bias state-specific action selection.This mapping connects textual descriptions such as “river” with corresponding game attributes and promising actions.
Challenges: Text analysis is learned without annotations by using automatically available control feedback, such as game score, across the changing state space.The paper motivates this setup because representative annotation over an enormous game state space is impractical.
Approach: The method integrates noisy or incomplete textual advice into Monte-Carlo Search while retaining effective control when advice is absent or mapping estimates are suboptimal.The model combines linguistic features with a non-linear action-value function trained from simulated-game feedback.

2. Learning Game Play from Text

The paper explains textual guidance as a way to enrich state-action prediction with correspondences between game attributes, actions, and words. Under control-feedback training, these features help Monte-Carlo Search learn promising actions from limited simulated play.

Textual Generalization: Textual features enrich a state-action classifier by connecting game states and actions with words appearing in guiding sentences and other contexts.A text-free classifier may miss associations when similar state-action examples are absent from training data.
Feedback-Based Learning: Control feedback evaluates simulated state-action choices and updates feature weights while sampling the action space for promising pairs.The feedback comes from simulating a limited number of game turns after an action.

3. Related Work

The paper situates its method within grounded language acquisition and Monte-Carlo game playing, distinguishing it from approaches requiring parallel annotations, complete instructions, or manually encoded domain knowledge.

Grounded Language Acquisition: Grounded language acquisition learns linguistic analysis from non-linguistic situated contexts, including images, game events, and robot actions.Existing methods are tailored to particular grounding contexts because parallel data vary substantially in structure.
Representation and Alignment: Prior grounding systems vary in how they represent non-linguistic input, linguistic input, and word-to-structure alignment.Representations range from discretized regions or action sequences to syntactic trees and semantic templates.
Representation and Alignment: This method avoids explicit alignment because parallel data are unavailable and instead extracts relevant text information for a control application.It uses state-action transitions already present in the game rather than inducing a richer hierarchical structure over the state-action space.
Learning from Control Feedback: Unlike methods translating complete instructions into fixed action policies, this approach treats manuals as high-level, state-contingent advice and biases a learned policy with partial analysis.The text may describe several strategies and need not specify the correct action for every game state.
Relation to Prior Work: Earlier game-grounding work used annotated traces, reconstructed game rules, or manually encoded domain knowledge, whereas this method learns text analysis and game play from game feedback.The feedback-driven setup avoids pre-compiled game traces that may be impractical to collect in complex games.
Monte-Carlo Game Playing: The action-value model uses a non-linear approximation that represents text analysis as latent variables and is reported to generalize better than linear alternatives.The non-linear model jointly supports estimating untried action values and incorporating textual information.

4. Monte-Carlo Search

Monte-Carlo Search estimates action values by simulating games from the current state and repeatedly improving its simulation policy. The paper specializes this estimation to each state and integrates stochastic game dynamics, rewards, and feedback-driven learning.

MDP Formulation: The game is represented as an MDP with state space S, action space A, stochastic transitions T(s′ | s, a), and reward function R(s).Actions assign moves to all units controlled during a turn, while transitions reflect game rules and opposing-player actions.
MDP Formulation: A policy π(s, a) selects actions probabilistically, while Qπ(s, a) measures expected total reward after taking action a in state s.The objective is an optimal policy maximizing expected total reward and therefore the chances of winning.
Simulation Search: Monte-Carlo Search estimates Qπ(s, a) from rewards observed in multiple simulated-game roll-outs starting at the current state.Each roll-out samples transitions and selects actions according to a simulation policy until completion or truncation.
Practical Assumptions: Full-game roll-outs may be truncated because Civilization II simulations are expensive, using the game score as a noisy reward available at every stage.The built-in AI is used as the opponent in the experiments.
Simulation Search: After a fixed number of roll-outs, the algorithm plays the action with the highest average final simulated reward and repeats this process at each actual game state.The simulation policy improves from the roll-outs, directing later simulations toward higher-scoring regions.
State-Specific Learning: Q(s, a) is relearned for each observed state, making the representation simpler and learnable from fewer observations than a global action-value function.This state-specific relearning is important when the game state space is extremely large.

5. Adding Linguistic Knowledge to the Monte-Carlo Framework

The method adds language grounding to Monte-Carlo game search by jointly modeling sentence relevance, predicate structure, and action quality from simulated-game feedback. Extracted linguistic features are integrated into a neural action-value model that evaluates candidate actions.

Model structure: The model performs three tasks: selecting a state-relevant sentence, labeling its predicate structure, and predicting actions from game and text features.These components are first modeled separately and then integrated into one coherent model.
Sentence relevance: Sentence relevance is modeled using features combining sentence attributes with the current game state and candidate action.The model identifies the sentence most relevant to each state-action context rather than using the entire document uniformly.
Predicate structure: Predicate labeling assigns each sentence word to action-description, state-description, or background categories using word, part-of-speech, and dependency features.The labeling conditions on the sentence’s syntactic structure.
Action selection: The action-value function combines game features with the selected sentence and predicate labeling, then selects the action maximizing Q(s, a).The feature layer is computed from the active relevance and predicate units, and the output layer forms a weighted linear combination.
Model structure: Text analysis decisions are latent variables in hidden neural-network layers, while the output layer represents the action-value function.The joint model combines two text-analysis components with action-value estimation.
Parameter estimation: Parameters are learned online from simulated-game roll-outs, with observed outcomes updating the text and action-value components at each game state.The action-value function is relearned for each new state to specialize it to the corresponding subgame.

6. Applying the Model

The paper applies its model to Civilization II by representing rich game states and actions, using score-ratio utility feedback and text–game features within Monte-Carlo search.

6.1 Game States and Actions: Civilization II states include the world map, tile attributes, and the locations and attributes of cities and units.Actions are constrained by game rules and include city construction, unit movement, irrigation, and other unit-specific operations.
6.2 Utility Function: The player’s utility is the ratio of its game score to the opponent’s score because full-game roll-outs are infeasible.The score ratio is a noisy indicator of civilization strength; it performed better empirically than score difference across algorithms and baselines.
6.3 Features: Model features combine text attributes, game attributes, and their correspondences to identify relevant manual sentences and predicate labels.Sentence relevance uses game–sentence feature products and word-overlap tests, while predicate labeling uses words, part-of-speech tags, and dependency information.
6.3 Features: Figure 8 distinguishes features testing game attributes from those testing manual words using blue and red highlights, respectively.The action-value layer combines the game state, candidate action, selected sentence, and predicate labeling.

7. Experimental Setup

The experiments evaluate the language-informed Monte-Carlo player on Freeciv using the Civilization II manual, repeated simulations, and win-rate comparisons against the built-in AI.

7.1 Data: The evaluation uses the official Civilization II manual, containing 3638 word types and 2083 sentences averaging 16.9 words.The manual covers game rules, interface information, and basic strategy advice.
7.2 Experimental Framework: The method is tested in Freeciv, an open-source reimplementation instrumented for programmatic state measurement, action execution, saving, loading, and game control.Freeciv’s server and client were also modified to accelerate simulation and remove crashes while preserving game rules and functionality.
7.2 Experimental Framework: Each experiment starts from the same initial state, runs for 100 steps, and performs 500 roll-outs per step, each lasting 20 simulated steps.With about 18 units per player, the roll-outs require approximately 180,000 action decisions.
7.2 Experimental Framework: The framework uses one primary game and multiple simulated games initialized from the primary game’s current state.Separate Freeciv server–client instances communicate through the experimental framework to support parallel simulation.
7.3 Evaluation Metrics: Performance is measured by the percentage of games won against Freeciv’s built-in heuristic AI, averaged over independent runs.The primary metric counts wins within the first 100 steps, which underestimates performance because unfinished games are treated as losses.

8. Results

Across Civilization II evaluations, the language-aware Monte-Carlo agent outperforms text-unaware baselines, while richer linguistic analysis and textual guidance improve performance. Text helps the search reach high-score regions faster, although computational cost and strategy assumptions constrain the approach.

Game performance: 65.4% win rate in full-length games versus 31.5% for the best text-unaware baseline.On the primary 100-step evaluation, the language-aware method wins 53.7% of games versus 26.1% for the best non-language-aware method.
Textual advice and game performance: Textual information guides Monte-Carlo search toward high-score regions faster than a non-text-aware latent-variable model.The full model’s observed score improves dramatically over a small number of roll-outs.
Linguistic representation and game performance: 46.7% win rate for sentence relevance without predicate labeling, showing that deeper syntactic analysis further improves performance.Identifying advice relevant to the current game state remains essential, while predicate labeling adds performance beyond sentence relevance alone.
Linguistic representation and game performance: 39.6% win rate without dependency information, indicating that dependency features are crucial to predicate-labeling performance.The ablation removes all dependency features and leaves predicate labeling based only on word-type features.
Model complexity versus computation time: With a fixed computation budget, the text-aware model still produces the best performance despite higher computational demands.Non-linear models require more computation for parameter estimation, reducing the number of roll-outs possible in a fixed time.
Learned game strategy: The models learn a basic rush strategy, and performance differences reflect how well they learn that strategy; score maximization favors its fast win condition.The models assume game units are independent, which limits coordination for more complex strategies.

9. Conclusions

The paper presents a text-grounded control approach that learns language analysis and game strategies jointly from control feedback. In Civilization II, textual information improves game-playing performance and supports robust play under reduced simulation budgets and noisy language analysis.

The model enriches a learned policy with text features, jointly identifying relevant game-state text and inducing predicate structures through Monte-Carlo Search.Linguistic decisions and action selection are trained together using control feedback.
Textual information significantly improves game win rate over strong language-agnostic baselines.The paper evaluates this effect in the Civilization II game-playing setting.
The model sustains good performance with fewer simulations despite its greater complexity.This indicates that acquired textual knowledge remains useful when computation is reduced.
Predicate labeling and syntactic structure further improve gameplay, while ignoring syntax substantially harms performance.The results emphasize the value of deeper linguistic representations.
Tightly coupling control and linguistic features yields robust performance despite noise in automatic language analysis.

Bibliographical Note

The article substantially extends two earlier conference publications by analyzing model properties and increasing the volume of the reported work.

The article extends two conference publications with analyses of linguistic representation, bootstrapping dependence, and representational power versus empirical complexity.
The extended article also increases the volume of the prior work.

Appendix A. Parameter Estimation

Parameter estimation uses backpropagation to update a multilayer model whose hidden representations encode linguistic decisions and whose output estimates action quality.

The appendix simplifies the parallel second layers by deriving updates for one layer and noting that the other is analogous.
The model activates sentence or predicate nodes with softmax, computes third-layer features deterministically, and forms Q as a linear combination of those features.The output layer uses weights w to combine the feature vector f.
Q = w · f defines the model’s action-value output as a weighted combination of final-layer features.
Parameters are estimated by gradient descent on mean-squared error using standard error backpropagation.The update follows the gradient of the error with respect to each model parameter.
Online updates are derived separately for final-layer weights and the sentence-relevance and predicate-labeling parameters.The output updates use the observed action value Q = Q(s, a) and a learning rate α_w.

Appendix B. Example of Sentence Relevance Predictions

The appendix illustrates sentence-relevance predictions using an excerpt from the Civilization II strategy guide, with model-identified relevant sentences highlighted.

The example displays a portion of the Civilization II strategy guide and highlights sentences identified as relevant by the text-aware model.
The excerpt explains how terrain surrounding a new city is organized into a city radius.It describes citizens working the surrounding terrain in an x-shaped pattern.

Appendix C. Examples of Predicate Labeling Predictions

The appendix illustrates predicate labeling of manual sentences, distinguishing action, state, and background descriptions. Examples cover city construction, military protection, settlement expansion, terrain improvement, and other game actions.

The method labels manual words as action-description, state-description, or background, with incorrect predictions marked alongside correct labels.The examples demonstrate the labeling scheme on game-manual sentences.
Manual examples describe city construction, including building cities, city walls, and wonders subject to technology requirements.The examples include city-building actions and the condition that a required advance must be discovered before constructing a wonder.
The examples also cover military actions and states, including capturing undefended cities and keeping phalanx units inside cities for protection.These sentences connect game states such as being undefended with actions such as moving an army and capturing a city.
Other labeled sentences concern terrain improvement, settlement placement, and maritime exploration or transport.Examples mention building cities except on ocean terrain, improving terrain with settlers or engineers, and using ships to explore or transport units.

Appendix D. Examples of Learned Text to Game Attribute Mappings

The appendix shows how text is mapped to game attributes and how those mappings contribute to relevance, predicate-labeling, and action-value features. The feature templates combine linguistic cues with player, city, unit, neighborhood, state, and action information.

The model associates words such as “attack,” “build,” “grassland,” and “settler” with game attributes, actions, terrain, city properties, and unit states.The appendix lists strongly weighted attributes for example words, including city construction, roads, settlements, terrain, and city improvements.
Sentence-relevance features use word presence, matches to unit or neighborhood attributes, and matches to the action under consideration.Additional templates incorporate the current unit type and action type when evaluating sentence relevance.
Predicate-labeling features combine candidate labels with lexical, part-of-speech, dependency-tree, unit-name, action-name, and state-attribute information.The templates distinguish action, state, and background labels while using dependency structure and word properties.
Action-value features include player-level quantities such as veteran units, wealth, production, research progress, and controlled or explored world percentages.The listed features cover economic outputs, science, technology progress, world control, and exploration.
City- and unit-level templates add construction, growth, production, governance, terrain, resources, distances, health, movement, veteran status, and nearby enemy information.The model also includes city and unit counts, average and total city size, player and opponent scores, and predicate-labeled word interactions with states and actions.
Predicate-labeled words are combined with current state and action attributes to form features linking textual cues to candidate actions.These combinations include word-label pairs with the current unit type, considered action, and nearby attributes.