KRK

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 , 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 .

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 , knowledge extraction and compression, feature detection and tuning, learning , genetic programming, pattern recognition, decision trees, logic and logic programming , inductive and deductive reasoning, rule-based modeling, problem solving and SAT . In 1977, Donald Michie addressed KRK and the infinite board .

See also

• Center Manhattan-Distance
• El Ajedrecista
• Distance
• Endgame Tablebases
• Huberman's program
• Infinite Board
• Interior Node Recognizer
• KPK
• Knowledge
• Learning KRK
• Manhattan-Distance
• Mate Search
• Mop-up Evaluation
• Oracle
• Retrograde Analysis
• Rook Endgame
• Search Pathology
• Space-Time Tradeoff
• Tempo
• Triangulation
• Zugzwang

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.
• 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
• Eduardo F. Morales (1994). Learning Patterns for Playing Strategies. ICCA Journal, Vol. 17, No. 1, pdf
• Ulrich Thiemonds (1999). Ein regelbasiertes Spielprogramm für Schachendspiele. University of Bonn, Diplom thesis, pdf (German)

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
• Zacharias Georgiou, Evangelos Karountzos, Yaroslav Shkarupa, Matthia Sabatelli (2016). A Reinforcement Learning Approach for Solving KRK Chess Endgames. pdf

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

• Longest mate in King and Rook versus King endgame by Joe Leslie-Hurd, February 16, 2005
• UCI Machine Learning Repository: Chess (King-Rook vs. King) Data Set by Michael Bain
• Checkmate - King and rook - Wikipedia
• How to Mate With King and Rook Vs King: 19 Steps - wikiHow
• Chess Corner - Chess Tutorial - Checkmating with Lone Rook

References

Up one Level