MatPlus.Net

 Website founded by
Milan Velimirović
in 2006

16:19 UTC
ISC 2024
 
  Forum*
 
 
 
 

Username:

Password:

Remember me

 
Forgot your
password?
Click here!
SIGN IN
to create your account if you don't already have one.
CHESS
SOLVING

Tournaments
Rating lists
1-Oct-2024

B P C F





 
 
MatPlus.Net Forum Internet and Computing 8-Men Tablebase
 
You can only view this page!
(1) Posted by Andrew Buchanan [Sunday, Apr 25, 2021 05:47]

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.

 
(Read Only)pid=20985
(2) Posted by Eric Huber [Sunday, Apr 25, 2021 13:40]

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.
 
 
(Read Only)pid=20990
(3) Posted by Torsten Linß [Sunday, Apr 25, 2021 18:15]

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
 
   
(Read Only)pid=20992
(4) Posted by Viktoras Paliulionis [Monday, Apr 26, 2021 00:55]

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?
 
   
(Read Only)pid=20993
(5) Posted by Torsten Linß [Monday, Apr 26, 2021 07:48]

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.
 
   
(Read Only)pid=20995
(6) Posted by Joost de Heer [Monday, Apr 26, 2021 08:57]

 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.
 
   
(Read Only)pid=20996
(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, ...).
 
   
(Read Only)pid=20997
(8) Posted by Viktoras Paliulionis [Monday, Apr 26, 2021 12:26]

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.
 
   
(Read Only)pid=20998
(9) Posted by Torsten Linß [Monday, Apr 26, 2021 12:53]

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...]
 
 
(Read Only)pid=20999
(10) Posted by Dmitri Turevski [Wednesday, Apr 28, 2021 17:17]

 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!
 
   
(Read Only)pid=21018
(11) Posted by Torsten Linß [Thursday, Apr 29, 2021 22:05]

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. ;-)
 
   
(Read Only)pid=21034
(12) Posted by Dmitri Turevski [Friday, Apr 30, 2021 08:57]

 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.
 
   
(Read Only)pid=21037
(13) Posted by Torsten Linß [Monday, May 3, 2021 17:02]

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.]
 
   
(Read Only)pid=21076
(14) Posted by Andrew Buchanan [Thursday, May 6, 2021 07:03]

So experts, please:

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?
 
   
(Read Only)pid=21104
(15) Posted by James Malcom [Thursday, May 6, 2021 15:33]

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."
 
   
(Read Only)pid=21111
(16) Posted by Andrew Buchanan [Thursday, May 6, 2021 15:45]

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.
 
 
(Read Only)pid=21112
(17) Posted by Peter Wong [Tuesday, May 11, 2021 06:16]

Thanks for the tip about this important update, Andrew!

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.
 
 
(Read Only)pid=21131
(18) Posted by Geir Sune Tallaksen Østmoe [Tuesday, May 11, 2021 09:31]

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.
 
 
(Read Only)pid=21135

No more posts


MatPlus.Net Forum Internet and Computing 8-Men Tablebase