Towards the Automatic Synthesis of Interpretable Chess Tactics

AI summary

Overview

Research area: Explainable reinforcement learning and symbolic machine learning, applied to chess — specifically inductive logic programming (ILP), chess tactic representation, and interpretability of game-playing agents.

Technical level: Intermediate. The motivation and evaluation are accessible to a general AI audience, but full engagement with the method requires some familiarity with first-order logic / Horn clauses, ILP, and chess engine evaluation.

Scope: The paper is explicitly labelled preliminary work and proposes a symbolic sub-policy model of chess tactics derived from patterns learned by the PAL ILP system, together with coverage and divergence metrics for evaluating those tactics, an empirical comparison against a random baseline using Stockfish 14 and Maia Chess, and a proposed (not yet run) engine-augmentation experiment.

What This Paper Is About

State-of-the-art reinforcement learning agents beat human experts at chess and other games using better strategies, not just faster calculation, but their decision-making is opaque. The authors' goal is to learn a human-readable representation of chess play in the form of first-order logic rules modelling chess tactics, so that players could gain insight into better play. They adapt patterns learned by the PAL system, define metrics to measure whether those tactics suggest reasonable moves, and test them against strong and weak reference engines.

Key Contributions

1. A symbolic sub-policy model for chess in which a tactic is a first-order logic rule that binds to a position and suggests one or more legal moves, built by adapting patterns learned by the ILP system PAL.
2. A divergence metric based on discounted cumulative gain (DCG) that measures how closely a tactic's ranked move suggestions match the best moves of a reference chess engine, extending a metric previously used to analyse world chess champions.
3. An empirical evaluation of seven synthesized tactics (can_threat, can_check, can_fork, discovered_check, discovered_threat, skewer, pin) over 325,830 positions, measured by coverage and divergence against Stockfish 14, Maia-1100, and a random baseline.
4. A proposed computational evaluation scheme in which an off-the-shelf engine (Maia Chess, maia1, targeted toward 1100 ELO) is augmented with the synthesized tactics and its win rate is compared against its unmodified self.

Main Findings

• Tactics vary widely in generality. Coverage ranged from approximately 0 for discovered_check to 0.96 for can_threat and discovered_threat. The authors conclude from the high coverage values that can_threat and discovered_threat are too general, while discovered_check is too specific, and that can_check (0.45), can_fork (0.32) and skewer (0.22) strike a balance between these extremes.

• Most tactics are closer to a weak engine than random is. Against Maia-1100, divergence was 1.19 for discovered_threat, 4.02 for can_check, 4.67 for can_fork, 4.9 for pin and 5.41 for skewer, versus 8.28 for the random baseline. Two tactics were worse than random on this measure: can_threat at 9.22 and discovered_check at 18.64.

• No tactic resembles a strong engine. Against Stockfish 14, every tactic had a higher divergence than the random baseline (328.09): can_threat 378.94, discovered_threat 375.97, discovered_check 338.55, pin 526.45, can_check 549.19, can_fork 676.45 and skewer 748.4.

• The tactics qualitatively resemble a beginner. On the basis of the Maia-1100 and Stockfish 14 divergence patterns, the authors conclude that their tactics resemble those of a beginner chess player. They note the moves are evaluated somewhat similarly to a weak engine's best moves but not to a strong engine's.

• Sub-policies are incomplete by construction. A tactic or set of tactics does not represent a complete chess policy: some positions match no tactic, and positions matching multiple tactics require an arbitration process that the authors describe as not obvious.

• 1-ply limitation. All patterns except pin are 1-ply dynamic patterns containing a single make_move predicate; pin was static as learned by PAL and was converted into a dynamic pattern. The authors illustrate the limitation with a position where White has no immediate forking move, but the sequence 1. Nxb4, ... Rxc7, 2. Nd5+ produces a fork.

Methodology in Plain English

The authors treat a chess tactic as a rule written in first-order logic. A rule has a head describing a concept (for example, "this piece can check the opponent's king") and a body listing conditions that must hold on the board. If a rule matches — that is, if its variables can be bound to pieces and squares in the current position — it suggests one or more moves, which must be legal.

To obtain the rules, they start from seven patterns that the PAL (Patterns and Learning) ILP system was shown to learn, and modify each so it also emits a move suggestion. PAL itself frames pattern learning as an ILP problem: given background knowledge, positive examples and negative examples, induce a hypothesis that entails all positives and no negatives. PAL learns patterns using a heuristically constrained relative least general generalization (rlgg) algorithm and an automatic example generator that perturbs an example and asks for a classification label.

To judge whether a tactic is useful, they define two metrics:

• Coverage — the fraction of positions in an evaluation set that the tactic matches.
• Divergence — for each matched position, a move's error is the absolute difference between the engine's evaluation of its own best move and the engine's evaluation of the tactic's suggested move; positions evaluated as "Mate in X" rather than centipawns are given an arbitrary large value. Because a tactic may suggest multiple moves, the errors are combined with discounted cumulative gain, dividing each error by log2(1+i) for the i-th ranked suggestion, then averaging over matched positions. A divergence near zero means the suggestions look like the engine's best moves; large values mean they differ substantially.

For experiments, they use Stockfish 14 as the strong reference, chosen as winner of the TCEC 2020 Championship, and Maia Chess's maia1 model targeted toward 1100 ELO as the weak reference, roughly a beginner. Search depth is limited to 1-ply for both to resemble the tactics' own one-move lookahead. The random baseline tactic matches every position and returns a random legal move. Suggestions are capped at 3 and their output order is treated as the ranked order. The tactics were manually translated from Prolog into Python. The evaluation set comes from 5,000 games in the January 2013 archive of standard rated games played on lichess.com, generating 325,830 positions by iterating through each game's move list and adding each resulting position.

Finally, they propose an engine-augmentation experiment (Algorithm 1): determine the lowest-divergence tactic applicable to a position, and if one exists, play its first suggestion instead of the engine's own chosen move.

Why This Matters

Impact on research. Most explainable RL work learns policies for optimal control in continuous environments; discrete game environments such as chess have received little attention. This paper shows a route to interpretable chess behaviour via ILP-derived rules and provides a quantitative way (coverage plus DCG-based divergence) to judge whether such rules are meaningful rather than trivially general or specific.

Real-world applications.

• Chess coaching and training tools that explain why a move is suggested, in the vocabulary of tactics that players already learn.
• Game analysis software, where engines are already widely used for analysis and tournament preparation, but usually surface evaluations without explanation.
• Interpretability tooling for reinforcement learning agents in other discrete domains, since the sub-policy framing and divergence metric are not chess-specific in principle.
• Educational settings, where rules expressed in first-order logic are human-readable and can be inspected, unlike a network with thousands of parameters.

Industry relevance. Chess engines are used extensively in game analysis and tournament preparation, and expert players already consume engine suggestions and evaluations. An interpretable layer that speaks in tactics could make that tooling more pedagogically useful. More broadly, the work is relevant to anyone building systems that must explain their decisions in rule-like, auditable terms.

Future Directions

• Automatic tactic learning. PAL requires manual labelling of generated examples and manual effort to convert learned patterns into tactics. The authors aim to learn tactics automatically from a dataset of chess positions and move suggestions using a modern ILP system such as Popper.
• Divergence as an optimization target. They propose investigating alternate ILP algorithms that use their divergence metric as a loss function to optimize tactics.
• Beyond 1-ply: move combinations. The current tactics only look one move ahead. Extending the model to express and recognize combinations — sequences where the matching pattern appears only after several moves — is named as a useful avenue.
• Longer-term strategic plans. They wish to investigate expressing concepts from chess literature such as centre control and pawn structure.
• Validating interpretability claims. The paper's appeal to interpretability rests on similar claims made about rule-based strategies; the authors call for rigorous user studies using evidence-based measures of interpretability, specifically investigating the ease of learning and applying these tactics in real human games.
• The proposed win-rate experiment. Whether an engine augmented with the tactics would have a significantly higher win rate than the unmodified version of itself remains a hypothesis to be tested.

Target Audience

Researchers working on explainable reinforcement learning and symbolic or neuro-symbolic AI; inductive logic programming practitioners interested in applications; and chess engine or game-AI developers interested in interpretable, tactic-level move suggestion. It is also suitable for graduate students looking for a compact example of formulating an interpretability problem as an ILP task with an evaluation metric tied to a domain-specific reference system.

Authors’ abstract

State-of-the-art reinforcement learning agents are capable of outperforming human experts at games like chess, Go and StarCraft II. These agents do not simply take advantage of their digital hardware in being able to react and calculate faster than humans, but employ better strategies that lead to more victories. Interpreting these strategies would give human players valuable insight into how to improve their play. In this preliminary work, we propose a symbolic sub-policy model for playing chess. Inspired by chess tactics, our model attempts to incorporate domain knowledge to improve interpretability. We adapt patterns learned by an inductive logic programming system called PAL to derive our model. We contribute a divergence metric to evaluate our model against a random baseline, and find a set of tactics that is able to suggest moves of similar playing strength to a human beginner. Finally, we propose a computational evaluation scheme for the model by augmenting an off-the-shelf engine with it.