On-demand tablebase generation

[hgm]

I guess I was wrong: there are checkmates in KQKx that are not mates in KQK, where the x blocks the only escape square. The number of KQK mates is 364, (if my 3-men buider got that right), and the number of corresponding mates in KQKx would be 61x364 = 22,204. For ever KQK mate there would be just a few positions where the black King had one escape, and it is now blocked by an x that can also not defend against the check.

Your number is very close to this. So it seems you don't take account of the fact that the defender can capture the white K or Q.

[Evert]

I guess I was wrong: there are checkmates in KQKx that are not mates in KQK, where the x blocks the only escape square. The number of KQK mates is 364, (if my 3-men buider got that right), and the number of corresponding mates in KQKx would be 61x364 = 22,204. For ever KQK mate there would be just a few positions where the black King had one escape, and it is now blocked by an x that can also not defend against the check.

Your number is very close to this. So it seems you don't take account of the fact that the defender can capture the white K or Q.

My 3-men generator also gets 364 mate positions for KQK, so that seems correct (I get the same number of mate-in-one from those that Marcel's generator reports).

Anyway, I was indeed missing captures by the defending black piece, and I wasn't marking BTM positions with the white king in check as illegal.
Both those taken care of, I now get

Code: Select all

 0    21344 8860204 204.284ms
 1   143608 (new win)  214.175ms
      60332 (new loss) 230.664ms
 3   175336 (new win)  249.453ms
     118200 (new loss) 274.174ms
 5   386940 (new win)  311.436ms
     205836 (new loss) 362.92ms
 7   481560 (new win)  426.284ms
     254280 (new loss) 490.57ms
 9   552580 (new win)  572.151ms
     351804 (new loss) 643.968ms
11   586540 (new win)  746.352ms
     393860 (new loss) 832.198ms
13   563584 (new win)  944.063ms
     420212 (new loss) 1022.49ms
15   493552 (new win)  1147.52ms
     385960 (new loss) 1228.19ms
17   363332 (new win)  1341.71ms
     311984 (new loss) 1396.24ms
19   271212 (new win)  1490.39ms
     259280 (new loss) 1539.33ms
21   218872 (new win)  1614.77ms
     200928 (new loss) 1653.59ms
23   170204 (new win)  1714.28ms
     177288 (new loss) 1746.35ms
25   162516 (new win)  1804.38ms
     183164 (new loss) 1836.43ms
27   165424 (new win)  1892.47ms
     180696 (new loss) 1923.29ms
29   135468 (new win)  1977.12ms
     143228 (new loss) 2004.62ms
31    94168 (new win)  2047.58ms
     101608 (new loss) 2068.24ms
33    62804 (new win)  2100.63ms
      67428 (new loss) 2118.73ms
35    41392 (new win)  2146.32ms
      42976 (new loss) 2157.28ms
37    32620 (new win)  2176.8ms
      34676 (new loss) 2188.81ms
39    34092 (new win)  2203.04ms
      39528 (new loss) 2214.11ms
41    35616 (new win)  2235.02ms
      45388 (new loss) 2246.51ms
43    39268 (new win)  2266.59ms
      45808 (new loss) 2281.08ms
45    29912 (new win)  2301.24ms
      32880 (new loss) 2310.93ms
47    22632 (new win)  2330.73ms
      24872 (new loss) 2339.38ms
49    17184 (new win)  2352.36ms
      19576 (new loss) 2361.78ms
51    16976 (new win)  2371.8ms
      19440 (new loss) 2380.24ms
53    13528 (new win)  2390.42ms
      17096 (new loss) 2398.38ms
55    12440 (new win)  2410.09ms
      14672 (new loss) 2417.36ms
57    11320 (new win)  2426.17ms
      13296 (new loss) 2432.53ms
59     6824 (new win)  2443.57ms
       7896 (new loss) 2449.5ms
61     5896 (new win)  2455.24ms
       6848 (new loss) 2460.67ms
63     5304 (new win)  2466.09ms
       5872 (new loss) 2472.55ms
65     5344 (new win)  2478.97ms
       5504 (new loss) 2485.55ms
67     4312 (new win)  2495.74ms
       5248 (new loss) 2503.02ms
69     4568 (new win)  2508.19ms
       5096 (new loss) 2513.41ms
71     4152 (new win)  2519.29ms
       5232 (new loss) 2524.42ms
73     4016 (new win)  2529.06ms
       4856 (new loss) 2535.39ms
75     4032 (new win)  2545.25ms
       4760 (new loss) 2551.73ms
77     3032 (new win)  2556.14ms
       2752 (new loss) 2560.61ms
79     1944 (new win)  2564.17ms
       1512 (new loss) 2571.01ms
81     1128 (new win)  2574.51ms
       1608 (new loss) 2579.23ms
83     1248 (new win)  2582.47ms
       1304 (new loss) 2587.47ms
85      408 (new win)  2595.11ms
        544 (new loss) 2601.5ms
87      216 (new win)  2603.75ms
        160 (new loss) 2606.91ms
89       72 (new win)  2608.74ms
         48 (new loss) 2610.97ms
91       96 (new win)  2612.78ms
         80 (new loss) 2615.27ms
93       80 (new win)  2617.22ms
         56 (new loss) 2618.95ms
95        0 (new win)  2620.8ms
          0 (new loss) 2622.29ms
Done after 96 iterations and 2622.78ms

for the Ferz and

Code: Select all

 0    20512 8881020 250.148ms
 1   141824 (new win)  260.633ms
      45664 (new loss) 284.694ms
 3   129772 (new win)  300.174ms
      64128 (new loss) 325.242ms
 5   192008 (new win)  350.642ms
      69564 (new loss) 386.438ms
 7   144096 (new win)  409.677ms
      63464 (new loss) 435.146ms
 9   141004 (new win)  456.577ms
      54604 (new loss) 483.062ms
11   115708 (new win)  502.087ms
      44916 (new loss) 523.259ms
13    98024 (new win)  539.883ms
      34184 (new loss) 558.496ms
15    83512 (new win)  575.619ms
      28308 (new loss) 590.781ms
17    70936 (new win)  606.108ms
      24940 (new loss) 621.276ms
19    58564 (new win)  632.427ms
      15064 (new loss) 645.125ms
21    40792 (new win)  655.831ms
      11036 (new loss) 665.22ms
23    23416 (new win)  672.21ms
       6232 (new loss) 680.798ms
25    12040 (new win)  686.036ms
       4016 (new loss) 691.81ms
27     7544 (new win)  698.771ms
       1752 (new loss) 706.801ms
29     2704 (new win)  710.638ms
        800 (new loss) 714.667ms
31      672 (new win)  717.099ms
         24 (new loss) 720.585ms
33       24 (new win)  722.38ms
         24 (new loss) 723.868ms
35       24 (new win)  725.622ms
         24 (new loss) 727.247ms
37       72 (new win)  730.477ms
          0 (new loss) 732.102ms
Done after 38 iterations and 732.543ms

for the knight.

[hgm]

OK, thanks. That sounds more reasonable as what I got. (I.e. much closer to the number of mates I counted by hand.) It also dawned on me that the number of mates does not depend on whether the black defender is iron or not, and can thus be easily verified from standard EGT (for Knight) or with Fairy-Gen (for Ferz).

[Evert]

OK, thanks. That sounds more reasonable as what I got. (I.e. much closer to the number of mates I counted by hand.) It also dawned on me that the number of mates does not depend on whether the black defender is iron or not, and can thus be easily verified from standard EGT (for Knight) or with Fairy-Gen (for Ferz).

I tried comparing with Fairy-Gen (woud work for KQKN as well of course), but unfortunately I can't make heads or tails of its standard output. Does it print the number of checkmate positions somewhere?

[hgm]

Hmm, yes, I guess this is non trivial, and I had to consult the README file myself on how to use it.

In any case you should ignore what it prints while running, as these are not syymetry-corrected numbers, only indicated to give an idication of the progress it is making. It creates a file rep2.txt which contains the symmetry-corrected data. Unfortunately that data still has to be multiplied by 4.

Furthermore, when you use it in (default) DTC mode, it does not tell you the mates at all, as King captures and other winning conversions are just heaped into one. So you have to run with the -m flag, to calculate DTM. Then the line labeled "1." gives you the checkmates ("0." are the King captures). E.g. "3men -m KQ.K" produces a rep2.txt

Code: Select all

KQ_K

WON.wtm      62496
K capture    26369
other        36127
  0.          5742
  1.            91
  2.           338
  3.           739
  4.          1870
  5.          3536
  6.          6371
  7.          9977
  8.         13513
  9.         10950
 10.          2825
 11.            14
WON.btm      50224
stalemate      218
W check       6312
LEGAL        56184
TOTAL        62496

The "1. 91" gives the checkmates, and indeed 4*91 = 364.

Applying this method to the 4men gives

KQ.KF = 4*4866 = 19,464
KQ.KN = 4*4187 = 16,748

Based on my hand calculation that first number seems to be in the right ball-park. I could not find any place on-line anymore where the nalimov .tbs files are hosted, so I could not check the KQKN number.

[Evert]

Ah, I wasn't including evasions by other pieces at all, but then I also wasn't discounting positions where black would try to get out of check by taking its own secondary piece.

With all that taken care of, I now get

Code: Select all

 0    19464 7884856 211.989ms
 1   133480 (new win)  221.787ms
      49792 (new loss) 238.215ms
 3   153876 (new win)  253.921ms
     102112 (new loss) 277.206ms
 5   341780 (new win)  311.856ms
     171108 (new loss) 357.86ms
 7   397352 (new win)  408.614ms
     197416 (new loss) 461.691ms
 9   398040 (new win)  519.739ms
     231720 (new loss) 570.568ms
11   350152 (new win)  639.535ms
     211084 (new loss) 687.144ms
13   257104 (new win)  751.345ms
     180804 (new loss) 792.597ms
15   181500 (new win)  850.383ms
     112572 (new loss) 877.544ms
17   108888 (new win)  914.316ms
      75896 (new loss) 934.733ms
19    71304 (new win)  960.546ms
      47356 (new loss) 976.702ms
21    46184 (new win)  998.341ms
      35968 (new loss) 1012.15ms
23    39056 (new win)  1028.89ms
      31324 (new loss) 1042.08ms
25    43772 (new win)  1056.08ms
      36624 (new loss) 1067.33ms
27    45224 (new win)  1085.19ms
      39392 (new loss) 1098.53ms
29    38308 (new win)  1114.34ms
      33192 (new loss) 1126.44ms
31    31736 (new win)  1144.82ms
      24264 (new loss) 1153.82ms
33    24172 (new win)  1165.9ms
      16536 (new loss) 1173.89ms
35    16416 (new win)  1183.97ms
      12408 (new loss) 1193.94ms
37    13248 (new win)  1203.54ms
       9016 (new loss) 1211.48ms
39     9304 (new win)  1218.91ms
       5992 (new loss) 1226.62ms
41     9504 (new win)  1239.07ms
       7448 (new loss) 1245.35ms
43    12080 (new win)  1250.69ms
      11768 (new loss) 1256.8ms
45    22808 (new win)  1263.48ms
      21744 (new loss) 1271.59ms
47    33696 (new win)  1281.77ms
      27776 (new loss) 1295.07ms
49    27600 (new win)  1308.5ms
      22448 (new loss) 1317.63ms
51    20312 (new win)  1328.24ms
      19320 (new loss) 1340.69ms
53    17952 (new win)  1351.65ms
      15040 (new loss) 1358.88ms
55    17880 (new win)  1368.25ms
      15432 (new loss) 1375.61ms
57    15960 (new win)  1386.57ms
      14344 (new loss) 1395.35ms
59    16184 (new win)  1403.49ms
      13360 (new loss) 1411.2ms
61    16432 (new win)  1419.19ms
      15584 (new loss) 1426.63ms
63    19832 (new win)  1440.9ms
      18056 (new loss) 1449.36ms
65    24752 (new win)  1458.74ms
      22136 (new loss) 1471.36ms
67    24056 (new win)  1485.9ms
      19552 (new loss) 1494.82ms
69    20536 (new win)  1504.68ms
      15624 (new loss) 1514.23ms
71    16480 (new win)  1526.35ms
      12376 (new loss) 1533.99ms
73    12000 (new win)  1541.71ms
       9168 (new loss) 1549.17ms
75     9568 (new win)  1557.87ms
       7128 (new loss) 1564.63ms
77     6320 (new win)  1570.4ms
       5080 (new loss) 1575.69ms
79     4848 (new win)  1582.31ms
       2736 (new loss) 1587.21ms
81     2304 (new win)  1590.67ms
       1128 (new loss) 1595.05ms
83      864 (new win)  1600.19ms
        520 (new loss) 1606.42ms
85      400 (new win)  1610.17ms
        208 (new loss) 1614.24ms
87       56 (new win)  1616.26ms
         40 (new loss) 1618.69ms
89        8 (new win)  1620.39ms
          0 (new loss) 1621.64ms
Done after 90 iterations and 1622.05ms

for the iron Ferz and

Code: Select all

 0    16748 7884856 224.39ms
 1   117728 (new win)  233.501ms
      30416 (new loss) 253.258ms
 3    91792 (new win)  266.464ms
      38152 (new loss) 287.653ms
 5   127408 (new win)  303.326ms
      31920 (new loss) 327.581ms
 7    56540 (new win)  339.856ms
      14132 (new loss) 352.973ms
 9    31268 (new win)  363.011ms
       6532 (new loss) 371.404ms
11    13320 (new win)  376.6ms
       2964 (new loss) 381.838ms
13     6184 (new win)  385.534ms
       1080 (new loss) 389.822ms
15     1488 (new win)  394.513ms
        272 (new loss) 398.851ms
17      416 (new win)  405.324ms
         24 (new loss) 409.602ms
19       24 (new win)  411.439ms
          0 (new loss) 412.923ms
Done after 20 iterations and 413.365ms

for the iron Knight. So at least my checkmate positions seem to agree with FairyGen.

Speaking of which, is it possible that I have an old version of that? It doesn't seem to understand the "-m" flag, it just segfaults.

[hgm]

I am not sure I ever updated Fairy-Gen. But as I was on a new laptop, I googled for it and found the link I announced for it on CCRL forum, and downloaded that zip file. That was the version I was using, and I expect it is the same as what you did.

The -m argument has to be first, like "4men -m KQ.KN". I don't think Fairy-Gen is very clever in parsing its arguments; they have to come in a fixed order.

[Evert]

Well, the version I have definitely doesn't know about a -m commandline option (only -xboard). The readme file is dated Nov 1 2011.

[hgm]

Well, the README.txt of the evrsion I have also writes that date under the prologue, but at the end contains a changelog with the following text:

Code: Select all

                          CHANGE LOG

Version 1.1, Nov 10, 2011
* fixed bug in probing (wrong diag symmetry)
* fixed wrong determination of color-binding from piecedef.ini
* added -0 option, which allows black to null-move
* added -s option, which makes stalemate a win (-0 -s = forced pass)
* ask user if he wants to continue after DTC overflows
* use tabs in xboard output for less jumpy formatting
* print XBoard thinking output for probe (DTC score)
* make XBoard also show (octal) maximin positions
* command syntax now is "4men [-xboard] [-0] [-s] KBB.K"

Version 1.2, Nov 17, 2011
* added posibility to 'seed' arbitrary positions to arbitrary state
* changed treatment of stalemate when null-moving allowed
* added flag for building DTM in stead of DTC
* improved description README file
* new command syntax: "4men [-xboard] [-m] [-0] [-s] [-f FILENAME] KBB.K"

I got it through the link here: http://kirill-kryukov.com/chess/discuss ... f=6&t=6258

[Melin]

I dug up my ancient (1996) 'pretty fast' kbnk and kqkr generators. It turns out they still work:
KBNK takes 76 ms.
KQKR takes 342 ms.
Single core. Machine+compiler speed has improved by a factor 22000 over the years.

Very nice.

Got a slight additional improvement using the bitboards for the bishop, instead of for the black king. This gives higher bit density, the number of calls to enter is reduced by about half.