On-demand tablebase generation

[hgm]

To get back to the more orthodox stuff:

I am stll looking for a reasonable first approximation to a P-slice where one of the Pawns has rached 8th rank, without actually adding the Queen as an extra man, and doing a 5-men slice. The most reasonable assumption seems to be that, with nearly a full Queen ahead, white will win as soon as he gets a 'free move' with that Queen. Meaning it should be his turn, he should not be in check, and the Queen should not be pinned. As long as it is not his turn the Queen could be captured, or the opponent could promote to Queen too. And as long as he is in check, it could be a perpetual, or there could be a skewer.

This is not that easy to translate into a recipe for EGT building, though. There already is a problem in the initialization: when you assign all wtm non-checks as won, you will create postions where every black move will lead to such a won position, but where he is not in check. The problem then arises whether this will be a stalemate, or a regular lost position. So you have first detect checkmates when the won[] set still only contains checks and broken positions, then assign all non-white-in-checks a won status too, and then again verify all btm positions against this new won[] bitmap to get the initially-lost positions.

During retrograde propagation you don't want to retro-move the Queen, as the aim is just to prove you can hide from check without him getting a shot at your Queen in the position where it promoted. As soon as you can move it elsewhere, the assumption is that you are won, so there is no interest in getting that Queen elsewhere. This would make you miss opportunities to capture the checking piece, however. So you must consider retro-moves from a successor EGT where black has one fewer piece, and that piece is left checking the white King after uncapturing it. In principle that is not a problem, because it would still be a 4-men end-game, the new Queen replacing the black piece, and so amenable to on-the-fly generating. Wtm positions where white is in check but can capture the checker with his Queen cannot be considered a free move with that Queen (so no automatic win), but they can be verified by probing the successor.

[hgm]

Hmm, if I am not mistaking KQKN does need a conversion to win. With an Iron Knight is seems a general draw.

Queen vs. Iron Ferz seems a general win, though. In the hope that you can easily check this, here are my numbers for that:

Code: Select all

hgm@hgm-xboard:~/EGT$ ./slow3 --verbose
start = 644440
 0.    17363  7350680 ( 0.005 /  0.000 /  0.000)
 1.    35782   115616 ( 0.018 /  0.001 /  0.005)
 2.    69115   120149 ( 0.022 /  0.008 /  0.023)
 3.    95506   237683 ( 0.027 /  0.013 /  0.045)
 4.    99837   223399 ( 0.026 /  0.014 /  0.072)
 5.   120676   231427 ( 0.028 /  0.007 /  0.098)
 6.   133245   248721 ( 0.026 /  0.013 /  0.126)
 7.   143329   254952 ( 0.029 /  0.008 /  0.152)
 8.   153364   253563 ( 0.025 /  0.014 /  0.181)
 9.   154842   240785 ( 0.029 /  0.009 /  0.206)
10.   159946   227138 ( 0.025 /  0.011 /  0.235)
11.   164422   213916 ( 0.027 /  0.014 /  0.260)
12.   161980   200213 ( 0.024 /  0.009 /  0.287)
13.   147999   178288 ( 0.024 /  0.011 /  0.311)
14.   133425   151927 ( 0.024 /  0.013 /  0.335)
15.   111828   120330 ( 0.021 /  0.010 /  0.359)
16.    90468    94612 ( 0.016 /  0.006 /  0.380)
17.    70835    72191 ( 0.014 /  0.004 /  0.396)
18.    50638    51751 ( 0.030 /  0.019 /  0.410)
19.    37476    37342 ( 0.012 /  0.007 /  0.440)
20.    25138    25037 ( 0.009 /  0.004 /  0.452)
21.    16418    16184 ( 0.015 /  0.000 /  0.461)
22.    10273    10113 ( 0.007 /  0.001 /  0.476)
23.     6737     6482 ( 0.006 /  0.002 /  0.483)
24.     4356     3738 ( 0.010 /  0.000 /  0.489)
25.     3035     2375 ( 0.005 /  0.001 /  0.499)
26.     1945     1680 ( 0.010 /  0.003 /  0.504)
27.     1100      961 ( 0.006 /  0.002 /  0.514)
28.      467      418 ( 0.007 /  0.002 /  0.520)
29.      208      193 ( 0.004 /  0.000 /  0.527)
30.       54       63 ( 0.003 /  0.000 /  0.531)
31.       25       22 ( 0.005 /  0.002 /  0.534)
32.       28       22 ( 0.003 /  0.000 /  0.539)
33.       47       45 ( 0.003 /  0.001 /  0.542)
34.       84       73 ( 0.003 /  0.000 /  0.545)
35.      105      104 ( 0.003 /  0.000 /  0.548)
36.      176      139 ( 0.008 /  0.006 /  0.551)
37.      155      125 ( 0.004 /  0.002 /  0.559)
38.      172      165 ( 0.009 /  0.000 /  0.563)
39.      194      137 ( 0.003 /  0.000 /  0.572)
40.      415      230 ( 0.004 /  0.001 /  0.575)
41.      769      447 ( 0.008 /  0.002 /  0.579)
42.      650      505 ( 0.003 /  0.000 /  0.587)
43.      515      495 ( 0.004 /  0.002 /  0.590)
44.      164      218 ( 0.003 /  0.001 /  0.594)
45.       64       60 ( 0.005 /  0.000 /  0.597)
46.       22       13 ( 0.006 /  0.005 /  0.602)
47.       33       20 ( 0.003 /  0.002 /  0.608)
48.       46       26 ( 0.004 /  0.001 /  0.611)
49.        5        7 ( 0.004 /  0.002 /  0.615)
max DTM = 49
times total= 0.619 far= 0.233
total time 1.968 sec, cpu time 1.580 sec

[Evert]

Hmm, if I am not mistaking KQKN does need a conversion to win. With an Iron Knight is seems a general draw.

Queen vs. Iron Ferz seems a general win, though. In the hope that you can easily check this, here are my numbers for that:

I'll check it out, but unfortunately it's not a quick change because I don't have the Ferz as a playable piece in Leonidas (which my tablebase generator is based on at the moment). Hopefully more tomorrow.

I'm a little surprised that without capturing the knight KQKN cannot generally be won, since you don't depend on zugzwang and can drive the king to the edge of the board with checks, but I guess if the knight and king get close enough together the knight can get in the way. This should be testable using an already existing tablebase by enumerating the winning paths that do not go through a conversion.

[Evert]

One idea I had involved "imperfect tablebases": if the final goal is not mate but something else (say, promotion or capture), then you do not know for sure that the final position the tablebase path leads you to is a win. However, if you play out the path to the tablebase terminal position and then continue with the normal search, this will tell you quickly enough whether the position is really won or not (assuming that if it isn't, that's because there's a short-term tactical reason). Compared to doing a regular search to depth N, this should still be relatively cheap (especially if the search has no hope of reaching the tablebase terminal position on its own).

However, it's not so obvious what to do if it turns out that the final tablebase position is not won: obviously you try alternatives, but do you start at the end of the tablebase tree and back up to where you first probed the tablebase (as a normal alpha/beta search would do), or do you try to pick a completely different path from the beginning? Either way - you need to update the tablebase with the new information that the position that you thought was won isn't, but then that information needs to propagate through the tablebase as well. A bit messy.

[hgm]

There was unfortunately no easy way to make Fairy-Max play Iron Knight, otherwise I would have tried to checkmate it. Queen vs Iron Bishop was a general draw two, while I would have sworn it would be winnable by just staying on the other color. But it seems it can use the Bishop as a shield, to cross ranks or files attacked by the Queen, and thus escape the confinement.

I am not sure it could be tested with conventional tablebases, Because the defending side there would in general avoid conversion, because it would lead to an even faster mate, which is an extra handicap that makes it easier for the strong side to force a mate without conversion.

Of course it could still be that my 2+2-men generator is simply in error.

If Q vs Iron N is easier for you, we could of course compare those too; it is not a dead draw like KNNK, and there is a sizable number of wins that would unlikely to be correct if the generator was not perfect:

Code: Select all

hgm@hgm-xboard:~/EGT$ ./slow3 --verbose
start = 644440
 0.    12295  7350680 ( 0.005 /  0.000 /  0.000)
 1.     9898    85484 ( 0.015 /  0.000 /  0.005)
 2.    10794    36387 ( 0.012 /  0.003 /  0.020)
 3.     8522    41685 ( 0.017 /  0.002 /  0.032)
 4.     5025    25998 ( 0.014 /  0.003 /  0.049)
 5.     2828    14744 ( 0.008 /  0.001 /  0.063)
 6.     1481     8578 ( 0.006 /  0.000 /  0.071)
 7.      880     4447 ( 0.012 /  0.002 /  0.077)
 8.      622     3196 ( 0.005 /  0.001 /  0.089)
 9.      478     2181 ( 0.004 /  0.002 /  0.094)
10.      293     1427 ( 0.004 /  0.001 /  0.098)
11.      252     1002 ( 0.006 /  0.000 /  0.102)
12.      154      739 ( 0.003 /  0.002 /  0.108)
13.      156      521 ( 0.003 /  0.001 /  0.111)
14.      102      608 ( 0.004 /  0.002 /  0.114)
15.      136      376 ( 0.004 /  0.001 /  0.118)
16.      209      469 ( 0.010 /  0.009 /  0.122)
17.      114      606 ( 0.012 /  0.002 /  0.132)
18.      102      480 ( 0.004 /  0.001 /  0.144)
19.       73      396 ( 0.003 /  0.000 /  0.148)
20.       55      328 ( 0.009 /  0.000 /  0.151)
21.       48      252 ( 0.003 /  0.001 /  0.160)
22.       16      200 ( 0.003 /  0.001 /  0.163)
23.       23       78 ( 0.004 /  0.001 /  0.166)
24.       12      111 ( 0.003 /  0.000 /  0.170)
25.        8       72 ( 0.003 /  0.000 /  0.173)
26.        4       34 ( 0.003 /  0.000 /  0.176)
27.        2       12 ( 0.011 /  0.000 /  0.179)
28.        2        8 ( 0.003 /  0.001 /  0.190)
29.        2        9 ( 0.006 /  0.002 /  0.193)
max DTM = 29
times total= 0.199 far= 0.039
total time 0.874 sec, cpu time 0.660 sec

[hgm]

However, if you play out the path to the tablebase terminal position and then continue with the normal search, this will tell you quickly enough whether the position is really won or not (assuming that if it isn't, that's because there's a short-term tactical reason).

I don't think this will work. Even if the terminal position (say a safe promotion) is won, there is no guarantee that the defending side cannot force you to an earlier promotion that is not won. It only allowed you to reach the terminal position because you told it that all the other promotions would lose even quicker. But if one of the quick ones doesn't, he might be able to force you to that quick one, and successfully defend against you reaching the previous terminal one, now he doesn't have to worry about that other one too.

E.g when white has a passer on the b-file and e-file in a Pawn ending, and his King is nowhere to be seen, he has an easy win, as the black King cannot stop both. But he can easily stop either one of them, if promoting the other would turn out to be a draw.

[Evert]

There was unfortunately no easy way to make Fairy-Max play Iron Knight, otherwise I would have tried to checkmate it. Queen vs Iron Bishop was a general draw two, while I would have sworn it would be winnable by just staying on the other color. But it seems it can use the Bishop as a shield, to cross ranks or files attacked by the Queen, and thus escape the confinement.

I am not sure it could be tested with conventional tablebases, Because the defending side there would in general avoid conversion, because it would lead to an even faster mate, which is an extra handicap that makes it easier for the strong side to force a mate without conversion.

Of course it could still be that my 2+2-men generator is simply in error.

If Q vs Iron N is easier for you, we could of course compare those too; it is not a dead draw like KNNK, and there is a sizable number of wins that would unlikely to be correct if the generator was not perfect:

Well, it turned out to be not as much work as I had thought to hack in the Ferz: I actually do have move tables for the Ferz, which I use for the non-rook moves of the Spartan general. So it was almost a one-line change afterall.

Unfortunately I'm not convinced that this is really helping us, since it looks like I get completely different numbers from you. With the Ferz:

Code: Select all

 0    22640 8849260 228.842ms
 1   147432 (new win)  239.83ms
      69056 (new loss) 256.974ms
 3   190260 (new win)  278.602ms
     136172 (new loss) 306.066ms
 5   444600 (new win)  348.751ms
     244896 (new loss) 412.811ms
 7   567632 (new win)  487.105ms
     325804 (new loss) 571.775ms
 9   686692 (new win)  662.79ms
     464700 (new loss) 771.39ms
11   706420 (new win)  932.577ms
     522120 (new loss) 1034.88ms
13   609708 (new win)  1184.75ms
     508556 (new loss) 1272.6ms
15   456384 (new win)  1413.47ms
     431828 (new loss) 1483.48ms
17   347836 (new win)  1607.97ms
     369852 (new loss) 1667.18ms
19   268352 (new win)  1770.64ms
     303044 (new loss) 1819.51ms
21   215788 (new win)  1906.12ms
     249092 (new loss) 1946.1ms
23   184568 (new win)  2020.21ms
     217468 (new loss) 2059.55ms
25   172708 (new win)  2131.97ms
     198852 (new loss) 2166.19ms
27   135840 (new win)  2226.92ms
     159520 (new loss) 2255.34ms
29   105700 (new win)  2306.03ms
     131572 (new loss) 2331.13ms
31    97748 (new win)  2374.68ms
     127648 (new loss) 2398.08ms
33    80796 (new win)  2437.46ms
     103276 (new loss) 2458.8ms
35    68168 (new win)  2494.17ms
      90272 (new loss) 2515.2ms
37    49920 (new win)  2543.45ms
      68920 (new loss) 2557.78ms
39    35076 (new win)  2581.63ms
      50792 (new loss) 2593.64ms
41    19132 (new win)  2613.86ms
      25056 (new loss) 2625.6ms
43    13364 (new win)  2636.3ms
      19376 (new loss) 2644.14ms
45    11144 (new win)  2653.43ms
      17196 (new loss) 2660.71ms
47    11512 (new win)  2674.82ms
      17404 (new loss) 2683.49ms
49    11000 (new win)  2692.06ms
      17608 (new loss) 2699.25ms
51     8736 (new win)  2708.31ms
      16080 (new loss) 2716.19ms
53     7584 (new win)  2728.13ms
      13704 (new loss) 2734.08ms
55     4484 (new win)  2740.88ms
       7936 (new loss) 2746.73ms
57     2976 (new win)  2752.44ms
       4992 (new loss) 2757.31ms
59     2676 (new win)  2764.9ms
       3928 (new loss) 2772.32ms
61     1376 (new win)  2779.51ms
       1864 (new loss) 2783.27ms
63      512 (new win)  2786.09ms
        928 (new loss) 2789.16ms
65      680 (new win)  2791.35ms
       1736 (new loss) 2795.18ms
67      384 (new win)  2797.96ms
        640 (new loss) 2800.86ms
69      312 (new win)  2803.2ms
        552 (new loss) 2805.83ms
71      192 (new win)  2808.28ms
        400 (new loss) 2812.69ms
73      136 (new win)  2818.1ms
        224 (new loss) 2823.06ms
75        0 (new win)  2825.38ms
          0 (new loss) 2827.73ms
Done after 76 iterations and 2828.62ms

Iteration 0 are simply the number of won (checkmate)/illegal positions that are found first.

For the knight:

Code: Select all

 0    22640 8849260 228.58ms
 1   147432 (new win)  240.085ms
      63280 (new loss) 268.429ms
 3   174072 (new win)  286.965ms
     115440 (new loss) 325.294ms
 5   386232 (new win)  358.06ms
     173272 (new loss) 432.976ms
 7   359428 (new win)  481.688ms
     187088 (new loss) 550.029ms
 9   340292 (new win)  605.601ms
     208392 (new loss) 671.111ms
11   304020 (new win)  735.39ms
     185256 (new loss) 795.314ms
13   282040 (new win)  853.157ms
     185048 (new loss) 909.993ms
15   270916 (new win)  965.766ms
     177008 (new loss) 1019.63ms
17   250368 (new win)  1075.82ms
     155108 (new loss) 1125.62ms
19   233180 (new win)  1176.67ms
     156848 (new loss) 1224.34ms
21   235680 (new win)  1276.11ms
     158864 (new loss) 1326.44ms
23   229772 (new win)  1377.65ms
     153856 (new loss) 1423.25ms
25   204108 (new win)  1470.61ms
     128268 (new loss) 1515.01ms
27   167700 (new win)  1556.61ms
      98760 (new loss) 1588.57ms
29   133360 (new win)  1625.61ms
      78388 (new loss) 1653.87ms
31   106992 (new win)  1680.66ms
      62780 (new loss) 1702.92ms
33    80072 (new win)  1725.98ms
      57132 (new loss) 1745.21ms
35    64636 (new win)  1768.17ms
      46820 (new loss) 1784.42ms
37    47688 (new win)  1802.45ms
      34692 (new loss) 1817.71ms
39    31172 (new win)  1832.45ms
      23680 (new loss) 1843.43ms
41    17104 (new win)  1856.6ms
      13020 (new loss) 1864.23ms
43     8240 (new win)  1871.52ms
       7256 (new loss) 1878.92ms
45     3392 (new win)  1885.89ms
       3528 (new loss) 1892.81ms
47     2384 (new win)  1897.62ms
       2664 (new loss) 1902.07ms
49     1304 (new win)  1905.32ms
       1280 (new loss) 1909.95ms
51      616 (new win)  1912.79ms
        360 (new loss) 1916.5ms
53       80 (new win)  1918.88ms
         16 (new loss) 1921.66ms
55        0 (new win)  1924.78ms
          0 (new loss) 1928.21ms
Done after 56 iterations and 1929.39ms

What I find odd either way is that the knight seems to be a poorer defender than the Ferz (max DTM is smaller), but I make no claim that these numbers are actually correct. I'll have to do some real testing/debugging before I can say anything about that.

I thought that making Sjaak play with iron pieces would be relatively easy (simply not defining a capture move for the enemy pieces would do it), but unfortunately that has the side-effect of getting rid of check as well. Perhaps adding a per-piece "iron" property would be easier, then I can just mask out that bitboard when doing move generation. Not sure when I get round to that though.

[hgm]

Well, the fact that the numbers are different already is most useful. It means I will not be wasting time by scrutinizing the code more.

Taking away white captures was indeed what came to my mind too, but like you say, it would make the King iron too. I guess in this particular case it is acceptable that all black non-royals are iron, so I could just put a test based on this at the point where it runs into an occupied square, to either break out of the ray-scan loop or let it pass.

[Evert]

The first thing I'll have to work out is why I get the same number of checkmate positions for both endings (KQKF and KQKN), that looks highly suspicious to me (doesn't mean it's wrong of course).

One thing I may have overlooked: it's possible that both the queen and the ferz (or knight) are treated as "iron" at the moment.

One thing I noticed: it looks like max DTM is larger for the Ferz in your case as well, so it seems to be correct that the Ferz is a better defender than the Knight in this situation.

[hgm]

That does indeed seem wrong. There should be more cases where a position that is checkmate in KQK is not checkmate now because the Knight attacks the Queen or white King, then there are when the Ferz attacks the Queen or white King. Ferz might be able to interpose a bit better, (the white King occupies a square from which the Knight can interpose), but that should not nearly make up for it.

I am not sure max DTM is a good measure for quality of the defender. The number of wins seems much more important. After that the average DTM seems more important than the max.