On-demand tablebase generation

[syzygy]

I suspect mine is probably slowed down by whatever bug causes the tablebase to not work correctly. Or the algorithm is just too simple and stupid. Or both.

Obviously I haven't seen your code, but you probably re-use the move generator of your engine instead of writing dedicated routine working as much as possible on the index as board representation.

Also you are using forward generation instead of retrograde analysis. Instead of doing a 1-ply search for each position on each iteration, you could start with the positions that are mate, mark all positions that go 1 ply back, then loop over the table and do the 1-ply search only on those positions. This way you find losses and from those you can go 1 ply back and mark positions as wins (no need for a 1-ply search here). From the newly found wins you go 1 ply back to the potential losses, and so on.

[hgm]

The 'on-the-fly' EGTs never made it to the top of my to-do list. Not because I have abandoned the idea, but because my engine is usually crushed in the middle-game long before any solvable positions would come in view.

I thought FairyGen was significantly faster on KBNK than 10 sec. IIRC it was more like 4 sec, on an 1.3GHz Celeron-M. (But it was long ago, so I could be wrong.) Anyway, it uses an algorithm that I now consider to be extremely slow. The 4-men case is important, as I considered it the model for a P-slice in end-games with many Pawns, and I think it should be possible to generate such P-slices in under 0.2 sec.

Btw, I remember I did place a retrograde KPK generator in the public domain, (here on the forum), especially for people who could not use Glaurung's because of the license restrictions.

As to KKW: that should be quite easy even without any EGT. If engines have difficulty checkmating a bare King at fast TC, this can usually be cured by a specially adapted PST for that purpose. Just multiplying the table for the bare King with a factor 5 usually does the trick.

Also relevant could be an observation I made in Suicide R vs K end-game: where it took minutes to find the winning line in some positions with alpha-beta by micro-Max (with altered winning condition), the same positions could be solved in a second when I switched to using minimax. (But micro-Max doesn't have a dual-bound hash table; with dual bounds alpha-beta works better, although still not as good as plain minimax.) What happens is that in minimax the search simply starts building a DTM EGT in the hash table. A 2-men is of course only 2 x 4096 positions, so that easily fits.

I have never tried if the same trick also works for 3-men, where it would become relevant for normal checkmating in regular Chess variants. These have 2 x 256K, which still should fit almost without losses in typical hash table sizes of today. If it does, you could simply switch off beta cutoffs when you reach 3-men level. (I.e. set beta = INF at the top of Search.)

[Sven]

Also you are using forward generation instead of retrograde analysis. Instead of doing a 1-ply search for each position on each iteration, you could start with the positions that are mate, mark all positions that go 1 ply back, then loop over the table and do the 1-ply search only on those positions. This way you find losses

One ply back from a mate, that's a win, isn't it? Or are you already two plies back from the mates at that point?

[Evert]

Obviously I haven't seen your code, but you probably re-use the move generator of your engine instead of writing dedicated routine working as much as possible on the index as board representation.

Discussions without code are complicated.

I'll clean up what I have and post it for discussion purposes, but since the algorithm is not great it may not be such an interesting discussion.

I actually don't reuse the board representation or move generation - at least not directly. I loop over all squares for all pieces (skipping the ones that are excluded by symmetry or because pieces overlap), then in the inner loop I construct an occupancy bitboard from the piece positions. If the king is in check I actually generate a second one with the position of the king cleared.
I then call each piece's individual generator, passing square and occupancy, and get back a bitboard with all move possibilities. From this I generate successor positions and look up their score. I then set the score for the current node to best/worst result of all child nodes+1 (depending on whether I'm being mated or trying to avoid mate). It's actual mini-max, I should probably change that to negamax.

Also you are using forward generation instead of retrograde analysis. Instead of doing a 1-ply search for each position on each iteration, you could start with the positions that are mate, mark all positions that go 1 ply back, then loop over the table and do the 1-ply search only on those positions. This way you find losses and from those you can go 1 ply back and mark positions as wins (no need for a 1-ply search here). From the newly found wins you go 1 ply back to the potential losses, and so on.

My initial idea was the following:
I mark all positions that are mate and push them on a (fifo) stack. Then I enter a loop where I pop elements off the stack. For each position I pop off the stack I generate the precursors. These have an expected score of 1-worse than the current node. If I've visited the node before and it has the expected score, I do nothing. If I haven't visited the node before I assign it the expected value I just found and push the node onto the stack. If I have visited the node before, I update the score and push the node onto the stack.
Once the stack is empty I've processed all positions and I'm done.

I thought that doing it this way would minimise the redundant work I need to do (because I only work on the positions that I actually need to work on) and I thought that the situation of visiting a node and having to update its score wouldn't actually occur (because the first time I find it is also the closest to mate it can be). The stack can probably grow relatively large though (of the order of the tablebase itself) so that's a downside to this method. Otherwise I think it's basically what you're describing?

Anyway, when I started to implement that it didn't work and I figured I was better off picking a simpler algorithm that was easier to debug and getting that to work first.

[Evert]

The 'on-the-fly' EGTs never made it to the top of my to-do list. Not because I have abandoned the idea, but because my engine is usually crushed in the middle-game long before any solvable positions would come in view.

Same here, of course, but still: these things are fun.

There are more significant things I could be doing to Leonidas in terms of making it stronger. I played it against Jazz the other day (not a particularly strong program) and it was badly slaughtered.

I thought FairyGen was significantly faster on KBNK than 10 sec. IIRC it was more like 4 sec, on an 1.3GHz Celeron-M. (But it was long ago, so I could be wrong.)

Even if it's 10 seconds on an old Celeron, that's better than my 10 seconds on a new i7.

Btw, I remember I did place a retrograde KPK generator in the public domain, (here on the forum), especially for people who could not use Glaurung's because of the license restrictions.

Ah yes, now that you mention it: I do remember that.

As to KKW: that should be quite easy even without any EGT. If engines have difficulty checkmating a bare King at fast TC, this can usually be cured by a specially adapted PST for that purpose. Just multiplying the table for the bare King with a factor 5 usually does the trick.

Well, I tried that and it didn't help. Could be something else messing up of course. It did surprise me, because KKW didn't seem like it should be overly difficult. When I say fast time control, it's something in the order of 40 moves/few seconds. If I relax that a bit there's no real issue.

Also relevant could be an observation I made in Suicide R vs K end-game: where it took minutes to find the winning line in some positions with alpha-beta by micro-Max (with altered winning condition), the same positions could be solved in a second when I switched to using minimax. (But micro-Max doesn't have a dual-bound hash table; with dual bounds alpha-beta works better, although still not as good as plain minimax.) What happens is that in minimax the search simply starts building a DTM EGT in the hash table. A 2-men is of course only 2 x 4096 positions, so that easily fits.

I have that (a 2-bound hash table) on my list of something to experiment with. It sounds like it would be useful in some cases at no real cost in the more general case.

[syzygy]

Also you are using forward generation instead of retrograde analysis. Instead of doing a 1-ply search for each position on each iteration, you could start with the positions that are mate, mark all positions that go 1 ply back, then loop over the table and do the 1-ply search only on those positions. This way you find losses

One ply back from a mate, that's a win, isn't it? Or are you already two plies back from the mates at that point?

Oops, you are right.

So positions 1 ply back from mate or otherwise lost positions can be marked as won.
Positions 1 ply back from won positions should be marked as "potential loss".
On each iteration:
- for a potential loss, do a 1-ply search for potential losses to see if they are really lost. Then immediately mark the positions 1 ply back from the new loss as newly won.
- for a newly won position, mark the positions 1 ply back as potential losses.
This results in 2 ply per iteration, which is quite efficient.

[syzygy]

I actually don't reuse the board representation or move generation - at least not directly. I loop over all squares for all pieces (skipping the ones that are excluded by symmetry or because pieces overlap), then in the inner loop I construct an occupancy bitboard from the piece positions. If the king is in check I actually generate a second one with the position of the king cleared.
I then call each piece's individual generator, passing square and occupancy, and get back a bitboard with all move possibilities. From this I generate successor positions and look up their score. I then set the score for the current node to best/worst result of all child nodes+1 (depending on whether I'm being mated or trying to avoid mate). It's actual mini-max, I should probably change that to negamax.

Ok, this seems similar to what I do.

My initial idea was the following:
I mark all positions that are mate and push them on a (fifo) stack. Then I enter a loop where I pop elements off the stack. For each position I pop off the stack I generate the precursors. These have an expected score of 1-worse than the current node. If I've visited the node before and it has the expected score, I do nothing. If I haven't visited the node before I assign it the expected value I just found and push the node onto the stack. If I have visited the node before, I update the score and push the node onto the stack.
Once the stack is empty I've processed all positions and I'm done.

Instead of a separate fifo stack I just loop through the table. This is quite fast even for 6-piece tables. By first marking all precursors that are "potential losses" before actually verifying them, I save a lot of double work.

I thought that doing it this way would minimise the redundant work I need to do (because I only work on the positions that I actually need to work on) and I thought that the situation of visiting a node and having to update its score wouldn't actually occur (because the first time I find it is also the closest to mate it can be). The stack can probably grow relatively large though (of the order of the tablebase itself) so that's a downside to this method. Otherwise I think it's basically what you're describing?

Somewhat, I guess, but the "otherwise" covers quite some detail .

I think the generator used for the Lomonov tables used a kind of stack, i.e. lists of nodes to be updated and communicated between the various nodes of the distributed super computer it ran on.

[Evert]

This is the main body of my 3-men generator. Before this I mark positions that are checkmate as TB_MATE and positions that are stale-mate or where the defending king ("black") captures the last piece (meaning the two squares are equal) as TB_DRAW. All other positions are initialised to TB_INVAL.

The variables dks and aks refer to "defending king square" and "attacking king square" respectively. "as" is the square of the first piece (originally the a stood for "archbishop", which was what I originally wrote the code for). All details of how the tablebase is indexed is hidden in probe_tb3 and store_tb3 inline functions.

Code: Select all

   done = false;
   while (!done) {
      done = true;
      for (int side = WHITE; side <= BLACK; side++) {
         sides other = next_side[side];
         for (int idks = 0; idks < sizeof dks_squares / sizeof *dks_squares; idks++) {
            int dks = dks_squares[idks];
            for (int aks = 0; aks < 64; aks++) {
               if ((flip_diag2_bb&make_bitboard_square(dks)) && (flip_diag3_bb&make_bitboard_square(aks)))
                  continue;
               if (king_attack[dks] & make_bitboard_square(aks)) continue;
               if (dks == aks) continue;
               for (int as = 0; as < 64; as++) {
                  if (aks == as) continue;
                  if (dks == as) continue;
                  int8_t score = probe_tb3(tb, dks, aks, as, side);

                  /* Skip positions that are already marked as DRAW or MATE -
                   * they never get updated again.
                   */
                  if (score == TB_DRAW) continue;
                  if (score == TB_MATE) continue;

                  bool is_draw = true;             /* We will try to disprove this */
                  int8_t best_score = (side == WHITE) ? TB_INVAL : -TB_INVAL;
                  int8_t start_score = best_score;

                  if (side == WHITE) { /* White to move */
                     bitboard_t occ = make_bitboard_square(aks) | make_bitboard_square(dks);
                     bitboard_t atk = tb->movegen(as, occ);
                     if (atk & make_bitboard_square(dks))  /* Black king in check -> illegal */
                        continue;

                     /* Generate follow-up positions and determine the
                      * best score.
                      */

                     /* King moves */
                     bitboard_t akm = king_attack[aks] & ~(king_attack[dks] | make_bitboard_square(as) | occ);
                     while (akm) {
                        int aks = bitscan64(akm);
                        akm ^= make_bitboard_square(aks);

                        int8_t score = probe_tb3(tb, dks, aks, as, other);
                        is_draw = is_draw && (score==TB_DRAW);
                        if (score != TB_INVAL && score != TB_DRAW)
                           best_score = min(best_score, score+1);
                     }

                     /* Piece moves */
                     while (atk) {
                        int as = bitscan64(atk);
                        atk ^= make_bitboard_square(as);

                        int8_t score = probe_tb3(tb, dks, aks, as, other);
                        is_draw = is_draw && (score==TB_DRAW);
                        if (score != TB_INVAL && score != TB_DRAW)
                           best_score = min(best_score, score+1);
                     }
                  } else {             /* Black to move */
                     bitboard_t occ = make_bitboard_square(aks);
                     bitboard_t atk = tb->movegen(as, occ);

                     bitboard_t dkm = king_attack[dks] & ~(king_attack[aks] | atk);

                     /* If we can capture White's last piece, it's a draw */
                     if (dkm & make_bitboard_square(as)) {
                        is_draw = true;
                        dkm = board_empty;
                     }

                     /* Generate follow-up positions and determine the
                      * best score.
                      */

                     while (dkm) {
                        int dks = bitscan64(dkm);
                        dkm ^= make_bitboard_square(dks);

                        int8_t score = probe_tb3(tb, dks, aks, as, other);
                        is_draw = is_draw && (score==TB_DRAW);
                        if (score != TB_INVAL && score != TB_DRAW)
                           best_score = max(best_score, score+1);
                     }
                  }

                  /* Update score as needed */
                  if (is_draw) best_score = TB_DRAW;

                  if (best_score != start_score && score != best_score) {
                     store_tb3(tb, dks, aks, as, side, best_score);
                     done = false;
                  }
               }
            }
         }
      }
   }

It's essentially a triple loop over the three squares, it just looks a bit ugly because it's skipping over positions that have already been covered by symmetry.

The 4-men code is similar, except there's an extra loop and an extra piece on the white side.

[Evert]

So positions 1 ply back from mate or otherwise lost positions can be marked as won.
Positions 1 ply back from won positions should be marked as "potential loss".
On each iteration:
- for a potential loss, do a 1-ply search for potential losses to see if they are really lost. Then immediately mark the positions 1 ply back from the new loss as newly won.
- for a newly won position, mark the positions 1 ply back as potential losses.
This results in 2 ply per iteration, which is quite efficient.

So to make sure I understand this correctly: once a position has been marked as "won", it gets skipped on a later iteration through the list and never needs to be looked at again, correct?

[Sven]

So positions 1 ply back from mate or otherwise lost positions can be marked as won.
Positions 1 ply back from won positions should be marked as "potential loss".
On each iteration:
- for a potential loss, do a 1-ply search for potential losses to see if they are really lost. Then immediately mark the positions 1 ply back from the new loss as newly won.
- for a newly won position, mark the positions 1 ply back as potential losses.
This results in 2 ply per iteration, which is quite efficient.

So to make sure I understand this correctly: once a position has been marked as "won", it gets skipped on a later iteration through the list and never needs to be looked at again, correct?

Only after having used it for this part of the algorithm:

- for a newly won position, mark the positions 1 ply back as potential losses.