CEN: Thomas Ströhlein’s Endgame Tables,a 50 th Anniversary

Abstract

We should not let February 2020 recede too far into the distance without celebrating the 50^th 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.

were presented for the five pawnless endgames KRk, KQk, KRkb, KRkn and KQkr. While Bellman’s Dynamic Programming (1965) noted that optimal endgame play could be defined, Ströhlein’s computational graph-theory discovered, illustrated and analysed it.2

Bellman (1965) notes that two positions may be regarded as equivalent, $P_{1} \sim P_{2}$ in the sense that one can move from either to the other. However, the equivalence classes so defined do not quite correspond to all the positions of an endgame force. There is, for example, no KNNk position that precedes or succeeds 8/8/8/8/8/1NN5/2K5/k7 b.

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 Titan Atlas by 1968 sported 0.75MB core-store, 40MB disc and fixed-point add/multiply times of 1.6/5.0µs. $2.5m in 1964 ≈ $21m in 2020, ‘top ten’ petaflop money.

Fig. 1.

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.

Fig. 2.

1964: the LRZ, Richard-Wagner-Strasse 18, and the AEG TR4 (Bauer, 2007).

Table 1

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

Other work on relations, graphs and games (Schmidt, G. and Ströhlein, T., 1985; Ströhlein, T., 1976; Ströhlein, T. and Zagler, L., 1977) contributed to their definitive books on the subject (Schmidt and Ströhlein, 1989, 1993). These include the broader applications of games, one of which – program verification – is also relevant in the world of models and games.

Fig. 3.

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 ‘50^th’ with his family and longtime friend and colleague Gunther Schmidt on Feb. 23^rd, 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.

Fig. 4.

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 $\dots$ a7, the R on a1 $\dots$ b8; (b) p89, wtm ‘positions with a clear main variant’: first move and others uniquely optimal, correct depths; (c) p101, the correct list of KRk max-depth positions, the last move capturing the Black king as suggested by the ‘17’; (d) p107, KRkb wtm wins with dtc ⩾ 4.

Fig. 5.

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!’ ≡ 1.Rb2 is uniquely optimal and dtc = 8 white moves; (b) p89 r1 c1, a4a5/a2, ‘TB5’ ≡ uniquely optimal 1.Rb5!, Ka1° 2.Kb3! Kb1° 3.Rc5! Ka1° 4.Rc1#!, dtc indeed is 4m; (c) p89 last position, d4h2/c1, ‘KD3’ ≡ uniquely optimal 1.Kd3!, Kb1! 2.Kc3! Ka1! 3.Kb3! Kb1° 4.Rh1#!, dtc = 4m; (d) p101 last position, b1g7/f7, ‘17’ (counting the capture of the king), i.e., dtc = maxDTC = 16m; (e) p107 r5 last position, a3d7/b1f4, ‘11Td4*’ ≡ ‘dtc = 11m, 1.Rd4!! is the only winning move’.

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 40^th anniversary celebration of LRZ in 2007.

Fig. 6.

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

References

Althöfer, I. (2019). Althöfer, I. (2019) Private correspondence, 2019-12-09.

Bauer, F.L., ed. (2007). 40 Jahre Informatik in München: 1967-2007, Festschrift, esp. (pp. 101–102). Fakultät für Informatik (IN) der Technischen Universität München.

Bellman, R.E. (1965). On the application of dynamic programming to the determination of optimal play in chess and checkers. PNAS, 53(2), 244–247. doi:10.1073/pnas.53.2.244.

Bitsavers (2007) http://bitsavers.trailing-edge.com/pdf/aeg-telefunken/tr4/. A TR4 archive.

Bleicher, E. (2010). http://www.k4it.de/. Sub-7-man DTM EGT query service.

CPW (2020a). https://www.chessprogramming.org/TR-4 The Telefunken-Rechner 4.

CPW (2020b). https://www.chessprogramming.org/Thomas_Strohlein.

de Man, R., Guo, B. & Fiekas, N. (2018). F’s query interface to deM/G’s s8m DTZ

_{50}^{″}

EGTs.

Haworth, G.McC. (2020). centaur.reading.ac.uk/89998/. This note with supporting data, image, pgn and text files.

10.

Jansen, P.J. (1992). KQKR: Awareness of a fallible opponent. ICCA Journal, 15(3), 111–131. See also ICCA Journal, 15(4), 179–191 and 16(1), 3–17.

11.

Kopec, D. (1990). Advances in man-machine play, esp. §2.4. In

T.A.

Marsland and

Schaeffer (Eds.), Computers, Chess and Cognition.

12.

Lomonosov (2012). http://tb7.chessok.com/. Facility for querying sub-8-man DTM EGTs.

13.

Nalimov, E.V., Haworth, G.M. & Heinz, E.A. (2000). Space-efficient indexing of chess endgame tables. ICGA Journal, 23(3), 148–162. doi:10.3233/ICG-2000-23304.

14.

Sapper, G. (2020). http://www.qslnet.de/member1/dj4kw/tr4.htm. The Telefunken TR4 at the Leibniz Computing Centre, Bavarian Academy of Sciences, Munich.

15.

Schmidt, G. & Ströhlein, T. (1985). On kernels of graphs and solutions of games: A synopsis based on relations and fixpoints. Dedicated to F.L. Bauer on the occasion of his 60^th birthday. SIAM J. on Algebraic and Discrete Methods, 6(1), 54–65. doi:10.1137/0606006.

16.

Schmidt, G. & Ströhlein, T. (1989). Relationen und Graphen, Springer-Verlag, Berlin (Mathematik für Informatiker), esp. pp. 199–202.

17.

Schmidt, G. & Ströhlein, T. (1993). Relations and Graphs, esp. pp. 194–196. In the Springer Discrete Mathematics for Computer Scientists series, as improved, extended and translated. doi:10.1007/978-3-642-77968-8.

18.

Ströhlein, T. (1970). Untersuchungen über kombinatorische Spiele. Doctoral dissertation, Technische Hochschule, München.

19.

Ströhlein, T. (1976). Iterative Berechnung der Kerne eines Graphen und der Lösung eines Spiels. In Graphen, Algorithmen, Datenstrukturen (ed. H. Noltemeier). Ergebnisse des Workshops WG76, 2. Fachtagung über graphentheoretische Konzepte der Informatik. 16^th–18^th June, 1976, Göttingen, München. Hanser.

20.

Ströhlein, T. (2020). Private communication: Six bound volumes of original TR-4 lineprinter listings covering KRkn and KQkr wins and losses, a copy of ‘TUM-INFO’ and Relations and Graphs in German and in English.

21.

Ströhlein, T. & Zagler, L. (1977). Analysing games by Boolean matrix iteration. Discrete Math., 19, 183–193. doi:10.1016/0012-365X(77)90033-4.

22.

Ströhlein, T. & Zagler, L. (1978). Ergebnisse einer vollständigen Analyse von Schachendspielen König und Turm gegen König, König und Turm gegen König und Läufer. Institute für Mathematik und Informatik, Technische Universität München. TUM-INFO-09-78-00=0200/1-FBMA.

23.

Tamplin, J.T. & Haworth, G.M. (2001). Ken Thompson’s 6-man tables. ICGA Journal, 24(2), 83–85. http://centaur.reading.ac.uk/4561/ . doi:10.3233/ICG-2001-24207.

24.

Van den Herik, J. (2020). Private correspondence.