From: pjj+@cs.cmu.edu (Peter Jansen)
Subject: Endgame databases (KQKN,KRKN) (was Re: forced mate with these pieces?)
Organization: School of Computer Science, Carnegie Mellon
Date: Tue, 25 Aug 1992 21:55:46 GMT

[I made up this reply about a month ago, but never got around to posting. 
 My apologies if this is now slightly obsolete...]


In article <TAB.92Jul10101209@fanny.qt.IPA.FhG.de>,
tab@qt.IPA.FhG.de (Thomas Bantel) writes:

>Nice! Who did all this analysis? Was it done using a computer chess program?
>If you have comparable information for other endings, I would be interested 
>in it!

Yes, this is computer analysis: the position I gave and its main
variation were extracted from the KQKN endgame database (basically
a large array containing the number of moves to win for all the
positions with these pieces).

To get an idea how such 'endgame databases' are generated, you could look,
for example, in Levy and Newborn's "How computers play chess" (p129 ff).
There are also articles on endgame databases in many issues of the
ICCA Journal, the "Advances in Computer Chess" series, and various
journals and proceedings (AI, Parallel Computing, ...).
From time to time the topic pops up on this newsgroup as well.

>>Not entirely trivial, perhaps, and more difficult than KQKB,
>>but considerably easier than KQKR or KRKN.
>>
>>-- Peter
>
>I can't agree! KRKN should be a draw as far as I know. Although there are 
>positions where the rook wins, most positions are drawn.
>
>Thomas Bantel (tab@qt.IPA.FhG.de)

And in article <1992Jul10.222814.5022@talon.ucs.orst.edu>,
linb@ucs.orst.edu (Benjamin Lin) says:

>Certainly!  Isn't KR v. KN a draw?
>-benoni

Yes, KRKN is a generally drawn ending. In about two thirds of the
(legal) positions, White to move can only draw against best defense.
The other third of the positions are wins for White. It is true that
about half of these are immediate wins (can take the Knight or mate),
but that still leaves some 15% non-trivial wins, some of which are
rather interesting.

To give you an idea, here are the two maximin positions (deepest wins
with optimal play on both sides) for KRKN. Equi-optimal moves are given
in brackets, and a "U" indicates a unique winning move (i.e. all the
other moves draw). (Exclams are mine, and purely subjective...).

		8  - * - * - * - *
		7  k - * - * - * -
		6  - * - * - * - *
		5  K - * - * - * -   White: Ka5, Ra1
		4  - * - * - * - *   Black: ka7, nd2
		3  * - * - * - * -
		2  - * - n - * - *
		1  R - * - * - * -

		   a b c d e f g h


1. Rd1(U) ne4 2. Rd4!(U) ng3 3. Rd7+ [Kb5] kb8 4. Rf7! [Kb5, Kb6] kc8
5. Kb6 [Kb5] kd8 6. Kc6(U) ke8 7. Rf3(U) nh5 8. Kd6(U) ng7 9. Rf1 [Rf2] nh5
10. Ke6 ng7+ 11. Kf6 kf8 12. Rf2 ne8+ 13. Ke6+(U) kg8 14. Rd2 [Ke7] ng7+
15. Kf6 ne8+ [nh5+] 16. Ke7 ng7 17. Rd5 kh7 18. Kf8!(U) kh6 [Kg6]
19. Rd6+(U) kh7 20. Rd7 kh8 21. Rd1 [Rd2,Rd3,Ra7,Kf7] ne6+ 22. Kf7 [Ke7] ng5+
23. Kg6 ne6 24. Ra1 [Rb1,Rc1,Re1,Rg1,Kf6] nf4+ [kg8,nf8+,nc7] 25. Kf7 nh5
26. Rh1 Kh7 27. Rxh5 mate

		8  - * - * - K - *
		7  * - * n * - * -
		6  - * - * - * - k
		5  * - * - * - * -   White: Kf8, Rc1
		4  - * - * - * - *   Black: kh6, nd7
		3  * - * - * - * -    (White is in check)
		2  - * - * - * - *
		1  * - R - * - * -

		   a b c d e f g h

1. Ke7(U) ne5 2. Kf6(U) ng4+ 3. Kf5(U) ne3+ 4. Kf4(U) ng2+ 5. Kg3 ne3
6. Rc5(U) kg6 7. Kf4(U) ng2+ 8. Kf3! ne1+ 9. Kg4! nd3 10. Rc6+(U) kf7
11. Kf5(U) ke7 12. Rc4!(zugzwang) kf7 13. Rc7+ ke8 14. Ke6(!) [Ke4] nf4+
15. Ke5(U) ng6+ 16. Kf6(U) kd8! 17. Rg7!(U) nf4 18. Ke5(U) nd3+ 19. Kd6
kc8 [ke8] 20. Rg3! ne1 [nf2] 21. Rb3 [Rc3+,Kd5,Ke5] ng2 22. Ke5
kd8 [kc7,kd7,ne1] 23. Ke4 ke8 (or any) 24. Rh3 ne1 (or any) 25. Rh2
kf8 (or any) 26. Re2 and 27. RxN or KxN 1-0.

-- Peter