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
Endgame tablebase generation for newbies
Moderators: hgm, Rebel, chrisw
-
- Posts: 18
- Joined: Sun Jan 03, 2021 1:19 pm
- Full name: Simon Reed
-
- Posts: 18
- Joined: Sun Jan 03, 2021 1:19 pm
- Full name: Simon Reed
Re: Endgame tablebase generation for newbies
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:
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)
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)
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)
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Endgame tablebase generation for newbies
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).
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Endgame tablebase generation for newbies
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.
-
- Posts: 24
- Joined: Mon Dec 17, 2018 3:33 am
- Full name: Jase de Lace
Re: Endgame tablebase generation for newbies
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 ...
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 ...
-
- Posts: 18
- Joined: Sun Jan 03, 2021 1:19 pm
- Full name: Simon Reed
Re: Endgame tablebase generation for newbies
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
But the position you gave is a mate in 2. So.. I counted that as above a queen
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Endgame tablebase generation for newbies
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 wrote: ↑Sat Jan 16, 2021 10:30 pm 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.
-
- Posts: 27807
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Endgame tablebase generation for newbies
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.
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.
-
- Posts: 433
- Joined: Fri Dec 16, 2016 11:04 am
- Location: France
- Full name: Richard Delorme
Re: Endgame tablebase generation for newbies
I think that the correct numbers are: 111282 wins, 54394 draws and 30932 invalid positions (can capture opponent king).Nomis wrote: ↑Fri Jan 15, 2021 9:39 pm 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:(That's only half of it, with the pawn on files A to D)Code: Select all
Total: found 111721 wins Table contents: 168024 positions, 111721 wins, 56303 draws (and 28584 invalid positions)
Now, how can I check these results ? Does that look right ?
Is there somewhere an equivalent to the perft numbers ?
Thanks
Richard Delorme
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Endgame tablebase generation for newbies
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.