Computer Chess Club Archives


Search

Terms

Messages

Subject: KNNNNKQ (long)

Author: Marc Bourzutschky

Date: 23:51:33 01/29/05


Because of the 24-fold permutation symmetry of the 4 knights, KNNNNKQ has a
state space comparable to that of a typical 6-man ending with pawns, making it
accessible to tablebase generation on a home computer. While of course never
occurring in practice, KNNNNKQ has been of some interest to endgame theorists
ever since A. Troitzky (1866-1942) published a study in 1912 in which he asserts
that the knights will generally win.  Among the other important contributions
Troitzky made to endgames involving knights was to demonstrate that KNNNKN is
usually a win, and of course his famous analysis of KNNKP.

Another reason KNNNNKQ is of some interest to endgame theorists is that one can
expect a lot of positions with mutual zugzwang, where having the move is bad
for either side.  One might even expect full point mutual zugwangs where
whoever is to move loses.  Such FP zugwangs arise occasionally in symmetric
endgames with pawns (a simple example is W: Kf5,Pe4  B: Kd4,Pe5 where whoever
has the move loses) but are very rare in asymmetric piece endings.

Originally I had planned to implement a general 7-man tablebase generator using
Johan de Koning's clever algorithm which requires very little memory.  However,
I got lazy and used the same basic scheme as Ken Thompson in his pioneering
work.  This is rather memory hungry, but even using 1 bit of RAM for every
position in the state space requires less than 2G for KNNNNKQ, and so can be
done even within the 2G virtual memory restriction on Windows XP. Generation
took just under 4 days on a 3.6Ghz Pentium, and a 1-ply consistency check took
almost another 2 days.  The final compressed tablebase occupies about 6.3 Gb.
Since a generic ending with 7 pieces is almost 100 times larger than KNNNNKQ
such endings would rather stretch the resources available to hobby programmers,
so I don't expect to see systematic generation for a few years to come.

The longest win for the knights is in 85 moves (using DTC metric), and about
62.5% of all the initial positions are won, while about 35% are drawn.  However,
the winning percentage drops to 41% if trivial 1-move mates and captures are
excluded.  So the knights indeed win often, but there are a lot of positional
draws.  Of the approximately 10 billion legal positions for white to move,
26,725 are mutual zugzwangs, and there are 6 full point mutual zugzwangs.

Below are the FP mutual zugzwangs and a few other positions.  For the mzugs the
lines with both white and black to move are given.  Exclamation marks
following moves indicate that any other move would lead to a worse result.

The first two FP mzugs differ only by the location of one of the knights:

[D] 8/3N4/8/2Nq4/8/N7/2N5/K1k5 w - -

1. Ne3 Qd4+! 2. Ka2 Qb2#

1... Qf3 2. Ka2! Qg2 3. Nb3+ Kd1 4. Kb1! Ke2 5. Ndc5 Qh1+ 6. Kb2 Kf3 7.
Nd3 Kg3 8. Nc4 Qb7 9. Nce5 Kh4 10. Kc3 Kg5 11. Nbd4 Qb1 12. Nec6 Kg6 13. Nf3
Kf6 14. N2d4 Qa1+ 15. Kd2 Qf1 16. Nde5 Qg2+ 17. Kd3 Qh3 18. Ke4 Qg2 19. Kf4
Qf1 20. Nd7+ Kf7 21. Kg3 Ke8 22. Nde5 Qb1 23. Kf4 Qb2 24. Nf5 Qg2 25. Nd6+ Kf8
26. Nd7+ Kg8 27. Nf5 Qc2 28. Nce5 Qc1+ 29. Kg4 Qh1 30. Kg5 Qg2+ 31. Kf6 Qa2
32. Ne7+ Kh7 33. Nf8+ Kh6 34. Nf5+ Kh5 35. Ng7+ Kh6 36. Ng4#

[D] 8/3N4/4N3/2Nq4/8/N7/8/K1k5 w - -

1. Nb8 Qe5+! 2. Nd4 Qxd4+! 3. Ka2 Qb2#

1... Kd1 2. Nb6 Qe5+ 3. Ka2 Qh2+ 4. Kb3 Qg3+ 5. Kb4 Qe1+ 6. Kb5 Qg3 7.
Nac4 Ke2 8. Nbd7 Qg1 9. Nf4+ Kf3 10. Nfd3 Qb1+ 11. Kc6 Qh1 12. N7e5+ Kg3+ 13.
Kd7 Qh7+ 14. Kd6 Qh4 15. Kd5 Qd8+ 16. Nd6 Kh2 17. Ne4 Kg1 18. Kd4 Qb6+ 19. Kc3
Qa5+ 20. Kc2 Kh2 21. Kd1 Qa2 22. Ke1 Qa4 23. Ndc4 Kh3 24. Kd2 Qa8 25. Ke3 Kh4
26. Ncd6 Qa7+ 27. Kf3 Kh3 28. Nf5 Qa8 29. Nf4+ Kh2 30. Ng4+ Kg1 31. Ne2+ Kf1
32. Nge3+ Ke1 33. Nf4 Qc6 34. Nfg2#

[D] 8/8/q7/4N3/8/2k2N2/7N/1K4N1 w - -

1. Ne1 Qb6+ 2. Kc1 Qh6+ 3. Kb1 Qxh2 4. Ka1 Qb2#

1... Kb3 2. Kc1 Kc3 3. Kd1 Qa1+ 4. Ke2 Qa7 5. Ke1 Qa8 6. Ne2+ Kb4 7. Nhg4
Kc5 8. Nc3 Qa1+ 9. Kd2 Qb2+ 10. Kd3! Qa1 11. Ne3 Kd6 12. Nf5+ Ke6 13. N5d4+
Ke7 14. Kc4 Qa6+ 15. Ncb5 Kf6 16. Nec6 Kg6 17. Kd5 Kh5 18. Nd6 Qa8 19. Ke4 Qa3
20. N6f5 Qc1 21. Ng3+ Kg6 22. Nfe5+ Kf6 23. Kd5 Qb1 24. Ne4+ Kg7 25. Nf5+ Kh8
26. Neg3 Qb3+ 27. Kd6 Kh7 28. Ne4 Kh8 29. Ng5 Qa3+ 30. Ke6 Qb3+ 31. Kf6 Qb2
32. Nd8 Qb6+ 33. Nde6 Qb2 34. Kg6 Qb1 35. Nef7+ Kg8 36. Nh6+ Kh8 37. Ngf7#

[D] 8/8/8/3N1N2/8/1k1qN3/8/K4N2 w - -

1. Nde7 Qc3+ 2. Kb1 Qb2#

1... Ka4 2. Kb2! Qb3+ 3. Kc1! Qa3+ 4. Kc2 Kb5 5. Nd2 Kc6 6. Nb3 Kd7 7.
Nbd4 Ke8 8. Nc4 Qa2+ 9. Kc3 Qb1 10. Ncd6+ Kd7 11. Nf6+ Kc7 12. Kc4 Qc1+ 13.
Kd5 Qh1+ 14. Nfe4 Kd7 15. Kc5 Qc1+ 16. Nc4 Kc7 17. Nf6 Qe1 18. Ng7 Qc1 19.
Nge6+ Kb8 20. Nd7+ Kb7 21. Ne5 Ka7 22. Kd6 Qh6 23. Kc7 Qh7+ 24. Nd7 Qh2+ 25.
Kc8 Qh8+ 26. Nd8 Qg8 27. Nb5+ Ka6 28. Nc7+ Ka7 29. Na3 Qe6 30. Nab5#

The next two FP mzugs can be obtained by shifting the previous position 1 or
2 columns to the right, respectively.  Another interesting observation is that
the pieces are initially located within a 6x6 square, and it turns out that
on a 6x6 board this position is the only FP mzug.  After noticing that the
position is also a FP mzug on a 7x7 board I had conjectured with some analysis
that it would also be a FP mzug on 8x8, which is now confirmed.

[D] 8/8/8/4N1N1/8/2k1qN2/8/1K4N1 w - -

1. Nc6 Qd3+! 2. Ka1 Qd1+ 3. Ka2 Qc2+ 4. Ka1 Qb2#

1... Kb4 2. Kc2! Qb3+ 3. Kd2 Qc3+ 4. Ke2 Qb2+ 5. Ke3 Qc1+ 6. Kf2 Qc5+ 7.
Kg3 Qb5 8. N1h3 Qb8 9. Ne6 Qg8+ 10. Nhg5 Qb8 11. Kf2 Qh8 12. Nf4 Kc5 13. Nge6+
Kb6 14. Nfd3 Ka7 15. Nd7 Ka6 16. Nfd4 Qh2+ 17. Ke1 Qg2 18. N7e5 Qg1+ 19. Kd2
Qb1 20. Kc3 Kb6 21. Nc4+ Ka7 22. Ndc5 Ka8 23. Nd6 Ka7 24. Nc8+ Kb8 25. Ne7 Ka7
26. Kc4 Qf1+ 27. Kd5 Qg2+ 28. Kd6 Qh2+ 29. Kc6 Qh1+ 30. Nd5 Kb8 31. Nb5 Ka8
32. Kb6 Qg2 33. Ne7 Qh3 34. Nc6 Qf5 35. Nec7#

[D] 8/8/8/5N1N/8/3k1qN1/8/2K4N w - -

1. Kb2 Qg2+ 2. Kb3 Qb7+! 3. Ka3 Qb6 4. Nf4+ Kc4! 5. Ka2 Qb3+! 6. Ka1 Kb4
7. Ng7 Ka3 8. Nge6 Qb2#

1... Kc4 2. Kd2! Kd5 3. Ne3+ Ke5 4. Ng7 Qa8 5. N7f5 Qa5+ 6. Ke2 Qa2+ 7.
Kf3 Qa8+ 8. Kf2 Qa1 9. Nh4 Ke6 10. Nf3 Qh8 11. Kg2 Qg8 12. Nf2 Kd6 13. Nd3
Qa2+ 14. Kh3 Qb1 15. Nfe5 Qa1 16. Ne4+ Ke6 17. Nf3 Kd7 18. Nde5+ Kd8 19. Kg4
Qc1 20. Nd5 Qc8+ 21. Kf4 Qe6 22. Nef6 Qh3 23. Nc6+ Kc8 24. Nfd4 Qh2+ 25. Kf5
Qh3+ 26. Ke5 Kb7 27. Ncb4 Qh2+ 28. Ke6 Kc8 29. Nf5 Qe2+ 30. Kd6 Qh2+ 31. Kc6
Kd8 32. Nd4 Qe5 33. Nb5 Qg3 34. Nd6 Qa3 35. Nb7+ Kc8 36. Nb6+ Kb8 37. Nfd5 Qa1
38. Nd6 Qc1+ 39. Kd7 Ka7 40. Nbc8+ Kb8 41. Na6+ Ka8 42. Ndb6#

Below one of the 9 maximal lines for white:

[D] 8/N7/qN6/8/8/8/6N1/1k1KN3 w - -

1. Nac8! Qa3 2. Nh4! Qb3+ 3. Ke2! Qb5+ 4. Kf2 Qb2+ 5. Kf1! Qb5+ 6. Kg1 Qg5+ 7.
Neg2! Qf6 8. Kh2! Qe5+ 9. Kh3 Qe4 10. Kg3! Qe5+ 11. Kf3 Qf6+ 12. Ke3 Qh6+ 13.
Kd3 Kc1 14. Kd4 Qg7+ 15. Ke4 Qg4+ 16. Ke5 Qg7+ 17. Ke6 Qc7 18. Kf6 Qc3+ 19.
Kg6 Qg3+ 20. Kh5 Qe5+ 21. Kh6 Qh8+ 22. Kg5 Qd8+ 23. Kf4 Qc7+ 24. Kf3 Qh7 25.
Kf2 Qc2+ 26. Kg3 Qc3+ 27. Nf3 Qg7+ 28. Kh3 Qf6 29. Kg4 Qe6+ 30. Kg3 Qg6+ 31.
Kh2 Qc2 32. Nh4 Qc7+ 33. Kg1 Qc5+ 34. Kh1 Kb1 35. Ng6 Qh5+ 36. N2h4 Qe2 37.
Kg1 Kc2 38. Ng2! Qd1+ 39. Kh2! Kd3 40. Nd7 Ke4 41. Nc5+! Kd4 42. Ne6+! Ke4 43.
Ng6f4 Ke5 44. Nb6 Qc2 45. Nd7+! Kd6 46. Ndf8! Ke7 47. Kg3! Qb1 48. Kg4 Kf7 49.
Nh4! Qg1+ 50. Kh5 Qd1+ 51. Kh6 Qe1 52. Nhg6 Qa1 53. Nh5 Qh1 54. Nef4 Ke8 55.
N8e6 Kd7 56. Kg5 Kd6 57. Nf6 Qe1 58. Ne8+ Kc6 59. Kf6 Kb6 60. Nd5+ Kb5 61.
N8c7+ Ka5 62. Ngf4 Qa1+ 63. Ke7 Qa3+ 64. Kd7 Qa4+ 65. Kd6 Qa1 66. Nd8 Qa3+ 67.
Kd7 Ka4 68. Nc6 Qa1 69. Nce6 Ka3 70. Kd6 Qc1 71. Ned4 Qf1 72. Kc5 Qc1+ 73. Kb5
Qf1+ 74. Nfe2 Qf7 75. Kc4 Qb7 76. Ndb4 Qh7 77. Nd3 Qg8+ 78. Kc3 Qd5 79. Nb2
Qg5 80. Ne5 Qh6 81. Nec4+ Ka2 82. Nd3 Kb1 83. Kb3 Qg7 84. Na3+ Ka1 85. Ndc2#

One of the 4 longest wins for the queen:

[D] K6N/8/8/8/8/8/N1k2qN1/4N3 b - -

1... Kb3! 2. Nc1+ Kc4! 3. Kb7 Qd4! 4. Kc6 Qd5+! 5. Kc7 Qe5+! 6. Kd7 Kd5! 7.
Ned3 Qe6+! 8. Kc7 Qd6+! 9. Kb7 Qc6+! 10. Kb8 Qb6+ 11. Kc8 Qa7 12. Nh4 Qa6+ 13.
Kb8 Qd6+ 14. Kb7 Qe7+ 15. Kb6 Qd8+ 16. Ka6 Qa8+ 17. Kb5 Qb8+! 18. Ka5 Kc4 19.
Ka6 Qd6+ 20. Ka5 Qc7+ 21. Ka6 Qc6+ 22. Ka7 Kb5 23. N8g6 Qc7+ 24. Ka8 Kb6 25.
Ne7 Qa7#

Finally, here is the original Troitzky study, in a slightly modified form. The
original version has variations involving KNNNKN and KNNKP, but the transition
to KNNNNKQ can be avoided with a faster win.  But even the modified version
contains both KNNNNKQ and KNNNKN:

[D] 8/P1k2P2/6q1/N1K5/5n2/8/3p1N2/8 w - -

1.a8N+ {1.a8Q? Qh5+ 2.Kb4 Nd5+ 3.Ka3 Qf3+ 4.Kb2 {4.Nb3 Qxf2} 4...Qc3+ 5.Kb1
5...Qc1+} 1...Kd7 2.f8N+ Ke8 3.Nxg6 Nd3+ {After 4...Nxg6 5.Nc4 White wins the
pawn and enters a won KNNNKN ending} 4.Nxd3 d1Q 5.Nde5 Qg1+ 6.Kb5! Kd8 7.Nb7+
7...Kc8 8.Nd6+! Kd8 9.Ndf7+ Kc8 10.Nb6+ Kb7 11.Nbc4 Qb1+ 12.Kc5 Qg1+ 13.Kd5
13...Qg2+ 14.Ke6 Qh3+ 15.Ke7 Kc7 16.Ng5 Qh2 17.Ne6+ Kb7 18.Ngf4 Ka6 19.Kd6 Ka7
20.Nd5 Qh6 21.Nc6+ Kb7 22.Nd4 Qg6 23.Kc5 Qg1 24.Nd6+ Ka7 25.Kc6 Qb1 26.N4b5+
26...Kb8 27.Nc5 Qc2 28.Nb4 Qc1 29.Na6+ Ka8 30.Nbc7+ Ka7 31.Ndb5#



This page took 0.02 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.