THE ENDGAME KING, ROOK AND BISHOP vs. ROOK
(KRBKR)
By Danny Kopec, Brent Libby, and Chris Cook
Department
of Computer Science,
Although this endgame has been studied for several hundred years, it is far from understood by most human chess players, including very strong ones. 1,2,7 There are a number of reasons which suggest that further study of this endgame is worthwhile:
1) in practice it occurs relatively frequently amongst the elementary (no pawns) endings. 2) Grandmasters frequently make game—theoretic value—changing errors. 1,2,9 3) It has been subjected to exhaustive analysis by construction of a database of 121,110,528 positions. 4,5,8,9 4) The chess literature has tended to repeat the same positions as examples. 4,5,7,9
Ken Thompson has found that most positions in the domain space are drawn (approximately 60%) while 40.1% are winable with the strong side to move. 8 His study also revealed that some positions require 59 moves to win. Tarrasch has stated, “This endgame is as difficult as it is beautiful”. 7 Benko calls it the “headache ending”. 1,2 All the literature and analysis for KRBKR suggests complexity. Since the ending by its very nature will often arise after many moves of play, humans will often stumble from the precipice of the long treacherous path which distinguishes correct play from faulty play. Many positions look the same, and yet due to minute differences in the placement of one of the pieces, are not. Furthermore, the winning method from won positions is often very subtle with a number of phases, while a drawn position will often involve a difficult defence spanning 50 moves with many permutations of similar configurations.
We hope to “demystify” this ending by representing the relevant concepts in a knowledge-based program. For example, there are the well-known drawing positions, the “Cochrane” (Diag. 2) and the “Szen” (Diag. 5), and winning positions, the “Philidor” and its derivative, the “Lolli” (Diag. 1). 1,2,4,7 However once precise position of any of the pieces changes, unknown terrain is entered. It is expected that interrogation of Thompson’s KRBKR database will uncover many secrets in the domain, especially when applied to a benchmark of positions (presently 30) where strong human players have erred. Such a knowledge-based approach employing an advice language (a type of forerunner to expert systems) and a database was used in the study of the King-Rook-King-Knight (KRKN) domain. 3 This led to the discovery of many positions where moves counter—intuitive to text-book advice were required for correct play. 6 However KRBKR is clearly a more complex domain than KRKN, and so a database is required to determine the correct move in almost any position.
We have constrained our study to the weaker (defensive) side of this ending, and have developed a working program in Pascal on the VAX 11/780 running VMS. At present the program consists of some 1600 lines of code for a four ply search with alpha-beta and quiescence for checks and captures. We are also employing an expert system shell (EXSYS) including 26 rules of inference as a front end to the program. In addition to the standard material, draw, and mate considerations, the program focuses On: 1) King to center values 2) relative piece-pair separations 3) opposition between piece-pairs 4) a notion of is Between and 5) target zones which the defending king aims for. The expert system determines which rule(s) match a given position and then gives probabalistic advice as to what board constraints should be achieved or maintained.
Plans
In the future we hope to link the expert system directly with the search program. The benchmark positions in cooperation with the Thompson database will be used in a number of ways. There will be a statistical analysis of the performance of diverse programs with different amounts of search and domain-specific knowledge for this endgame. In effect we will attempt to classify every position in the domain and determine how many ply of search a chunk of knowledge in it is worth.
References
1. Benko, Pal, (1985) “Endgame Laboratory”, Chess Life,March, pp.43—45.
2. Benko, Pal, (1983) “Endgame Laboratory”, Chess Life May, pp.45—47.
3. Bratko, Ivan, Kopec, Danny, and Michie, Donald, (1978) “Pat tern-based representation of chess end—game knowledge, The Computer Journal vol. 21, No. 2, pp. 149—53
4. Fine, Reuben, (1941) Basic Chess Endings David McKay & Co. pp. 509—515.
5. Keres, Paul, (1984) Practical Chess Endings B.T. Batsford Ltd., pp. 190—192.
6. Kopec,
Danny and Niblett, Tim (1980), “How hard is the play
of King-Rook—King-Knight ending? Advances in Computer Chess
2 (ed. M.R.B. Clarke),
7. Tarrasch,
Siegbert, (1931) The Game of Chess
David McKay
8. Thompson, Ken, (1986) “Retrograde Analysis of Certain End— games, ICCA vol. 9, No. 3, pp. 131—139.
9. Thompson, Ken, (1987) Unpublished personal communication.