Source-linked AI summary
Learning Explainable Representations of Complex Game-playing Strategies
Abhijeet Krishnan, Colin M. Potts, Arnav Jhala, Harshad Khadilkar, Shirish Karande, Chris Martens
TL;DR
Players may need extensive practice or access to experts to acquire strategies that help refine their mental models. This paper learns strategies as executable procedures, using a chess approach and a transformer-based approach for programmatic strategies. The learned chess strategies approximate a beginner better than a random baseline, while the transformer method is competitive with prior work and more sample efficient.
Problem
Acquiring strategies that help players refine mental models can require many hours of deliberate practice or access to expert knowledge, while player understanding of learned strategies has received less attention.
Source: §1 · p. 2Method
Results
Chess strategies approximate a human beginner better than a random baseline, and the transformer method is competitive with LEAPS in performance while more sample efficient.
Source: §4.4 · p. 10, §6 · p. 11Takeaways & Limitations
The learned strategies provide an automatic route to strategies players can use to refine their mental models.
Source: §1 · p. 2The work plans to test more game environments, investigate strategy interpretability, and measure whether strategies measurably improve player performance.
Source: §6 · p. 11
Abstract
from arXiv · showhide
As part of learning to play complex games, human players develop develop abstractions for concepts and strategies of gameplay consistent with game rules to improve their performance. These concepts are applied to explain other players' actions, and to inform their own actions in-game. Understanding other players' strategies is a crucial part of such improvement, but requires time and effort. In this paper, we propose a strategy similar to human cognition for training RL agents to synthesize learned strategies and policies as executable procedures based on sequences of gameplay actions. We present methods to automatically learn such programs to play chess and to solve tasks in a grid-based environment. We show that the learned strategies produce effective actions, and can be learned from gameplay data.
1. Introduction
Players use strategies to build mental models, but acquiring good strategies can require extensive practice or expert knowledge. This paper defines strategy synthesis as learning interpretable gameplay procedures and develops two approaches to do so.
1. Introduction
- Players can use optimal strategies to improve gameplay, but learning good strategies may require many hours of deliberate practice or access to experts.Automatically learned strategies could help players refine their mental models without relying on those routes to acquiring expertise.Source: §1 · p. 2
- Strategy synthesis is the automatic learning of parameterized gameplay action sequences that players can understand and use to improve their in-game performance.The paper notes that prior strategy-learning work has focused more on algorithms and representations than on player understanding and factors affecting interpretability.Source: §1 · p. 2
- Prior strategy-learning work has devoted less attention to how well learned strategies can be understood by players and what affects their interpretability.Examples include constraint-satisfaction rules for Nonograms, domain-specific rules for Hanabi, and executable programs learned through program synthesis.Source: §1 · p. 2
- The paper presents a chess strategy model based on chess literature and a transformer method for learning programmatic strategies.The chess strategies approximate a human beginner better than a random baseline; the transformer method is competitive with prior state of the art while more sample efficient.Source: §1 · p. 2
2. Strategy Synthesis
The paper frames strategy synthesis as reinforcement learning, with the learned strategy serving as a policy parameterization. Unlike ordinary RL, it adds a constraint that the strategy align with a player's mental model, and proposes computational interpretability metrics as a substitute for evaluating that alignment.
2. Strategy Synthesis
- The RL framing describes an optimal policy parameterized by a model that maximizes expected return in a Markov Decision Process.The MDP is specified by states, available actions, transition probabilities, rewards, and a discount factor.Source: §2 · p. 2
- Strategy synthesis uses the strategy model as the policy parameterization and the synthesis algorithm as the optimization procedure, with an added constraint of alignment to the player's mental model.The paper says it is unclear how alignment may be meaningfully evaluated.Source: §2 · p. 2
- The paper proposes computational interpretability metrics from explainable AI as a substitute for alignment between a learned strategy and a player's mental model.Interpretability is described as generating explanations in a form understandable to nonexperts, enabling them to predict model behavior.Source: §2 · pp. 2–3
- Cognitive-chunk count and model size are cited as metrics found to correlate with interpretability.These are presented as correlations, not as a direct measure of player understanding or strategy-model alignment.Source: §2 · p. 3
3. Learning Chess Strategies
The section presents a Prolog-based chess strategy model, an ILP learning procedure, and an evaluation showing that learned strategies can approximate a human beginner better than a random baseline.
3. Learning Chess Strategies
- The section reports that its algorithm learns strategies that approximate a human beginner better than a random baseline.The model is inspired by chess tactics, and the evaluation defines coverage and divergence for a strategy on a set of positions.Source: §3 · p. 3, §3.1 · pp. 3–4
3.1 Chess Strategy Model
- A chess strategy is a first-order logic rule in Prolog: Position describes the input state, while From and To specify the move.The model uses a domain-specific predicate vocabulary; Figure 1 presents the strategy model as Prolog pseudocode, with each feature_i clause defined as a vocabulary rule.Source: §3.1 · p. 3, Figure 1 · p. 3
3.2 Learning Chess Strategies using ILP
- The chess strategy-learning problem is formalized as ILP over positive and negative position–move examples, with the learned hypothesis serving as the strategy.Popper is modified to generate legal moves and prune strategies that are never applicable or fall below an empirically determined training-recall threshold.Source: §3.2 · p. 4
3.3 Evaluation
- With Stockfish 14 as the distance metric, learned strategies imitate the training set better than the random baseline.Evaluation used 1,297 beginner-game position–move pairs for training and 100 held-out pairs, reporting accuracy, coverage, and divergence as 20-bucket histograms.Source: §3.3 · p. 4
4. Learning Programmatic Strategies with Transformers
The paper models programmatic strategy synthesis as reinforcement learning and applies a decision transformer to learn executable strategies in discrete environments. On Karel tasks, the learned method is competitive with LEAPS and more sample efficient.
4.1 Programmatic Policy Synthesis as a Reinforcement Learning Problem
- Programmatic policy synthesis seeks a program in a DSL that approximates a target policy, formulated as finding an optimal policy in a synthesis MDP.The synthesis state is a partially expanded program, and actions apply production rules to selected non-terminals; valid applications advance the state deterministically, while invalid ones leave it unchanged.Source: §4.1 · p. 7
4.2 Applying Decision Transformers to Programmatic Policy Synthesis
- Decision Transformer trajectories sequence returns-to-go, states, and actions, which are embedded and processed by GPT to autoregressively predict future actions.A learned timestep embedding is added to each token because one timestep corresponds to three tokens.Source: §4.2 · pp. 7–8
- For discrete synthesis actions, the model masks invalid choices, uses cross-entropy loss, and samples from the predicted action distribution.Sequential GRU state embeddings empirically improve performance over direct state embeddings.Source: §4.2 · p. 8
4.3 Karel Domain
- Karel programs control a grid-world agent that moves and interacts with markers, with perceptions for detecting obstacles and markers.The evaluation uses six tasks with different goals and reward structures, and randomly sampled initial configurations at each episode reset.Source: §4.3 · p. 8
4.4 Evaluation
- The Decision Transformer is evaluated on Karel programmatic policy synthesis, trained using a dataset of 50,000 programs contributed by Trivedi et al. (2021), with Chen et al. (2021)'s hyperparameters and training procedure.Source: §4.4 · p. 8
- The Decision Transformer is competitive with LEAPS in performance while being more sample efficient on Karel tasks.Table 1 reports mean return and unique programs explored for the best program found on each task; standard deviations are in parentheses.Source: §4.4 · p. 10, Table 1 · p. 10
5. Related Work
Related work covers neural program synthesis from varied specifications and programmatic policies as interpretable or game-MDP policies. This paper investigates transformer-based synthesis from MDP rewards.
Neural program synthesis
- Neural program synthesis applies neural networks to program synthesis, with prior work using formal rules, input/output examples, demonstrations, language prompts, and MDP rewards.The paper’s transformer-based approach targets synthesis from MDP rewards.Source: §5 · p. 10
Learning programmatic policies
- Interpretable-policy research includes program surrogates [Orfanos & Lelis, 2023; Qiu & Zhu, 2022; Trivedi et al., 2021; Inala et al., 2020; Verma et al., 2018, 2019] and programmatic policies for game-based MDPs [Medeiros et al., 2022].This work investigates a transformer-based architecture for the same task.Source: §5 · pp. 10–11
6. Conclusion and Future Work
The conclusion links strategy synthesis to mental-model matching, interpretability, and program synthesis, and presents two approaches with reported strategy-learning results. It also identifies broader benchmarking and player-focused evaluation as future work.
6. Conclusion and Future Work
- The paper frames strategy synthesis through its connections to mental-model matching, model interpretability, and program synthesis.It introduces a rule-based chess strategy model and a transformer-based method for programmatic strategies.Source: §6 · p. 11
- The chess rule-based model better approximated a beginner than a random baseline, while the transformer-based programmatic method was competitive with a state-of-the-art method and more sample-efficient.The conclusion describes the chess approach as based on chess tactics and the transformer approach as learning programmatic strategies.Source: §6 · p. 11
- Future work will benchmark programmatic policy methods across more game environments, investigate strategy interpretability, and measure effects on player performance.Source: §6 · p. 11