﻿﻿ MatPlus.Net

Website founded by
Milan Velimirović
in 2006

9:32 UTC
 ISC 2021

Remember me

 CHESS SOLVINGTournamentsRating lists1-Jul-2021

MatPlus.Net Forum Internet and Computing 8-Men Tablebase

### 8-Men Tablebase

Hi,

An important update on 8-Men Tablebase by Marc Bourzutschky.

http://arves.org/arves/index.php/en/2-ongecategoriseerd/1509-8-men-tablebase-first-explorations?fbclid=IwAR2BwvtDqDsu_2HIZjzHKWGgzJg42e1SX1SugBV_fLxr8KfQ3rfp3iOt1C4

This is worth reading in detail, but one point demands quotation:

QUOTE
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. [...] 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.

One of the interesting new outcomes obtained from 8-Men Tablebase:
(= 4+4 )

White to move loses
Black to move loses

Marc Bourzutschky provides some incredible variations and welcome explanations at the link above.

BTW, the idea of 8-men tablebases is not very original:
https://pdb.dieschwalbe.de/search.jsp?expression=a%3D%27pali%27+and+wpieces%3D2+and+bpieces%3D6+and+g%3D%27h%23%27+and+year%3D%27201%25%27

Even 7-men-tablebase problems had been published 16 year prior to the Lomonossov tablebases:
https://pdb.dieschwalbe.de/search.jsp?expression=PROBID%20IN%20%27P1014870;%20P1014888%27

Torsten, I think such tablebases require a supercomputer, which I unfortunately don’t have (I created the above problems without using any tablebases). What computer resources did you need to create 7-men tablebases?

There are subsets of the tablebase that can be generated independently of the rest of the tablebase. Bourzutschky picked the material KQRR-kqrr with at most 2222255026372 position. That requires about 2 TB of storage. That's less than the complete 6-men tablebases. These days that's doable on a medium-sized workstation or even an upper-end desktop PC. It gets more interesting when pawns are on the board.

In 1996, when generating P1014870 and P1014888 I used a PC with at most 8MB main memory. The material I picked (without Queen) was just particularly suitable.

QUOTE
BTW, the idea of 8-men tablebases is not very original:

The idea of 8-man tablebases exists ever since the first idea of tablebases, it's just that until recently the resources needed for 8-men TBs weren't available. s# tablebases (and h# tablebases) are probably easier because they're a lot less deep (compare max depth of the 7-piece s# TBs to the max depth of # TBs...), and therefore require less resources.

(7) Posted by Torsten Linß [Monday, Apr 26, 2021 10:47]

Wrong #1: The resources for doing the eg KQRR-kqrr (with only 2T positions, or other pawnless 8-men tablebases) were available 10 years ago (the hardware would have been about 12.000 EUR in those days).

Wrong #2: The crucial point is not depth (move length), but total number of positions, and the *number of legal positions* does not depend on the stipulation (h#, s#, #/eg, ...).

KQRR-kqrr is very simple case since it is symmetrical and has repeating pieces. For example, KQRN-kqbn has more than 10T of legal positions (there are more of them with illegal ones in total). In addition, this number should be multiplied by two (White to move, Black to move). Minor tables should also be included (when at least one piece is captured). This would require more than one HDD for just one tablebase.

Indeed, also you need more than one byte to store a DTM > 256... ;-) Some disc space can be saved by using compression. I pipe my outputs through GNU-zip. That saves about 75-80% of disk space. [Though packing and unpacking takes extra time...]

QUOTE
In 1996, when generating P1014870 and P1014888 I used a PC with at most 8MB main memory. The material I picked (without Queen) was just particularly suitable.

Took me a while to realize how exactly not having a queen is beneficial. I guess the point is that w/o a queen any capture would lead to an a priori non-solvable selfmate, so you didn't have to generate all the minor 6-men & 5-men tables at all?

Doing that with only 8M of RAM is really impressive. Table generation itself could be pretty streamlined, but searching them with this little memory should have taken weeks if not months!

I've just redone that particular table base. It has only 64241 positions. 7 byte suffice to code the position, 1 byte suffices for depth and correctness. That's less than 502KB to store the whole table base. ;-)

QUOTE
It has only 64241 positions.

I must be missing something obvious.

There are something like 462 (I guess) ways to legally place two kings if you count mirrored and rotated positions as one.
The white knight can be placed on any of the remaining 62 squares, exclude 8 from where it would check the opponent king (we go for lower bound estimate of legal positions)
Ditto the black knight: 61 - 8.

462 * (62 - 8) * (61 - 8) = 1322244

It seems like there are more than a million of meaningfully different positions for KS-KS alone.

Edit:
Unless you mean that there are 64241 positions with a finite DTM. But then this statement is misleading:
QUOTE
The crucial point is not depth (move length), but total number of positions, and the *number of legal positions* does not depend on the stipulation (h#, s#, #/eg, ...).

If the crucial point is the number of positions with a finite DTM then this number drastically depends on the stipulation: in, for example, KS-KS there are no solvable selfmates, but every legal position is a solvable helpmate.

Indeed, KRRBS-kb is rather sparse, which made its computation possible 25 years ago. Other s#-tablebases are more dense. I've encountered some where more then 30% of the legal positions have a solution. In h#-tablebases this ratio is close to 100%. [No idea what that ratio is for eg-tablebases.]

If the longest mate with 8 pieces is less than the longest with 7, where does it go from here in 9,10,...,32? Might we already know the longest mate in all of chess?

Andrew, I'm fairly sure we just need to wait a bit for them to generate a longer mate. :-)

Tim Krabbe, Journal Entry #393: https://timkr.home.xs4all.nl/chess2/diarytxt.htm

After the revealing of the mate in 549, this is said: "A scary part of Haworth's article is where he extrapolates the findings in sub-8-man Endgame Tables to predictions for 8- to 10-man endgame.

(cue graph, estimates for 8, 9, and 10 checkmate lengths in plies along with the known 1-7 lengths)

It is "pretty awesome that maxDTM seems to be doubling with each man," Haworth writes - in this logarithmic graph, we see what that might mean: an 80% probability that a 10-man endgame exists where a forced mate takes more than 5,000 moves."

James that expectation for 8 pieces that you wrote about has not been fulfilled. That's the news. There are some reasons to speculate about more complexity with 9 pieces, due to their being a few more unbalanced but close match-ups, but the underlying idea is now that more pieces means more space to find a speedier mate.

Here's another rare full-point mutual zugzwang position from the article:
(= 4+4 )

"wtm lost in 1; btm lost in 13"

For WTM, although there's a dual mate after 1.S~, this is just like the set play of a complete block 2-mover.

There doesn't seem to be a PGN file for the BTM win (not sure what's in the EPD files). Can anyone find the win? Since the metric used is Distance to Conversion, presumably it takes White 13 moves to win a black piece. Stockfish without access to tablebases can't find it.

Hard to prove without a tablebase. My best guess is that White can force a knight exchange in 13 moves, but Stockfish without tablebases doesn't know that a knight exchange proves a win for White.

Since a knight exchange is a general win, I suppose this material is also a general win, with exceptions like this zugzwang.