On-demand tablebase generation

[hgm]

I was wrong about the stride; with 33 there are still collisions. The smallest you can make it is 40 (5 ranks). This interleaves the 6th, 7th ans 8th rank with the 1st, 2nd and 3rd of the next board. That wastes 8 squares per stored board (the squares of the wrong color in 4th and 5th rank), or 8/32 = 25%.

This could be avoided by changing to a 45-degree rotated board, so that Bishops become orthogonal sliders. The board will be diamond shaped in that representation, though:

Code: Select all

 .  .  .  b1 a2 .  .  .
 .  .  d1 c2 b3 a4 .  . 
 .  f1 e2 d3 c4 b5 a6 .
 h1 g2 f3 e4 d5 c6 b7 a8
 .  h3 g4 f5 e6 d7 b8 .
 .  .  h5 g6 f7 e8 .  .
 .  .  .  h7 g8 .  .  .

But it is possible to lay out such a board in memory without any losses, when you map it on 9x7 before linearizing:

Code: Select all

xx......xxxx....xxxxxx..xxxxxxxx..xxxxxx....xxxx......xx
                                xx......xxxx....xxxxxx..xxxxxxxx..xxxxxx....xxxx......xx
                                                                xx......xxxx....xxxxxx..xxxxxxxx..xxxxxx....xxxx......xx

The stride for the Bishop would than be just 32 times larger than that of the previous piece, and only at the edges of the table there would remain a few holes that are not filled in. Another advantage is that it becomes easier to distribute the Bishop moves over several loops that are more cache friendly (which might become imprtant when you do 5-men, and must rely heavily on DRAM). You can do horizontal moves in one loop, and vertical moves in another, just as with Rooks. The index remains a trivial function of the standard square numbering, so that all steps of a slider move have the same square-number difference on the board and the same board step always translates to the same index step.

For KBBK exploiting color binding of the second Bishop didn't give me any significant speedup, btw. This is of course because with like Bishops there is nothing to do, so that the generation time is already about half of that for KBNK to start with. So KBBK binding the first Bishop to 1 color only took 180ms. Of course you would lose that advantage in the presence of Pawns, where KBKB can be generally won with like as well as unlike Bishops. So in general it would still pay to exploit a second color-bound piece.

[Evert]

So I seem to have developed a new hobby: writing tablebase generators.

I was annoyed with some of the design decisions in my last attempt, which made it a bit tricky to do things like KQKR (more than one piece on the black side). So I decided to build one from the ground up again, this time with a different storage/update scheme.

In my previous attempt, the DTM (or DTC) table was the main data structure I used, and I would probe into that to figure out if I'd processed a position before or not. My new generator uses bitlists for everything (implemented as bitboards), indexed as [wk][wp1][wp2][…][bp1][…] and with set bits corresponding to the position of the black king. I think this is similar to HGM's generator.

I alternate between loss and win finding, collecting newly found positions into a "new" list:

Code: Select all

/* Find new won positions from recently found lost positions */
old = new
new = empty
for all positions in "old":
   record all precursors (as "won")

/* Filter out previously won positions */
new &= ~won;

/* Update list of won positions */
won |= new;

/* Find new lost positions from recently found won positions */
old = new
new = empty

for all positions in "old":
   test all precursors and record those that are lost (as "lost")

I can transcribe the bitlist into the DTM table when I have found the newly won positions. By construction this never updates the same position twice.

I have a few things to speed things up:

1. When testing if a position is lost I simply and the bitmask of black king moves into the "won" mask (derived from the configuration of the other pieces). If there is a move that does not lead to a won position, then the current position is not lost (otherwise I have to try moves by other black pieces that may be present, but those I will have to make/unmake).
2. I keep track of the position of the white king in newly won or newly lost positions, and skip positions where the white king is not in a "winning" location. I do the same for the first white piece (indexed with the position of the white king).

The second idea gave a huge speed boost in my old generator, it seems to be less of a benefit here, which is odd. The indexing scheme in my old generator is different and it's possible that this causes the difference.

There are a few things I don't do:
1. Updating the index on the fly. Right now I calculate it from scratch, using a generic function for N pieces. This could safe quite a bit of time.
2. Exploit the symmetry of the board. I'm planning to have this as an optional feature, but if I can make it fast enough without it I may just not bother with it.

With all that, my new generator is about a factor of 3-5 slower than my old one, which is not bad considering that one does use the symmetry to speed things up. It's about a factor 30 slower than Marcel's generator posted earlier in this thread.

That means I have some work to do to get generating KBNK back to under 1s, which seems like a good target time.

Interestingly enough, writing the new generator only took me two evenings, rather than a week.

[Evert]

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.

It seems like wasted effort to consider positions with the "wrong" bishop for on-the-fly generation, since you know what colour your bishop is on. If you can exploit the 8-fold symmetry, that's a different case, since that buys you more than restricting the bishop to a single colour does.

By the way, I was planning to treat the Spartan lieutenants as colour-bound for the purpose of tablebase generation (but I would not bind them to their colour, as I would the bishop; I would just not try colour-changing moves for them). Positions after colour-changing moves would still be probed, of course, but the scores stored for them would be wrong.

If the main effect of this is taking a longer path to a win by keeping the lieutenants on their respective colours, that's not such an issue. I wonder if it can ever happen that I miss a win (or a draw) that depends on a sequence of colour-changing moves though...

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.

This is indeed a very useful trick.

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.

I do something like this for my new generator as well, and it does speed up the detection of mates on the first cycle. However, that's still a small fraction of the time it takes to step through the entire tablebase.

[hgm]

You can do 'bulk verification' of the lost positions: in stead of AND-ing 'won' with the black-King move set to see if any moves remain, you could (repeatedly) AND the black-King occupancy with the won mask shifted over all King moves. The occupancy bit won't survive if one of the shifted won masks has a zero, i.e. if the king move corresponding to the shift would reach a non-won position. But in this case you can do it for the entire black 'King bundle' of 64 positions, without the need to extract the individual bits first.

Initially I did this as

Code: Select all

lost = potentiallyLost & 
        (won << 1 | edge_w) &
        (won << 7 | edge_ne) &
        (won << 8 | edge_n) &
        (won << 9 | edgenw_w) &
        (won >> 1 | edge_e) &
        (won >> 7 | edge_sw) &
        (won >> 8 | edge_s) &
        (won >> 9 | edge_se);

But then I realized I could use convolution tricks to reduce the number of operations:

Code: Select all

trap = (won << 1 | edge_w)
     & (won >> 1 | edge_e);    // w,e mask
lost = potentiallyLost & trap; // takes care of w & e masking 
if(!lost) continue;            // early cutoff opportunity
trap &= won;                   // n,e,i mask
trap = (trap << 8 | edge_n)
     & (trap >> 8 | edge_s);   // nw, ne, sw, se, n, s mask
lost &= trap;                  // masks off all other escapes
// must still verify escapes through other black pieces

This reduces the oprations from 8 shifts + 16 AND/OR to 4 shifts + 9 AND/OR.

Sometiimes forward moving does better than retro-moving. In particular when the forward moves are guaranteed to give cache hits. The crux is that retro-moving makes the cache dirty, because you test the state of the current position, to see if it is lost-in-N, and if it is, you start retro-moving to mark all parent position as newly-won. While many of those will not be visited by the scan before they have to be flushed out of some cache level(s). With forward moving you would approach the problem from the position you want to decide, and you would probe the daughters with read-only accesses. So you would only dirty the cache for the entry you are working on any way.

I use that system now for the white King moves to neighboring ranks. My storage scheme is lightly different from yours, as I split the King rank and file coordinates:

EGT[wKr][w1][w2/b1][wKf]

where bK is a bitboard. For 8x8 that would put an entire white-King rank in a cache line. And when looping over wKr the problem automatically reduces to 3/8 of its size, as an orthodox King only covers 3 ranks. That makes wKr ideal for outer-most loop. But that again makes that white-King retro-moves to another rank store something that won't be needed for a very long time, the fate of which is to be flushed from the cache, and it is very inconvenient that it is dirty. So I had a speedup by treating the off-rank white King moves as forward moves. When I have been working on all white-King in-rank retro moves for given w1 and w2 the newly-won positions for that rank will be cached and dirty. (It is quite unlikely that these 8x64 = 512 positions would not have contained any lost-in-N during most of the building process.) I then just probe the corresponding cache lines for the neighboring ranks in lost-in-N. By treating these together I can again make use of convolution tricks:

Code: Select all

t0 = lost[N][rank+1][...][0] | lost[N][rank-1][...][0]; // a-file
t1 = lost[N][rank+1][...][1] | lost[N][rank-1][...][1]; // b-file
t2 = lost[N][rank+1][...][2] | lost[N][rank-1][...][2]; // c-file
...
t0 |= t1; // a, b
t1 |= t2; // b, c
t2 |= t3; //
...
newlyWon[rank][...][0] =      t0; // a, b
newlyWon[rank][...][0] = t0 | t1; // a, b, c
newlyWon[rank][...][0] = t1 | t2; // b, c, d
...

(I unrolled the loop, to not have to worry about edge effects.) This means that for the entire rank I only have to do 24 OR operations, while naively treating all off-rank moves separately would take you 2*4 + 6*6 = 44 OR operations.

The downside is that you would be OR-ing with 0 values at times when the EGT is still very sparsely populated. With retro-moving only you can skip all moving whenever you encounter a 0 bitboard. Nevertheless it apparently pays off (at least for generally-won end-games, but it are those that take the most time to generate): I have reduced the KBNK build time now to 230 ms (exploiting color-binding). I haven't tried 2+2-men yet. Problem is that you have to worry about conversions there. (The 3+1 men would currently also not work if one of the white pieces could cause checkmate by itself, as it initializes all bits where the black King is on top of an unprotected white piece as 0 in the won[] bitmap.) Perhaps I should first try it with an end-game that doesn't need conversions to be won (e.g. KQKN).

[Evert]

You can do 'bulk verification' of the lost positions: in stead of AND-ing 'won' with the black-King move set to see if any moves remain, you could (repeatedly) AND the black-King occupancy with the won mask shifted over all King moves. The occupancy bit won't survive if one of the shifted won masks has a zero, i.e. if the king move corresponding to the shift would reach a non-won position. But in this case you can do it for the entire black 'King bundle' of 64 positions, without the need to extract the individual bits first.

Ah, clever.
I did think that something like that would be possible, but I couldn't figure out how to do it. It does have the unfortunate side-effect of breaking the nice split I have between the code that places the pieces on the board and the code that handles the retrograde/prograde analysis of the positions, but if the speed-up is significant, that is a price worth paying. I'll try it out.

It also breaks non-orthodox kings, which is also a shame. Then again, the only variant on an 8x8 board that I know of that has a non-orthodox king is knightmate. For other board sizes I think there's only Xiang-Qi, which is sufficiently different that I wouldn't want to use a generic tablebase generator for it anyway.

I use that system now for the white King moves to neighboring ranks. My storage scheme is lightly different from yours, as I split the King rank and file coordinates:

EGT[wKr][w1][w2/b1][wKf]

where bK is a bitboard. For 8x8 that would put an entire white-King rank in a cache line. And when looping over wKr the problem automatically reduces to 3/8 of its size, as an orthodox King only covers 3 ranks. That makes wKr ideal for outer-most loop.

Clever. Not particularly beautiful, but still a very nice idea. I did worry about > 4 men tablebases, since there's no way of fitting the bitmasks in cache.

When I have been working on all white-King in-rank retro moves for given w1 and w2 the newly-won positions for that rank will be cached and dirty. (It is quite unlikely that these 8x64 = 512 positions would not have contained any lost-in-N during most of the building process.) I then just probe the corresponding cache lines for the neighboring ranks in lost-in-N. By treating these together I can again make use of convolution tricks:

Code: Select all

t0 = lost[N][rank+1][...][0] | lost[N][rank-1][...][0]; // a-file
t1 = lost[N][rank+1][...][1] | lost[N][rank-1][...][1]; // b-file
t2 = lost[N][rank+1][...][2] | lost[N][rank-1][...][2]; // c-file
...
t0 |= t1; // a, b
t1 |= t2; // b, c
t2 |= t3; //
...
newlyWon[rank][...][0] =      t0; // a, b
newlyWon[rank][...][0] = t0 | t1; // a, b, c
newlyWon[rank][...][0] = t1 | t2; // b, c, d
...

(I unrolled the loop, to not have to worry about edge effects.) This means that for the entire rank I only have to do 24 OR operations, while naively treating all off-rank moves separately would take you 2*4 + 6*6 = 44 OR operations.

I have a hard time picturing what that code does (and what the t0, t1, t2… masks are). I'm guessing it's collecting east/west moves by the king…?

The downside is that you would be OR-ing with 0 values at times when the EGT is still very sparsely populated. With retro-moving only you can skip all moving whenever you encounter a 0 bitboard. Nevertheless it apparently pays off (at least for generally-won end-games, but it are those that take the most time to generate): I have reduced the KBNK build time now to 230 ms (exploiting color-binding).

Way to raise the bar there. Not that I'm trying to compete, of course. Just, you know, not be horribly slow.

I haven't tried 2+2-men yet. Problem is that you have to worry about conversions there.

Indeed. That's actually something I also haven't tried to do yet. I'm thinking the easiest is to simply do a hybrid DTM/DTC, but I'm not sure what the consequence of that would be. It has the downside that you need to figure out if a capture leads to a win, which is hard to do in the general case (without the relevant reduced tablebase).

(The 3+1 men would currently also not work if one of the white pieces could cause checkmate by itself, as it initializes all bits where the black King is on top of an unprotected white piece as 0 in the won[] bitmap.)

That's a good point. I think I have the same issue.

Perhaps I should first try it with an end-game that doesn't need conversions to be won (e.g. KQKN).

Sounds reasonable.

[hgm]

It also breaks non-orthodox kings, which is also a shame. Then again, the only variant on an 8x8 board that I know of that has a non-orthodox king is knightmate.

Not necessarily. For other royal types you just need a different pattern of shifts. You just shift by all the retro-move vectors of the black non-royal, and AND the lot. You could still do it with a completely general table-driven generator:

Code: Select all

for(i=0; i<KINGMOVES; i++) lost &= won << shift[i] | edge[i];

where edge would map out the squares from which the corresponding (non-retro) step would leave the board.

For other board sizes I think there's only Xiang-Qi, which is sufficiently different that I wouldn't want to use a generic tablebase generator for it anyway.

Well, Xiangqi is an absolute disaster because of the perpetual rules. These are intrinsically incompatible with retrograde analysis.

I have a hard time picturing what that code does (and what the t0, t1, t2… masks are). I'm guessing it's collecting east/west moves by the king…?

Indeed, they are all temporaries, collecting wtm positions that have at least one winning move (i.e. a set bit in the lost-in-N of the daughter position). So the first step creates the sets that can be won by N and S moves. Then you combine two of those to get the sets that can be won by N, S, NE and SE moves (or NW, SW, N and S moves as seen from the square E of you). And finally you join two of those to get the positions that can be won by all 6 forward and backward moves. It is basically just a matter of doing things in a clever order when OR-ing the lost sets together, so that intermediate results you get for calculating one square can also be used for the next square on that rank.

Indeed. That's actually something I also haven't tried to do yet. I'm thinking the easiest is to simply do a hybrid DTM/DTC, but I'm not sure what the consequence of that would be. It has the downside that you need to figure out if a capture leads to a win, which is hard to do in the general case (without the relevant reduced tablebase).

Currently I am doing the calclation with a single won-so-far bitmap, and a lot of lost-in-N bitmaps. But it would be easy to alter that to store multiple won-in-N-or-less bitmaps (storing the won |= newlyWon update to a fresh section of memory rather than writing it back). Then you can easily do conversions for DTM: Normally, when you scan over positions you would skip the 'broken' ones, where two pieces coincide. But when you are retro-moving white, and placing a black piece on top of a white in the board scan, in stead of taking the lost[N] element [wK][w1][b1] to work from, you simply take lost2[N][wK][w1], where lost2 is the lost[] set of the relevant successor (which depends on which black piece you tried to place). Otherwise it can use exactly the same code. During verification you would have to probe the won[N] bitmap of a successor lacking a white piece when you generate a capture with the black non-royal, rather than of the current EGT.

The most tricky part is the captures that the black King would do. Bits in the King bundle that correspond to positions where the black King coincides with a white piece are already set in the initialization if the white piece was protected, but if it was not, they now are permanent escapes (as white retro-moving does not allow you to reach them). But in practice they could still be lost; these bits should really be taken from the won[N] set of the successor EGT lacking that white piece. So I guess the won[] bitmap should be initialized to assume all these broken positions should be won, (the bit set even when unprotected, as occupancy bits of black pieces are also always set), so that the bulk verification would also leave positions that can escape through a capture in the potential-losses set. As an extra step you would then have to AND the potential losses with kingAttacks[w_i] to see if any of them had a capture on white piece i, and if the set is non-empty probe the won[N] bitmap of the successor EGT lacking that piece at occupied[w_i] to see if you should clear them out of the set as well.

Code: Select all

for(i=0; potentiallyLost && i<whiteNonRoyals; i++) {
  if(potentiallyLost & kingAttacks[sqr[i]]) {
    if((successor[i]->won[N][...] & sqr2bit[sqr[i]]) == 0)
      potentiallyLost &= ~kingAttacks[sqr[i]];
  }
  lost[N+1][...] = potentiallyLost;
}

Fortunately you would only have to do that when no non-converting moves provided an escape, as you would test that first.

[Evert]

It also breaks non-orthodox kings, which is also a shame. Then again, the only variant on an 8x8 board that I know of that has a non-orthodox king is knightmate.

Not necessarily. For other royal types you just need a different pattern of shifts. You just shift by all the retro-move vectors of the black non-royal, and AND the lot. You could still do it with a completely general table-driven generator:

Code: Select all

for(i=0; i<KINGMOVES; i++) lost &= won << shift[i] | edge[i];

where edge would map out the squares from which the corresponding (non-retro) step would leave the board.

True. Still a bit of a hassle though.

For other board sizes I think there's only Xiang-Qi, which is sufficiently different that I wouldn't want to use a generic tablebase generator for it anyway.

Well, Xiangqi is an absolute disaster because of the perpetual rules. These are intrinsically incompatible with retrograde analysis.

I don't really understand why that would be the case.

You would enter a tablebase position following a capture. Any capture would break the chase sequence, so the only problem I can see is with chase sequences within the "optimal" path in the tablebase, but an optimal move sequence cannot contain a repetition, so it is again not relevant.

What am I missing?

[hgm]

The problem is that you have to prevent the weak side ('black') from perpetually checking, and conventional retrograde analysis will not do that. The lost positions in the perpetual loop will always have a daughter that is not yet decided (because it is a loop), and so it will never get decided. The retrograde analysis doesn't know the check is a non-allowed repetition, because it only knows what happens after the check, not what has happened before it.

Formally the problem is that the entire game history since the last irreversible move becomes a part of the game state, and (in combination with the board position) decides what moves you are allowed to do. That is also the case when drepeats are draws, but there it does not hurt, because undecided positions will be draws by default.

Of course you cannot really include the game history in the table-base index, that would explode the number of positions. People that built Xiangqi tablebases used some complicated algorithm to identify perpetual loops, and then consider the loop as a single position with multiple exits, and decide the loop when all exits get plugged.

[Evert]

The problem is that you have to prevent the weak side ('black') from perpetually checking, and conventional retrograde analysis will not do that.

Ah, I hadn't thought of perpetual checks.

Formally the problem is that the entire game history since the last irreversible move becomes a part of the game state, and (in combination with the board position) decides what moves you are allowed to do. That is also the case when drepeats are draws, but there it does not hurt, because undecided positions will be draws by default.

So am I correct in thinking that this would only affect draw scores from the table? If so, you can still trust a winning line, but you cannot blindly play into a drawn line and need to use the tablebase to guide the search: positions that are "lost" are still "lost" and you only need to follow the "possibly drawn" lines only. The ones that lead into a cycle will be eliminated by the search eventually.

This doesn't sound too bad to me.

Of course you cannot really include the game history in the table-base index, that would explode the number of positions. People that built Xiangqi tablebases used some complicated algorithm to identify perpetual loops, and then consider the loop as a single position with multiple exits, and decide the loop when all exits get plugged.

That does sound complicated., but it's something that can be done after the tablebase is generated, right? Basically, you verify each draw by doing a forward search until you either reach a repetition, or you reach a position that is "known" to be a proper draw (lack of mate potential or a prior tablebase, which is trusted).
But then, that sounds like what I suggested above: just let the engine search take care of it.

[hgm]

This doesn't sound too bad to me.

But it is. In general it means that your entire tablebase will consist of draws, (plus a few mates and mate-in-1) as soon as the opponent has a piece of importance. E.g. KRPKR is generally won by Xiangqi rules, but there is no way to ever prevent the black Rook from perpetually checking. You can always threaten a perpetual from two directions when not actually checking. First time he moves the Pawn after your Rook took distance from the Palace you have a forced perpetual.

You cannot do anything after the tablebase is generated, (if you generate in the conventional way), because generating the tablebase essentially tells you nothing that you couldn't have known before: he can start a perpetual in any position, so there is no forced win.

The best solution I could think of (but have not tried yet) is tabulating only the 'untainted' positions, where there is no checking or chasing history. If the verification qualifies as a check or chase, you cannot probe the EGT at that point, but have to search deeper until you can. So you get a conventional alpha-beta search of only checks and chases for black, while white tries to exhaust the checking possibilities as quickly as possible by turning them into repeats. Every non-check non-chase move by black can be found in the EGT, and 'hash pruned'.

Whether this is feasible or not depends on how large these trees would on average grow. Of course you would try checking / chasing moves during verification as a last resort only, after all others were found to lead to 'won' positions. In KRPKR the tree would remain pretty small:

Code: Select all

check - step out sideways - check on old King square - KxR
                         \
                          - check from distance - step King back - check on old King square - KxR
                                                                \
                                                                 - check from distance = repeat