On-demand tablebase generation

[hgm]

I never saw the use of verification code. Your generator is either sound, or it isn't. Your hardware is either sound, or it isn't. If it isn't, you can also not trust any verification code you run on it. Doing verification always seemed an inconsistent form of paranoia to me.

Pawns are interesting. But there is no need to ever make them mobile. Moving a Pawn is a conversion into another EGT, which you should have generated first. You should then simply probe the (legal!) moves of the Pawn into that pre-generated EGT, in the verification step. After constructing the mates you can probe the pre-generated successor EGTs with the Pawn moves from the current. (In practice this means you have to OR the successor tables into the current one, with the caveat that for some placements of the mobile pieces the successor might not be reachable with the particular Pawn move, because they block it.)

So the general way to do it is do a forward search from the current Pawn structure with Pawn moves and null-moves only, and the pieces just represented by a count that you decrease on any capture move that the Pawns make. Eventually these bring a Pawn on the 8th rank. As a first approximation you can consider those won when white is to move and not in check. The forward search then determines in which order you will build the P-slices: as long as a slice has P-moves to a P-slice that has not yet been built, you built that first. 8th-rank P-slices can only be built after the successor that is created by capturing the 8th-rank Pawn has been built. So effectively Pawns disappear when they reach the 8th rank, so that eventually you will end up in a leaf (representing a Pawn-less EGT). Then you can start generating that end-game, and work your way back towards the root of the search tree.

[Evert]

I never saw the use of verification code. Your generator is either sound, or it isn't.

Correct. The purpose is to help catch bugs in the tablebase generator. There's no need to run the verification in production code.

It's actually fast enough that it doesn't matter either way, but just like debugging code for things like the search and move generator, it should be switched off afterwards.

Anyway, the reason for going back to look at it was that I'd noticed an odd case of the program throwing away its bishop in a KBNK ending (and refusing to take the bishop when given the choice). Turns out this was a problem with the probing code rather than the tablebase: capturing the bishop converts to KNK, for which there is no tablebase, which caused the probing code to return "position invalid/unknown", which was interpreted by the search as "move was illegal". Oops.

Fixed it now by always returning a draw score when there is a single minor on the board (because I didn't feel like generating KBK and KNK), but I should probably handle this differently...

Pawns are interesting. But there is no need to ever make them mobile. Moving a Pawn is a conversion into another EGT, which you should have generated first. You should then simply probe the (legal!) moves of the Pawn into that pre-generated EGT, in the verification step. After constructing the mates you can probe the pre-generated successor EGTs with the Pawn moves from the current. (In practice this means you have to OR the successor tables into the current one, with the caveat that for some placements of the mobile pieces the successor might not be reachable with the particular Pawn move, because they block it.)

So the general way to do it is do a forward search from the current Pawn structure with Pawn moves and null-moves only, and the pieces just represented by a count that you decrease on any capture move that the Pawns make. Eventually these bring a Pawn on the 8th rank. As a first approximation you can consider those won when white is to move and not in check. The forward search then determines in which order you will build the P-slices: as long as a slice has P-moves to a P-slice that has not yet been built, you built that first. 8th-rank P-slices can only be built after the successor that is created by capturing the 8th-rank Pawn has been built. So effectively Pawns disappear when they reach the 8th rank, so that eventually you will end up in a leaf (representing a Pawn-less EGT). Then you can start generating that end-game, and work your way back towards the root of the search tree.

That would work too, of course. At the moment my generator isn't really set up in a way to make that easy, unfortunately.

[Evert]

Hmm… looks like I'm not quite done with debugging yet:

Code: Select all

+--+--+--+--+--+--+--+--+
|  |+ |  |+ |  |+ |  |+ |
+--+--+--+--+--+--+--+--+
|+ |  |+ |  |+ |  |+ |  |
+--+--+--+--+--+--+--+--+
|  |+ |  |+ |  |+ |  |+ |
+--+--+--+--+--+--+--+--+
|+ |  |+ |  |+ |  |+ |  |
+--+--+--+--+--+--+--+--+
|  |+ |  |+ |  |+ |  |+ |
+--+--+--+--+--+--+--+--+
|+ |  |+ |R |+ |  |+ |  |
+--+--+--+--+--+--+--+--+
|  |+ |  |+ |  |+ |  |+ |
+--+--+--+--+--+--+--+--+
|K |  |k |  |+ |  |+ |  |
+--+--+--+--+--+--+--+--+
TB score: Mate in 21 ply (11 moves)
Rd3-b3 Mate in 20 ply (10 moves)
Rd3-c3 Mate in 20 ply (10 moves)
Rd3-g3 Mate in 20 ply (10 moves)
Rd3-h3 Mate in 20 ply (10 moves)
Ka1-a2 Mate in 20 ply (10 moves)
Rd3-a3 Mate in 22 ply (11 moves)
Rd3-e3 Mate in 22 ply (11 moves)
Rd3-f3 Mate in 22 ply (11 moves)
Rd3-d4 Mate in 26 ply (13 moves)
Rd3-d5 Mate in 26 ply (13 moves)
Rd3-d6 Mate in 26 ply (13 moves)
Rd3-d7 Mate in 26 ply (13 moves)
Rd3-d8 Mate in 26 ply (13 moves)
Rd3-d1 Mate in 26 ply (13 moves)
Rd3-d2 draw

[tpetzke]

The missing draw for Rd1 is especially serious.

I tried your speed tuning and its a bit more difficult for me.

First in the KPK endgame I init the table from the promotions also with higher distance mates, which would be missing in the new/old tables.

Then in the Search for New Mates the former lost positions are not enough to find all New Mates, I have to transform each possible lost position back to the 8 original positions it could have come from (in the 8fold symmetries scheme), which I don't. Otherwise I miss positions. An example would be WK/BK/WR = C3/A1/D2 which was not recognized as Mate in 2 because its source position B3/A1/D2 was mapped away.

I have a working method were I store all found won positions in an array of 28 vectors (Mate in 28 is the longest distance) and just use the positions from the vector in the search of new lost positions. This gives a bit of a speedup but is a bit ugly. I probably go back to plain and stupid.

Thomas...

[Evert]

The missing draw for Rd1 is especially serious.

It's not as worrying as it seems when you realise that it only picks up Rd2 as a draw because white's only move is Kxd2, in other words, if you discard captures the position is stalemate.

The problem is with detecting whether successor positions are lost. If I return false here if any captures are possible the results are fine. Now, the position following the capture should also have been scored as a draw, but somehow it isn't. I haven't investigated yet.

First in the KPK endgame I init the table from the promotions also with higher distance mates, which would be missing in the new/old tables.

Then in the Search for New Mates the former lost positions are not enough to find all New Mates, I have to transform each possible lost position back to the 8 original positions it could have come from (in the 8fold symmetries scheme), which I don't. Otherwise I miss positions. An example would be WK/BK/WR = C3/A1/D2 which was not recognized as Mate in 2 because its source position B3/A1/D2 was mapped away.

Most of the complexity for me is hidden in the probe/store code. If I need to check the score of a position the code that does the lookup is the same that is used by the probing code. This takes care of mapping the position to the "canonical" layout. If I store the value of a position I do the same, so it doesn't matter if a move takes me out of the canonical layout: it gets mapped there when I do a store anyway.

This keeps everything fairly simple and easy to debug, but it's probably not entirely optimal (I always remap coordinates, even if I could know that I don't have to). I did have some problems with what HGM calls "quasi-symmetric positions" (see http://home.hccnet.nl/h.g.muller/EGT7/sympos.html), mainly because I didn't really understand what that was about (a diagram would have helped).

In my loop over positions I only loop over positions in the canonical layout (of course).

[hgm]

The problem I address there is that the canonical sector is defined from only a subset of the pieces. (E.g. in Nalimov the two Kings: white in the a1-d1-d4 triangle, and black on or below the a1-h8 diagonal.) So in case both Kings are on the diagonal, but some other pieces are not, it is not defined what the canonical representation is. Of course you can take all pieces into account to avoid that, but the space savings are very small, and it makes it more difficult to exploit exchange symmetry of two equal pieces (which would buy you a factor 2 or 6...)

So it is more convenient to keep both versions of the position in the table. But then you have to artificially enforce their equivalence, because somethimes you will reach one with a move from the canonical sector, (A King stepping onto the diagonal in Nalimov), sometimes the other. So each time you update one of them, yu have to update the other.

[Evert]

The problem is with detecting whether successor positions are lost. If I return false here if any captures are possible the results are fine. Now, the position following the capture should also have been scored as a draw, but somehow it isn't. I haven't investigated yet.

Ah, found it: captures should be excluded when doing a retro move, but they weren't everywhere. This caused the position in the tablebase (after KxR) to be overwritten with a spurious "lost" score.

Now to figure out why KQKR stops after only 10 iterations...

[Evert]

The problem I address there is that the canonical sector is defined from only a subset of the pieces. (E.g. in Nalimov the two Kings: white in the a1-d1-d4 triangle, and black on or below the a1-h8 diagonal.) So in case both Kings are on the diagonal, but some other pieces are not, it is not defined what the canonical representation is. Of course you can take all pieces into account to avoid that, but the space savings are very small, and it makes it more difficult to exploit exchange symmetry of two equal pieces (which would buy you a factor 2 or 6...)

So it is more convenient to keep both versions of the position in the table. But then you have to artificially enforce their equivalence, because somethimes you will reach one with a move from the canonical sector, (A King stepping onto the diagonal in Nalimov), sometimes the other. So each time you update one of them, yu have to update the other.

Yup.
Once I'd spent an evening hunting for the bug that was caused by ignoring this (which lead to an inconsistency) it was perfectly clear what it meant.

Sometimes you have to get burned before the message sinks in.

[hgm]

Indeed, I also had a very hard time debugging this. Until I imagined the following picture, then it suddenly became obvious:

Code: Select all

_______________________________|__________________________________
|                        |     |     |                           |
|<                    stored part   >|<     omitted part        >|
|                        |     |     |                           |
|<      true canonical sector >|     |                           |
|                        |  Q  |  Q' |                           |
|                        | / \ | / \ |                           |
|                        |/   \|/   \|                           |
|                        /     /     \                           |
|                       /|    /|\    |\                          |
|                      / |   / | +   | +                         |
|                     /  |  /  |  \  |  \                        |
|                    P   | /   | du\ |   P'                      |
|                        |/    | pli\|                           |
|                        /     | cats\                           |
|                       /|     |     |\                          |
|                      R |     |     | R'                        |
|________________________|_____|_____|___________________________|
                               |
                           symmetry axis

I have a hard time making my code faster, btw. I seem to get stuck at about 750ms real time (560 ms CPU time). Marcel's Pretty-Fast generator takes 129 ms real time on my machine (but that includes counting). That is similar if you account for the factor 8 lost on symmerty. SO I guess this is close to the best one can do, with a single CPU.

[hgm]

Of course it is also possible to exploit color binding to reduce the amount of work, (or even memory requirement). In the case of KBNK you only have to consider positions with the Bishop on light squares. The others are mirror images. This would not work in the presence of a totally asymmetric piece (but left-right symmetry, or even rotation symmetry would be OK.) But even then, for on-the-fly generation, you would know what color your Bishop has. Note that with 8-fold symmetry you cannot exploit this on even-size boards, as mirroring breaks the color binding.

KBBK speeds up a factor 4 that way, as would KBKB. (You could exploit that in 8-fold symmetry, by separating like- and unlike-Bishop positions, to gain a factor 2) In On-the-fly generation these would of course be accompanied by Pawns. So even though it is a special case, only applicable with Bishops, it would be helpful in a lot of end-games, meaning that in those end-games you can afford more, or less-favorably-placed Pawns.

Exploiting the space savings is a bit more tricky. With the standard layout the table would only be used in a checkered fashion. If the color-bound piece does not determine the highest bits of the index (and in my generator the highest bits are derived from the white-King rank), you could interleave successive slices to fill up each other's holes. I.e. in stead of using

index = FACTOR*(bishopSqr + 64*whiteKingRank) + otherStuff

one can use

index = FACTOR*(bishopSqr + 33*whiteKingRank) + otherStuff

which leaves only 3% of the space unused, rather than 50%.

So I guess I will alter the generator such that all loops over the non-Kings contain a statement

if(color[sqrN] & colorBindingN) continue;

where each piece N has its own colorBinding variable, and color[] contains 1 (light) and 2 (dark) squares. So that the initialization can test if a piece is color bound, and set its colorBinding variable to 1 or 2 depending on whether it should be on light or dark squares. (And keep it 0 for ergodic pieces.) The strides used to increment the index when scanning the piece should also be variables rather than constants, so that the initialization code can adapt them likewise.

Some other tricks that I found useful in optimizing:

When you mark 'broken positions' that have two white pieces coinciding as won with wtm during the mate-costruction phase, there is no need to test for board occupancy during white retro-moving. Because when it is already marked as 'won', it can never become 'newlyWon'. This is particularly useful for leaper retro-moves. (For sliders occupancy also blocks further moving along the ray, so you cannot ignore occupancy.) I use this for white-King retro-moving. (The generator is written for orthodox-Kings only, and these are leapers.) There is also no need to worry that you might stumble on a black King, as you could only do that from a position where the Kings are standing next to each other. And such positions should never be marked as 'lost' with black to move.

I construct the mates by joining attack sets of all pieces other than black King (where black pieces contribute their 'occupied' bit as 'attack set'). But I remove the white King from that (it could be 'protected' by another white piece, but that still should not deter you from capturing it!). This leaves the black-King 'no-go area', which initializes the won[] bitmap. Then I remove all the occupied squares, plus the neighborhood of the white King, where black could never be mated (because he can never be there at all, or can capture the white King with his own King). These are the 'potential mates', which basically is the 'potentially lost' set of the zeroth iteration. It has to be verified in the usual way, against the won[] bitmap (at this stage the no-go area), by shifting and masking with the latter to see if there is an accessible square next to the King where it could flee (which would clear the bit for the corresponding King position). That finally leaves the mate candidates in the current King bundle, (usually none at all), which then still have to be verified through moves of the other black pieces (if any) in the usual way.

To calculate for a game where stalemate is a loss, you would not have to start with the checks as mate candidates, but basically with the entire board (~0ull & ~occupied & ~kingAttacks[whiteKingSqr]).