\documentstyle[12pt,a4]{article}
\input{epsf}
\begin{document}
\bibliographystyle{plain}

\section*{Learning rules from chess databases}
Early work on propositional learning from logic databases such
as those provided by chess endgames played a key role in highlighting
the easy-inverse trick which was later used in developing systems such as
Kardio \cite{bratko:kardio}. These databases are good sources
of examples for both learning and testing rules.
In fact relatively simple chess problems
have in the past defeated Machine Learning systems which have otherwise
proved rather successful on a range of real-world tasks.
The data here concerns one such simple problem: that of the KRK endgame.
In this, there are three pieces left on the chess board: White
King, White Rook and Black King. The problem of
learning rules for recognising illegal positions when it is white's turn
to move (WTM) was first proposed in \cite{expform:cigol}. This has since
become a widely accepted test-bed for ILP systems.
Examples of a position that is illegal (left) and legal (right)
are shown below
\begin{figure*}[htb]
% \begin{figure}
\noindent
\epsfxsize=\textwidth
% \epsfysize=3.0in
\centerline{\epsfbox{ilpbkfig1.eps}}
\end{figure*}

The position on the left is illegal since BK:e1 is in check with WTM.
ILP systems usually use the following information to learn the concept:
\begin{itemize}
\item Examples are represented by the predicate {\bf illegal/6}. The
	arguments of this predicate stand for the file (column) and rank
	(row) coordinates for the WK, WR and BK. 
\item The background knowledge provided is simply the ordering of rows
	or columns on a chess board. The predicate {\bf lt/2} tabulates
	pairs row or column values where one is less than the other.
	The predicate {\bf adj/2} tabulates row or column values that
	are adjacent.
\end{itemize}

Another, more difficult problem is to do with predicting optimal depth of
win (that is, the number of moves to checkmate). In the data here, the
exhaustive database for the KRK domain acts as a source of example positions,
each of which has associated with it optimal depth of win information.
Here this is represented by the predicate {\bf krk/7}. The arguments for
this predicate stand for depth of win, and the file (column) and rank
(row) coordinates for the WK, WR and BK.
The typical ILP task is to learn the sub-concept
`black-to-move KRK position won optimally for white in $N$ moves''.
Preliminary results of classifiers for ``won in 0 moves'' up to
``won in 5 moves'',  can be found in \cite{bainsrin:krkwin}.
The background knowledge used consisted of ground instances of the predicates
``symmetric difference'' between files and ranks and
``strictly less than'' ($<$) for all unordered pairs of the file values
$\{\mbox{a}, \ldots, \mbox{h}\}$ and all unordered pairs of the rank values
$\{1, \ldots, 8\}$.

The data files are held in compressed TAR format. Within
the TAR file, they are as used in the original {\em Golem\/} \cite{mugfeng:golem}
experiments. That is, background knowledge files have a ``.b'' suffix,
positive example files have a ``.f'' suffix, and negative example files
have a ``.n'' suffix.

\begin{thebibliography}{}

\bibitem{bainsrin:krkwin}
Bain M. and Srinivasan A. (1995).
Inductive Logic Programming With Large-Scale Unstructured Data.
In D. Michie K. Furukawa and S. Muggleton, editors,
{\sl Machine Intelligence 14}. Oxford University Press.

\bibitem{bratko:kardio}
Bratko I., Mozetic I. and Lavrac N. (1989).
{\sl Kardio: a Study in Deep and Qualitative Knowledge for Expert Systems}.
MIT Press, Cambridge Mass.

\bibitem{expform:cigol}
Muggleton S.H., Bain M.E., Hayes-Michie J. and Michie D. (1989).
An experimental comparison of human and machine learning formalisms.
{\sl Proceedings of the Sixth International Workshop on Machine Learning}

\bibitem{mugfeng:golem}
Muggleton S.H. and Feng C. (1990).
Efficient induction of logic programs.
{\sl Proceedings of the First Conference on Algorithmic Learning Theory},
Tokyo.


\end{thebibliography}


\end{document}
