Explanation of the unique triangle

[EricLang]

I started to create my own tablebases a few weeks ago with my own software. Now I would like to know how the unique triangle a1-d1-d4 works.
Currently I use my "unique block" a1-d1-d4-a4, which I can understand
I can't understand the symmetry of the triangle. Is there someone who can explain this?

[guyhaw]

The board can be 'flipped' a-h when Pawns are on the board without changing the essentials of the positions.
The convention has been, I think, to keep the stm King in a-d, and flip the board a-h if it is not.
There is an irony in this, because the initial position has the Kings in e-h.

When there are no Pawns on the board, the board can also be rotated 90 degrees clockwise.
The convention has, in this case with some EGT authors but not all, been to keep the stm King in a1-d1-d4 (and the s-not-tm King in a1-h1-h8).
When both Kings are not on a1-h8, this means that 8 positions are equivalent to one conformant position.
If both Kings are on a1-h8, both 'flips' around a1-h8 are conformant. Nalimov, for good reasons, does not choose to eliminate one of them.

I hope this is clear.
g

[EricLang]

I'll read your post a few times and react when I get it, or not
Thanks.

[syzygy]

You understand a1-d1-d4-a4, which means you understand that a chess position without pawns "does not change" if you flip the board horizontally or vertically.

Now observe that a chess position without pawns does not change either if you mirror the board in one of the two diagonals a1-h8 and h1-a8.

This means that any chess position without pawns is equivalent to a chess position with (for example) the white king in the triangle a1-d1-d4. You can find this position as follows:
1. start with a chess position and look for the white king.
2. if the white king is in the e, f, g or h file, then flip the whole board horizontally. now the white king is in the a, b, c or d file.
3. if the white king is in one of rows 5, 6, 7, 8, then flip the whole board vertically. now the white king is in the square a1-d1-d4-a4.
4. if the white king is still outside the triangle a1-d1-d4 (i.e. it is on one of the squares a2, a3, a4, b3, b4 or c4), then mirror the whole board in the a1-h8 diagonal. The white king will end up at one of b1, c1, d1, c2, d2 or d3, i.e. in the a1-d1-d4 triangle.

[EricLang]

Yesssss! I get it!
Thanks very much!

[h.g.muller]

The diagonal symmetry is tricky, as by looking at only two pieces to decide if a position is in the tablebase or not, means that symmetry-equivalent positions differing only in the location of pieces you did not consider (i.e. everything except the Kings in Nalimov) now occur twice in the tablebase.

It took me a lot of debugging before I realized that the two mirror-imaged positions do not automaticallly keep the same state (e.g. DTM), and that you have to force it to remain the same by updating both equivalent entries whenever a move coming from the uniquely-represented sector of the TB triggers the change of one of them (because you know the mirrored update will not occur, as the mirror-image of the uniquely represented part is lacking.)

So if the tabebase consists of 3 'sectors', A, B and C, where the diagonal reflection maps A onto B and v.v., and C onto itself (as a non-identity, i.e. C' onto C" and v.v.), and you elimnated B from the TB (but not C"), then:

1) All moves that lead into A are automatically OK, and taken as they are.
2) All moves that lead into B are remapped back to A by diagonal reflection.
3) All moves from C to C are automatically OK, as in (1).
4) All moves from A into C, must be applied as they are, as well as apllied after diagonal reflection, to make sure they affect C' and C" equally. (If the normal one affects C', the mirrored one affects C", and v.v.)

Note that when you make use of exchange symmetry of equal pieces, vertical and horizontal reflections can also map the symmetry-indicating pieces onto each other, leading to a similar situation as you only have with the diagonal reflection when all pieces are considered different.

My new 7-men builder will use two white pieces as symmetry indicators. When all pieces are different, I will use the familiar system of confining one to a1-d1-d4, and if it is on the diagonal, the second to a1-h1-h8, to get the canonical representation. This produced 518 canonical constellations for those pieces. I will avoid picing the white King for this, to not needlessly complicate the K-slice factorization of the generation process. If white has two identical pieces, I will use these pieces as symmetry indicators. If I counted correctly, in that case there are 275 canonical constellations.

[EricLang]

Hmm I'll have to study on that Mr. Muller

My unique triangle is working. Now I need some more compression.
The methods I use are:
1) Unique triangle, Precalculated legal king-combinations (where the distance between them is larger then 1)
2) Determine the number of bits, needed for a position: If the max-dtm is small I only use the required bits in the compressed file.
3) Compression in blocks of 8 kilobyte, the indices of the blocks are written to the end of the compressed file (also compressed of course)

What can I do more?
My KQQK file for white to move is around 450 KB. Nalimov's is much smaller...

[syzygy]

For kqqk, the indexing scheme can be further improved by removing the symmetry caused by having two pieces of the same kind. Each positions k,q1,q2,k corresponds to a position k,q2,q1,k.

To get rid of this symmetry, only index pairs q1,q2 (of squares) with 0 <= q1 < q2 <= 63. There are 64*64 pairs (q1, q2) (and 64*63 pairs with q1!=q2) but only 64*63/2 pairs (q1, q2) with q1 < q2.

There is an easy way to map pairs of integers 0 <= q1 < q2 to an integer 0 <= Q < 64*63/2:

Q = q1 + q2*(q2-1)/2.

Going back from Q to (q1, q2) is as simple as:

Code: Select all

q1 = Q;
q2 = 1;
while (q1 >= q2) {
  q1 -= q2;
  q2++;
}

More generally, three queens (of same colour) can be indexed by

Q = q1 + q2*(q2-1)/2 + q3*(q3-1)*(q3-2)/6

and so on.

Further symmetry can be removed by considering the case that the white king is on the a1-d4 diagonal. In that case, the black king is either on the a1-h8 diagonal or can be mapped to the lower part of the board. If the black king is on the diagonal as well, then one of the other pieces can be mapped to below the diagonal (unless it's on the diagonal), etc. This can get quite complicated and most likely is hardly worth it.
Also you can remove broken positions. Easiest is removing "positions" with two pieces on the same square (by ordering the pieces p1, p2, p3, p4, p5 and renumbering them so that 0 <= p1 < 64, 0 <= p2 < 63, 0 <= p3 < 62, 0 <= p4 < 61, 0 <= p5 < 60). Next step is removing illegal positions with the moving side in check. Easiest is positions with kings on neighbouring squares.

Most of these indexing tricks interfere which each other. This does not make them impossible, but it does make them exceedingly hard to implement correctly. The big question is whether it's worth it to go to extremes. I now believe that it is not worth it to spend too much effort on eliminating broken positions. Broken positions can be dealt with quite efficiently by letting the compression algorithm treat them as don't cares (i.e. assign that value that most likely is best for compression, which doesn't need to be the same value for each broken position).

Symmetry caused by Identical piece types should probably be removed, because there seems to be no way that a compression algorithm could remove that redundancy (and the gain is a factor of 2 with two identical pieces, a factor of 6 with three identical pieces).

To not let complicated indexing affect generation speed, it might be a good idea to use (very) simple indexing for the generator and then re-index before compression. The simple indexing could be as simple as 10 x 64 x 64 x 64 for kqqk. When done properly, you can perform mirror operations more or less directly on the index instead of going through the hassle of decoding the index into a sequence of squares, mirroring the squares, and encoding the mirrored squares into a new index value.


Next subject. What is your compression method?

Your point 2) suggests that you try to pack position values in e.g. 5 bits if there are at most 32 different values. Is that your compression? Or do you first pack positions in as few bits as possible (and pack those into bytes), then compress the result?

The first option gives lousy compression. The second option most likely only hurts compression as it hides some of the redundancy that a good compression algorithm can exploit.

[h.g.muller]

I am interested in compression methods, as I have not yet fully worked out the method I am using in my 7-men generator during building, and am not very knowledgeable on compression methods in general. (I know about Hufman coding, but that is about it.)

I guess the requirements for compression during generation are quite different from those for probing a finished tablebase. During generation, the lost positions become available in batches of the same DTx value N ('lost(N)'), and it would be a waste of time to merge the sets for different N with each other before you have them all. So I compress all sets independently, and store them one behind the other. Which of course would be a disaster for probing. The indiviual lost(N) sets are very sparse, sometimes extremely so (e.g. just a few thousand positions out of a tablebase of a hundred million). Even the most common DTx usually does not cover more than 5% of all positions.

So what I am using is a kind of Run-Length coding for the number of non-lost positions, implying a single lost position to follow. This should encode most lost positions in a single byte. This would make the worst case, for very densely populated cycles in a very quickly won end-game (like KQQQKNN, say), which migt have 10% of the position with one DTx, rather unfavorable, though (0.8 bits/position, hardly smaller than a plain bitmap).

There ar actually two worries at the opposite ends of the spectrum: In very lengthy generally won end-games, there are very many cycles, each cycle is very sparse, (needing large run-length, not fitting in a single byte), and yet almost all positions are eventually lost, and so occur in one of the lost(N) sets. If nearly all lost positions are encoded by multiple bytes, this causes problems on the disk, which has to store all lost(N) sets. On the other end, if a certain lost(N) set is very densely populated, it overflows the space that can be reserved for it in memory. Not because the individual positions require large RL and thus many bits, but simply because there are so many positions.

To combat the latter problem, I have set apart a large number of the single-byte RL codes to code for a pair of run lengths, (two very smal RL). In the limit of very dense sets, say 10%-20% populated, most run lengths will be below 10, and two of them can be encoded in a single byte. (Drawback is of course that the maximum single RL that can now represented by a single-byte code goes down, huting the compression of sparse sets.) My current guess for the overall optimum is to set apart codes for all pairs with RL1 + RL2 < 17. This takes 153 codes, leaving 103 for single RL codes or spacer codes. (Say 100 codes for RL 0-99, and spacers of 100, 200 and 4096 zeros.). Then the average number of bits per position goes down to ~5 in sets with more than 10% population, while only growing above 8-bits below ~2% population.

After the raw tablebase is generated (all lost(N) sets on the disk), the RL-encoded sets would have to be merged, and sliced up in short segments that can be independently encoded, and would contain a mixture of DTx, which is recognizable from the encoding (unless you make it a bitbase).

[guyhaw]

szyzygy - do you have a source/reference for that neat formula for 'Q' which enumerates the positions of like men?

The P-slices can be classified within an endgame by (spm1, spm2) where spm1 is the number of single-square P-moves if all the stm's pawns are to convert, and spm2 is the same sum for the side-not-to-move, i.e. (48, 48) for the initial position. The actual P-slices can be identified within the (spm1, spm2) super-slice by (Q1, Q2) where the squares are numbered from a2=0, b2=1, a3=8 ... to h7=47.

g

[syzygy]

szyzygy - do you have a source/reference for that neat formula for 'Q' which enumerates the positions of like men?

I came up with it myself, so I don't have a reference. The general formula works with binomials.

Let Bin(n, k) denote the number of k-element subsets of an n-element set. Then Bin(n, k) = n! / (k! x (n-k)!). This is basic combinatorics. The values Bin(n, k) are the values in Pascal's triangle.

To index sequences 0 <= x_1 < x_2 < ... < x_k < N = 64, take

Idx(x_1, x_2, ..., x_k) = Bin(x_1, 1) + Bin(x_2, 2) + ... + Bin(x_k, k).

The nice thing is that this doesn't depend on N, so you can use the same formula if N = 62 (e.g. two white queens on a chess board with two kings and the empty squares numbered 0, 1, 2, ..,. 61).

To prove that the formula works, we will show that Idx(x_1, ..., x_k) maps sequences 0 <= x_1 < x_2 < ... < x_k = N one-to-one to the range 0, 1, 2, ..., Bin(N, k) - 1. We use induction on k.

For k=1, this is trivial: Idx(x_1) = x_1 maps 0 <= x_1 < N to the range 0, 1, ..., N-1 = Bin(N, 1) - 1.

For k > 1, let M = x_k. Look at sequences 0 <= x_1 < x_2 < ... < x_(k-1) < M. These sequences correspond to (k-1)-element subsets of {0, 1, 2, ..., M-1}, so there are Bin(M, k-1) such sequences.

By the induction hypothesis, we know that Idx(x_1, ..., x_(k-1)) maps these sequences one-to-one to the range 0, 1, ..., Bin(M, k-1) - 1.

Therefore Idx(x_1, ..., x_(k-1), M) = Idx(x_1, ..., x_(k-1)) + Bin(M, k) maps these sequences one-to-one to the range Bin(M, k), ..., Bin(M, k-1) + Bin(M, k) - 1 = Bin(M+1, k) - 1. (To see that Bin(M, k-1) + Bin(M, k) = Bin(M+1, k), either look at Pascal's triangle, or observe that there are Bin(M, k-1) k-element subsets of 0, 1, ..., M that include 0 and Bin(M, k) k-element subset of 0, 1, ..., M that do not include 0.)

So Idx(x_1, ..., x_k) with x_k = M fixed, maps 0 <= x_1 < ... < x_(k_1) < M one-to-one to the range Bin(M, k), ... , Bin(M+1, k) - 1.

Observe that these ranges for varying M are exactly adjacent. So as M runs from k-1 (which is the minimum possible value of x_k) to N-1, Idx(x_1, ..., x_k) maps sequences 0 <= x_1 < x_2 < ... < x_k < N one-to-one to the range Bin(k-1, k) = 0, 1, 2, ..., Bin(N, k) - 1. Q.E.D.

[guyhaw]

szyzygy - many thanks, good work.

A difficult thing to 'come up with' - the enumeration of like-men dispositions is something I've come across and forgotten more than once.
I'll have a longer look at your proof of 'consecutive 1-1 enumeration' but I'm sure it's fine.

This is needed to enumerate P-slices of EGTs: we don't necessarily need or want each P-slice in its own file, but somehow we do want to be able to manage P-slices as 'data objects' up and down the memory-hierarchy.
g

[h.g.muller]

For the format of the 6/7-men EGT generator I am building, I do plan to have each P-slice in a separate file. So their will not be anything like KRPKRP.btm, but I will have things like KRe2KRh7.btm, KRd6KRd7.btm, etc.

So the matter of ordering of the different Pawn constellations will simply never crop up.

It seems wiser to do it this way as it allows building of partially complete EGTs for pawny end-games, without causing confusion or forcing you to make provisions for a "not-present" state of a position in the table. Some of the more nonsensical Pawn constellations (such as 5 Pawns on 2nd/7th rank) might then be left out, as their sensical predecessors, e.g. with only two connected Pawn on 7th rank, might already be proven fully won by pushing one of those Pawns to promotion.

[syzygy]

So the matter of ordering of the different Pawn constellations will simply never crop up.

In a way it does crop up, because you're not fully free in the order you generate pawn slice files.

I don't think ordering pawn slices is very difficult. Make sure lower "pawn values" are closer to promotion, e.g. for white a7 = 0, h2 = 47 and for black a2 = 0, h7 = 47. Use these values to calculate the index (while making sure the index function is strictly increasing in all variables). Then "higher slices" will depend only on "lower slices".

Some of the more nonsensical Pawn constellations (such as 5 Pawns on 2nd/7th rank) might then be left out, as their sensical predecessors, e.g. with only two connected Pawn on 7th rank, might already be proven fully won by pushing one of those Pawns to promotion.

I wouldn't like the idea of leaving out "nonsensical" successors. There will always be cases in which a "nonsensical" successor positions is the key to the solution. Or do you mean generating them but throwing them away once their predecessors have been generated?

[guyhaw]

I'm with syzygy here, recommending that no-one makes chessic decisions when generating EGTs.

Generating EGTs is a mathematical exercise, building up the picture of 'unmoves', traversing 'backwards' the lattice of move-based connections between positions. Once one starts second-guessing the facts, only one thing is going to happen: sooner or later, the facts will outflank chessic intuition.

For an example of this happening, look back at the initiative of Herik, Hershberg and Nakad of 1987 [21 years is a long time in computing terms.] They wished to exhaustively analyse a KRP(a2)KbBP(a3) position that came up in a game of Timman's. They made a few chessic assumptions, as the computing task needed to be cut down (something difficult to appreciate now as FREEZER will generate a DTC/Z EGT for this P-slice of KRPKBP in minutes as it is no more complex than a 4-man endgame). The papers are:

Herik, H.J. van den, Herschberg, I.S. and Nakad, N. (1987). A Six-Men-Endgame Database: KRP(a2)KbBP(a3). ICCA Journal, Vol. 10, No. 4, pp. 163-180.
Herik, H.J. van den, Herschberg, I.S. and Nakad, N. (1988). Karpov Amends Timman's Analysis. ICCA Journal, Vol. 11, No. 1, pp. 32-33.
Sattler, R. (1988). Further to the KRP(a2)KbBP(a3) Database. ICCA Journal, Vol. 11, Nos. 2/3, pp. 82-87.Herik, H.J. van den, Herschberg, I.S. and Nakad, N. (1988).
A Reply to R. Sattler's Remarks on the KRP(a2)-KbBP(a3) Database. ICCA Journal, Vol. 11, Nos. 2/3, pp. 88-91.
Herschberg, I.S., Nakad, N. and Onneweer, D. (1988). De Constructie van een Database voor het Eindspel KRP(a2)KbBP(a3). Internal Report, University of Limburg, Dept. of Computer Science.

Sattler patiently investigated Herik et al's assumptions and came up with counterexamples. Of course, the Herik EGT was close but not the full cigar. Herik amended his stats, and I don't even know if they were right second time round - though we are surely in a position with a combination of WILHELM and FREEZER to find out now.

Komissarchik and Thompson separately computed the KQPKQ endgame (to the DTZ metric I think) and disagreed. The problem was a combination of chessic intuition and programming correctness. The mistakes were not all on Komissarchik's side. I think Thompson had forgotten about underpromotion or assumed 'no underpromotion'.

Once chessic arguments start to invade the mathematical logic in the cause of 'simplification', the results become untrustworthy and are probably wrong.
g

[h.g.muller]

Perhaps I should elaborate on this, then. The judgement that a certain successor P-slice is non-sensical is is not a chessic one. It is something that follows from the calculation:

To calculate, say Ka4b4c7d7Kh7, you need to probe successors after Pawn push or capture. If the successors do not exist yet, they would have to be calculated. And so on, recursively. The mentioned P-slice of KPPPPKP has 5 successors (with white to move): two normal Pawn pushes, two promotions (times 4, if we consider under-promotions), and capture of the h-Pawn.

Now there are several strategies one can employ. First strategy could be to first calculate all successors, before starting to calculate the current slice. This is the usual way, and could be described as (retrograde) breadth first. But an alternative (which I believe to be superior if one is not interested in an exhaustive generation, but merely in solving the current P-slice (because the current board position of the game you are playing falls in it, say), is to only calculate one of the successors (say the one after c8=Q), and for the time being consider all other white zeroing moves as losses (depth first).

Now seeding an EGT only with wins from single successor will in general not produce a correct EGT: some winning-distances might be larger than they should be, and some won positions might show up as draws or losses in stead. Now you might not care about the slowed-down wins, as you were not caculating the current P-slice for its own sake and to get a DTx, but only calculate it as a successor of a slice you are really interested in, or because you are generating WDL in the first place. (If you re building DTZ, the DTZ of the successors are not of interest, you only need to know if they are won or not.) But to be of any use, the EGT always should have all WDL correct.

The only way to guarantee the latter is if all WTM positions are already wins. As long as there are (wtm) draws or losses, there is no guarantee that they would not change into wins by one of the converting or zeroing moves not yet considered. So in that case, you could calculate another successor, and repeat the building process including the seeding from that successor. (As a refinement there could be a 'mask' that defines a subset of the positions, and makes us satisfied if all positions indicated by the mask have been established to be wins, ignoring all other positions.)

This sounds inefficient, because you might have to re-generate the silce as many times as there are (white) successors, plus one (as you might be able to force a general win without considering any successors at all, e.g. in KQe4h3Ke5h4). But you might be able to cut off a tree of successors that is far larger, and super-complicated (e.g. because there are 5 Queens on the board). And you re not forced to do it for every slice, you can only do it for slices where there are one or two very obvious winning moves (like c8=Q and d8=Q in the example).

So my over-all algorithm for pawny end-games will actually be a combination of forward (meta-)seach with retrograde analysis: the forward search will be applied not occur in a tree of positions, connected by moves, but in a tree of P-slices connected by conversions (zeroings). But this forward search will have the same characteristics as we are used to: there can be beta cutoffs when the winning side has the move, and 'move' ordering is important for getting the cutoff as early as possible. And you can do iterative deepening. P-slices lying on the branches that were cut off are by definition non-sensical: sensible play would always avoid them.

Of course the non-sensical P-slices could be of interest to problemists and such, so eventually someone will have to generate them. But it would be an enormous advantage to be able to calculate the sensible 99% of P-slices of KPPPPKP without first having to do KQQQKQQ, KQQRQKQQ, KQQQKQR, ... And I think this is exactly what the described algorithm will give you. Most of the P-slices will be able to get complete, fully valid, mathematically certain DTZ assignments, without the need to build nonsense like KQQQKQQ. And for the ones that don't... Who cares? My aim is not to have all tablebases. Only the important ones. That applies equally to P-slices, which in my mind are separate tablebases.

From the above it will also be clear how I order the Pawn constellations: the forward recursive search will generate them in an order that will depend on the details of the forward search (move ordering, cutoffs), which I don't want to specify in advance (and maps in a totally unpredictable way onto an ordering anyway, dependent on which other pieces are on the board).

[syzygy]

Of course the non-sensical P-slices could be of interest to problemists and such, so eventually someone will have to generate them. But it would be an enormous advantage to be able to calculate the sensible 99% of P-slices of KPPPPKP without first having to do KQQQKQQ, KQQRQKQQ, KQQQKQR, ... And I think this is exactly what the described algorithm will give you. Most of the P-slices will be able to get complete, fully valid, mathematically correct DTZ assignments, without the need to build nonsense like KQQQKQQ. And for the ones that don't... Who cares? My aim is not to have all tablebases. Only the important ones. That applies equally to P-slices, which in my mind are separate tablebases.

What is your aim exactly? To get P-slices with complete, fully valid, mathematically certain DTZ assignments, or to construct tablebases on the fly for positions that occur on the board and discard them afterwards?

Personally I don't see much of a point in generating tablebases on the fly (with an exception for tablebases with blocked pawns in a correspondence game). For actually improving gameplay, I believe that tablebases should be available in the search tree for positions that are not yet on the board. (I know excessive probing from disk slows down the search, but this can be dealt with by probing intelligently.) I think that by far most games are won/drawn/lost before a position on the board is reached with 7 men or less (if ever).

If the aim is to construct (only) "the" sensible tablebases and P-slices, and to have them 100% mathematically correct, then I agree that it may not be strictly necessary to first calculate the value of each and every non-sensible position. However, it is inevitable that for calculating a sensible tablebase, you will need to calculate at least part of several non-sensible subtablebases and sub-P-slices (WDL, of course). But which part?

Most likely, the generator won't be able to generate only "part" of a non-sensible subtablebase or sub-P-slice. So you're stuck with generating the whole tablebase or P-slice. To do this mathematically correctly, you'll need to generate at least part of the non-sensible subsubtablebases or subsub-P-slices. However, by the previous assumption this means generating the full subsubtable or subsub-P-slice. And so on. It's very hard to see how anything could be gained here.

However, I cannot exclude the possibility that your generator is somehow able to generate only "part" of a non-sensible subtablebase or sub-P-slice and exactly that part that is required for the sensible tablebase or P-slice. Still, this part will require parts of non-sensible subsubtables or subsub-P-slices, etc. This seems exceedingly complicated to me. What is more, when generating some of the other sensible tablebases and P-slices, you will need parts of the same non-sensible subtable, sub-P-slices, subsubtables and subsub-P-slices, but *other* parts. The complexity is simply bewildering.

I can see how by choosing for on-the-fly generation and by cutting corners, you might get something that works most of the time. Working most of the time is perfectly fine for a chess engine; a chess engine is built out of assumptions that hold only most of the time. But I really don't see how you can construct mathematically perfect tablebases and P-slices without fully constructing (in WDL) all possible subtablebases and sub-P-slices AND not losing an enormous amount of efficiency.

[h.g.muller]

My own interest in end-games is to improve play of my engine, and to determine end-game values of fairy pieces. For that purpose I am at just the opposite opinion as you: there is no future in pre-computing and storing tablebases, as their size and number grows just to fast with the number of men. At todays technology, I don't think there is any way to even store the useful set of 7-men, while it will be fairly easy to generate most 8-men you encounter in game play on the fly at normal (40/40) time controls (relying on pre-computed WDL tables for the promotion positions).

But all that is not really relevant for the point at hand.

Generation of part of a P-slice (a complete tablebase of pawnless end-game is a single P-slice, so I will use that termminology for both) is possible and easy in the following sense: the generation is done on the complete P-slice (so this does not save any work), but the generated data is only required to be correct for the selected part of the P-slice. The fact that another part might be incorrect is purely due to some white zeroing moves not having been handled correctly. So there is no savings on the work required to generate the P-slice itself, but there is savings in the work you have to put in generating successors.

To come back to the practical example: Ka4b4c7d7Kh7 in DTZ can be correctly generated without first generating KQQQQKQ, KQQQRKQ, KQQRRKQ, KQRRRKQ, KQRBNKQ, ... Surely you must see some advantage in that.

Partially correct P-slices in themselves are not of great interest, and it would probably not be worth storing them (except for the promotion tables, perhaps). They would purely solve as an aid to catch some exceptional conditions in predecessor P-slices. My ideas on this are not fully developed yet. I am thinking of situations like Ka6b7h4Ke6f7, where the 'obvious' winning move is b8=Q, whch has the fastest possible DTZ (so once you prove it is winning, there is no need to search for alternatives). But of course there are also positions in the tablebase where the black King is on or defending b8, and there b8=Q does not work. But for those positions h5 will work. Now I don't want progress to be blocked because there are also positions where the black King can stop promotion of the h-Pawn, because those were already won by b8=Q.

Perhaps this is indeed only an issue in on-the-fly generation. For pre-computing, one would probably start with the slices KQa6b7Ke6f7 (h-Pawn promoted) and KQa6h4Ke6f7 (b-Pawn promoted), and you would be able to find quick checkmates for 100% of the wtm positions within those slices and some of their black successors, without the need for ever probing any white successors. And then you would work your way back from those P-slices, to P-slices Ka6b7hxKe6f7, with x=7, 6, 5, which would all still be 100% won by immediate zeroing, either by b8=Q or by pushing the h-Pawn, depending on where the black King is.

[EricLang]

A lot of stuff to study I see. Thanks for all reactions.

Next subject. What is your compression method?

Your point 2) suggests that you try to pack position values in e.g. 5 bits if there are at most 32 different values. Is that your compression? Or do you first pack positions in as few bits as possible (and pack those into bytes), then compress the result?

The first option gives lousy compression. The second option most likely only hurts compression as it hides some of the redundancy that a good compression algorithm can exploit.

First I "bitpack" all positions.
Second I compress the bitpacked data with a general data-compression-algorithm, which I got from internet. I work with Delphi and the unit is called ZlibEx.

[syzygy]

First I "bitpack" all positions.
Second I compress the bitpacked data with a general data-compression-algorithm, which I got from internet. I work with Delphi and the unit is called ZlibEx.

Have you tried without bitpacking? I would not be surprised if that gives better results (especially in cases in which you don't pack a integral number of positions in each byte, e.g. 3 of 5 bits per positions, but also in general).

[guyhaw]

Not quite sure why this thread ended up here, but still ...

It seems like hgm's interest is in generating sufficient WDL information about an endgame position during a game, and not in generating definitive DTx EGTs in the usual retro-only way. This is a valid interest. In fact, in the last few man-machine matches, Kasparov/Karpov were so concerned about their 6- and 5-man endgame play being exposed by the harsh light of perfect information that (a) 6-man EGTs were banned and (b) 5-man theoretical draws were to be conferred on the game without the defender being required to defend the draw. Fortunately, no situation calling on the 'theoretical draw' rule was required: otherwise, there would have been a global moan from the interested spectators.
The counter to the restriction on pre-computed EGTs is to compute them during the game (e.g. a SHREDDER/FREEZER combination for blocked Pawns), starting with the WDL EGTs if these were allowed. EGT generation is highly parallelisable, and I would almost make parallelisability a 'S(hould)' in my MoSCoW prioritisation of requirements on future EGT-generation algorithms and programs. As an aside to platform futures, increased power seems to be coming more from multicore architectures than higher-power single processors: one only has to observe Intel, AMD (of course), Nvidia Tesla and FPGA offerings.

Note that, with the 'theoretical draw' rule, the Fressinet-Kosteniuk rapid game (Villandry, Oct 2007, Krabbe chess diary #363, 237 moves), won in KRBKR by Kosteniuk, would have finished over 100 moves earlier in a (theoretical) draw. KQKPKQ and KRPKR are not easier to defend either.

However, we shouldn't get hgm's EGTs confused with the definitive EGTs which this discussion board has so far focussed on. You might also be able to tell that I am distinctly unenthusiastic about proposed classification of endgames or P-slices into 'sensical/nonsensical', or of positions into 'blessed/damned' (re any k-move rule).

The DTZ(k) metric, as hgm points out, does have the advantage over DTC/DTM that if there is a move zeroing the move-count, changing the phase, and winning, no other successors need be consulted. 'dz', the depth under the DTZ metric, is 1: end of story.

g

[syzygy]

I think I get the idea now. With many pawns on the board, the slices become quite small (and many). It might be possible to a kind of minimax search on the slices which would allow some branches to be cut.

This will probably work to some extent if the relevant slices are generally won for one side. Indeed in your previous post you mentioned:

The only way to guarantee the latter is if all WTM positions are already wins. As long as there are (wtm) draws or losses, there is no guarantee that they would not change into wins by one of the converting or zeroing moves not yet considered. So in that case, you could calculate another successor, and repeat the building process including the seeding from that successor.

So your idea would only work for generally won pawn slices?

The DTZ(k) metric, as hgm points out, does have the advantage over DTC/DTM that if there is a move zeroing the move-count, changing the phase, and winning, no other successors need be consulted. 'dz', the depth under the DTZ metric, is 1: end of story.

True. For single positions this works very fine: if the Q-promotion wins, there is no need to probe the underpromotions. However, if there is only one position in the slice for which the Q-promotion is not winning, the underpromotion subtables will have to be probed and thus will have to be generated.

(Maybe we should continue this subtopic in a separate thread.)

[h.g.muller]

However, we shouldn't get hgm's EGTs confused with the definitive EGTs which this discussion board has so far focussed on. You might also be able to tell that I am distinctly unenthusiastic about proposed classification of endgames or P-slices into 'sensical/nonsensical', or of positions into 'blessed/damned' (re any k-move rule).

You go that wrong. There is nothing to confuse, as my EGTs are exactly that: definitive EGTs in any metric of choice. The only difference is that the degree of incompleteness of the set might be different. In my format, it will happen that 'KRPPKRP' will at some point only be available 99% complete as DTZ. For the competing formats this board focuses on KRPPKRP will then be 0% available in any metric, and probably remain so for a dozen more years, as those formats only allow 0% or 100% complete EGTs, and 100% will not be feasible because not all obscure successors after multiple (under-)promotions will have been done.

So the only difference will be availability. If they are available, they wil be the genuin thing. If they are not, it will be because no one classified them as sensible enough to make the effort to compute them. It is not the designer of the generator that decides if an EGT like KQQQQQK.dtm is sensical or not. It is public demand.

[h.g.muller]

... So your idea would only work for generally won pawn slices?

The DTZ(k) metric, as hgm points out, does have the advantage over DTC/DTM that if there is a move zeroing the move-count, changing the phase, and winning, no other successors need be consulted. 'dz', the depth under the DTZ metric, is 1: end of story.

True. For single positions this works very fine: if the Q-promotion wins, there is no need to probe the underpromotions. However, if there is only one position in the slice for which the Q-promotion is not winning, the underpromotion subtables will have to be probed and thus will have to be generated.

In its most simple form it would only work for totaly won (for wtm) Pawn slices. This seems a severe restriction, but in fact I believe it to already be extremely useful in practice, as it will cut off the path to successor phases with multiple queenings. It is to be expected that having a single (surviving) Queen is enough to have a totally won slice (when the opponent has no Pawns close to promotion).

And you are perfectly right about the exceptions: if there is only one non-won position, you would have to resolve it first. If needed, through generating the relevant successor. Since a P-slice has all non-Pawns in any positions, there will be exceptions. In the example that I gave, (Ka4b4c7d7Kh7) this can be when white is in check by h7. Obviously he cannot play the otherwise winning zeroing move c8=Q then. Now in this cas you can solve it within the slice, as you can play Kh6 (never min if th7 is defended or not), and now black has no further checks, and cannot prevent c8=Q on the next move, unless he now takes c7 or d7. In the latter case, black performs a conversion, cutting off the path to the other white 7-men successors. You will need those black successors, like in general you ned all black successors always. But they are only 6-men (and still Pawn-rich), so I guess that is only a minor thing.

So after considering only the successor after c8=Q, you end up with a 100% won (wtm) P-slice, that has almost every position as DTZ=0, but some at DTZ=1. This would be good for a beta cutoff if you were after WDL. If you are after DTZ, you now would have to still figure out if the DTZ=1 positions could be reduced to DTZ=0. You might recognize the position as in-check, and look for conversions that resolve the check, and s there are none, conclude that DTZ=1 is really the theoretical optimum for these positions, so that we are done.

I don't think much more can be achieved than that in 'talking down' any DTZ. Except of course that the 100%-won requirement should only be applied to positions where the game is not obviously finished: positions where white is checkmated (or other positions where there are no legal white conversions) will not improve their WDL state or DTZ on considering more successors. So if there are other positions with DTZ > 0 we should either be satisfied with the WDL (which will be good enough to provide DTZ of all predecessors!), or we should seach more successors.

The refinement I am playing with in my mind is that we might only apply the 100% won criterion to a pre-defined subset of the slice. But I am not sure yet how useful this would be. In any case the partially computed slice would not be useful in itself, it would only be used as an aid in proving a successor slice was won, and then discarded. This might make it useful for on-the-fly generation, but probably a waste of time if the aim is to pre-compute and store.

[syzygy]

In its most simple form it would only work for totaly won (for wtm) Pawn slices. This seems a severe restriction, but in fact I believe it to already be extremely useful in practice, as it will cut off the path to successor phases with multiple queenings. It is to be expected that having a single (surviving) Queen is enough to have a totally won slice (when the opponent has no Pawns close to promotion).

Yes, but my evaluation function already knows that without any generation.

If you really want to do on-the-fly generation, then I think it is clear: 1. ignore underpromotions, 2. mark positions with a queen up that are not immediately lost as won, 3. in general, mark as many probably won positions as won as you can. It makes no sense to strive for perfection when generating on-the-fly because that's the worst time-result trade off you can make.

On-the-fly generation for 8- or 7-men positions might in some sense be feasible for positions with many pawns. Not as an alternative to precomputed tablebases, but as an alternative or complement to alpha-beta search + hashtable.
But I doubt it will on the average give better results than doing a normal alpha-beta search and relying on the hash table.