On-demand tablebase generation

[syzygy]

So positions 1 ply back from mate or otherwise lost positions can be marked as won.
Positions 1 ply back from won positions should be marked as "potential loss".
On each iteration:
- for a potential loss, do a 1-ply search for potential losses to see if they are really lost. Then immediately mark the positions 1 ply back from the new loss as newly won.
- for a newly won position, mark the positions 1 ply back as potential losses.
This results in 2 ply per iteration, which is quite efficient.

So to make sure I understand this correctly: once a position has been marked as "won", it gets skipped on a later iteration through the list and never needs to be looked at again, correct?

Positions that are "newly won" need to be looked at in the next iteration in order to mark their precursors as "potential loss".

Whether a position with a winning value is "newly won" or not can be decided based on its value. Earlier I said I did 2 ply per iteration. More accurate is to say that I do 1 ply per "half iteration". In the first half I go over the wtm table, in the second half I go over the btm table.

Letting p denote the number of the iteration, I know that the "newly won" positions in the (say wtm) table I am looping through are won in p-1 or p plies, and I know that the "potential losses" in this table are losses in either p-1 or p plies (if confirmed as loss), so I confirm the white losses in p-1 / p plies (and mark black wins in p / p+1 plies) and I mark the black potential losses in p or p+1 plies. Then I increment p, switch sides, and I am in the same position again.

[Evert]

Ok, so to make sure I understand:

1. I mark all positions that are mate as "won". Say I put them on stack A. Other positions are "unknown"
2. For all positions that are marked as "won" I generate precursors. These are "potentially won". Say I put them on stack B. After this step stack A is empty.
3. For all positions that are marked as "potentially won" I generate descendants. If all of its descendants are "won", I change its state to "won" (and push it on stack A), with a score that is one worse than the best of its descendants. Otherwise one of its descendants is still "unknown" and we may get back here, so I do nothing. After this step, stack B is empty.
4. If I marked any positions as "won" in step 3, then stack A is no longer empty and I go back to step 2.
5. All positions that are won are marked as such (and have a DTM score, say). All other positions are marked as "unknown", which for all intent and purposes can be interpreted as "draw".

Does that sound right?

[syzygy]

1. I mark all positions that are mate as "won".

Note that you lose if you get mated!! I made the same mistake

The precursors of mates are "won" and need to be looked at once.

Captures I do similarly: I loop through all "capture positions", i.e. positions with one piece less, and for each position probe its value (not necessary if you have just 3-men as it will be a draw) and generate all "uncaptures". If the captured position is lost, the positions resulting from the uncapture are won. If the captured position is a draw, I mark the positions resulting from the uncapture as CAPT_DRAW (like your TB_DRAW). If the captured position is a win, the positions after uncapturing are potential losses.

The advantages of this are:
- I only need to probe the captured position once;
- for the remainder of the generation I can ignore all captures (I only have to avoid setting CAPT_DRAW positions to potential loss).

2. For all positions that are marked as "won" I generate precursors. These are "potentially won". Say I put them on stack B. After this step stack A is empty.

A potentially won position, i.e. a position with at least one winning move, is won. It's only the losses that are "potential".

(Or are you phrasing everything from white's point of view?)

[syzygy]

An alternative to marking precursors of wins as "potential losses" and verifying them later (or even immediately, which however is less efficient because of double work) is to initialise all positions with the number of moves into that position (which is different from the number of moves out of that position due to symmetries!).

Instead of marking a position as "potential loss" you can now decrement the number. When it reaches zero, you know that all moves lose, so the position is lost. No need for a verification step.

At first sight this seems more efficient, but for me it was not. I think the reasons are:
- the initialisation step costs quite a lot of time and you may initialise a lot of positions that never need to be verified anyway because they quickly turn out to win (this depends on the table).
- you can't do 2 plies at the same time. At least with DTZ / DTZ50 I need to know exactly in how many plies a move loses. If I do "loss in p-1" and "loss in p" at the same time, it might be that the second to last move into the position came from "won in p-1" and the last one came from "won in p-2". Now the generator will think the position is lost in p-1 while in fact is is lost in p. To avoid this, the generator has to verify anyway by doing a 1-ply search and all the advantage is gone.
- my method does not verify a "potential loss" immediately, but waits for the next iteration. This way a "potential loss" will often have been marked multiple times but will cost just one verification (at that iteration).
- the latter effect is reinforced by doing 2 plies at the same time.

It is also more complicated, because you need quite a big range of values to encode the number of moves.

[Evert]

(Or are you phrasing everything from white's point of view?)

Yes. Not consciously though, so it's good to be made aware of.

It's a bit odd if you think in negamax terms (where you flip lost/won when you flip the side to move); I think it's because I tend to think of things like KQK as "won".

[syzygy]

(Or are you phrasing everything from white's point of view?)

Yes. Not consciously though, so it's good to be made aware of.

It's a bit odd if you think in negamax terms (where you flip lost/won when you flip the side to move); I think it's because I tend to think of things like KQK as "won".

Yes, if it's just for KQK or KXK things can of course be simplified. Positions are either won or drawn.

[Evert]

Positions that are "newly won" need to be looked at in the next iteration in order to mark their precursors as "potential loss".

Whether a position with a winning value is "newly won" or not can be decided based on its value. Earlier I said I did 2 ply per iteration. More accurate is to say that I do 1 ply per "half iteration". In the first half I go over the wtm table, in the second half I go over the btm table.

Letting p denote the number of the iteration, I know that the "newly won" positions in the (say wtm) table I am looping through are won in p-1 or p plies, and I know that the "potential losses" in this table are losses in either p-1 or p plies (if confirmed as loss), so I confirm the white losses in p-1 / p plies (and mark black wins in p / p+1 plies) and I mark the black potential losses in p or p+1 plies. Then I increment p, switch sides, and I am in the same position again.

Ah, that's something I hadn't thought of, but I can use that with my code as well. It cuts the time for the 3 men sets by 30%.

[Evert]

I'm thinking of (eventually) adopting the following general idea. For this to work I need to make my (or at least, a) tablebase generator a) fast enough, and b) able to save its state and resume where it left off later. The latter is a technical detail, but it may be harder if the generator was not designed early on with this in mind (I haven't looked in great detail into any of the generators that are available as open source to see how easy or difficult this would be with one of them).

Then I would do the following:

1. In the search, probe for table bases as normal. However, if a tablebase is not available, we simply store the request. Here we can record things like the depth at which the tablebase was probed, whether it was recorded from a PV node or not, etc.
2. At the root and after an iteration has finished, we look at TB requests that have been issued during the search. Now we have a choice to make: do we enter the next iteration now? Or do we generate a tablebase first?
The answer can depend on whether we have a move to play in case time runs out before we're done with the tablebase, the depth at which the requests were made (out near the leaves it's maybe less important, but when it's at depth=2 it may be too late to really benefit from the tablebase) etc.
3. If we decide to generate the tablebase, we start doing so, but we do keep an eye on the clock. If time runs out before we are done, we suspend the TB generation and play the move we already found.
4. If the tablebase is done, we start the next iteration of the iterative deepening loop (unless there's some condition that says we don't bother because of the time).

There are many details to be worked out (the tablebases could take up quite a bit of memory, we need to have that in reserve somewhere; on the other hand, if we've generated one and it's no longer needed, we can simply ditch it). An efficient, but compact indexing scheme is probably important here.

[hgm]

You could just dedicate an extra thread to EGT generation, in addition to your search threads. You then either suspend one of the search threads, or the generation thread. That way you would never have to worry about saving the state of the generator.

Note that what makes this attractive is the fact that EGTs with Pawns, like KRPPPKRPP, are not really single EGTs at all, but fragment into P-slices. Because you know what Pawn structure you have in the root, you can discard most of the P-slices as unreachable. Especially with blocked Pawns there aren't too many P-slices that you can reach, and you only have to generate for those.

My guess is that it would be better to decide statically in the root which EGTs you are going to generate. The time it would take is largely predictable, and explodes with each extra non-Pawn. So when the root is in KRB...KRN... with ... some Pawns, the situation is completely hopeless, with each P-slice being an unsymetrical 6-men. At this stage you probably would plan to do KR...KR... and KB...KN..., to prepare for either trade. The search might reach too many non-sensical material signatures. If one side has a dangerous passer you might want to repare for having to sac your minor for it, and also build that one.

The most challenging issue in selective generation is to handle promotions. When you are generating complete EGTs, it is not that much of a problem that KRPPKRP in theory can convert to KQQRKQR: the latter is not that much bigger, Pawns venturing on 48 squares, Queens on 64. But with P-slices a Pawn that was constrained to a file, (and then being able to only reach the forward part of that file) has perhaps 3-4 possible squares, which jumps up to 64 on promotion. Obviously, you would not want to waste time on frivolous promotions.

Now what saves the day here is that in almost all P-slices of KQRPKRP, the game is not only totally won for white, but can actually be won 'with a handicap'. E.g. when you would alter the rules such that a white non-capture with a Pawn counts as an instant loss, and similarly for allowing black to move with a Queen... Most P-slices would still be totally won. This exploits the huge promotion gain or orthodox Chess. End-games that were interesting before promotion tend to become a walk-over after the first promotion. The handicap rules are of course designed to prevent you could ever convert to KQQRKRP or KQRPKQR. P-slices that are still 100% won with the handicap would certainly be so without it. And with DTC/DTZ you would not really care how they were won. So you would never have to do their bulky successors.

[Edit] perhaps 'totally won' should be softened a little bit here: there will of course be positions where white is checkmated from the start in KQRPKRP, no matter where the Pawns are. Such positions will remain lost whether white is allowed to advance his Pawn or to let a black Queen survive, or not. So the actual test would be to recalculate the P-slice under the assumption that the white or black promotion are winning, rather than losing and then see if there are positions in it that change result. If all second promotions are 'don't' cares, you just assume the worst, and there is no need to calculate them.

I guess what you really want is a generator for WDLX, where X is a 'don't know'. Yoou can than start to assume that the positions with a second promotion are X, and then generate backwards through the P-slices to see how far the X propagates. Eventually you will reach X-free P-slices.

[Evert]

You could just dedicate an extra thread to EGT generation, in addition to your search threads. You then either suspend one of the search threads, or the generation thread. That way you would never have to worry about saving the state of the generator.

Yes, that would work too - and it would work very nicely in an environment where I'm allowed to use more than one thread anyway. But I want to have a fall-back option in case I'm running in an environment where I'm not supposed to use more than one core. Of course I can still launch he generator in a separate thread and simply wait for it to finish (or time to run out).

Note that what makes this attractive is the fact that EGTs with Pawns, like KRPPPKRPP, are not really single EGTs at all, but fragment into P-slices. Because you know what Pawn structure you have in the root, you can discard most of the P-slices as unreachable. Especially with blocked Pawns there aren't too many P-slices that you can reach, and you only have to generate for those.

I haven't really thought about how to handle table bases with pawns (other than you lose the symmetry; probably all of it if we're generating for the position we need). Am I far off in thinking that I would simply take the pawns as given, assume they're fixed, and then move the pieces around? Perhaps have one mobile pawn?

My guess is that it would be better to decide statically in the root which EGTs you are going to generate. The time it would take is largely predictable, and explodes with each extra non-Pawn. So when the root is in KRB...KRN... with ... some Pawns, the situation is completely hopeless, with each P-slice being an unsymetrical 6-men. At this stage you probably would plan to do KR...KR... and KB...KN..., to prepare for either trade. The search might reach too many non-sensical material signatures. If one side has a dangerous passer you might want to repare for having to sac your minor for it, and also build that one.

I'd still prefer to leave it to the search to tell me what positions I might need, but it may just be a detail. Certainly deciding just based on the root position will be easier. Still, if the search never probes KR…KR… I'd prefer to not waste time (or storage space, but a 4 men double-sided table should be < 4 MB) generating it, but there would have to be some heuristic against generating "pointless" tablebases to get rid of some of the nonsense that the search explores.
The downside to doing this, of course, is that I don't figure out that I will need a particular tablebase, but that I figure out that I would have needed it. Hopefully before it becomes essential.

The most challenging issue in selective generation is to handle promotions. When you are generating complete EGTs, it is not that much of a problem that KRPPKRP in theory can convert to KQQRKQR: the latter is not that much bigger, Pawns venturing on 48 squares, Queens on 64. But with P-slices a Pawn that was constrained to a file, (and then being able to only reach the forward part of that file) has perhaps 3-4 possible squares, which jumps up to 64 on promotion. Obviously, you would not want to waste time on frivolous promotions.

Now what saves the day here is that in almost all P-slices of KQRPKRP, the game is not only totally won for white, but can actually be won 'with a handicap'. E.g. when you would alter the rules such that a white non-capture with a Pawn counts as an instant loss, and similarly for allowing black to move with a Queen... Most P-slices would still be totally won. This exploits the huge promotion gain or orthodox Chess. End-games that were interesting before promotion tend to become a walk-over after the first promotion. The handicap rules are of course designed to prevent you could ever convert to KQQRKRP or KQRPKQR. P-slices that are still 100% won with the handicap would certainly be so without it. And with DTC/DTZ you would not really care how they were won. So you would never have to do their bulky successors.

Makes sense to me. I would certainly try to avoid KQQRKRP, which would be pretty pointless unless black can promote its pawn immediately. Even then it'll probably simplify very quickly (to mate). I know there are things like KQQK or even KQQQK available out there, but it seems pretty pointless.

There's the tacky issue of underpromotions, which are probably completely irrelevant except maybe promotion to knight (with check). I'd prefer to create tables that assume I will win when I promote a pawn, and then let the search tell me what I need afterwards.

[Edit] perhaps 'totally won' should be softened a little bit here: there will of course be positions where white is checkmated from the start in KQRPKRP, no matter where the Pawns are. Such positions will remain lost whether white is allowed to advance his Pawn or to let a black Queen survive, or not. So the actual test would be to recalculate the P-slice under the assumption that the white or black promotion are winning, rather than losing and then see if there are positions in it that change result. If all second promotions are 'don't' cares, you just assume the worst, and there is no need to calculate them.

I guess what you really want is a generator for WDLX, where X is a 'don't know'. Yoou can than start to assume that the positions with a second promotion are X, and then generate backwards through the P-slices to see how far the X propagates. Eventually you will reach X-free P-slices.

Sounds like a good use for that redundant bit in two-sided bitbases.