CCRL Discussion Board

Hi,

Excuse my lack of knowledge on tablebase generation. I understand generating the full 7-piece tablebase is an uncomplete task as of yet, and also that even generating one sub-set of the 7-piece tablebase would also take an extra long time.

But I am curious if there are fast ways for calculating 1 specific 7-piece position? I want to know the definite evaluation of several 7-piece endgames that are occuring during my post-game analysis. Are there tools for this already? Or due to the dynamic programming approach of the tablebase generation, would the access to the evaluation of one specific 7-piece position require the entire subset of the relevant 7-piece tablebase?

Regards,

Have you tried freezer? It allows to restrict some pieces to certain squares (particularly useful with blocked pawns), so the table size can reduce dramatically.

EDIT: A very long distributed search could potentially solve a position, but for many positions this would not work.

I don't know other shortcuts. If the above does not work, you need the whole table, and all sub-tables first. Solving in WDL metric instead of DTM can help to reduce the needed time and space. Also be aware that some metrics and tablebase formats ignore the 50-move rule, which can be important for practical endgames.

This freezer software looks like what I wanted, I'll contact the author, I am sure he can improve his software if necessary for the KRPPKRP positions.

What is WDL and what is DTM?

WDL - Win/Draw/Loss - only game outcome is known for each position. Tables are very compact, faster to build, but using such tables some long winning lines can be hard to find. Scorpio bitbases, Shredderbases and Triplebases are of this kind.

DTM - distance to mate. Easy to use, harder to build and store. Nalimov tables are of this kind.

Also most of the currently used tablebases (including Nalimov) totally ignore the 50-moves rule, so such tables can easily deceive you into thinking the position is won, when in fact it may be drawn by 50 moves rule.

EDIT: Other metrics include DTC - distance to conversin, DTZ - distance to zeroing the 50-moves counter, and DTZ50 (my favorite) - it is DTZ that takes draw by 50 moves rule into account.

Most (+95%, if not more) of practical endgames with 7 pieces include pawns, thus i think the 50 move-rule is not so relevant, because it resets after a pawn move. The fastest solution to a win in a 7-piece solution would also most likely include pushing the pawns faster than waiting 50moves with maneuvering, so I think you can pretty much make a rule that in any position a pawn must be pushed within 5-10 moves because maneuvering more than 5-10 moves is useless (I am talking about rook endgames, it might be longer in bishop and knight endings) I'll ask the Freezer author whether such rule can be implemented inside Freezer (I am unsure if it already exists.)

EDIT: hmm, a pawn should be pushed in 5-10 moves by the side trying to win (ie with material advantage). The side with less material does not have to push.

So what is the bottleneck for an exhaustive search of a 7-piece position? I see that there is a 7-piece generator code somewhere on this site, and it claims to work on my 4GB of RAM. How long do you think it would take it to analyze all positions of KRPPKRP? Maybe we should collect money to rent a super computer to finish this calculation as quickly as possible.

I've another question.

Say this whole KRPPKRP tablebase is calculated. How much space would it take on disk, can you estimate? If the entire 6-man tablebase is 1.2TB, this KRPPKRP should be also around 1.2 TB or less. Am I correct?

krppkrp has 583 Giga positions, when all 6-men (33+42) has 4489. This gives an estimate of 1153*583/4489 = 150 Gb for the krppkrp table in Nalimov format (DTM), with not-so-good accuracy, so consider it to be in the 100-200 Gb range. Using Gaviota (a new and more compact DTM format) would cut this by 10%, using a more compact metric (DTC / DTZ) would cut this approximately by 30% / 50% respectively.

Space storage for a single 7-men table is not really an issue, the real issue for 7-men with many pawns is all the calculation needed who also has to solve all subendings resulting from pawn promotions. Considering promotion to queen only (thus giving flawed results in a very small percentage of positions) is a good shortcut for first attempts (5 subendings instead of 99), but a better (very) long term goal would be building all 7-men WDL tables (est. 10-15 TB) which would allow easy generation of every 7-men table (krppkrp or any other) in DTC or DTZ format. DTC or DTZ are suitable to find winning (although non-DTM optimal) lines (barring 50-move rule limitations but building WDL50 and DTZ50 tables would also be possible). On the other hand, going to 7-men DTM is looking at ~150 TB and the whole set would be needed to get most likely endings such as krppkrp, kpppkpp and the like.

Thank you for the explanation that gives me an overview of the problem.

I think if the KRPPKRP can fit into 150GB disk space, people will consider buying an SSD to make their online engine play even stronger. Right now, most people can't afford to put the entire 1.2TB of Nalimov tablebase onto SSD, so they select the trickier endings to be put on SSD, but I am sure most will invest in a 2nd SSD if the KRPPKRP is out. So that is good news.

May I learn how you reached the 583 Giga and the 4489 Giga numbers as the number of positions? Then I'll have an even better understanding. I know it should contain the term 64*64*63*62*61*60*59, but my combinatorics has weaken a bit currently, and I would like to hear the answer from you instead of digging it myself.

To calculate the overall number of positions in a given ending, you place kings first, then pawns (if any), then the remaining pieces.

In the case of krppkrp :

There are 1806 different positions of kings (taking a vertical symmetry into account) among which 106 leave 48 free squares for pawns (both kings on 1st/8th ranks), 724 leave 47 (1 king on 1st/8th ranks) and 976 leave 46 (no king on 1st/8th ranks).
This gives (106*48*47*46+724*47*46*45+976*46*45*44)/2=85166148 positions for kings+pawns (divide by 2 because the two white pawns are interchangeable).
Then place the rooks on the 59 remaining squares : 59*58=3422 possibilities.
Total = 85166148*3422*2 (multiply by 2 for white to move/black to move) = 582877116912 positions.

Positions recorded have the following characteristics :
- kings are never adjacent to each other
- pawns are always on legal squares (no pawn on 1st/8th rank)
- however many positions are illegal since the side not to move is in check (but these are impossible to enumerate with a simple formula, of course)
- positions with castling or en passant possibilities are not taken into account (also not so easy to enumerate, they represent only a very small percentage)

Here is a file containing combinatorial calculations for all 3-8 men endings (I didn't expect to release it so it doesn't have many comments - if something is unclear please let me know)
To translate Gpos into Gb for file size expectations, you can use the following rules (occasionnally very wrong but not so bad in the majority of cases and more accurate for global sets) : 4 pos/byte in DTM, 7 pos/byte in DTC, 8 pos/byte in DTZ or DTZ50, 50 pos/byte in WDL.

Awesome!

Hi,

Sorry to bump this topic, but are there any altedrnatives to freezer?
First of all it's expensive, and secondly I doubt whether it will be suported on my Windows 7 PC...

Thanks...

plinius wrote:I doubt whether it will be suported on my Windows 7 PC...

It says: "Freezer runs on all Windows PCs with at least Windows 98."

You're right ernest, I can confirm that it runs on my PC.
I got my hands on it...