Adventures with endgame tablebases

In an earlier Walkabout column (12 Mar. 2018) I looked at the engine Stockfish from a problemist’s perspective. Another major advance in computer chess has been the development of endgame tablebases, which in some ways are even more amazing than super-strong engines. Tablebases are essentially databases of endgame positions that have been exhaustively analysed so that their outcomes (win/loss/draw) with best play by both sides are known with certainty. Moreover, in these positions the result of every possible move has been determined precisely, and thus each winning or losing move is provided with a “depth-to-mate” number, i.e. how many turns before mate is forced. What this means is that for any tablebase position, we know its complete “truth” and how perfect play would proceed.

Early tablebases could only deal with settings of specific materials, e.g. K+Q vs K+R, but as computer performances improved, we saw the creation of general tablebases that could handle any combination of pieces up to a certain total number of units. A milestone was reached in 2012 when a Russian team used a supercomputer to generate the Lomonosov tablebases, which cover all possible endgames with seven units or fewer (barring the trivial cases of six pieces vs king). Consequently, the game of chess is more-or-less solved for such miniature positions! Here are some online resources for accessing these marvels of modern technology: (1) Nalimov EGTB – 6 pieces maximum (free); (2) Lomonosov Tablebases – 7 pieces maximum (annual subscription fee required, but free for fewer pieces); (3) Android app for Lomonosov – 7 pieces maximum (free and highly recommended).

[A fourth one is the free Syzygy Tablebases, which employs another metric called “depth-to-zeroing move” and is covered in the next instalment of this blog series. Because the Syzygy site boasts the feature of linking to specific positions, though, I am including such links for the diagrams below.]

Tablebases analysis and resultant discoveries about the endgame have had a profound effect on many facets of the game; see the Wikipedia entry on the subject for details. Here I will consider how tablebases affect chess composition, and delve into three positions that illustrate what has been made feasible in problems and endgame studies. These positions employ the same material of Q+S vs R+B+S, and although I didn’t realise it at the time, this is identical to the pieces used in some length-record settings uncovered by tablebases, where to force mate requires over 500 (!) moves. My initial aim was merely to give Lomonosov some random homebase positions (all units on their array squares) to test and see if any of them would yield interesting play. The most remarkable case that I came across, with a depth-to-mate number of 90, is diagrammed below. [Syzygy TB Link]

If we treat this position as a directmate problem that requires the quickest mate to be found, a surprisingly large number of white moves in the solution are uniquely forced. In deciding on the main variation, I tried to maximise the number of such precise moves, and in the given line 77 of the 90 white moves are unique and they are marked with an '!'. Since “only” 13 white moves have duals, these alternatives are specified as well whenever they occur. As in most lengthy tablebase solutions, the play is not really human-comprehensible. But out of all these perfect moves, the stand-outs are three instances where the white king retreats from e2 to d1 for no apparent reason. If this were a composed problem without any duals, these recurring Kd1! (at moves 22, 32, and 41) would have been a marvellous theme!

1.Qa4+! Kf7 2.Qb3+! Kg7 3.Qg3+! Kf7 4.Sd2! Be7 5.Qf3+! Sf6 6.Qb3+! Kf8 7.Qb8+! Kg7 8.Qg3+! Kf7 9.Sf3! Rh5 10.Sg5+! Kg7 11.Sh3+ (11.Se6+) Kf7 12.Sf4! Rh6 13.Qb3+! Ke8 14.Qe6 (14.Ke2) Kf8 15.Qc8+! Se8 16.Qf5+! Bf6 17.Ke2! Sd6 18.Qg4! Be7 19.Sg6+! Kf7 20.Se5+! Kf6 21.Sd7+ (21.Qf4+) Kf7 22.Kd1! Incredible! For instance, 22.Kd3? is one move slower, while 22.Kf3? takes another 195 moves to mate! 22…Rh1+ 23.Kc2! Rh2+ 24.Kd3! Rh6 25.Qf4+ (25.Qf3+) Kg7 26.Qg3+! Rg6 27.Qe5+! Kf7 28.Qd5+! Kg7 29.Qd4+! Kg8 30.Se5! Rg3+ 31.Ke2 (31.Kc2) Rg2+ 32.Kd1! Again! 32…Rg5 33.Qd5+! Kh7 34.Qe6! Rg1+ 35.Ke2! Rg2+ 36.Kf1 (36.Kf3) Rg7 37.Qh3+! Kg8 38.Ke2! Bf8 39.Qb3+! Kh8 40.Qe3 (40.Qf3) Kg8 41.Kd1! Yet again! Here some white king moves permit Black to draw, e.g. 41.Kf1? To see why, check the next diagram! 41…Be7 42.Sc6 (42.Qb3+) Bf8 43.Sd8! Be7 44.Qb3+! Kh7 45.Qd3+! Kg8 46.Qd5+! Kh8 47.Se6! Rf7 48.Qe5+ (48.Qh5+) Kg8 49.Qg3+! Kh8 50.Qg6! Rf1+ 51.Kd2! Rf2+ 52.Ke1 (52.Ke3) Rf7 53.Ke2! Rh7 54.Sf4! Bf8 55.Qg5! Sf7 56.Qf5 (56.Qd5) Kg8 57.Se6! Rh2+ 58.Kf1! Another mysterious retreat; now 58.Kd1? is slower by two moves. 58…Rh1+ 59.Kg2! Rh7 60.Qg4+ (60.Qg6+) Kh8 61.Qg3! Rg7 A strange-looking defence but it is the best. 62.Sxg7! Bxg7 63.Qh3+! Bh6 64.Kg3! Kg7 65.Kg4! Kf6 66.Qf3+! Ke6 67.Qb3+! Kf6 68.Qb6+! Ke7 69.Kf5! Sd6+ 70.Kg6! Bf4 71.Qd4! Bh2 72.Qh4+! Ke6 73.Qxh2! Kd5 74.Qg2+ (74.Qd2+/Qg3/Kg5) Ke5 75.Qc6! Se4 76.Qc4! Sd6 77.Qc5+! Ke6 78.Qd4! Se8 79.Qc4+! Kd6 80.Kf5! Sg7+ 81.Ke4! Se6 82.Qd5+! Ke7 83.Ke5! Sf8 84.Qd6+! Kf7 85.Qf6+! Kg8 86.Kf5! Sh7 87.Qe7! Sf8 88.Kg5! Sh7+ 89.Kh6! Sf6 90.Qg7!

In endgame studies, best play by both sides is assumed and since tablebases contain such perfect play information, they become a powerful resource for obtaining correct study positions. Some composers have written special programs to “mine” tablebases and generate studies that meet the criteria of soundness (dual-free variations) and interest (certain themes displayed). This method of composition is contentious for obvious reasons, but regardless, you can see some striking results of this approach in the problemist Árpád Rusz’s blog. Sometimes it’s even possible to “discover” a study by chance simply by examining the tablebase analysis of a random position. In the solution of the Mate-in-90 problem above, it’s mentioned that 41.Kf1? allows Black to draw. It turns out that the way in which Black forces a draw here is both precise and special – sufficiently so to work as a study. Here is the position in question, reflected and with the colours reversed: [Syzygy TB Link]

Black generally has a win with this material (as implied by the forced mate in the homebase diagram), but if the knights were exchanged, the remaining Q vs R+B is normally a book draw. The sacrificial opening 1.Sc5! is thus aimed at bringing about a knight swap via the fork, e.g. 1…Qd5 2.Sxe4 Qxe4 =. Black has two options that avoid an immediate exchange. (1) Accept the sacrifice with 1…Sxc5, but this diverts the black knight to the queen-side with the result that it cannot interfere with a perpetual check: 2.Rf2+ Kg7 3.Rg2+ Kh6 4.Rh2+ Kg5 5.Rg2+ Kf6 6.Rf2+, etc. If the king goes to the e-file, two sub-variations arise: (a) 6…Ke7 7.Re2 Se4 8.Bg2. With the knight about to be lost, Black’s only chance is 8…Qb6+ 9.Kh1! (9.Kf1/Kh2? would lose, e.g. 9.Kf1? Qf6+! 10.Kg1 Qd4+ 11.Kf1 Qa1+ 12.Re1 Qf6+ 13.Ke2 Qf2+) Qh6+ 10.Kg1 Qc1+ 11.Kh2 Qc7+ 12.Kh1 and Black can make no progress despite the material advantage, i.e. a positional draw. (b) 6…Ke5 7.Re2+ Se4 8.Bg2 Qb6+, and now in contrast to (a), 9.Kh1? would lose to 9…Kf4! 10.Rxe4+ Kg3 11.Bf1 Qh6+, but 9.Kf1 or 9.Kh2 draws – this dual is a pity – 9…Qb1+ 10.Re1 Qd3+ 11.Re2 Qd1+ 12.Re1 another positional draw. (2) The alternative 1…Qb6 seems to win the white knight without allowing perpetual check, as the piece is both pinned and doubly attacked, but 2.Rf2+! (unpinning the knight with check, e.g. 2…Ke7 3.Sxe4) induces 2…Sxf2 3.Sd7+ Ke7 4.Sxb6. I like how if Black doesn’t take the offered knight on the first move, White promptly sacrifices the rook instead!

How does this tablebase-produced study compare with existing compositions that involve the same material? The Chess Endgame Study Database, which enables searches based on the exact material used, brings up five studies with matching pieces. An examination of these varied endgames reinforces my view that the setting above is of publishable quality. However, among these examples there is an exceptional study that shows a similar kind of idea; though not an anticipation, it’s clearly the superior work thanks to its more intensive treatment of the theme, and I quote it below.

Naturally, we can set up this position on Lomonosov and check its analysis against the author’s solution. And this brings us to another salient feature of tablebases – their ability to confirm the soundness or otherwise of every miniature study ever composed. While engines like Stockfish are strong enough to solve most studies, they do so without necessarily providing certainty to the accuracy of the intended play. Tablebases can do these verification tasks perfectly and instantaneously, within the 7-piece limit. For testing directmate problems, programs like Popeye are still preferable because of the convenience of the solution files they produce, though again tablebases have a speed advantage when solving miniatures with lengthy solutions. In the case of the Matouš study here, it is proved to be sound and completely dual-free. [Syzygy TB Link]

Black has numerous threats in the diagram, including 1…Qxb2, 1…Qf2+, and 1…Sxe2 2.Rxe2 Qxh4+, so White has to start with forcing checks: 1.Rb8+ Kh7 (1…Kg7? 2.Sf5+) 2.Rb7+ Kg8 (2…Kh6? 3.Sf5+) 3.Sf5! Qf2+ (best because Black wants to avoid exchanging the knights, e.g. 3…Qc5 4.Rg7+ Kf8 5.Rxg1 Qxf5 =) 4.Kh1. Now Black has three plausible captures, and in the resulting distinct variations White’s methods of securing a draw are remarkably harmonious. (1) 4…Qxe2 5.Se7+! (5.Kxg1? Qg4+, the black knight is immune to capture because of deadly queen checks, not just here but for the rest of the variation!) 5…Kf7 6.Sd5+ Kf8 (6…Ke8 7.Re7+, 6…Ke6/Kg6 7.Sf4+) 7.Rb8+ Kg7 8.Rb7+ Kh6 9.Rb6+ Kg5 (9…Kh5 10.Sf4+) 10.Rg6+! Kf5 (10…Kxg6 11.Sf4+) 11.Rf6+ Kg4 (11..Ke5 12.Re6+! Kxe6 13.Sf4+) 12.Rg6+ Kh4 (12…Kh3 13.Sf4+) 13.Rh6+ Kg3 14.Rg6+ Kf3 (14…Kf2 15.Rg2+) 15.Rf6+ perpetual check. (2) 4…Qxf5 5.Bc4+! (again White can’t touch the knight: 5.Kxg1? Qe4! 6.Rb8+ Kg7 7.Bf1 Qg4+ 8.Bg2 Qd4+ 9.Kh1 Qd1+ 10.Kh2 Qd6+) 5…Kh8 (5…Kf8 6.Rf7+) 6.Rb8+ Kg7 7.Rb7+ Kg6 (7…Kf6 8.Rf7+) 8.Rb6+ Kh7 (8…Kg5/Kh5 9.Rb5) 9.Rb7+ Kh6 10.Rb6+ perpetual check. (3) 4…Sxe2 5.Sh6+! Kh8 (5…Kf8 6.Rf7+) 6.Sf7+ Kg7 7.Se5+ Kg8 (7…Kh6/Kf6 8.Sg4+) 8.Rb8+ Kh7 9.Rb7+ perpetual check.

Three different perpetual checks are arranged with great precision and economy in this wonderful study. I was delighted to find that it was selected for the FIDE Album, the anthology of the world’s best chess compositions. And as readers may have noticed, this First Prize winner was published back in 1981, well before computers were able to assist with the creation of any chess problems or studies. That’s a victory for human ingenuity, yes?