Paper deep dive
Learning Explainable Representations of Complex Game-playing Strategies
Abhijeet Krishnan, Colin M. Potts, Arnav Jhala, Harshad Khadilkar, Shirish Karande, Chris Martens
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 10/13/2026, 3:52:56 AM
Summary
This paper proposes methods for learning explainable, programmatic representations of game-playing strategies. It presents two approaches: 1) A strategy model for chess based on first-order logic (Prolog) learned via Inductive Logic Programming (ILP) to approximate human beginner strategies. 2) A transformer-based approach (Decision Transformer) for synthesizing programmatic policies in grid-based environments (Karel), demonstrating competitive performance with higher sample efficiency compared to existing methods like LEAPS.
Entities (10)
Relation Signals (8)
Programmatic Policy Synthesis → usesmodel → Decision Transformer
confidence 95% · We present a novel method for learning programmatic strategies using transformers... applying the decision transformer model...
Decision Transformer → evaluatedon → Karel
confidence 90% · We evaluate our method using tasks in a grid-based programming environment... Karel...
Chess Strategy Learning → usesmethod → Inductive Logic Programming
confidence 90% · We present a learning algorithm based on inductive logic programming that learns chess strategies...
Chess Strategy Model → usesrepresentation → Prolog
confidence 90% · We model a chess strategy as a first-order logic rule expressed in Prolog...
Decision Transformer → comparedwith → LEAPS
confidence 85% · We compare the performance of strategies learned using the decision transformer with those learned by using LEAPS...
Chess Strategy Evaluation → usesoracle → Stockfish 14
confidence 85% · As the oracles for calculating the distance metric, we used the chess engines Stockfish 14...
Chess Strategy Evaluation → usesoracle → Maia-1600
confidence 85% · As the oracles for calculating the distance metric, we used the chess engines... Maia-1600...
Chess Strategy Learning → →
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract: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.
Tags
Links
- Source: https://arxiv.org/abs/2610.07638v1
- Canonical: https://arxiv.org/abs/2610.07638v1
Trouble viewing inline? Open PDF directly →
Full Text
37,855 characters extracted from source content.
Expand or collapse full text
Learning Explainable Representations of Complex Game-playing Strategies Chris Martens Abstract 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. akrish13@ncsu.edu cmpotts@ncsu.edu ahjhala@ncsu.edu Venture IV 420, North Carolina State University, Raleigh, NC 27606 USA harshadk@iitb.ac.in Department of Aerospace Engineering, Indian Institute of Technology Bombay, Powai, Mumbai 400076, Maharashtra, India shirish.karande@tcs.com Tata Research Development and Design Centre, Pune 411013, Maharashtra, India c.martens@northeastern.edu Meserve 138 (Boston campus), Khoury College of Computer Sciences, College of Arts, Media and Design, Northeastern University, Boston, MA 02115 USA 1 Introduction Researchers in varied fields agree that people create mental models as shorthand for understanding the human experience (Boyan and Sherry, 2011). Mental models are described as “mechanisms whereby humans are able to generate descriptions of system purpose and form, as explanations of system functioning and observed system states, and as predictions (or expectations) of future system states” (Rouse et al., 1992). In the context of games, players refine their mental models through solitary practice or formal instruction, discussion of strategies among peers, or investigation of underlying game mechanics (Boyan et al., 2018). Evidence suggests that when provided with optimal game strategies, players are able to transfer them to their game play (Paredes-Olay et al., 2002). However, acquiring good strategies involves many hours of deliberate practice, or access to expert knowledge, which may not be easily available. Automatically learning good game-playing strategies that players can use to refine their mental model would help overcome this challenge. The problem of strategy synthesis can be defined as the automatic learning of paremeterized gameplay action sequences that can be applied as procedures in games, in some suitably interpretable representation, that can be understood by a player to change their mental model and measurably improve their performance in-game. Existing work focuses mostly on the computational learning algorithms and representations of strategies. For example, Butler et al. (2017) are able to learn strategies using constraint satisfaction as condition-action rules to solve the puzzle game of Nonograms. Canaan et al. (2018) use a genetic algorithm to learn strategies represented using domain-specific rules for the card game Hanabi. A recent line of work models a strategy as an executable program in a domain-specific programming language (DSL), which can then be learned by applying techniques from program synthesis (de Freitas et al., 2018; Mariño et al., 2021; Mariño and Toledo, 2022; Medeiros et al., 2022). Considerably less attention has been devoted to investigating how well the learned strategies can be understood by players, and which factors contribute to their interpretability. Our contributions in this work are two-fold. First, we present a cognitively-inspired strategy model for chess that is based on existing models of chess strategy found in the game’s literature. We present a learning algorithm and metrics to evaluate the effectiveness of a strategy. We show that the learned strategies can approximate a human beginner better than a random baseline. Second, we present a learning algorithm for programmatic representations of strategies based on the transformer model (Vaswani et al., 2017). We show that it is competitive with prior state-of-the-art while being much more sample efficient. 2 Strategy Synthesis We define strategy synthesis through the lens of reinforcement learning (RL). RL seeks to find an optimal policy π∗(⋅,θ) _*(·,θ) parametrized by a model θ that maximizes the expected return in a Markov Decision Process (MDP) ⟨,(s),,ℛ,γ⟩ ,A(s),P,R,γ . Our definitions of these terms are based on the treatment by Sutton and Barto (2018). Strategy synthesis attempts to solve the same problem as RL, with the strategy model being the parametrization θ of a policy, and the synthesis algorithm being the optimization procedure. Unlike RL, strategy synthesis has the additional constraint that the learned strategy model must be aligned with the mental model of the player. Model matching theory posits that the “alignment of game models and external situations can facilitate the player’s transfer of mental models between games and external situations” (Boyan et al., 2018). Alignment is framed as a matter of creating accurate facsimiles of the game, and providing the necessary tools and scaffolds to help players “make sense of” the strategy (Martinez-Garza and Clark, 2017). However, it is unclear how alignment may be meaningfully evaluated. As a substitute for alignment between a learned strategy and a player’s mental model, we propose using computational metrics for model interpretability derived from the field of explainable AI. Interpretability is defined as “the ability to not only extract or generate explanations for the decisions of the model, but also to present this information in a way that is understandable by human (non-expert) users to, ultimately, enable them to predict a model’s behaviour” (Puiutta and Veith, 2020). Some metrics that have been found to correlate with interpretability are the number of cognitive chunks used and the model size (Lage et al., 2019). 3 Learning Chess Strategies In this section, we describe our strategy model for chess inspired by the concept of chess tactics. We present a learning algorithm based on inductive logic programming that learns chess strategies from gameplay data. We evaluate the learned strategies and show that our algorithm can learn strategies that approximate a human beginner better than a random baseline. 3.1 Chess Strategy Model We model a chess strategy as a first-order logic rule expressed in Prolog (Wielemaker, 2003) using a domain-specific predicate vocabulary P. As seen in :tactic-model, the rule head of the strategy consists of the variables Position, From and To. The input state is described by Position, which is also expressed in first-order logic using P. From and To describe the output action, namely, the move which begins from the square From and ends on the square To. tactic(Position, From, To) ← feature_1 (⋯·s), feature_2 (⋯·s), ⋮ feature_n (⋯·s) :tactic-model Figure 1: Our chess strategy model expressed in Prolog pseudocode. Every feature_i clause is a rule defined in the predicate vocabulary. Our usage of first-order logic to model chess tactics is motivated by the following reasons — 1. Chess tactics are an important concept that human players use to think about chess (Szabo, 1984) and are useful in chess education (Gobet and Jansen, 2006). 2. First-order logic has been extensively used to model chess patterns (Berliner, 1975; Pitrat, 1977; Wilkins, 1979; Huberman, 1968; Bramer, 1977; Bratko, 1982). 3. Logic rules are commonly acknowledged to be interpretable and have a long history of research (Zhang et al., 2021). To evaluate the learned strategies, we define the metrics of coverage and divergence for a strategy σ on a set of positions P as follows — Coverage(σ,P) (σ,P) ≐|PA||P| coverage |P_A||P| coverage (1) DivergenceE(σ(⋅),P)≐1|PA|∑(s,a1)∈PA∑a2∈(s)σ(a2|s)dE(s,a1,a2) divergence _E(σ(·),P) 1|P_A| _(s,a_1)∈ P_A _a_2 (s)σ(a_2|s)d_E(s,a_1,a_2) divergence (2) where PAP_A is the set of positions in P where the strategy σ is applicable, and dEd_E is a distance measure between actions a1a_1 and a2a_2 in state s. 3.2 Learning Chess Strategies using ILP Inductive logic programming (ILP) is a form of symbolic machine learning that aims to induce a hypothesis (a set of logical rules) that generalizes given training examples. (Cropper and Dumančić, 2022). An ILP problem is specified by three sets of Horn clauses — • B, the background knowledge, • E+E^+, the set of positive examples of the concept, and • E−E^-, the set of negative examples of the concept. The ILP problem is to induce a hypothesis H∈ℋH (an appropriately chosen hypothesis space) that, in combination with the background knowledge, entails all the positive examples and none of the negative examples. Formally, this can be written as — ∀e∈E+,H∪B⊧e (i.e., H is complete) ∀ e∈ E^+,H∪ B e (i.e., H is complete) ∀e∈E−,H∪B⊧̸e (i.e., H is consistent) ∀ e∈ E^-,H∪ B e (i.e., H is consistent) We formalize the problem of learning a chess strategy as an ILP problem ⟨E+,E−,B⟩ E^+,E^-,B . E+E^+ is a set of ⟨position,move⟩ ,move tuples where the move made in the position is drawn from a target policy. E−E^- is a set of ⟨position,move⟩ ,move tuples where the move made in the position is not drawn from the target policy. B is the predicate vocabulary used to express positions, moves and chess strategies. We learn a hypothesis H that maximizes the number of examples entailed in E+E^+ and minimizes the number of examples entailed in E−E^-. The hypothesis H is our chess strategy σ. To solve this ILP problem, we use a Prolog-based ILP system called Popper (Cropper and Morel, 2021). We modify Popper to constrain it to produce legal moves and to prune strategies that are never applicable or whose recall on the training set is less than an empirically-determined threshold. fork(Position,From,To)←make_move(From, To, Position, NewPosition),attacks(To, Square1, NewPosition),attacks(To, Square2, NewPosition),different_pos(Square1, Square2), aligned fork&(Position,From,To) \ ←\\ & make\_move(From, To, Position, NewPosition),\\ & attacks(To, Square1, NewPosition),\\ & attacks(To, Square2, NewPosition),\\ & different\_pos(Square1, Square2),\\ aligned :tactic-fork Figure 2: An interpretation of the fork tactic from the chess literature using our predicate vocabulary. The first attacks clause states that the piece at To attacks the opposing piece at Square1 in the current position. 3.3 Evaluation To evaluate our system for chess strategy synthesis, we trained it using a dataset of 1297 (position, move) pairs sampled from online games played by beginner players, and evaluated it on a held-out set of 100 pairs using the metrics of accuracy, coverage and divergence. To serve as the oracles for calculating the distance metric, we used the chess engines Stockfish 14 (Romstad et al., 2021) and Maia-1600 (McIlroy-Young et al., 2020). As baseline strategies, we used the aforementioned chess engines, and the random strategy. We report the results for each of accuracy, coverage and divergence as a histogram with 20 buckets. We see that when using Stockfish 14 as a distance metric, the learned strategies are better at imitating the training set than a random baseline. (a) Divergence histogram for T evaluated using Maia-1600 div-t1600-m1600 (b) Divergence histogram for T evaluated using Stockfish 14 div-t1600-sf14 Figure 3: Divergence histograms for T (a) Coverage histogram for T cov-t1600 (b) Accuracy histogram for T acc-t1600 4 Learning Programmatic Strategies with Transformers In this section, we present a novel method for learning programmatic strategies using transformers that is competitive with state-of-the-art methods while being more sample efficient. We first describe how problem of synthesizing programmatic strategies can be modeled as a reinforcement learning problem. We then present our method, which applies the decision transformer model to discrete environments. We evaluate our method using tasks in a grid-based programming environment and show that the strategies learned by our method are competitive with a state-of-the-art programmatic policy synthesis algorithm, while being much more sample efficient. 4.1 Programmatic Policy Synthesis as a Reinforcement Learning Problem Programmatic policy synthesis is the problem of approximating a target policy using a program, as specified by some DSL. We cast this as a RL problem by modeling the program synthesis environment as an MDP. Formally, given a DSL G=(V,Σ,R,S)G=(V, ,R,S) (Sipser, 1996) which defines the space of possible programmatic policies, and an MDP ℳexecM_exec in which a programmatic policy σ can execute and obtain reward, we define the programmatic policy synthesis task as that of finding an optimal policy in the MDP ℳsynM_syn, where: • syn≐w∈(V∪Σ)∗|S⇒∗wS_syn \w∈(V∪ )^*\ |\ S *w\ and is the current sequence of terminals and non-terminals in the partially expanded program (w0,w1,⋯,wi,⋯)(w_0,w_1,·s,w_i,·s). • syn≐R×V×ℕA_syn R× V×N and is the space of all actions consisting of applying a rule r to a non-terminal symbol v located at index i in the current state. • synP_syn is the transition function which represents the deterministic transition to a state where the production rule has been applied to the selected non-terminal symbol if such an action was valid. If not, the state remains unchanged. • d0,syn(S)=1d_0,syn(S)=1 • rsyn≐rexec,if current state s∈syn is terminal0,otherwiser_syn casesr_exec,&if current state s _syn is terminal\\ 0,&otherwise cases • γsyn=1 _syn=1 Given this formulation, we can learn strategy models in the form of a program (in some DSL) using an RL algorithm. 4.2 Applying Decision Transformers to Programmatic Policy Synthesis Decision transformers were proposed by Chen et al. (2021) as an architecture to apply the sequence-modeling capabilities of transformers (Vaswani et al., 2017) to sequential decision problems. Trajectories τ are represented as: τ=(R^1,s1,a1,R^2,s2,a2,⋯,R^T,sT,aT)τ= ( R_1,s_1,a_1, R_2,s_2,a_2,·s, R_T,s_T,a_T ) (3) where rewards rtr_t are modeled as the returns-to-go R^t=∑t′=tTrt′ R_t= _t =t^Tr_t . States, actions and returns are embedded using separate, fully-connected layers. Additionally, an embedding is learned for each timestep and added to each token. This is different from the standard positional embedding used by transformers, as one timestep corresponds to three tokens. The tokens are then processed by a GPT (Radford et al., 2018) model, which predicts future actions via autoregressive modeling. The original decision transformer architecture cannot handle environments with discrete actions like ℳsynM_syn, and hence we make the following modifications to the architecture: • Action Masking: To ensure that the model does not sample invalid actions, we mask out invalid actions by following the approach described in Huang and Ontañón (2022). Informally, given the unnormalized logits representing action predictions, we mask out invalid actions by setting their logits to −∞-∞ and apply a softmax to obtain a probability distribution. • Cross-entropy loss: The original architecture used a simple L2 loss since actions were continuous. For discrete actions, we use a cross-entropy loss as is usual with classification tasks (Bishop, 2006). • Sampling from action distribution: The original architecture uses a regression layer to predict the continuous-valued action. Since we are dealing with discrete actions, we sample from the predicted action distribution to obtain the action. Additionally, to better represent the sequential nature of states in the MDP, we embed the state using a sequential model, specifically a GRU (Cho et al., 2014). This follows from existing approaches to sentence embedding for information retrieval (Palangi et al., 2016; Kiros et al., 2015; Le and Mikolov, 2014). We empirically find that this improves the model’s performance when compared to embedding the state directly 11 1 The code release for this paper can be found at (blinded for review) .. 4.3 Karel Domain Figure 5: A sample Karel world of size 4×64× 6. The blue diamond represents a marker. The agent cannot travel through walls. Karel is a simple programming language designed for teaching programming to beginners (Pattis, 1994). Programs written in Karel are used to control an agent that can move around a grid world and interact with markers in the world. The agent has actions for moving and interacting with markers, and perceptions for detecting obstacles and markers. Trivedi et al. (2021) introduce six different tasks for the Karel domain with different goals and reward structures. The initial configuration for these tasks are randomly sampled for each episode reset. They also introduce a DSL to represent programmatic strategies for solving these tasks (see Figure 4.3). ⟨ ⟩ <program> ::= ‘DEF’ ‘run’ ‘m(’ ⟨ ⟩ ‘m)’ <stmt> ::= ‘REPEAT’ <cste> ‘r(’ <stmt> ‘r)’ | <stmt> <stmt> | <action> | ‘IF’ ‘c(’ <cond> ‘c)’ ‘i(’<stmt> ‘i)’ | ‘IFELSE’ ‘c(’ <cond> ‘c)’ ‘i(’ <stmt> ‘i)’ ‘e(’ <stmt> ‘e)’ | ‘WHILE’ ‘c(’ <cond> ‘c)’ ‘w(’ <stmt> ‘w)’ <cond> ::= ‘not’ ‘c(’ <cond_without_not> ‘c)’ | <cond_without_not> <cond_without_not> ::= ‘frontIsClear’ | ‘leftIsClear’ | ‘rightIsClear’ | ‘markersPresent’ | ‘noMarkersPresent’ <action> ::= ‘move’ | ‘turnLeft’ | ‘turnRight’ | ‘putMarker’ | ‘pickMarker’ <cste> ::= ‘R=’<int> 4.4 Evaluation To investigate if the decision transformer can perform well on the programmatic policy synthesis task, we evaluate it using the Karel environment and tasks. We train the decision transformer using a dataset of 50,000 programs contributed by Trivedi et al. (2021). We use the same hyperparameters and training procedure as in Chen et al. (2021). A learned strategy’s reward is measured as its average return over 10 random initial states. We compare the performance of strategies learned using the decision transformer with those learned by using LEAPS Trivedi et al. (2021). We also compare the number of candidate programs searched by each method. From the results in Table -results, we see that the decision transformer is competitive with LEAPS in terms of performance, while being more sample efficient. Table 1: Mean return ([0,1.1][0,1.1]) of the best program found and number of unique programs explored by LEAPS and the Decision Transformer model on each Karel task. The standard deviation is reported in parentheses. Task Mean Return Unique Programs LEAPS DT LEAPS DT cleanHouse 0.16 (0.13) 0.23 3627 59 fourCorners 0.35 (0.00) 0.35 9872 55 harvester 0.61 (0.21) 0.66 11708 28 randomMaze 0.97 (0.04) 1.0 295 63 stairClimber 0.74 (0.49) 1.1 298 49 topOff 0.80 (0.11) 0.66 30278 63 5 Related Work Neural program synthesis Program synthesis is the task of automatically finding a program in the underlying programming language that satisfies the user intent expressed in some form of specification (Gulwani et al., 2017). Examples of specifications include formal rules (Manna and Waldinger, 1980), input/output pairs (Neelakantan et al., 2016; Devlin et al., 2017; Gaunt et al., 2017; Shin et al., 2018; Bunel et al., 2018; Lázaro-Gredilla et al., 2019; Chen et al., 2019; Yang et al., 2021), demonstrations (Sun et al., 2018; Xu et al., 2018; Burke et al., 2019), natural language instructions/prompts (Liang et al., 2023) and MDP rewards (Li et al., 2020; Trivedi et al., 2021; Qiu and Zhu, 2022). Neural program synthesis focuses specifically on applying statistical learning methods based on neural networks to the problem of program synthesis. We attempt to synthesize programs from MDP rewards using a transformer-based approach to the task. This is motivated by the empirical success of the transformer model on sequence learning tasks. Learning programmatic policies A reinforcement learning policy’s interpretability refers to the ability of a human to understand, generate explanations for and predict the policy’s behavior (Puiutta and Veith, 2020). A result-based approach towards learning interpretable policies is by learning a surrogate model that approximates the original model with a simpler, ante-hoc explainable one (Speith, 2022). A line of work focuses on learning surrogate models in the form of programs (in some programming language) (Orfanos and Lelis, 2023; Qiu and Zhu, 2022; Trivedi et al., 2021; Inala et al., 2020; Verma et al., 2018; Verma et al., 2019). A related line of work focuses on learning programmatic policies for game-based MDPs (Mariño et al., 2021; Mariño and Toledo, 2022; Medeiros et al., 2022). This work investigates the use of a transformer-based architecture to the same task. 6 Conclusion and Future Work We presented the problem of strategy synthesis and explored its connections to mental model matching, model interpretability and program synthesis. We introduced two novel approaches towards strategy synthesis – a) a rule-based strategy model for chess based on chess tactics, and an associated learning method, which we showed could learn strategies that better approximated a beginner than a random baseline, and b) a transformer-based learning method for programmatic strategies that was competitive with a state-of-the-art programmatic policy learning method while being more sample-efficient. In future work, we plan to benchmark the decision transformer, and other programmatic policy learning methods, on a wider range of game-based environments. We also plan to investigate the interpretability of the learned strategies, and to measure the extent to which they are able to measurably improve a player’s performance. References Berliner (1975) H. J. Berliner A representation and some mechanisms for a problem solving chess program. Technical report Carnegie-Mellon Univ Pittsburgh PA Dept of Computer Science. Cited by: item 2. Bishop (2006) C. M. Bishop Pattern recognition and machine learning (information science and statistics). Springer-Verlag, Berlin, Heidelberg. External Links: ISBN 0387310738 Cited by: 2nd item. Boyan et al. (2018) A. Boyan, R. McGloin, and J. A. Wasserman Model matching theory: a framework for examining the alignment between game mechanics and mental models. Media and Communication 6 (2), p. 126–136. External Links: ISSN 2183-2439, Document Cited by: §1, §2. Boyan and Sherry (2011) A. Boyan and J. L. Sherry The challenge in creating games for education: aligning mental models with game models. Child Development Perspectives 5 (2), p. 82–87 (en). External Links: ISSN 1750-8606, Document Cited by: §1. Bramer (1977) M. A. Bramer Representation of knowledge for chess endgames towards a self-improving system. Ph.D. Thesis, Open University (United Kingdom). Cited by: item 2. Bratko (1982) I. Bratko Knowledge-based problem-solving in al3. Machine intelligence 10, p. 73–100. Cited by: item 2. Bunel et al. (2018) R. Bunel, M. Hausknecht, J. Devlin, R. Singh, and P. Kohli Leveraging grammar and reinforcement learning for neural program synthesis. In International Conference on Learning Representations, External Links: Link Cited by: §5. Burke et al. (2019) M. Burke, S. V. Penkov, and S. Ramamoorthy From explanation to synthesis: compositional program induction for learning from demonstration. In Robotics: Science and Systems XV, External Links: Document, Link Cited by: §5. Butler et al. (2017) E. Butler, E. Torlak, and Z. Popović Synthesizing interpretable strategies for solving puzzle games. In Proceedings of the 12th International Conference on the Foundations of Digital Games, FDG ’17, New York, NY, USA. External Links: ISBN 9781450353199, Link, Document Cited by: §1. Canaan et al. (2018) R. Canaan, H. Shen, R. Torrado, J. Togelius, A. Nealen, and S. Menzel Evolving agents for the hanabi 2018 cig competition. In 2018 IEEE Conference on Computational Intelligence and Games (CIG), Vol. , p. 1–8. External Links: Document Cited by: §1. Chen et al. (2021) L. Chen, K. Lu, A. Rajeswaran, K. Lee, A. Grover, M. Laskin, P. Abbeel, A. Srinivas, and I. Mordatch Decision Transformer: Reinforcement Learning via Sequence Modeling. In Advances in Neural Information Processing Systems, Vol. 34, p. 15084–15097. External Links: Link Cited by: §4.2, §4.4. Chen et al. (2019) X. Chen, C. Liu, and D. Song Execution-guided neural program synthesis. In International Conference on Learning Representations, External Links: Link Cited by: §5. Cho et al. (2014) K. Cho, B. van Merriënboer, C. Gulcehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio Learning phrase representations using RNN encoder–decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), A. Moschitti, B. Pang, and W. Daelemans (Eds.), Doha, Qatar, p. 1724–1734. External Links: Link, Document Cited by: §4.2. Cropper and Dumančić (2022) A. Cropper and S. Dumančić Inductive logic programming at 30: a new introduction. Journal of Artificial Intelligence Research 74, p. 765–850 (en). External Links: ISSN 1076-9757, Document Cited by: §3.2. Cropper and Morel (2021) A. Cropper and R. Morel Learning programs by learning from failures. Machine Learning 110 (4), p. 801–856. Cited by: §3.2. de Freitas et al. (2018) J. M. de Freitas, F. R. de Souza, and H. S. Bernardino Evolving controllers for mario ai using grammar-based genetic programming. In 2018 IEEE Congress on Evolutionary Computation (CEC), Vol. , p. 1–8. External Links: Document Cited by: §1. Devlin et al. (2017) J. Devlin, J. Uesato, S. Bhupatiraju, R. Singh, A. Mohamed, and P. Kohli RobustFill: neural program learning under noisy I/O. In Proceedings of the 34th International Conference on Machine Learning, D. Precup and Y. W. Teh (Eds.), Proceedings of Machine Learning Research, Vol. 70, p. 990–998. External Links: Link Cited by: §5. Gaunt et al. (2017) A. L. Gaunt, M. Brockschmidt, N. Kushman, and D. Tarlow Differentiable programs with neural libraries. In Proceedings of the 34th International Conference on Machine Learning, D. Precup and Y. W. Teh (Eds.), Proceedings of Machine Learning Research, Vol. 70, p. 1213–1222. External Links: Link Cited by: §5. Gobet and Jansen (2006) F. Gobet and P. J. Jansen Training in chess: a scientific approach. Education and chess. Cited by: item 1. Gulwani et al. (2017) S. Gulwani, O. Polozov, and R. Singh Program synthesis. Foundations and Trends® in Programming Languages 4 (1–2), p. 1–119. External Links: ISSN 2325-1107, Document Cited by: §5. Huang and Ontañón (2022) S. Huang and S. Ontañón A Closer Look at Invalid Action Masking in Policy Gradient Algorithms. The International FLAIRS Conference Proceedings 35 (en). Note: arXiv:2006.14171 [cs, stat] External Links: ISSN 2334-0762, Link, Document Cited by: 1st item. Huberman (1968) B. J. Huberman A program to play chess end games. Ph.D. Thesis, Department of Computer Science, Stanford University.. Cited by: item 2. Inala et al. (2020) J. P. Inala, O. Bastani, Z. Tavares, and A. Solar-Lezama Synthesizing programmatic policies that inductively generalize. In International Conference on Learning Representations, External Links: Link Cited by: §5. Kiros et al. (2015) R. Kiros, Y. Zhu, R. R. Salakhutdinov, R. Zemel, R. Urtasun, A. Torralba, and S. Fidler Skip-thought vectors. In Advances in Neural Information Processing Systems, Vol. 28. External Links: Link Cited by: §4.2. Lage et al. (2019) I. Lage, E. Chen, J. He, M. Narayanan, B. Kim, S. J. Gershman, and F. Doshi-Velez Human evaluation of models built for interpretability. Proceedings of the AAAI Conference on Human Computation and Crowdsourcing 7 (1), p. 59–67. External Links: Link, Document Cited by: §2. Lázaro-Gredilla et al. (2019) M. Lázaro-Gredilla, D. Lin, J. S. Guntupalli, and D. George Beyond imitation: zero-shot task transfer on robots by learning concepts as cognitive programs. Science Robotics 4 (26), p. eaav3150. External Links: Document Cited by: §5. Le and Mikolov (2014) Q. Le and T. Mikolov Distributed representations of sentences and documents. In Proceedings of the 31st International Conference on Machine Learning, p. 1188–1196 (en). External Links: ISSN 1938-7228, Link Cited by: §4.2. Li et al. (2020) Y. Li, F. Gimeno, P. Kohli, and O. Vinyals Strong generalization and efficiency in neural programs. External Links: 2007.03629 Cited by: §5. Liang et al. (2023) J. Liang, W. Huang, F. Xia, P. Xu, K. Hausman, B. Ichter, P. Florence, and A. Zeng Code as policies: language model programs for embodied control. In 2023 IEEE International Conference on Robotics and Automation (ICRA), p. 9493–9500. External Links: Document Cited by: §5. Manna and Waldinger (1980) Z. Manna and R. Waldinger A deductive approach to program synthesis. ACM Trans. Program. Lang. Syst. 2 (1), p. 90–121. External Links: ISSN 0164-0925, Document Cited by: §5. Mariño et al. (2021) J. R. H. Mariño, R. O. Moraes, T. C. Oliveira, C. Toledo, and L. H. S. Lelis Programmatic strategies for real-time strategy games. Proceedings of the AAAI Conference on Artificial Intelligence 35 (1), p. 381–389. External Links: Link, Document Cited by: §1, §5. Mariño and Toledo (2022) J. R. Mariño and C. F. Toledo Evolving interpretable strategies for zero-sum games. Applied Soft Computing 122, p. 108860. Cited by: §1, §5. Martinez-Garza and Clark (2017) M. M. Martinez-Garza and D. B. Clark Two systems, two stances: a novel theoretical framework for model-based learning in digital games. In Instructional Techniques to Facilitate Learning and Motivation of Serious Games, P. Wouters and H. van Oostendorp (Eds.), p. 37–58 (en). External Links: ISBN 978-3-319-39298-1, Link, Document Cited by: §2. McIlroy-Young et al. (2020) R. McIlroy-Young, S. Sen, J. Kleinberg, and A. Anderson Aligning superhuman ai with human behavior: chess as a model system. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’20, New York, NY, USA, p. 1677–1687. External Links: ISBN 9781450379984, Link, Document Cited by: §3.3. Medeiros et al. (2022) L. C. Medeiros, D. S. Aleixo, and L. H. S. Lelis What can we learn even from the weakest? learning sketches for programmatic strategies. (arXiv:2203.11912) (en). Note: arXiv:2203.11912 [cs] External Links: Link Cited by: §1, §5. Neelakantan et al. (2016) A. Neelakantan, Q. V. Le, and I. Sutskever Neural programmer: inducing latent programs with gradient descent. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, Y. Bengio and Y. LeCun (Eds.), External Links: Link Cited by: §5. Orfanos and Lelis (2023) S. Orfanos and L. H. S. Lelis Synthesizing programmatic policies with actor-critic algorithms and relu networks. External Links: 2308.02729 Cited by: §5. Palangi et al. (2016) H. Palangi, L. Deng, Y. Shen, J. Gao, X. He, J. Chen, X. Song, and R. Ward Deep sentence embedding using long short-term memory networks: analysis and application to information retrieval. IEEE/ACM Transactions on Audio, Speech, and Language Processing 24 (4), p. 694–707. External Links: ISSN 2329-9304, Document Cited by: §4.2. Paredes-Olay et al. (2002) C. Paredes-Olay, M. J. F. Abad, M. Gámez, and J. M. Rosas Transfer of control between causal predictive judgments and instrumental responding. Animal Learning & Behavior 30 (3), p. 239–248 (en). External Links: ISSN 1532-5830, Document Cited by: §1. Pattis (1994) R. E. Pattis Karel the robot: a gentle introduction to the art of programming. John Wiley & Sons. Cited by: §4.3. Pitrat (1977) J. Pitrat A chess combination program which uses plans. Artificial Intelligence 8 (3), p. 275–321. Cited by: item 2. Puiutta and Veith (2020) E. Puiutta and E. M. Veith Explainable reinforcement learning: a survey. In International Cross-Domain Conference for Machine Learning and Knowledge Extraction, p. 77–95. Cited by: §2, §5. Qiu and Zhu (2022) W. Qiu and H. Zhu Programmatic reinforcement learning without oracles. In International Conference on Learning Representations, External Links: Link Cited by: §5, §5. Radford et al. (2018) A. Radford, K. Narasimhan, T. Salimans, and I. Sutskever Improving language understanding by generative pre-training. External Links: Link Cited by: §4.2. Romstad et al. (2021) T. Romstad, M. Costalba, and J. Kiiski Stockfish 14. External Links: Link Cited by: §3.3. Rouse et al. (1992) W.B. Rouse, J.A. Cannon-Bowers, and E. Salas The role of mental models in team performance in complex systems. IEEE Transactions on Systems, Man, and Cybernetics 22 (6), p. 1296–1308. External Links: Document Cited by: §1. Shin et al. (2018) E. C. Shin, I. Polosukhin, and D. Song Improving neural program synthesis with inferred execution traces. In Advances in Neural Information Processing Systems, S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (Eds.), Vol. 31. External Links: Link Cited by: §5. Sipser (1996) M. Sipser Introduction to the theory of computation. 1st edition, International Thomson Publishing. External Links: ISBN 053494728X Cited by: §4.1. Speith (2022) T. Speith A review of taxonomies of explainable artificial intelligence (xai) methods. In Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency, FAccT ’22, New York, NY, USA, p. 2239–2250. External Links: ISBN 978-1-4503-9352-2, Link, Document Cited by: §5. Sun et al. (2018) S. Sun, H. Noh, S. Somasundaram, and J. Lim Neural program synthesis from diverse demonstration videos. In Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 4790–4799. External Links: Link Cited by: §5. Sutton and Barto (2018) R. S. Sutton and A. G. Barto Reinforcement learning: an introduction. MIT press. Cited by: §2. Szabo (1984) A. Szabo Computer chess tactics and strategy. Ph.D. Thesis, University of British Columbia. External Links: Link, Document Cited by: item 1. Trivedi et al. (2021) D. Trivedi, J. Zhang, S. Sun, and J. J. Lim Learning to Synthesize Programs as Interpretable and Generalizable Policies. In Advances in Neural Information Processing Systems, Vol. 34, p. 25146–25163. External Links: Link Cited by: §4.3, §4.4, §5, §5. Vaswani et al. (2017) A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin Attention is all you need. In Advances in Neural Information Processing Systems, I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (Eds.), Vol. 30. External Links: Link Cited by: §1, §4.2. Verma et al. (2019) A. Verma, H. Le, Y. Yue, and S. Chaudhuri Imitation-Projected Programmatic Reinforcement Learning. In Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. d. Alché-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32. External Links: Link Cited by: §5. Verma et al. (2018) A. Verma, V. Murali, R. Singh, P. Kohli, and S. Chaudhuri Programmatically interpretable reinforcement learning. In Proceedings of the 35th International Conference on Machine Learning, J. Dy and A. Krause (Eds.), Proceedings of Machine Learning Research, Vol. 80, p. 5045–5054. External Links: Link Cited by: §5. Wielemaker (2003) J. Wielemaker An overview of the swi-prolog programming environment.. p. 1–16. Cited by: §3.1. Wilkins (1979) D. E. Wilkins Using patterns and plans to solve problems and control search. Stanford University. Cited by: item 2. Xu et al. (2018) D. Xu, S. Nair, Y. Zhu, J. Gao, A. Garg, L. Fei-Fei, and S. Savarese Neural task programming: learning to generalize across hierarchical tasks. In 2018 IEEE International Conference on Robotics and Automation (ICRA), Vol. , p. 3795–3802. External Links: Document Cited by: §5. Yang et al. (2021) Y. D. Yang, J. P. Inala, O. Bastani, Y. Pu, A. Solar-Lezama, and M. Rinard Program Synthesis Guided Reinforcement Learning for Partially Observed Environments. arXiv (en). Note: arXiv:2102.11137 [cs] External Links: Link Cited by: §5. Zhang et al. (2021) Y. Zhang, P. Tiňo, A. Leonardis, and K. Tang A survey on neural network interpretability. IEEE Transactions on Emerging Topics in Computational Intelligence 5 (5), p. 726–742. External Links: ISSN 2471-285X, Document Cited by: item 3. Figure 6: The domain-specific language (DSL) for constructing programs in the Karel environment.