On-demand tablebase generation

[hgm]

It should not be possible that positions that go into the newlyWon table have different DTM, and all mated-in-N positions that get decided in the same pass should have the same N, with this algorithm.

When you have a parent of a freshly decided mated-in-N position, i.e. a newly-Won candidate, you do check if there is already a faster mate for it in the real table, and not in newlyWon, right?

[Evert]

I suspect you do unnecessary work in the second step: you don't have to check positions that have no score associated with them, only those that lead to a won position.

I do the following (for double-sided tables):

iter=0: set all positions where black is mated to mate-in-0 ("lose in 0").

iter=1: loop over all positions that are "lose in 0" (in general: iter-1) and mark all precursors (retro-move) as "win in 1" (ply).

iter=2: loop over all positions that are "win in 1" (in general: iter-1). Generate precursors (retro-move) for each position and test whether all descendants are lost (forward move). If they are, then mark this position as "lose in 2" (ply).

iter=3: as iter=1, but make sure you don't overwrite positions that have already been marked as "won".

iter=4: as iter=2

etc.

I think one can combine the odd and even iteration steps in my scheme. For some reason this was slower for me, I'm not sure why (I think it's supposed to be more efficient). I find the above break-down conceptually easier to follow; somehow I always get confused while writing code for doing two retro moves in a row.

It also has the advantage that you should only ever find (and process) new "mate-in-iter" positions at every step and nothing else.

So far I've found writing a general-purpose retrograde analyser surprisingly tricky: it's very easy to make mistakes that wreck the whole thing, and debugging it can be a bit tricky (using the 8-fold symmetry to cut back on the number of positions you have to process doesn't help here, because a move like Ka1-a2 flips everything along the diagonal).

[tpetzke]

So far I've found writing a general-purpose retrograde analyser surprisingly tricky: it's very easy to make mistakes that wreck the whole thing, and debugging it can be a bit tricky (using the 8-fold symmetry to cut back on the number of positions you have to process doesn't help here, because a move like Ka1-a2 flips everything along the diagonal).

I'm with you with that. I first tried to write one that can handle 3 and 4 men but it had a lot of code that just tested whether there is a 4th piece present and I then decided to do a 3men only first and get that one right before moving to the next step.

I have the 8fold symmetry in place (in KPK only 2fold). In my move method I check whether the WK moves out of the core area and if it does transform the board so he is back in. My whole board is just an "int".

When I have time I'll give your algorithm a try just to see how it performs compared to mine. In the KPK it takes only 20 loops to generate the positions up to Mate in 28, but then needs 8 loops to correct the inconsistencies. Yours probably is consistent right from the start but might take a bit more loops.

Thomas...

[tpetzke]

It should not be possible that positions that go into the newlyWon table have different DTM, and all mated-in-N positions that get decided in the same pass should have the same N, with this algorithm.

I'll check that.

Edit: I checked it. Its not. Different "Mates in" hit the same spot in the newlyWon table. I think this works as designed. I assign a Winning score to a position without having tested all forward moves from that position whether this is the best Winning score. Often it is or in the same loop the spot is hit several times with different Mate distances and chances are the best is among them, but it is not certain. So some inconsistencies build up.

Thomas..

[hgm]

You don't clear 'newlyWon' after copying the wins back to the main table, so it keeps containing the 'oldly won' positions? Then you would indeed have to check not to overwrite an already short DTM with a larger one.

But during an iteration you should always produce the same mated-in-N (and thus attempt to assign the same mate-in-N to newlyWon). If you would produce a shorter one, it can only be because even the best move goes to a shorter mate-in-N, which means that you should already have assigned it on the previous iteration. When you assign the mated-in-N, are you sure you skip those that were already assigned a (faster) mated score?

[hgm]

This is promising:

I get all 464 mates of KBNK (plus all 4.4M won wtm positions) in 3ms now, for completely unsymmetric generation (2MB bitmaps). My old unsymmetric generator took 160ms for this.

Now let's see how fast I can iterate. (Must debug that first. And currently it still does it the slow way, scanning the entire bitmap for set bits, rather than using a directory map to remember where the words with set bits are.)

[tpetzke]

I implemented your algorithm and it indeed generates a consistent set right away. It is in total now twice as fast as my old one for KRK. I still have to test the other ones as well.

I had some trouble with retro move generation in combination with the 8fold symmetries. I missed some positions when the retro move involved the WK just outside the 10 core squares. It took me a while to figure that out.

It was overall an very interesting exercise.

Thomas...

[hgm]

Indeed, exploiting symmetry is a big pain. I had lots of trouble to get that working in FairyGen. And the result was that it became impossible to do asymmetric pieces, non-square boards, etc. So in the generator I am building now I completely forget about it. Even in orthodox Chess only positions with Pawns are of interest, and symmetry buys you zilch there.

[tpetzke]

Even in orthodox Chess only positions with Pawns are of interest, and symmetry buys you zilch there.

You still have two-fold which is compared to the 8 fold rather simple and still should save 50% memory and cpu time.

[hgm]

Only extremely rarely. The presence of the Pawn breaks the symmetry. With a single Pawn that is a certainty on a board of even width. With an even number of Pawns you can indeed have symmetric Pawn structures, but they are rare, and the more Pawns you have, the more exceptional they are.

So the symmetry plays no role during generation. It is just that you only have to generate for half the Pawn structures (e.g. only a-d Pawns for single-Pawn end-games). The other half you can simply reflect after the generation. (Or, probably more efficiently, reflect in the probing code.)