Endgame tablebase generation for newbies

[asanjuan]

Hello again.

I would like to understand how to make my own tablebases, starting with something basic, like the 3-men tablebases. I have read the CPW, but it leaves me with a few unsolved questions, for example:

- a backwards move generation is needed?

- How do you handle the captures in this backward move generation? I mean: if I have a KPK position, handling captures means that I should generate KPKN previous position where the pawn captures the knight, and so it produces the KPK position that I have? It is quite confusing.

or this one, very nice:
- how do you handle the promotions? In a KPK endgame, when promoting, the position is transformed in a KQK endgame... How to manage this situations?

You can conclude that I'm a bit lost in this matter. It is true. So I need a reference manual, or a simple explanation, before reading any other's sources.

I need to understand the basic ideas.
Can someone give me an advice?

Regards.

[hgm]

- a backwards move generation is needed?

Not really; it is mainly a (great) speedup. In principle each iteration could loop through the entire tablebase, generating forward moves from every yet-undecided position, to examine the DTx of the daughter positions, and conclude its own DTx from those. Where a position is won if any of its daughters is won (and then gets the DTx of that daughter + 1), and is lost if all of its daughters are lost (getting the largest DTx of any daughter, if you count in full-moves).

It is a bit expensive to do this for all possible positions in every iteration, though. It is much faster to keep track of which positions are 'newly won' or 'newly lost' (i.e. in the latest iteration), because only the parents of those (which you reach by backward moving) then need to be treated this way. (And for the won positions, you would not even have to generate forward moves, because the position you reached it through is guaranteed to be its daughter with the smallest DTx, if it doesn't have a smaller DTx already.

Note that forward captures would reach into a successor EGT.

- How do you handle the captures in this backward move generation? I mean: if I have a KPK position, handling captures means that I should generate KPKN previous position where the pawn captures the knight, and so it produces the KPK position that I have? It is quite confusing.

Backward captures ('un-captures') would leave the uncaptured piece on the from-square (which is the to-square of the corresponding forward move). If you build the EGT using backward moves, you should start (next to identifying all checkmate positions) by 'seeding' it from all its possible successor EGTs. You can either do this by generating un-captures from these successors' won positions (you would do this on every iteration when building DTM), or you could just loop through the EGT you are building, to generate forward captures into the successor EGT, and probe the DTx there.

In my old generator I don't even make a distinction between the EGTs (as successors after capture are negligibly small anyway), and absorb all successor EGT into the main one, by using the 'broken positions' in the latter to store them. (I use the convention that captured pieces are put on the same square as the white King.) Then I can generate the whole thing as if it was a single EGT.

or this one, very nice:
- how do you handle the promotions? In a KPK endgame, when promoting, the position is transformed in a KQK endgame... How to manage this situations?

Indeed, promotions are the most nasty aspect. In principle KQK, KRK, KBK and KNK are all 'promotion-successors' of KPK. The forward (under-)promotion moves of KPK lead to positions in these successors, and you would have to probe them all to see which has the best DTx. That means they would have to be built first, before you can start building KPK. And this time they are of the same size (equal number of men) as the one you really want to generate!

When you use backward moving, you loop through all KQK, KRK etc. EGTs to find won positions with the Q, R, ... on the 8th rank, so you can 'unpromote' them to a Pawn on the 7th, and mark all position in KPK you can reach that way as won.

[asanjuan]

Oh... it is even harder than what I thought!

[AlvaroBegue]

I think hgm gave you a lot of good information, but there is a much easier way to do things "for newbies".

In order to generate some EGT, first make sure all the successor EGTs are available: If they are not, generate them recursively. Then have an array of signed char indicating our current score for each position in the EGT, with 0 meaning "unknown", 128-n meaning "mate in n" and -(128-n) meaning "mated in n" or something of that sort. Now loop over all positions in the EGT and update the score by doing a depth-1 search, looking up in the successor EGTs if needed.

This scheme is wasteful in several places (notably looking up successor EGTs in every iteration), but it will probably get you to 4-piece EGTs without much trouble.

[tpetzke]

This is how I do it for the 3 men on the fly when the engine starts

I generate the tables in the order KRK, KQK, KPK

1. Init.
Generate all positions with black to move and look whether they are mate (or stalemate). Store them as "MATED in 0". For each found mate generate the retro moves and all positions reached store them as "MATE in 1"

Check whether you have a stalemate. Store that as DRAW.

Check whether the black king can capture the unprotected white piece. Store them also as DRAW.

If the white piece is a pawn and in the position is at the 8th rank, replace it by a queen and rook, look into the already generated KRK and KQK table and store the better of the scores in the KPK table (you have to lookup both because sometimes KRK wins, where KQK shows a stalemate)

2. Loop over your "MATE in 1" positions. generate the retro moves in that position and for each resulting position check whether ALL forward moves lead to nothing better than "MATE in 1". If so, this position is a "MATED in 1" position.

3. Loop over your "MATED in 1" positions, generate all retro moves and all positions you reach are a MATE in 2.

4. Start again with point 2, but now look for MATE in 2 etc...

Stop if no new positions are found, all positions you did not touch are DRAW.

If it works you might explore 8fold symmetries later, but this is a bit more tricky. I recommend to try the plain stupid stuff first.

That's it.

Thomas

[asanjuan]

I think hgm gave you a lot of good information, but there is a much easier way to do things "for newbies".

Oh, yes please, go ahead...

In order to generate some EGT, first make sure all the successor EGTs are available: If they are not, generate them recursively. Then have an array of signed char indicating our current score for each position in the EGT, with 0 meaning "unknown", 128-n meaning "mate in n" and -(128-n) meaning "mated in n" or something of that sort. Now loop over all positions in the EGT and update the score by doing a depth-1 search, looking up in the successor EGTs if needed.

This scheme is wasteful in several places (notably looking up successor EGTs in every iteration), but it will probably get you to 4-piece EGTs without much trouble.

Ok. The "newbie" approach looks more clear.

[asanjuan]

This is how I do it for the 3 men on the fly when the engine starts

I generate the tables in the order KRK, KQK, KPK

1. Init.
Generate all positions with black to move and look whether they are mate (or stalemate). Store them as "MATED in 0". For each found mate generate the retro moves and all positions reached store them as "MATE in 1"

Check whether you have a stalemate. Store that as DRAW.

Check whether the black king can capture the unprotected white piece. Store them also as DRAW.

If the white piece is a pawn and in the position is at the 8th rank, replace it by a queen and rook, look into the already generated KRK and KQK table and store the better of the scores in the KPK table (you have to lookup both because sometimes KRK wins, where KQK shows a stalemate)

2. Loop over your "MATE in 1" positions. generate the retro moves in that position and for each resulting position check whether ALL forward moves lead to nothing better than "MATE in 1". If so, this position is a "MATED in 1" position.

3. Loop over your "MATED in 1" positions, generate all retro moves and all positions you reach are a MATE in 2.

4. Start again with point 2, but now look for MATE in 2 etc...

Stop if no new positions are found, all positions you did not touch are DRAW.

If it works you might explore 8fold symmetries later, but this is a bit more tricky. I recommend to try the plain stupid stuff first.

That's it.

Thomas

Pretty clear explanation!
There is a lot of work to be done!

Thank you very much.

PS: I will post again when all the "stupid stuff" is done.

[AlvaroBegue]

I think hgm gave you a lot of good information, but there is a much easier way to do things "for newbies".

In order to generate some EGT, first make sure all the successor EGTs are available: If they are not, generate them recursively. Then have an array of signed char indicating our current score for each position in the EGT, with 0 meaning "unknown", 128-n meaning "mate in n" and -(128-n) meaning "mated in n" or something of that sort. Now loop over all positions in the EGT and update the score by doing a depth-1 search, looking up in the successor EGTs if needed.

This scheme is wasteful in several places (notably looking up successor EGTs in every iteration), but it will probably get you to 4-piece EGTs without much trouble.

Rereading my post, I notice I left two important things out, although perhaps they are obvious.

One thing is that the entries in the char array should be initialized to 0.

The other one is that one keeps iterating through the whole table doing depth-1 searches, until no nodes change value. At that point, anything that is still "0=unknown" can be interpreted as "0=draw".

[Nomis]

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

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 10583 positions where white can promote in 9 plies
Found 5816 positions where white can promote in 10 plies
Found 2529 positions where white can promote in 11 plies
Found 1975 positions where white can promote in 12 plies
Found 1402 positions where white can promote in 13 plies
Found 1408 positions where white can promote in 14 plies
Found 1455 positions where white can promote in 15 plies
Found 1320 positions where white can promote in 16 plies
Found 1139 positions where white can promote in 17 plies
Found 1002 positions where white can promote in 18 plies
Found 1015 positions where white can promote in 19 plies
Found 930 positions where white can promote in 20 plies
Found 772 positions where white can promote in 21 plies
Found 661 positions where white can promote in 22 plies
Found 655 positions where white can promote in 23 plies
Found 558 positions where white can promote in 24 plies
Found 584 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 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

[hgm]

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.