Syzygy tablebases

[hgm]

The other trouble with wanting just the interesting tables is often they have the uninteresting tables as dependencies.

i.e. for a simple generator KRPP v KRP depends on all KRxx v KRx tables being generated first, however uncommon they are in practice and however unlikely they are to impact the table you actually want

You could try to build a clever generator that escapes some of those dependencies but doing so correctly is not trivial.

Actually it should not be so bad. For one, with DTZ you only need to prove a certain promotion is won, and promotion to Q would usually do the trick. If it does, there is no reason to consider any other promotions.

Secondly, you don't care how the promotion to Q wins. You can afford to prove it wins without a second promotion of teh same side, even if that is vastly more cumbersome. A win is a win, in DTZ.

Finally, KRPPKRP is not really a monolitic table. It is a large collection of 4-men (KRKR) P-slices, that have a partial order relation between them. Promotion in Chess is so decisive, that in the large majority of these P-slices the one to promote first wins trivially. That is, the resulting KQRPKRP end-game succeeding that P-slice might still be 100% winnable under additional restrictions on the winner, e.g. adopting the additional rule that (surviving) opponent promotion instantly loses, while own second promotion (or even Pawn pushing) is forbidden. Then you would never need any KQRxKRx with x != P to solve that. And if the losing Pawn is not very close to promotion, such positions are still trivially completely won. And their predecessor P-slices can then be solved based on that win.

P-slices that cannot be 100% won that way, e.g. because the losing Pawn is already advanced too far, in an initial iteration could be declared 100% losing. That would still not be very damaging, because likely (with a QR vs R majority) you can pretty easily prevent advance of the Pawn. So these could still be proved 100% winning by conversions that do win trivial (R-for-R trades, or even Q-for-R trades). This way you would solve the overwhelming majority of the P-slices.

Note that the troublesome P-slices are usually those with many Pawns on 7th rank. These are usually of no interest, as the recommended way of winning their pre-decessors would not be to march a 2nd and 3rd Pawn to the 7th rank once you get your 1st one there, but immediately promote that first one, and finish the job with that Queen. So in a real game you would not need them, because they are sort of unreachable: to get to them you would have to go through P-slices that can already be won inother ways. So you might not have all of KRPPKRP, but you would have all of it you ever need. And even if you don't, it is better to have some that you could use, than nothing at all.

[Rein Halbersma]

Partial Information Endgame Databases were already described 10 years ago by the Chinook team that solved checkers. They indeed consider promotions into other endgames and order the subendgames by the rank of the most advanced pawn. https://webdocs.cs.ualberta.ca/~nathans ... abases.pdf

[Dirt]

The other trouble with wanting just the interesting tables is often they have the uninteresting tables as dependencies.

i.e. for a simple generator KRPP v KRP depends on all KRxx v KRx tables being generated first, however uncommon they are in practice and however unlikely they are to impact the table you actually want

You could try to build a clever generator that escapes some of those dependencies but doing so correctly is not trivial.

Actually it should not be so bad. For one, with DTZ you only need to prove a certain promotion is won, and promotion to Q would usually do the trick. If it does, there is no reason to consider any other promotions.

Secondly, you don't care how the promotion to Q wins. You can afford to prove it wins without a second promotion of teh same side, even if that is vastly more cumbersome. A win is a win, in DTZ.

Finally, KRPPKRP is not really a monolitic table. It is a large collection of 4-men (KRKR) P-slices, that have a partial order relation between them. Promotion in Chess is so decisive, that in the large majority of these P-slices the one to promote first wins trivially. That is, the resulting KQRPKRP end-game succeeding that P-slice might still be 100% winnable under additional restrictions on the winner, e.g. adopting the additional rule that (surviving) opponent promotion instantly loses, while own second promotion (or even Pawn pushing) is forbidden. Then you would never need any KQRxKRx with x != P to solve that. And if the losing Pawn is not very close to promotion, such positions are still trivially completely won. And their predecessor P-slices can then be solved based on that win.

P-slices that cannot be 100% won that way, e.g. because the losing Pawn is already advanced too far, in an initial iteration could be declared 100% losing. That would still not be very damaging, because likely (with a QR vs R majority) you can pretty easily prevent advance of the Pawn. So these could still be proved 100% winning by conversions that do win trivial (R-for-R trades, or even Q-for-R trades). This way you would solve the overwhelming majority of the P-slices.

Note that the troublesome P-slices are usually those with many Pawns on 7th rank. These are usually of no interest, as the recommended way of winning their pre-decessors would not be to march a 2nd and 3rd Pawn to the 7th rank once you get your 1st one there, but immediately promote that first one, and finish the job with that Queen. So in a real game you would not need them, because they are sort of unreachable: to get to them you would have to go through P-slices that can already be won inother ways. So you might not have all of KRPPKRP, but you would have all of it you ever need. And even if you don't, it is better to have some that you could use, than nothing at all.

Occasionally you'll need to promote to a knight. In any case, your whole scheme seems non-trivial, and for imperfect results.

[kbhearn]

Actually it should not be so bad. For one, with DTZ you only need to prove a certain promotion is won, and promotion to Q would usually do the trick. If it does, there is no reason to consider any other promotions.

Secondly, you don't care how the promotion to Q wins. You can afford to prove it wins without a second promotion of teh same side, even if that is vastly more cumbersome. A win is a win, in DTZ.

Finally, KRPPKRP is not really a monolitic table. It is a large collection of 4-men (KRKR) P-slices, that have a partial order relation between them. Promotion in Chess is so decisive, that in the large majority of these P-slices the one to promote first wins trivially. That is, the resulting KQRPKRP end-game succeeding that P-slice might still be 100% winnable under additional restrictions on the winner, e.g. adopting the additional rule that (surviving) opponent promotion instantly loses, while own second promotion (or even Pawn pushing) is forbidden. Then you would never need any KQRxKRx with x != P to solve that. And if the losing Pawn is not very close to promotion, such positions are still trivially completely won. And their predecessor P-slices can then be solved based on that win.

P-slices that cannot be 100% won that way, e.g. because the losing Pawn is already advanced too far, in an initial iteration could be declared 100% losing. That would still not be very damaging, because likely (with a QR vs R majority) you can pretty easily prevent advance of the Pawn. So these could still be proved 100% winning by conversions that do win trivial (R-for-R trades, or even Q-for-R trades). This way you would solve the overwhelming majority of the P-slices.

Note that the troublesome P-slices are usually those with many Pawns on 7th rank. These are usually of no interest, as the recommended way of winning their pre-decessors would not be to march a 2nd and 3rd Pawn to the 7th rank once you get your 1st one there, but immediately promote that first one, and finish the job with that Queen. So in a real game you would not need them, because they are sort of unreachable: to get to them you would have to go through P-slices that can already be won inother ways. So you might not have all of KRPPKRP, but you would have all of it you ever need. And even if you don't, it is better to have some that you could use, than nothing at all.

First off, i didn't say not doable, i said not trivial :)

The point about dividing the task by pawn slice certainly holds true.

Not caring about pawnslices and lines with multiple promotion opportunities on the other hand, not so much.
1) races are commonly critical lines for positions that lead to both sides promoting.
2) if your first pawn is stopped by the enemy rook covering the promotion square, pushing the other one of your own pawns to the 7th is a common winning try, especially with connected passers where the pair on the 7th guarantees a queen survives usually and not just a sacrificed opponent rook.

As such, i would consider the slices with 2-3 pawns on the 7th to be rather important.

The paper rein linked i was aware of the concept, and would indeed work provided that enough of the pawn promotions can be resolved to known that that particular pawn slice then becomes known. Since you're doing it slice by slice it wouldn't be much wasted computer time if you find out that your current strategy for partially known dependencies is insufficient for a current slice to resolve to known.

I don't know how much your strategy of just generating the queen promotions would work though - N promotions with check for sure can change things, but even B or R promotions - can you formally prove that if the Q promotion didn't work that the B and R promotion can safely be ignored under some wide set of conditions? There's certainly occasional stalemate defenses that rely on them to avoid - and i'd be uncomfortable assuming i caught every class of them.