Pattern-based representation of chess end-game

knowledge
I. Bratko*, D. Kopec and D. Michie
Machine Intelligence Research Unit, University of Edinburgh, Hope Park Square, Meadow
Lane, Edinburgh EH8 9NW

Students of computer chess aim at an operational theory of

Master skill—operational in the sense that it can be run on
the machine. In one form of the aspiration Masters must be
defeated across the board under full tournament conditions,
so far achieved only for 'blitz' chess but not for play under
standard time control (see SIGART Newsletter No. 62, 1977).
Another form of the 'Master skill' aspiration aims at correct
play for defined subsets of chess. It is not known whether
'strong mastery' in this sense is attainable for the complete
game or whether chess is 'hard' in the sense of Knuth (1976).
We can, however, start with elementary endings such as King

Downloaded from https://academic.oup.com/comjnl/article/21/2/149/477547 by guest on 03 January 2024

and Queen versus King (denoted KQK), KRK, KBBK,
KBNK and KPK, and seek to extend mastery backwards
a step at a time into the game's increasingly complex hinter-
land.
Work at Edinburgh follows the second approach, seen as a
means for studying forms of knowledge representation in
relation to three desiderata: (a) forms more powerful than
present programming languages for specifying strategies,
(b) forms more suitable for proofs of correctness of strategies
and (c) forms more convenient for automatic optimisation
of strategies ('machine learning').
None of the above listed end-games contains anything prob-
lematical from a Master's point of view and computer programs
embodying correct strategies have been written for all of
them. In reviewing this work Bramer (1977) remarks that the Fig. 1 From Basic Chess Endings (R. Fine)
task, not of playing such end-games correctly, but of expressing
in program form the knowledge required for correct play, file. A backward neighbour is a protector (distance 1)
has turned out to be surprisingly and disproportionately hard. or a potential protector (distance > 1).'
For his own implementations of KRK and KPK Bramer uses
pattern-based models of a general kind now accepted as Some of these relations may be very useful if developed further.
indispensable to the extension of machine mastery into more For example, if a pawn is 'overloaded', in that it is performing
complex chess subdomains. Such exercises as KRK and KPK several roles at once, its removal may lead us to a winning
can be done (with some difficulty) without special programming strategy. An example in practice is shown by the problem
tools; but it needs only a small step in the direction of greater position in Fig. 1 taken from Fine's (1964) Basic Chess
complexity to bring us into territory where the use of such Endings. Its solution becomes clearer when we consider the
tools become critical. number of roles performed by .the pawn on square 33 (square
In this paper we describe pattern descriptional aids to = 9 x file + rank).
strategy building in two areas more complex than KRK, Thus,
KPK, KQK and the rest; namely (a) pawns-only positions and 33 [1, 31], i.e. pawn on 33 is a Counterpawn to pawn on 31,
(b) the defence of king and knight against king and rook.
33 [2, 32], i.e. pawn on 33 is a Ram to pawn on 32,
Describing pawn structures 33 [3, 21], i.e. pawn on 33 is a Sentry to pawn on 21,
Tan (1977) has developed a program which breaks down any 33 [8, 33], i.e. pawn on 33 is a Potential Protector to pawn
K + P ending into a basic description of its components. on 22.
Using a vocabulary which is defined in Kmoch's (1959) Rather than queening the passed RP immediately, which would
Pawn Power, the pawn formations are broken down into result in a quick draw due to stalemate, the solution lies in
Fronts, i.e. islands containing opposing pawns, and further White's capture of that pawn on 33.
subdivided into Groups (same colour only). The role of each A graph representation of the same position is given in the
pawn in terms of its relationships to other pawns is then lower part of Fig. 2, using Tan's notation with the addition of A
defined, as shown in the upper part of Fig. 2 which uses terms to denote a passed pawn.
explained by Tan as follows: Another concept put forward by Tan is the ADD (Attack
'An enemy pawn ahead on the same file is a counterpawn, Defence Diagram, see Fig. 3). Some of the relations proposed
and a sentry when it is on a neighbouring file . . . Counter- for an ADD are as follows: (a) relations within fronts; (b)
pawns and mutual sentries of distance 1 are called rams defences to threats arising from (a); (c) possible attacks of
and levers respectively. Friendly relations give rise to a kings against pawns; (d) defences to (c); (e) support possibili-
duo when the pawns are abreast on two neighbouring ties; (/) joint attacks. Tan also breaks down the relationships
files, and a twin (doublepawn) when they are on the same that go into the ADD into Backus-Naur Form. As yet there is
•Present address: Jozef Stefan Institute, Ljubljana, Yugoslavia.

Volume 21 Number 2 149

 assembles relevant patterns and pieces of advice from which
GRAPHICAL NOTATION to construct his rules (13K).
Counterpawn < >• In addition subdomain specific predicates are normally
HOSTILE RELATIONS Ram < •+. > required for each new Advice Table. The POP-2 system itself
occupies 19K 36 bit words of store.
Sentry < > Modules 1 and 2 are chess independent and can be used for
Lever <• + -> solving other combinatorial problems. The domain specific
knowledge directs the action of module 1 in the following
Duo = way: a rule is invoked by a pattern-match with the current
Twin = situation (chess position) and the corresponding pieces of
FRIENDLY RELATIONS
Potential Protector = advice are then tried one by one until module 1 can find a
Protector =/= 'forcing tree' that guarantees the achievement of better-goals
Passer (our notation) ^ while preserving holding-goals.
Considered as an ultra-high level programming language,
AL1 seems to provide a natural means of describing heuristics
in combinatorial algorithms. In one experiment (Michie,
1976) the King + Rook v. King ending (KRK), regarded by
Zuidema (1974) as a laborious programming task, was ex-
pressed as an Advice Table and a strategy checked out at a
cost of only two man-days. More recently (Bratko, 1978)

Downloaded from https://academic.oup.com/comjnl/article/21/2/149/477547 by guest on 03 January 2024

= Black Pawn the whole mating procedure known from the chess books was
compressed into a Table of only one rule, comprising 5 pieces
(~] =White
Whi Pawn of advice expressible as follows:
76 1. Look for a way to mate opponent's king in two moves.
2. If the above is not possible, then look for a way to further
constrain the area on the chessboard to which the opponent's
Fig. 2 Graphical representation for chess position shown in Fig. 1 king is confined by our rook.
3. If the above is not possible, then look for a way to move our
king closer to opponent's king.
no working program for the ADD. As a step towards imple-
mentation, we have tested how the evaluations would work 4. If none of the above pieces of advice 1, 2, 3, works, then
on some simple K + P endings. It seems that at least three look for a way of maintaining the present achievements
concepts must be added: (a) opposition, (b) triangulation, in the sense of 2 and 3 (i.e. make a waiting move).
(c) outside passed pawns. These features are important and 5. If none of 1, 2, 3, or 4 is attainable then look for a way of
occur frequently. obtaining a position in which our rook divides the two kings
either vertically or horizontally.
AL1 'advice taker' system The 'and-or' tree search, carried out by module 1 of the AL1
In a related use of pattern-based representations of chess system when generating a forcing tree satisfying a corresponding
knowledge we have developed a linguistic vehicle for applying piece of advice, is limited to a depth of 2 ply for pieces 2, 3 and 4,
McCarthy's (1959) 'advice taker' concept. In Advice Language and to 3 ply for pieces 1 and 5. Quality of play was respectable
1 (Michie, 1976) knowledge is conveyed to the system in the by the standards of the chess books, never needing more than
form of one or more advice tables, each specifying a number of 25 moves to force the mate. The worst case minimax-optimal
rules. A rule is applied to a position (in a manner familiar to path length is known to be 16 moves (Clarke, 1977).
commercial users of decision tables, and to academic users of
production systems) if and only if the position matches the
rule's 'condition pattern'. Associated with each rule is a list BG1 = WK NIL
of pieces of advice. Each piece of advice is specified in terms of
Huberman-type (Huberman, 1968) better-goals and holding-
goals, together with move-constraints to control the branching 4
of the search and a depth limit to terminate it when no way
has been found of achieving the given better-goals. WG2
AL1 has been implemented in the POP-2 programming
language as a package consisting of four comparatively WG1
independent modules (core-occupancy of compiled code on
the PDP-10 is shown in parentheses): Key: Threat"
Defence
1. A problem-solver performs tree search in whatever problem
space is specified to it by the legal move generator, using WK White king
the domain specific knowledge contained in the currently WG White group
loaded Advice Tables (2K). BK Black king
BG Black group
2. An Advice Table editor acts as a link between the system NIL Null group
and the user, enabling him to create, extend and modify
Fig. 3 The ADD corresponding to the position shown in Fig. 1. In
the system's Table held knowledge interactively (4K). the form described by Tan (1977) the ADD would not
3. A playing module executes a strategy generated by the indicate the self-stalemate threat which the BK generates
problem-solver in the form of a Huberman-type forcing jointly with BG1. The above diagram is based on an extended
tree (6K). notation which takes care of this. For a fuller account Tan's
paper should be consulted. Integers denote the minimal
4. Chess-relevant but subdomain independent POP-2 predicates number of moves required to carry out a threat
act as the building blocks from which the table writer

150 The Computer Journal

HOW DIFFICULT IS THE KNKR PROBLEM?
"—Chess books: Keres, KNKR, 2 pages.
From chess Fine, KRKN, 8 pages.
player's Longest variation in Fine before capture of the Knight: 24 moves; longest known variation 27 moves.
point of view: —Tournament games: usually a comparatively easy draw, but there are examples where the weaker side went
wrong (e.g. Neumann-Steinitz, 1870).

—Knowledge v. search:
1. Rules of chess: don't get mated! Up to 24 moves before losing knight plus up to 16 moves before
being mated:
« 80 ply
2. Additional advice: don't lose knight!
From chess ~ 48 ply
programmer's <
point of view: 3. Additionally: keep king and knight together!
Necessary, and probably sufficient, lookahead is:
10 ply

Downloaded from https://academic.oup.com/comjnl/article/21/2/149/477547 by guest on 03 January 2024

4. Advice contained in KNKR table.
To preserve draw, and conserve king-centrality:
4 ply

Fig. 4 Salient features of the KNKR end-game. The size of the total problem space, after reduction by disregarding symmetric cases, lies be-
tween 3 x 106 and 4 x 106. The boxedfiguresshow the depth of search necessary, for the program's given state of knowledge, to select
a draw-preserving move. Ply = half move

The KNKR game of king and knight. A correct treatment of such positions
In further experiments with the AL1 system, the king + knight with king and knight separated would require additional
v. king + rook ending (KNKR) was used as an experimental knowledge.
domain that is not trivial from the human expert's point The upper table of Fig. 5 specifies four rules (CR, R l , R2, ER)
of view. Fig. 4 presents some data that illustrate the difficulty by the 'Yes, No, Don't-care' column patterns. These patterns
of this end-game. The first two items, chess books and tourna- refer to POP-2 predicates flanking the table:
ment games, give some insight into the difficulty from the OKEDGE —our king on the edge;
chessplayer's point of view. The difficulty from the pro-
grammer's point of view is illustrated by the third item which OKONSEP —our king and our knight separated (distance
indicates the relationship between the amount of knowledge greater than 4 in king moves);
possessed by the program and the depth of game-tree search CORNCASE—corner case, a special 'classical' situation
required for correct play. (e.g. Fine, 1964) with the king in the corner,
The KNKR ending is usually drawn, but under certain requiring exceptional treatment.
circumstances the stronger side (the one with the rook) can The current chess position is matched against the rule patterns
win. A winning procedure, when there is one, consists usually from left to right. As soon as a match is found the correspond-
of combining three basic principles (Fine, 1964): ing rule is applied. For example, if the position does not
1. Create mating threats. satisfy the CORNCASE condition and the king is on the edge
and the king and knight are not separated, then rule R2 matches
2. Force separation of king and knight. the position and the list of pieces of advice 1, 5, 6, 7, 8, 12 is
3. Stalemate and capture the knight. applied. The pieces of advice are defined by the lower table
The KNKR advice table must cope with the above threats in Fig. 5. Consider for example Advice no. 1 called
and thus preserve a draw for the weaker side when starting KiLLROOK. The better-goal to be satisfied in them-to-move
from a theoretically drawn position (in all such, the king and positions specified with this piece of advice is TRDEAD
knight are not separated). The table, shown in Fig. 5, contains (their rook dead). As already stated, depth of search is limited
enough knowledge (according to experimental tests) both to to 4 ply, and to improve search efficiency we also specify
preserve the draw in positions with king and knight sufficiently holding-goals NOT ONLOST (not our knight lost without
close together and to maintain the degree of centrality of the compensation) and TRDEAD OR CHECK (their rook dead
weaker side's king while searching to a depth of at most 4 ply or their king in check). By this the search is limited to con-
(half-moves). Centralisation of the king is important to the sideration of immediate captures and checking-moves, which
weaker side because mating threats can occur only when the amounts to looking for ways of forking their king and rook.
king is on the edge. Therefore when the king is on the edge This tactic is indicated by the fact that there is no other way
the defence becomes considerably more difficult. The KNKR to force capture of the rook.
table thus actually conserves the degree of easiness of defence. When testing the correctness of the table a variety of players,
When the king is started on the edge and not separated from two of National Master strength (rated over 2300 on the
the knight, for those positions which are theoretically drawn, international scale), have engaged the system in play for a total
the table preserves the draw in all cases tested. Recently elapsed time of more than 10 hours (150 moves on each side,
a class of specially tricky positions has been discovered by starting from different positions). No absolute way exists of
D. Kopec, not previously known in chess literature, where the proving correctness for all possible positions short of either
only correct defence requires a counter-intuitive separation (a) exhaustive checking through the total space of 3-4 million

Volume 21 Number 2 151

 rules
KNKR Table CR Rl R2 ER
condition OKEDGE — N Y
predicates OKONSEP — N N
CORNCASE Y —
' 9 1 1 10
2 5 11
lists of 3 6 12
pieces of •< 4 7
advice 11 8
11
12
Better- Holding-goals
goals
us-to-move them-to-move

Downloaded from https://academic.oup.com/comjnl/article/21/2/149/477547 by guest on 03 January 2024

<J
w
X
H w
s
00 oo
O a, w
O w
O O H
o gO

3SCL
OND
O

DND

NDL

NDL
Q i-l

EAD
\FE2
Z
Z
Q
1 Z Q Q

s Q
g
o
H
O
00

zO
Q
a;
H
O
P-I
^4
O
U
&4
O
O
^4
O
6
O
O
zo
H
z
s
o z z z o
1: KILLROOK — Y (Y) Y Y
2: HOLD1 (Y) Y Y — Y Y Y Y Y (Y) Y
3: HOLD2 (Y) Y Y — Y Y — Y Y (Y) —
4: HOLD3 Y Y Y — Y — Y Y Y 00 —
5: HOLDEDG1 Y Y Y — Y — Y Y — (Y) —
6: HOLDEDG2 Y Y Y — — — Y — — Y —
o
f1 7: HOLDEDG3 Y Y Y — — — — Y — (Y) —
8: HOLDEDG4 Y Y Y — — — — — — Y —
9: CORNCASE 00 (Y) (Y) — — — — — — — —
10: APPROKON Y — Y Y Y — — — — — — — —
11: SURVIVE 1 Y Y Y
12: SURVIVE2 — — Y —
Fig. 5 The upper table is the KNKR Advice Table as written and tested. The integer lists index a repertoire of 12 pieces of advice. These are
shown in the lower table expanded in the form of calls to indicated subsets of the 14 goal predicates listed along the top. 'Y's enclosed in
brackets are logically implied by the other predicates selected in the same row. The symbols in parentheses (utm) and (ttm) mean 'us-to-
move' and 'them-to-move' respectively

positions or (b) formal proof. ALl's tabular format offers forward search. As an annotation on this last remark, we
simplifications which make the latter an attractive topic for append results, kindly supplied by D. Slate, of having the
study. leading US tournament program CHESS 4.5 play the KNKR
When playing the KNKR ending on the PDP-10 computer the game against an expert opponent from selected starting
present implementation of AL1 spends on average about one positions.
minute of computer time per move, mostly due to the com-
parative inefficiency of the forcing-tree generating routine. Performance of CHESS 4.5 tournament program with KNKR
The program examines about 10 nodes in the game-tree per Tournament programs have the aim of playing reasonably
second. When run on comparable machines, other chess- well, but not of course with guaranteed correctness, in all
playing programs, e.g. CHESS 4.5 (Slate and Atkin, 1977) phases of the game: opening, mid-game, and ending. Such
or MASTER (Birmingham and Kent, 1977) examine at least 'general' chess programs cannot pay much attention to specific
a few hundred positions per second. A new version, AL2, features of different position-types. Rather these programs
is under construction with an eye to increased run-time effici- embody generalised chess principles, or heuristics, hopefully
ency, among other improvements. But considering ALl's applicable to the large majority of possible positions. Lack of
efficiency from the point of view of programmer productivity, position-type specific knowledge is to some extent balanced
these experiments gave evidence of great savings. Table writing by deep lookahead, facilitated by fast game-tree search routines,
and check-out for KNKR occupied one of us (I.B.) for less efficient tree-pruning, efficient coding, and fast hardware.
than six weeks. We doubt whether correct play, especially if CHESS 4.5 was required to defend the weaker side of KNKR
'centrality preservation' is to be included, could be program- against a human opponent rated just over 2000 on the US
med using standard methods in less than a substantial multiple Chess Federation scale, i.e. an 'expert'. The program ran on a
of this figure other than by promoting large proliferations of CDC 6400 machine, on which it was able to win the 1976

The Computer Journal

ACM Computer Chess Championship (more recently it has lack of specific advice: 'Keep king and knight together!' and
had highly successful trials on the much faster Cyber 176). 'Preserve the centrality of the king!' could not be entirely
CHESS 4.5's general evaluation function was used without compensated by the efficient and comparatively deep search
allowing any adjustment or special 'tuning' to the KNKR to 7 or 8 ply.
problem. Search depth was set to 7 ply. Since forced variations
are searched beyond this pre-set horizon, moves 8 ply deep
were occasionally searched in the present case. Under these Discussion
conditions, CHESS 4.5 typically looked at a few tens of thou- It was pointed out by Shannon (1950) on general grounds, and
sands of nodes per move and spent up to 120 seconds per move, more recently by Berliner (1974) on the basis of authoritative
typically between 30 and 60 seconds. new theoretical and experimental work, that fast tree-search
and uniform heuristics will not suffice for mechanising the
Three trials were made, using test positions taken from those
highest levels of chess skill. In spite of impressive recent
used in the experimental validation of the KNKR table earlier
progress up the human tournament scale by 'brute force'
described.
programs the knowledge-gap from which these programs suffer
1. A 'classical' difficult defence (Fine, 1964; Keres, 1974) with still bars them from the higher reaches. The work here reported
the weaker side's king in the corner. CHESS 4.5 found shows that the weaknesses inherent in the brute force style can
correctly the move considered most difficult in the books, be shown up even by quite a simple chess subdomain. The
but then stumbled on the fourth move of the main 'book' same subdomain, however, yielded readily to a more
variation, obtaining a lost position. knowledge-oriented approach, for which the AL1 system
2. Another difficult position, with the weaker side's king on the provided highly effective support.

Downloaded from https://academic.oup.com/comjnl/article/21/2/149/477547 by guest on 03 January 2024

edge (Keres, 1974). CHESS 4.5 found the only correct The underlying formal model of the AL1 problem-solver
defence against the main line given by Keres (i.e. 8 best closely matches the basic structure of a range of combina-
moves in a row). torial problems. Our experience supports the idea that the
3. A further position taken from our own tests, with the weaker Advice Language methodology should be applicable to prob-
side's king in the centre (easiest defence). CHESS 4.5 lems in such areas as algebraic manipulation, symbolic
allowed its king to be driven to the edge resulting in a harder integration, robot plan-formation, and a variety of optimisa-
defence. This enabled the opponent to create mating threats, tion and scheduling tasks. While detailed accounts appear
and after additional weaker moves by the program the elsewhere (Bratko, 1978; Bratko and Michie, 1978), this brief
king and knight got separated, leading to a lost position. overview was prepared in the hope of arousing interest among
those actively engaged in one or another of such areas.
It is interesting to observe that the program's opponent,
although an expert, after achieving theoretically won positions
never grasped the opportunity actually to defeat the program. Acknowledgement
This has a bearing on the level of difficulty of this subdomain. Thanks are due to the Research Community of Slovenia, to the
Conclusion: thanks to efficient tree-search, CHESS 4.5 was British Council and" to the University of Edinburgh for support
able to find a correct move in many difficult positions. But the and facilities.

References
BERLINER, H. (1974). Chess as problem solving: the development of a tactics analyser, Ph.D. Thesis. Pittsburgh: Carnegie-Mellon University.
BIRMINGHAM, J. A. and KENT, P. (1977). Tree-searching and tree-pruning techniques, Advances in Computer Chess 1 (ed. M. R. B. Clarke),
pp. 89-107, Edinburgh: Edinburgh University Press.
BRAMER, M. A. (1977). Representation of knowledge for chess endgames: towards a self-improving system, Ph.D. Thesis, Milton Keynes:
The Open University.
BRATKO, I. (1978). Proving properties of strategies expressed in the AL1 assertional language, (Inf. Proc. Letters, forthcoming.)
BRATKO, I. MICHIE, D. et. al. (1978). A representation for pattern-knowledge in chess end-games, Advances in Computer Chess 2, (ed. M. R.
B., Clarke, forthcoming).
CLARKE, M. R. B. (1977). A quantitative study of king and pawn against king, Advances in Computer Chess J (ed. M. R. B. Clarke)
pp. 108-118, Edinburgh: Edinburgh University Press.
FINE, R. (1964). Basic Chess Endings, New York: David McKay Company.
HUBERMAN, B. J. (1968). A program to play chess end games, Technical report no. CS106, Stanford University: Computer Science Depart-
ment.
KERES, P. (1974). Practical Chess Endings, London: Batsford Ltd.
KMOCH, H. (1959). Pawn Power, New York: David McKay Company.
KNUTH, D. (1976). Mathematics and computer science: coping withfiniteness,Technical report STAN-CS-76-541, Stanford: Department of
Computer Science.
MCCARTHY, J. (1959). Programs with common sense, Mechanisation of Thought Processes 1, London: HMSO.
MICHIE, D. (1976). An advice-taking system for computer chess, Computer Bulletin, Series 2, No. 10, pp. 12-14.
SHANNON, C. E. (1950). Programming a computer for playing chess, Phil. Mag, (Lond.), 7th ser. 41, pp. 256-75.
SLATE, D. J. and ATKIN, L. R. (1977). CHESS 4.5—the Northwestern University chess program, Chess Skill in Man and Machine (ed. P. Frey),
pp. 82-118, New York: Springer Verlag.
TAN, S. T. (1977). Describing pawn structures, Advances in Computer Chess 1 (ed. M. R. B. Clarke), pp. 74-88, Edinburgh: Edinburgh
University Press.
ZUIDEMA, C. (1974). Chess, how to program the exceptions? Afdeling Informatica, IW21/74, Amsterdam: Mathematisch Centrum.

Volume 21 Number 2 153