Endgame tablebase generation for newbies

[Nomis]

Thanks,

I had already filtered the promote-in-1 positions by running my quiescence search on them to get that number of 12762.

After your message I checked with a 3-ply full search, and all of them are winning. There's only these six positions that need to promote to a rook instead of a queen:



[d]8/1P6/8/8/8/8/8/5K1k/ w
(well, that first one could actually promote to a queen, but not immediately)

[d]8/1P6/k7/8/K7/8/8/8/ w
[d]8/1P6/k7/8/1K6/8/8/8/ w
[d]8/k1P5/8/K7/8/8/8/8/ w
[d]8/k1P5/8/1K6/8/8/8/8/ w
[d]8/k1P5/8/2K5/8/8/8/8/ w

[Nomis]

I'm replying to myself, as I started testing my table with random positions, and have new numbers after fixing a small bug in the backwards-move generation:

Code: Select all

Found 12762 positions where white can promote in 1 ply
Found 11278 positions where white can promote in 2 plies
Found 11300 positions where white can promote in 3 plies
Found 9513 positions where white can promote in 4 plies
Found 9624 positions where white can promote in 5 plies
Found 7604 positions where white can promote in 6 plies
Found 7864 positions where white can promote in 7 plies
Found 5729 positions where white can promote in 8 plies
Found 10511 positions where white can promote in 9 plies
Found 5777 positions where white can promote in 10 plies
Found 2564 positions where white can promote in 11 plies
Found 1982 positions where white can promote in 12 plies
Found 1416 positions where white can promote in 13 plies
Found 1433 positions where white can promote in 14 plies
Found 1457 positions where white can promote in 15 plies
Found 1315 positions where white can promote in 16 plies
Found 1122 positions where white can promote in 17 plies
Found 966 positions where white can promote in 18 plies
Found 941 positions where white can promote in 19 plies
Found 795 positions where white can promote in 20 plies
Found 685 positions where white can promote in 21 plies
Found 597 positions where white can promote in 22 plies
Found 670 positions where white can promote in 23 plies
Found 560 positions where white can promote in 24 plies
Found 586 positions where white can promote in 25 plies
Found 502 positions where white can promote in 26 plies
Found 572 positions where white can promote in 27 plies
Found 481 positions where white can promote in 28 plies
Found 307 positions where white can promote in 29 plies
Found 213 positions where white can promote in 30 plies
Found 78 positions where white can promote in 31 plies
Found 36 positions where white can promote in 32 plies
Found 22 positions where white can promote in 33 plies
Found 15 positions where white can promote in 34 plies
Found 8 positions where white can promote in 35 plies
Found 4 positions where white can promote in 36 plies
Found 3 positions where white can promote in 37 plies
Found 2 positions where white can promote in 38 plies
Found 0 positions where white can promote in 39 plies
Total: found 111294 wins
Table contents: 168024 positions, 111294 wins, 56730 draws (and 28584 invalid positions)

I'm so glad I decided to try this. This is so interesting.

So far I've found that stockfish on lichess will happily capture the king when given the opportunity :https://lichess.org/analysis/standard/8 ... /P7/8/8/_w

And also that my engine has a bug as it sees a win in a completely drawn position:

[d]8/8/8/8/K7/P2k4/8/8 b - - 0 1
(something related to promotions in QS, I suspect)

[syzygy]

There exist statistics for distance to mate, but I don't think it exists for distance to promotion. You should be careful there anyway: not all promotions are winning. You should calculate until the first move with the promoted piece.

It think it is sufficient to check that the promoted piece cannot be immediately captured by the other side. If promotion to Q leads to stalemate, you can still promote to R. (Q promotions seem irrelevant for KPK).

[hgm]

True. But running QS to establish that is needlessly expensive. You can simply seed the EGT by declaring all positions with the Pawn on the 8th rank and white to move as won. Because white cannot be in check if black has only a King. (That is, he would simply capture the black King in that case, and thus win anyway.) Then you start retrograding from those.

[Spill_The_Tea]

I thought having the King on c6, like so:
8/k1P5/2K5/8/8/8/8/8 w - - 0 1

would also force white to promote to a rook. And while it is faster (DTM2) - 1. c8=R Ka6 2. Ra8# , you can still safely promote to a queen after 1. Kd7 Kb6 2. c8=Q ...

[Nomis]

Ah -- good catch. I actually printed the six positions where the 3-ply searched returned a score somewhere above the value of rook but below a queen.

But the position you gave is a mate in 2. So.. I counted that as above a queen

[syzygy]

True. But running QS to establish that is needlessly expensive. You can simply seed the EGT by declaring all positions with the Pawn on the 8th rank and white to move as won. Because white cannot be in check if black has only a King. (That is, he would simply capture the black King in that case, and thus win anyway.) Then you start retrograding from those.

But running QS, if you want to call it that, is simple and cheap. If white can promote and the promotion square is either defended by white's king or not attacked by black's king, white wins.

[hgm]

Well, one of the things that makes it expensive is that you would have to run it on all 4*64*64 = 256*64 positions with a promoted Pawn. If you would just loop over the 4 Pawn locations, and for each of those over the 5 adjacent squares for black King location (20 things in total, 2 of which fall off-board for the a-Pawn), you could just correct the 20*64 losses (that you had assigned to them by default) obtained by adding a white King to draws / non-losses, without further testing. This would have unjustly declared the positions where the Pawn was protected to draws, but only the 3 non-Rook Pawns have 2 of those for 4 of the 5 (Pawn, black King) constellations, and those . You would finally correct those 3*4*2 = 24 positions back to losses.

It is usually much faster to selectively generate positions that satisfy a certain condition (such as adjacent K and P), then to run through all positions and test whether they satisfy the condition. If the conditions is only rarely satisfied.

I admit that the normal 'verification' step to judge whether 'potential losses' really have no move to a non-won wtm position is somewhat similar to a QS node, but in an efficient generator you would apply it only to predecessors of newly won positions. Which usually is only a small fraction of all positions. And codewise you have the example that it just reuses code you needed anyway during the iteration.

[abulmo2]

Hello,

I'm digging up this old thread to post a follow-up question.

Using the very valuable advice posted in this thread, I made a program to build a bit table for KPK endgames.

Here's the output:

Code: Select all

Total: found 111721 wins
Table contents: 168024 positions, 111721 wins, 56303 draws (and 28584 invalid positions)

(That's only half of it, with the pawn on files A to D)

Now, how can I check these results ? Does that look right ?
Is there somewhere an equivalent to the perft numbers ?

Thanks

I think that the correct numbers are: 111282 wins, 54394 draws and 30932 invalid positions (can capture opponent king).

[AlvaroBegue]

You can also run a consistency check. You can visit every position and check that the value it got assigned in the tablebase is consistent with the value of its children.