7 Piece Nalimov Tablebases

[Vegan]

I see posts periodically for 7 piece Nalimov tablebases and less often for other formats that don't seem to be popular. The problem with 7 piece Nalimov tablebases is the high memory requirements. Other formats attempt to overcome this but lack useful information such as distance to mate that the Nalimov format use.

Writing the program is easy, getting a machine to do the work is costly. And even with a fast machine, it will take many years to complete 7 pieces.

I have a page on generating the Nalimov tablebases and a proposed machine but with JEDEC memory capped at 8 GB for DDR2, and 16 GB for DDR3 there is not much that can be done until JEDEC comes to its senses and ceases the artificial cap on memory capacity.

Initially piece parts can be done with a 64 GB machine, the pawns will need much more.

[H.G.Muller]

Generating EGTBs with Pawns always takes a lot less memory than with Pawns. Only problem is that you hav to know which promotion positions are won, and which not. But, in the worst case, (of only a single Pawn), that follows from an EGTB without paws.

[Vegan]

When I generated some 6 piece parts, the pawn parts too much longer than the piece parts. About 3x more number crunching.

[H.G.Muller]

Yes, but time is not the same as space. EGTBs with pawns factorize into Pawn slices, which have a well-defined order due to Pawn moves being irreversible. So in effect every Pawn slice is really a seperate EGTB, converting to a successor end-game on each Pawn move. And you can build the Pawn slices in that order.

The time is only long because there are a lot of P-slices. But each P-slice of an N-men end-game with a single Pawn is only as large as an (N-1)-man end-game without symmetry, i.e. 8 stimes smaller than an N-men with symmetry. And for each additional Pawn, the size shrinks by another factor 64. So not much memory is needed. Just cranking through a lot of P-slices.

[Vegan]

The memory I refer to is the overhead of the complete piece set that has to be present for any pawn part to be considered. No free lunch.

There is a way out, astronomical disk storage and use uncompressed tablebases.

7 pieces is going to be brutal waiting on each part. It took a overclocked dual core intel 820 a long time (weeks) to do 33p parts, so 43p is going to be even more evil.

[H.G.Muller]

You are referring to the successor tablebases that promotions convert to? In most Pawn positions promotions are not possible. In the few where they are, the successor tablebases are read through in a single-pss sequantial access, directly from disk. (For DTC a bitbase would be sufficient, and only the fraction of positions with th promotion piece on 8th rank would be needed).

[Vegan]

I am only familiar with the Nalimov format. Consider tablebases as an onion. There are layers that are dependent on pieces to be present to cover the possibility of a pawn promotion. So for the trivial case of KK, all positions are a draw. Now KPK is variable as the pawn could queen if the king can achieve opposition and control the queening square. Now promotion to a knight or a bishop is a draw due to insufficient material. The promotion to a rook leads to mate as does the promotion to queen. So before KPK can be done, each of the sub tables are needed to be consulted to mark each position.

This same situation is the same as we add another pawn. This time we can be KPKP or KPPK and each is dependent on a the available piece positions to check for the draws and the wins as before. In the case of the 2 pawns the tables with 1 pawn are needed for the same queries.

Now with KPPKP we have 3 pawns, and dependencies on pieces, 2 pawns and 1 pawn are all needed to be consulted as well as the piece parts before KPPKP can be processed. The dependencies are the same, no pawns, then 1 then 2 and so on, just like layers in an onion.

The same dependencies exist with we move to KPPKPP where we have 4 pawns in the dependency chain.

Now the KPPPKPP position from 7 pieces (43) has 5 pawns in the dependency chain down to the basic pieces. Makes for 70 TB of compressed tablebases.

And the piece de resistance, KPPPKPPP from 8 pieces has a dependency chain of 6 pawns down to the basic pieces and represents a staggering amount of calculation to even contemplate. Here we are looking at 56x larger storage requirements.

How big is your hard disk?

[H.G.Muller]

I thought we were taking about RAM requirement here, not hard disk.

The dependencies you describe exit in theory, but in most cases not in practice. Take KPPPKPPP, for example. Some P-slices (with a white Pawn on the 7th) can can convert to KQPPKPPP. Now almost all P-slices of the latter are utterly won to white. There will be no need at al to figure out if KQPPKNNN, for instance, would still be won, because:

1) You won't have to allow black any promotions to get the fastest win
2) If you would allow him promotions, he would not promote to Knight
3) If you allow him to promote and keep the promotion pieces, it is no longer won in the first place.

[Vegan]

RAM is primary storage, disk is secondary, no real difference from a programming point of view, bit speeds are disparate.

Eugene's program is recursive. If it cannot find the corresponding minor to a given tablebase it will generate it. It has to have ALL dependencies to do the scanning. All of them, not a selection of this or that.

For the pawn that queens yes the distance to mate is short, not always though.

[H.G.Muller]

Well, the Nalimov generator is no good, and it cannot do 7-men. So I assume that the 7-men EGTBs will be generated by another generator, that does not suffer from this behavior.

The sensible way to approach the dependency problem is through using minimax with iterative deepening on the tablebase tree. If you see that all positions of a certain P-slice of KQPPKPPP are won when you make the assumption that every KQPPKQPP position is draw (because you can always prevent the promotion), there is no point in figuring out which KQPPKQPP positions are not lost after all. You simply prune the branch.

Similarly, when you see that a P-slice of KQPPKPPP is won even if you assume that all KQQPKPPP positons are lost (because you can force mate without a second promotion), the need to do KQQPKPPP would only arise if you were interested in the exact DTC within KQPPKPPP. (Because promotion might be quicker to enforce than mate.) But if you were only interested in the bitbase for KQPPKPPP, because you wanted to calculate DTC in KPPPKPPP, you would not bother with KQPPKPPP.

Chess is pretty much a "first promotion wins" game. Only for a very few P-slices, with multiple Pawns very close to promotion, you would really have to work. And indeed, it will require a lot of effort to figure out which slim winning chances you have when the 3 black Pawns are all on 7th rank. But most of the P-slices that could convert to this troublesome P-sice will not be affected at all. The retrograde building process will simply say: "Hey, when all his Pawns are on 7th rank, it becomes really hard to win this. So let us prevent him from pushing his Pawns."

[Vegan]

Ever thought to revise TBGEN? Not that hard. Templates are there for up to 4 pieces so 43 and 44 can be graunched into the code.

Dependencies push the work back until I have finished with 6 pieces once and for all. Need to focus on the current slice of the onion.

Hey, onion soup, yummy.