Abstract
Supervised learning requires large collections of accurately labeled examples. While chess engines and endgame tablebases can provide perfect evaluations, building datasets dedicated to learning a specific chess skill remains a separate challenge.
This paper presents a generic framework for automatically generating exhaustive labeled datasets over a finite state space. The proposed approach is independent of existing tablebases and relies on recursive propagation from an initial set of solved positions.
The underlying idea is inspired by human learning: rather than attempting to learn every aspect of chess simultaneously, a model should progressively acquire individual competencies through specialized datasets.
The framework is illustrated using the King and Rook versus King (KRK) endgame, but its design naturally extends to other endgames and, more generally, to any finite state-space problem satisfying the same assumptions.
Introduction
One of the strengths of human learning is its progressive nature.
A chess coach does not teach every concept simultaneously. Instead, learning is decomposed into elementary competencies such as basic checkmates, tactical motifs, or specific endgames. Each competency is mastered before introducing more complex concepts.
We believe that supervised learning can benefit from the same philosophy.
Rather than training a model on a heterogeneous collection of chess positions, we propose generating exhaustive datasets dedicated to a single competency. Each dataset becomes a complete learning module focused on one particular concept.
Our objective is therefore not to construct another endgame tablebase, but to build a generic framework capable of generating exhaustive labeled datasets for supervised learning.
KRK is chosen as the first case study because it represents one of the simplest complete endgame competencies while still requiring genuine reasoning.
General Framework
The framework is independent of chess.
Let:
- S be the finite set of possible states.
- V ā S be the subset of valid states.
- Pā be an initial predicate identifying solved states.
- R be a recursive propagation rule.
The algorithm consists of four steps:
- Generate all valid states.
- Evaluate the initial predicate.
- Propagate labels recursively.
- Stop when no additional state can be labeled.
The only application-specific components are the initial predicate and the propagation rule.
Consequently, the framework can be reused for many different problems.
KRK as a Case Study
To validate the framework, we consider the KRK endgame.
The first stage generates every legal KRK position.
These positions are stored in an indexed structure allowing constant-time lookup.
This exhaustive collection becomes the reference set used throughout the propagation process.
An important consequence is that legality never needs to be recomputed. Whenever a candidate position is generated, determining whether it is legal simply consists of checking whether it belongs to the reference set.
Initial Label Generation
Recursive propagation requires an initial set of solved positions.
For KRK, these correspond to positions where White can force checkmate in a single move.
Instead of implementing a dedicated mate detector, we reuse the existing chess engine with its search depth limited to one move.
This choice minimizes implementation complexity while relying on already validated software components.
Recursive Label Propagation
Starting from positions labeled Mate in nā1, the algorithm generates candidate predecessor positions.
The winning White move is already known. Only Black's possible replies must therefore be explored.
Each generated position is validated through membership in the precomputed legal position set. No chess legality verification is performed during propagation.
A position is labeled Mate in n when every legal Black reply leads to a position already labeled during a previous iteration.
The process repeats until a fixed point is reached.
Skill-Oriented Dataset Generation
The objective of the framework is not merely to assign labels.
Its purpose is to generate datasets dedicated to learning a specific competency.
In the KRK example, every generated position belongs to the same conceptual domain while being naturally organized according to the number of moves required to force checkmate.
This organization naturally produces datasets of increasing algorithmic complexity.
The key idea is that a supervised model should not learn chess as a monolithic problem. Instead, it should progressively acquire individual competencies through dedicated datasets, similarly to the way human players develop their understanding of the game.
Each competency therefore becomes an independent learning module, whose examples are exhaustive and whose complexity naturally increases as recursive propagation progresses.
Complexity
Unlike repeated independent searches, recursive propagation shares computation among all states.
Each valid position is generated only once and labeled at most once.
The computational cost is mainly determined by:
- predecessor generation,
- membership lookup within the legal position set,
- evaluation of the propagation rule.
The approach therefore trades repeated deep searches for a global propagation process over the finite state space.
Generalization
Although demonstrated on KRK, the framework is intentionally generic.
Any chess competency satisfying the following assumptions can be processed:
- exhaustive generation of valid positions,
- definition of an initial predicate,
- recursive propagation of labels.
Examples include KQK, KRKP, king and pawn endgames, tactical motifs, or any other finite family of chess positions.
More generally, the framework applies to any finite state-space problem where labels can be propagated recursively.
Future Work
KRK represents the first validation step of the proposed methodology.
The next objective is to apply the framework to the King, Bishop and Knight versus King (KBNK) endgame, one of the most challenging elementary pawnless endgames.
Unlike KRK, KBNK requires long-term coordination between three pieces, precise positional planning and accurate move ordering. It therefore provides a significantly more demanding benchmark for evaluating the framework.
Beyond KBNK, the broader objective is to determine whether competency-oriented supervised learning can lead to a reusable methodology. Rather than training a single model on all chess positions, the idea is to construct specialized datasets, each dedicated to one competency and naturally organized according to increasing algorithmic complexity.
If successful, this approach could provide the foundations of a structured curriculum for supervised learning, where progressively acquired competencies are combined to build stronger chess models.
Conclusion
This paper presented a generic framework for generating exhaustive labeled datasets dedicated to supervised learning.
Rather than treating chess as a single monolithic problem, the proposed approach decomposes learning into elementary competencies, each associated with its own exhaustive dataset.
KRK serves as the initial proof of concept, while KBNK will provide a more demanding validation of the methodology.
Ultimately, the objective is not only to generate datasets, but also to establish a reusable methodology for competency-oriented supervised learning based on recursive propagation over finite state spaces.
Comments