Home * Evaluation * Game Phases * Endgame * KRK

		KRK, the King and Rook versus King endgame is beside KQR the most elementary endgame with three pieces. If the rook can not be captured immediately - or the losing king isn't stalemated, checkmate can be forced by driving the losing king to the edge or corner of the board, the rook giving mate similar to the back-rank mate, the winning king locking all escape squares, often initiated by a rook tempo move to force the king into opposition.
KRK Mate in Two

Heuristics

Simple heuristics of a mop-up evaluation ^[1], only considering Center Manhattan-distance of the losing king, and Chebyshev distance and/or Manhattan distance between both kings, along with a tiny search, should be sufficient to execute the mate. Further, the rook may receive a bonus to maximize the absolute difference of its rank- and file-distances to the losing king, to confine the king without becoming attacked.

Despite todays engines have no difficulty to win this easily even without tablebases, deviation from optimal tablebase play, in particular in games with short time control, and most compact and efficient code considering symptoms of search pathology remain interesting issues ^[2].

Testbed

First implemented by Leonardo Torres y Quevedo in 1912 within his electro-mechanical KRK solver El Ajedrecista, KRK was and still is testbed and subject of research on evaluation and search heuristics and strategies, oracle approaches, mate search, search pathology, search versus knowledge, space-time tradeoff, retrograde analysis and tablebase generation ^[3], knowledge extraction and compression, feature detection and tuning, learning ^[4], genetic programming, pattern recognition, decision trees, logic and logic programming ^[5], inductive and deductive reasoning, rule-based modeling, problem solving and SAT ^[6]. In 1977, Donald Michie addressed KRK and the infinite board ^[7].

Selected Publications

1914

Henri Vigneron (1914). Les Automates. La Nature, pdf from cyberneticzoo.com, Translation by David Levy as Robots in David Levy, Monroe Newborn (1982). All About Chess and Computers. Springer, pp. 14-23, also in David Levy (ed.) (1988). Computer Chess Compendium, pp. 273-278.

1960 ...

Barbara J. Huberman (1968). A Program to Play Chess End Games. Technical Report no. CS-106, Ph.D. thesis. Stanford University, Computer Science Department

1970 ...

Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
Soei T. Tan (1972). Representation of Knowledge for Very simple Endings in Chess. Memorandum MIP-R-98, School of Artificial Intelligence, University of Edinburgh
Coen Zuidema (1974). Chess: How to Program the Exceptions? Technical Report IW21/74, Department of Informatics, Mathematical Center Amdsterdam. pdf
Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board. Advances in Computer Chess 1
David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
Ivan Bratko (1978). Proving Correctness of Strategies in the AL1 Assertional Language. Information Processing Letters, Vol. 7, No. 5, pp. 223-230. ^[8]
Thomas Ströhlein, Ludwig Zagler (1978). Ergebnisse einer vollstandigen Analyse von Schachendspielen: König und Turm gegen König, König und Turm gegen König und Läufer. Report, Institut für Informatik, Technical University of Munich (German)

1980 ...

Ross Quinlan (1983, 1985). Learning efficient classification procedures and their application to chess end games. Machine Learning: An Artificial Intelligence Approach
David Slate (1984). Interior-node Score Bounds in a Brute-force Chess Program. ICCA Journal, Vol. 7, No. 4
Reiner Seidel (1986). Deriving Correct Pattern Descriptions and Rules for the KRK Endgame by Deductive Methods. Advances in Computer Chess 4
Stephen Muggleton (1987). Duce, an oracle-based approach to constructive induction. Proceedings of the 10th IJCAI Conference, Milano, Italy. pdf
Stephen Muggleton, Michael Bain, Jean Hayes Michie, Donald Michie (1989). An Experimental Comparison of Human and Machine Learning Formalisms. 6. ML 1989, pdf

1990 ...

Stephen Muggleton (1991). Inductive Logic Programming. New Generation Computing, Vol. 8, pp. 295-318. ISSN 0228-3635.
Michael Bain (1992). Learning optimal chess strategies. ILP92
Ashwin Srinivasan, Stephen Muggleton, Michael Bain (1992). Distinguishing Noise from Exceptions in Non-monotonic Learning. ILP92
Michael Bain (1994). Learning Logical Exceptions in Chess. Ph.D. thesis, University of Strathclyde, CitySeerX
Ulrich Thiemonds (1999). Ein regelbasiertes Spielprogramm für Schachendspiele. University of Bonn, Diplom thesis, zipped ps, pdf (German) ^[9] ^[10]

2000 ...

Ivan Bratko (2001,2010). Prolog programming for artificial intelligence. Harlow England, Addison Wesley
David Gleich (2003). Machine Learning in Computer Chess: Genetic Programming and KRK. Harvey Mudd College, pdf
Aleksander Sadikov, Ivan Bratko, Igor Kononenko (2003). Search versus Knowledge: An Empirical Study of Minimax on KRK. Advances in Computer Games 10, pdf
Aleksander Sadikov, Ivan Bratko, Igor Kononenko (2005). Bias and pathology in minimax search. Theoretical Computer Science, Volume 349, Issue 2, pdf
Gabriel Breda (2006). KRK Chess Endgame Database Knowledge Extraction and Compression. Diploma thesis, Darmstadt University of Technology
Nicolas Lassabe, Stéphane Sanchez, Hervé Luga, Yves Duthen (2006). Genetically Programmed Strategies For Chess Endgame. GECCO 2006, pdf

2010 ...

Marko Maliković, Mirko Čubrilo, Predrag Janičić (2012). Formal Analysis of Correctness of a Strategy for the KRK Chess Endgame. Fifth Workshop on Formal and Automated Theorem Proving and Applications, Belgrade, Serbia, slides as pdf
Marko Maliković, Predrag Janičić (2013). Proving Correctness of a KRK Chess Endgame Strategy by SAT-based Constraint Solving. ICGA Journal, Vol. 36, No. 2

Forum Posts

My program can't mate KQK or KRK! by Rasjid Chan, CCC, March 11, 2013
algorithm - Chess task - King, Rook Vs King by Sreekanth Karumanaghat, Stack Overflow, April 13, 2013
Why minimax is fundamentally flawed by Harm Geert Muller, CCC, November 09, 2014 » Minimax

External Links

References

^ David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
^ Why minimax is fundamentally flawed by Harm Geert Muller, CCC, November 09, 2014
^ Thomas Ströhlein (1970). Untersuchungen über kombinatorische Spiele. Ph.D. Thesis, Technical University of Munich (German)
^ Michael Bain (1994). Learning Logical Exceptions in Chess. Ph.D. thesis, University of Strathclyde
^ Ivan Bratko (2001,2010). Prolog programming for artificial intelligence. Harlow England, Addison Wesley
^ Marko Maliković, Predrag Janičić (2013). Proving Correctness of a KRK Chess Endgame Strategy by SAT-based Constraint Solving. ICGA Journal, Vol. 36, No. 2
^ Donald Michie (1977). King and Rook Against King: Historical Background and a Problem on the Infinite Board. Advances in Computer Chess 1
^ Donald Michie (1976). AL1: a package for generating strategies from tables. ACM SIGART Bulletin, Issue 59
^ Diploma Theses — IDB
^ Uni Bonn - AG Intelligente Datenbanken - Was sind intelligente Datenbanken?

What links here?

Page	Date Edited
Ashwin Srinivasan	Aug 8, 2013
Barbara Liskov	Oct 30, 2014
Coiled	Mar 12, 2017
El Ajedrecista	Feb 25, 2015
Electro-Mechanical	May 2, 2016
Endgame	Sep 18, 2017
History	Jan 2, 2018
Huberman	Aug 9, 2013
KRK	Nov 26, 2016
Ludwig Zagler	Sep 6, 2017
Marko Maliković	Aug 10, 2013
Michael Bain	Aug 8, 2013
Minimax	Dec 29, 2017
Mirko Čubrilo	Aug 10, 2013
Mop-up Evaluation	Nov 26, 2016
Predrag Janičić	Aug 8, 2013
Ulrich Thiemonds	Apr 26, 2014

Up one Level

KRK

Table of Contents