Marc Bourzutschky did send this email with his first explorations of the fresh 8-men Tablebase.
An chess endgame tablebase is a database with all the (legal) positions with the outcome, calculated by a chesscomputer program.
At the end of this email, some endgamestudies are shown where new cooks have been found.
Also some new findings very long lines are included in this article.
An interesting contribution to endgame theory.
Look also at: Kirill Kryukov or NULP.
=========================================================
His email:
It has been about fifteen years since Yakov Konoval and Marc Bourzutschky (YKMB) published the first database results for 7-man endgames, and about thirty years since Lewis Stiller’s pioneering work on 6-man endgames, so as suggested by Moore’s law we are now due for results for 8-man endgames. In this note I briefly describe my 8-man work, and provide a link to some of the results.
One key discovery by YKMB is the so far longest winning line of 517 moves in the 7-man endgame kqnkrbn, more than twice the length of the previous record of 243 moves in the 6-man endgame krnknn. An important question is at what point the chess board becomes so crowded that adding more pieces does not lead to longer winning lines due to the increased likelihood of shortening captures. My results suggest that we may already be at or close to this saturation point: The longest winning line for 8-man endgames without pawns appears to be “only” 400 moves.
First some technical preliminaries: The computer algorithm employed is standard retrograde analysis, but using various tricks, largely due to Yakov Konoval, to make the generation feasible for hobby computing. I use the Distance to Conversion (DTC) metric, which is the shortest number of moves to either checkmate or capture. The databases are one-sided, meaning they contain only wins for White and losses for Black. As a result, kxky and the “flipped” ending kykx are generally different. Endings of the form kkx are not needed because the number of White wins and Black losses would obviously be exactly zero. This results in 1,632 possible 8-piece configurations for pawnless endings, and a total of 4,795 configurations if pawns are included. I don’t consider castling rights and ignore the 50-move rule. Another technical point is that for endings with more than one bishop it is useful to consider the relative colors of the bishops. I use a notation which I believe is due to Ken Thompson: the 4-digit number “abcd” denotes a configuration where White has “a” white-squared bishops and “b” black-square bishops, and Black has “c” white-squared bishops and “d” black-squared bishops. For example, krbkbn_1010 indicates same-colored bishops, and krbkbn_1001 indicates opposite-colored bishops. Because the 8x8 board has an even number of squares there is no intrinsic difference between white and black squares, so the configuration “abcd” is equivalent to “badc”.
Kirill Kryukov has computed the number of unique legal chess positions for all 8-man endings:
http://kirill-kryukov.com/chess/nulp/results.html
My generator matches his numbers exactly. I have done a number of other consistency tests, but not an exhaustive set, so the results described here should still be considered research.
After generating about 15% of the pawnless endings I’m quite confident to have captured the longest ones. While 15% seems like a small subset at first blush, most other piece configurations have large material differences between White and Black so that long lines are unlikely. As another point of reference, Harold van der Heijden’s study database contains positions for just over a quarter of the possible pawnless configurations. The attached file 8man_200.pgn contains 22 endings with winning lines 200 moves or longer. The longest with 400 moves is in krrnkrbb_0020, i.e., Black has two same-colored bishops. The longest ending without promoted pieces has 360 moves, in krrbnkqr. Many lines contain reciprocal zugzwangs, which are labeled “zz”. The endings krbbnkqn and kbbnnkrb appear twice, with different bishop parities. Some of the lines are truly bizarre, such as the kbbbnkrn_3000 position 3B4/k1B5/3N4/7r/8/6B1/8/1K5n where it takes White over 260 moves to capture the black knight trapped on h1, while avoiding Black sacrificing his rook for the white knight. Knowing the results for various 6-man endings provides some basic orientation about what exchanges to pursue or avoid. For example, the 6-man ending krnkbb_0020 is a win, while krbnkq is a draw. So White may exchange rooks in krrnkrbb_0020, but should avoid that in krrbnkqr. A particularly interesting case is the ending kbbbnkrb_2101. Since kbbbkr_2100 is a win, but kbbbkb_2101 is a draw, White may exchange his knight for the bishop, but should avoid Black sacrificing his rook for the knight.
Another interesting discovery relates to full-point reciprocal zugzwangs, i.e., positions where whoever is to move loses. While such fp zugzwangs are fairly common in endgames with pawns, they are exceedingly rare in endings without pawns. There are none in endings with 6 or fewer pieces, and only eighty in 7-man endings, a handful of which were known before the 7-man databases were generated. There is a single 7-man fp zugzwang position that has neither pawns nor knights: 8/8/8/8/2B2Q2/b7/1r3b2/2K1k3, but unfortunately Black has two same-colored bishops. The only fp zugzwang without pawns and knights or promoted pieces that I am aware of is a study by Javier Rodriguez Ibran: 8/8/8/8/8/B6b/1r4R1/1rkqQKR1 which has ten pieces and a nice symmetry. The new discovery here is an fp zugzwang in kqrrkqrr: 3R4/8/2q5/8/8/2k1r3/2r5/1R1K1Q2. This position seems like a difficult construction task. However, play is quite comprehensible and study-like, with some elegant quiet moves. The attached kqrrkqrr.fp.pgn has detailed analysis.
Regarding endgame studies, there so far don’t seem to be any major surprises of the same magnitude as for the 5-7 piece endings. For example, YKMB discovered for 7-man endings that rook + two minor pieces regularly win versus rook plus one minor piece, even though rook + one minor piece versus rook is generally drawn. It appears that the 8-man endings rook + two minor pieces versus three minor pieces generally follow what one would expect from the 6-man databases that result from trading of an equal pair of minor pieces. The endings krrbnkqr and krrnkrnn seem to give much better winning chances than the 6-man endings that result from trading a pair of rooks, but they may still not be general wins. I’m attaching a very limited sample of studies that I found interesting. There are quite a few others that are refuted by quick exchanges to 6-man endings that I felt were not really interesting and therefore did not include. An ending that may be of some theoretical interest is knnnnkrb. At first blush this may not look interesting given that knnnnkq is a general win as already shown by Troitzky about a hundred years ago, and confirmed by myself in what may have been the first complete 7-man database in 2004. However, it appears that in knnnnkrb Black can usually save the game by exchanging off the bishop for a knight. By contrast, this does not appear possible in knnnnkrn. Also, kbnnnkrb seems to be a general win regardless of whether the bishops are of the same or opposite color.
The attached spreadsheet 8man_20210412.xlsx contains basic information for all the endings I had generated as of April 12, 2021. I hope the meaning of the columns is fairly obvious. Maximal lines, statistics and zugzwangs are available at the link below:
https://drive.google.com/drive/folders/1hhqMEklD5D-GDIP5DIUGrfPuGCkwXDTI?usp=sharing
It is not feasible at this point to share the databases themselves because of their enormous size.
A little more detail on what is available at the link above:
(1) PGN files with maximal lines. For example, krrbnkqr.w.360.pgn contains a line where white to move (wtm) wins in 360 moves. For endings with different possible bishop parities those lines are listed separately. For example, krrnkrbb_0020.w.400.pgn has the longest line where the two black bishops have the some color, while krrnkrbb_0011.w.87.pgn has the longest line for opposite-colored bishops which is dramatically shorter.
(2) Basic ending statistics. For example, krrbnkqr.txt contains basic win/loss statistics, the exact count of White wins for each depth, and the Black losses for each depth. I hope the content is fairly self-explanatory. For endings with multiple bishops I also provide statistics for different bishop parities. For example, krbnkbnn_1010.stats.txt and krbnkbnn_1001.stats.txt have statistics for same- and opposite-bishop colored subsets of krbnkbnn.
(3) EPD files with zugzwangs. For each position, the EPD comment field lists the wtm and btm result. This requires a little more explanation because of the one-sided nature of the databases. Consider the krbnkbnn database. It contains information on whether wtm wins or not, and whether btm losses. So it can identify zugwangs where btm loses, and wtm does not win. It cannot resolve the wtm does not win positions further into wtm draws or wtm loses. It also cannot identify zugzwangs where wtm loses and btm draws. To fully resolve all positions and identify the remaining zugzwangs requires the “flipped” database kbnnkrbn. If a position shows up, with colors reversed, in both databases as “wtm does not win, btm loses”, then clearly wtm does not win resolves to wtm loses and it is an fp zugzwang. The remaining positions then resolve to wtm draws, btm loses. The file krbnkbnn.zz.epd contains over a million zugzwang positions, all but one are of the form “wtm draws, btm loses”. There is a single fp zugzwang: 8/8/8/8/2n5/8/R1Nb1k2/1B1K1n2 w - - 0 1 c0 "wtm lost in 1; btm lost in 13". The file kbnnkrbn.zz.epd contains only 778 positions. 777 of these are of the form “wtm draws, btm loses”, which, with reversed colors, are positions that in krbnkbnn would be zugzwangs of the form “wtm loses, btm draws”. Thus all zugwangs for krbnkbnn have been identified. The single fp zugzwang shows up in both files. For convenience, I have extracted fp zugzwangs into separate files: krbnkbnn.zz.fp.epd and kbnnkrbn.zz.fp.epd both contain the single fp zugzwang identified for this ending. For endings where the “flipped” ending is missing, the EPD comment will read “wtm not won; btm lost in x”. This is the case for krrbnkqr.zz.epd, because I don’t yet have kqrkrrbn.
Even if 8-man pawnless endings don’t have any record lengths, that does not necessarily mean there may not be new record lengths for 9-man endings. Using the standard piece strength quantification (queen=9, rook=5, bishop=3, knight=3) the strength difference between White and Black for an 8-man ending is always even, while for a 9-man ending it is always odd. This may lead to new dynamics. I’m generating a few 9-man endings to explore this, but am limited by my computer resources (two lower-end workstations with 1.5 TB RAM) to endings with significant permutation symmetries.
Endgames with pawns have fundamentally different dynamics. I have started working on 8-man databases with pawns, but because of the even larger size of these endings I will limit myself to very specific pawn configurations.
I welcome any comments, and in particular suggestions which, if any, additional pawnless 8-man endings would still be of interest. I would also be interested to collaborate with folks who have access to more extensive computational resources to expand this work.
=========================================================
Some cooks found by Marc Bourzutschky with this 8-men Tablebase:
=======================================
Some interesting new outcomes:
==============================================
Some very long lines to prove a result: