Inductive Learning of Chess Rules Using Progol

Contents and links

Introduction: The Chess Move Generator

Computer chess programs can be thought of as having two parts, a move generator and an algorithm for evaluating the strength of generated moves. The move generator effectively gives the computer information concerning the rules of chess. The datasets given here are part of an MSc project carried out within the laboratory where Progol learned such a move generator.

Structured Induction

The method used to learn the move generator is termed "Structured Induction" and was first used by Shapiro in 1982. Shapiro used structured induction for the KP v K and KP(a7) v KR problems using decision trees .

The structured method used here is slightly larger involving the splitting of the problem into some 40 sub-problems creating a structure some 15 levels deep. With structured induction clauses learned in an earlier part of the process are appended to our background knowledge to enable the learning of subsequent clauses.

In the datasets given here we illustrate the learning of the move generator using trainer selected examples (a subsequent part of the project involved learning from stratified random examples). As much as possible the initial background knowledge was expected to involve only the sort of immediately perceivable patterns (such as pieces, squares, colours, distances and directions) that a non chess player would have at his disposal.

It was also necessary to redefine negation (nott/1) to counter the unfortunate combination of negation and - type mode declarations within Progol (this combination would not be learned due to Progol creating non-ground clauses within its search). The interested reader may also note that certain predicates could only be learned using multiple board positions (such as check, double-check etc.). The Input to the final product is expected to be a legal board position (board/4, given as a series of ground clauses). The output from move/5 would be a list of all legal moves from this board position (with the exception of castling and the en-passant rule which would need some history of the game not included in the board/4 predicate... pawn promotion is also not dealt with).

The data files are held in a compressed archive of Progol source files, containing predicates as described above.


Goodacre J (1996)
Inductive Learning of Chess Rules Using Progol
MSc thesis, Programming Research Group, Oxford
Shapiro Alen D and Niblett (1982)
Automatic Induction of Classification Rules for a Chess Endgame,
In M.R.B. Clarke (Ed.) Advances in Computer Chess 3,
pp73-92 Oxford, Pergamon Press.
Shapiro Alen, D (1987)
Structured Induction in Expert Systems,
Turing Institute Press, Addison-Wesley.

Up to applications main page.

Machine Learning Group Home Page