Abstract

We should not let February 2020 recede too far into the distance without celebrating the 50th anniversary of Thomas Ströhlein’s (1970) Ph.D. thesis, Research on Combinatorial Games, see Fig. 1. Previously, Bellman (1965) had indicated that Dynamic Programming could be applied to endgames. Ingo Althöfer (2019) relates that the topic was proposed by F.L. Bauer after the backwards analysis of games and puzzles had been mentioned to him in the Netherlands by two Dutch colleagues, Max Euwe and Wim van der Poel (van den Herik, 2020).
The thesis considered perfect-information, win-loss games using the concepts and results of graph theory and boolean matrices. The properties of winning and optimal strategies were then described. After defining Graph Kernels, Ströhlein brought chess into scope and described the first realisation of a retrograde algorithm to create endgame tables. In the last of nine chapters, results including correct maximal depth figures1
TS’ figures in today’s depth-to-conversion notation ‘DTC’: KRk (maxDTC = 16 winner’s moves), KQk (10 moves), KRkb (18m), KRkn (27m) and KQkr (31m). Computers can quickly prove that Kk, KBk and KNk feature no wins.
Bellman (1965) notes that two positions may be regarded as equivalent,
The actual computations were carried out in the period 1967-9 (Schmidt and Ströhlein, 1989, 1993). These were the first years of a West German National Research Programme. They were also the last years of the AEG-Telefunken TR4 computer at the ‘LRZ’ Leibniz Rechenzentrum, see Fig. 2 (Bauer, 2007; Bitsavers, 2007; CPW, 2020a/b; Sapper, 2020). Lest we forget, this computer’s 0.25MB of core memory, 50MB of disc, and speeds of 4.5/30µs for fixed-point add/multiply represented leading edge performance in Europe when it was installed for $2.5m in 1964.3
Similarly, Cambridge University’s ∼$5m 1965

Richard Bellman, Thomas Ströhlein (CPW, 2020b) and the title page of Research on Combinatorial Games.
Ströhlein’s computer model of chess simplified the code for practical reasons. The king was not mated but captured after being surrounded like Richard III. This capture could also notionally be done by the opposing king but that would have been captured first! ‘Capture depths’ on some print-outs were therefore one more than dtc depths in today’s ‘DTC’ Depth to Conversion metric. With no pawns and with castling considered unavailable as now, the squares a1, a8, h8 and h1 were rightly considered equivalent. However, for simplicity of programming and of reading the output, the sides a1-a8 and a1-h1 were not, so Ströhlein’s raw count of maxDTC positions is only slightly less than double the number of distinct positions. White is the stronger side and the focus is on wins for White, mainly White to move. The table on p62 of the thesis gives the correct maxDTC figures as in Table 1 here. Clearly, the step up from 3-man to 4-man endgames was a major one and a considerable feat worth pondering.

1964: the LRZ, Richard-Wagner-Strasse 18, and the AEG TR4 (Bauer, 2007).
The thesis’ table on p62 – plus column six
In addition to consulting the relevant KQk and KRk positions, the number of positions involved exceeded the number of bits in memory so data had to be managed to and from disc. Thomas credits his computer scientist wife, Ingeborg, with the finer points of the computing including the fast bit manipulation in machine code. Some remarkably long computer runs were involved: the TR4 was notably more reliable than its successor, the TR440 (Bauer, 2007, p. 102). KQkr later became the icon of non-trivial endgames thanks in part to Thompson (Kopec, 1990) and Jansen (1992).
Consideration of the computer results continued after 1970 in association with Gunther Schmidt, acknowledged in the thesis. The outputs for KRk and KRkb were photocopied and bound, see Fig. 3, and further analysed in Ströhlein and Zagler (1978) which included, see Figs. 4 and 5:
pp 003-088: all KRk positions with an optimal move; ‘!’ indicates uniqueness, pp 089-100: a list of KRk positions with dtc ⩾ 4 and a unique optimal winning line, pp 101: a list of the maxDTC positions, i.e., with dtc = 16 moves,4 229 positions with dtc = 31 ply: 121 distinct, being 108 pairs ‘mirrored’ in a1-h8 plus 13 exclusively on a1-h8.
pp 105-202: a lexicographic list of all winning KRkb positions with dtc ⩾ 4. A winning move is given: ‘*’ ≡ ‘only winning move’ and ‘!’ ≡ ‘uniquely optimal’.

The KRkn and KQkr results, ‘TUM-INFO’ (1978) and Relations and Graphs (1989, 1993).
Thomas Ströhlein’s thesis and subsequent work has been an inspiration to later workers. We have since enjoyed Ken Thompson’s sub-6-man ‘EGT’ endgame tables on CD (Tamplin, J.T. and Haworth, G.M., 2001) and the Nalimov (2000) 6-man EGTs online (Bleicher, 2010). We now benefit from sub-8-man results (de Man et al, 2018; Lomonosov, 2012) and look forward to 8-man EGTs. However, this pioneering work and thesis is where it all started and they deserve to be better known. Thomas himself celebrated his ‘50th’ with his family and longtime friend and colleague Gunther Schmidt on Feb. 23rd, 2020, see Fig. 6.
Thomas Ströhlein (2020) has made a generous contribution of original and immaculately conserved material to the author’s EGT archive: this will afford further study. I also thank him for reviewing this note. I welcome any offers of help for my halting and inadequate attempts to do justice to his thesis in translation.

Extracts from pages of Ströhlein and Zagler (1978) including the exemplar positions of Fig. 5: (a) p03, the first results, wtm KRk positions, wK on a1, the bK (later captured) on a1

White to move positions taken from the extracts of Fig. 4, annotated wKwR/bK(bB), T ≡ Turm ≡ Rook: (a) p03 row 3 col. 9, a1b1/a3, ‘9TB2!’ ≡
The e-version of this note (Haworth, 2020) provides supporting files including an archive on the TR4, the thesis, some extracts from references cited in the thesis, various pgn and data files, and the 40th anniversary celebration of LRZ in 2007.

From left to right: Thomas Ströhlein, his wife Ingeborg and longtime friend and colleague Gunther Schmidt at the family ‘50th’ celebration on 23rd February, 2020 of his 1970 doctorate.
