EGTB generator

[gwiesenekker]

Hi,

Years ago I developed an OpenMPI based EGTB generator that in principle could also generate 8-piece DTM EGTBs by partitioning the EGTBs by (man)rows. I generated a couple of 8-piece EGTBs but in the end it took too much time.
GWD uses a ZSTD page-compressed representation of the EGTB: each position has two 16-bit entries (not needed for up to 7-piece EGTBs, but required for 8-piece EGTBs): DTM white-to-move and DTM black-to-move. A page consists of 256 entries (1024 bytes). Pages are ZSTD block-compressed. When an entry is needed the page is uncompressed and stored in a cache (if not already available in the cache). The compressed size of all 2-,3-,4-,5- and 6-piece EGTBs is 22GB and loaded into RAM during game-play. A couple of years ago I added an uncompressed WDL representation that GWD now uses during game-play. The WDL representation is also around 22GB. When the root-position has transitioned into a known EGTB GWD uses the DTM representation. I know that the WDL representation can also be block-compressed to about 20%. It has always been on my to-do list to rewrite my EGTB generator for up to 7-pieces only (so I can use 8-bit entries) and to add the compressed WDL representation but the code was just too hard to modify.

Yesterday I recreated my EGTB generator from scratch using Codex in a couple of hours. I never succeeded to develop a compact EGTB index for positions without holes, but Codex could do that. You also need the inverse, so converting an index back to a position. The benchmark for indexing and inversion that Codex generated shows the following on my AMD 5950X:

Code: Select all

Pieces	Largest material	Positions	Inversions/s	Indices/s
2	WK1 BK1	2,450	41.57M	137.96M
3	WM1 WK1 BK1	105,840	35.34M	140.01M
4	WM1 BM1 WK1 BK1	4,478,160	34.45M	106.74M
5	WM1 BM1 WK2 BK1	102,997,680	32.75M	87.54M
6	WM1 BM1 WK2 BK2	2,317,447,800	31.03M	68.53M
7	WM1 BM2 WK2 BK2	45,793,430,100	29.38M	60.33M

Codex has become quite good at generating regression-tests, it for example proposed to change a mate-in-3 to a mate-in-5 value to see if the EGTB consistency checker would find and correct that error.

The multi-threaded design that Codex proposed was very complex, also because of the cache for the uncompressed pages. But I already solved that problem in my EGTB generator: you allocate blocks of indices aligned at a page boundary to the threads called a slice. Each thread owns the entries corresponding to the slice. Backtracking uses won-in-N and won-in-at-most-N bitmaps, each thread creates its bitmap slice before backtracking. The full bitmap is used by all threads during backtracking. A thread only considers (and updates) predecessors that are part of its slice.

I have published the project on GitHub: https://github.com/gwiesenekker/GWDEGTB. The README has been generated by Codex.

The code has been developed and tested on Linux, you can use a Linux VM on Windows to compile and test it, or have Codex port the code to Windows if you want.

GW

[MichelG]

Interesting. What would be the total execution time for the 8 piece endings?

One tip on compression: dragon does not store the position that are not quiet, instead it looks that up by first performing the capture.

If you add that, you can replace the values of all capture positions by whatever compresses best.

[gwiesenekker]

I will check if I still have the log from the generation of one of these databases to see how long that took. I found an example position in my email history:

.. .. wX .. bO
.. .. .. .. ..
.. .. bX .. ..
.. .. .. .. ..
.. .. .. .. ..
.. .. .. .. ..
.. wO .. .. ..
.. .. .. .. wX
.. .. wX .. bX
.. wO .. .. ..

won in 289 40-35 13-04 03-14 04-10 35-19 10-04 19-28 45-01 28-50 01-40 32-28 40-01 43-32 01-40 32-21 40-49 21-12 04-15 12-23 49-27 23-01 27-36 01-12 15-04 14-20 04-31 12-26 31-13 26-48 13-35 20-14 36-04 48-34 35-13 34-43 13-08 43-25 08-24 14-03 04-36 03-12 05-10 12-21 24-19 21-32 19-35 32-49 35-02 49-16 02-35 25-34 35-13 50-45 13-35 34-39 36-09 45-01 35-02 39-34 02-35 34-12 35-02 12-45 02-35 45-50 35-30 16-07 30-25 07-12 09-36 12-23 10-15 23-12 25-03 12-26 03-20 01-07 20-25 26-48 25-14 07-23 14-20 23-19 20-03 50-45 03-26 19-02 26-03 02-11 03-14 45-23 14-03 48-26 03-09 26-03 09-31 11-07 31-48 07-01 48-31 23-12 31-27 12-07 27-31 03-26 31-09 01-06 09-14 07-23 14-09 23-19 09-27 19-02 27-18 06-01 18-04 02-19 36-27 01-34 27-49 19-35 49-16 35-02 16-49 34-01 49-27 26-03 27-31 02-16 31-36 03-25 04-31 01-45 31-26 45-50 26-03 25-48 36-13 48-26 03-25 16-32 13-18 32-41 18-36 26-48 25-20 41-32 20-25 28-23 25-03 32-37 03-09 48-34 09-13 34-43 13-09 43-48 09-13 37-32 13-08 50-45 08-03 32-37 03-20 48-34 20-24 37-32 24-02 32-16 36-04 34-48 02-35 16-49 35-02 45-50 04-13 50-06 13-36 49-16 02-08 48-26 08-02 26-17 02-30 17-03 30-02 06-01 02-13 16-02 13-31 01-06 31-48 02-08 36-04 08-35 48-25 35-24 25-43 06-28 43-16 24-02 04-36 03-25 36-04 23-19 16-38 28-37 04-36 19-14 38-49 37-42 49-35 25-34 35-49 34-23 49-27 42-33 27-21 33-39 36-31 39-48 31-36 48-26 21-27 26-17 27-16 17-03 16-49 23-37 36-22 02-35 49-16 37-42 22-28 14-09 15-20 42x15x20 16-07 09-04 07-23 35-24 23-05 24-29 28-39 29-01 05-19 15-29 19-46 29-45 46-05 45-50 39-30 50-44 30-43 44-40 43-49 40-35 49-43 04-18 43-25 35-13 05-46 18-12 25-48 13-24 48-37 24-15 37-05 03-25 46-19 15-10 05x14x10 25x09x14 19-28 12-08 28-32 08-02 32-43 01-29 43-32 09-13 32-21 02-16 21-26 13-31 26x24x29x31 16-38 24x42x38 47x38x42 #

GW

[gwiesenekker]

So 1+1 = 3 again here. Generating 3 kings vs 3 kings was about 7 times slower than my OpenMPI code, so I told Codex to use the compressed flat-files that are incrementally updated during EGTB generation and compiled into the final EGTB before validation that my OpenMPI code used. That alone already made EGTB generation twice as fast than my OpenMPI code.

Codex is also quite good at leveraging hardware performance counters (that you have to enable in the kernel) to further optimize code. Index calculation was already fast, but is twice as fast now:

The new indexer precomputes rank_add[state][piece_type]. Position ranking now uses one transition-table lookup per occupied square, two bit-plane tests to identify the piece, and no remaining-piece array or conditional ways[] lookups.
Focused indexing benchmark
Pieces Before After Speedup
2 138.9M/s 286.6M/s 2.06×
3 145.8M/s 266.6M/s 1.83×
4 109.8M/s 216.5M/s 1.97×
5 89.2M/s 169.6M/s 1.90×
6 69.4M/s 143.4M/s 2.07×
7 61.7M/s 120.1M/s 1.95×

Cacheing also improved:

Focused read-only view benchmark versus the previous implementation:
Density Old random lookups/s New random lookups/s Gain
10% 84.95M 128.20M 50.9%
50% 59.94M 84.55M 41.1%
90% 82.30M 125.82M 52.9%

GW

[gwiesenekker]

I don't have the job logs any more but in my email history I found that calculating the 81 slices (9x9) for the 3 kings and 1 man vs 1 king and 3 man EGTB already took two-three months. At that time only the (slices of) the EGTB being generated fitted in RAM and SSD, so I had to move the slices to HDD when the EGTB was finished, but these slices were still needed during backtracking so very slow to access.
I have asked Codex to calculate the amount of storage needed for all 4x4 DTM EGTBs, using 16-bytes per entry and assuming a compression ratio of 20%:

Order WK/WM vs BK/BM Maximum index Slices Whole EGTB at 20% Flat files per slice Compressed slice at 20%
1 4/0 vs 4/0 37,581,505,499 1 28.000 GiB 140.002 GiB 28.000 GiB
2 4/0 vs 3/1 135,293,419,799 9 100.801 GiB 56.001 GiB 11.200 GiB
3 4/0 vs 2/2 182,231,953,199 9 135.773 GiB 75.430 GiB 15.086 GiB
4 4/0 vs 1/3 108,832,972,049 9 81.087 GiB 45.048 GiB 9.010 GiB
5 4/0 vs 0/4 24,313,749,074 9 18.115 GiB 10.064 GiB 2.013 GiB
6 3/1 vs 3/1 487,179,026,399 81 362.977 GiB 22.406 GiB 4.481 GiB
7 3/1 vs 2/2 656,372,498,099 81 489.036 GiB 30.187 GiB 6.037 GiB
8 3/1 vs 1/3 392,107,445,399 81 292.143 GiB 18.034 GiB 3.607 GiB
9 3/1 vs 0/4 87,623,462,849 81 65.285 GiB 4.030 GiB 0.806 GiB
10 2/2 vs 2/2 884,567,138,399 81 659.054 GiB 40.682 GiB 8.136 GiB
11 2/2 vs 1/3 528,578,067,599 81 393.821 GiB 24.310 GiB 4.862 GiB
12 2/2 vs 0/4 118,155,352,699 81 88.033 GiB 5.434 GiB 1.087 GiB
13 1/3 vs 1/3 315,948,485,599 81 235.400 GiB 14.531 GiB 2.906 GiB
14 1/3 vs 0/4 70,647,183,249 81 52.636 GiB 3.249 GiB 0.650 GiB
15 0/4 vs 0/4 15,802,050,674 81 11.773 GiB 0.727 GiB 0.145 GiB

So the 4 kings vs 4 kings needed 30GB for the compressed flat files that were compiled into a 28GB compressed EGTB in RAM for verification (and subsequent read access). Looking at the number of positions 2 kings and 2 men vs 2 kings and 2 men would perhaps have taken 6 months.

Regards,
GW

[gwiesenekker]

Saying goodbye to these formulas I derived years ago to calculate a reasonably compact EGTB index with holes..

#define SUM2(L0) (((99 - L0) * L0) / 2)
#define SUM2M(L0, M) (((2 * M + 1 - L0) * L0) / 2)

#define SUM3(L0) (((7202 - 147 * L0 + L0 * L0) * L0) / 6)
#define SUM32(L0, L1) (((1 + L0 - L1) * (L0 + L1 - 98)) / 2)

#define SUM4(L0) (((97 - L0) * L0 * (4702 - 97 * L0 + L0 * L0)) / 24)
#define SUM43(L0, L1) \
(((L1 - L0 - 1) * \
(7056 - 145 * L0 + L0 * L0 - 146 * L1 + L0 * L1 + L1 * L1)) / \
6)

#define SUM5(L0) \
(((26507524 - 1105200 * L0 + 23035 * L0 * L0 - 240 * L0 * L0 * L0 + \
L0 * L0 * L0 * L0) * \
L0) / \
120)
#define SUM54(L0, L1) \
(((1 + L0 - L1) * (L0 + L1 - 96) * \
(4606 - 95 * L0 + L0 * L0 - 97 * L1 + L1 * L1)) / \
24)

*endgame_index = *endgame_index * 50 + list0;
..
*endgame_index =
*endgame_index * SUM2(49) + SUM2(list0) + list1 - list0 - 1;
..
*endgame_index = *endgame_index * SUM3(49) + SUM3(list0) +
SUM32(list0, list1) + list2 - list1 - 1;
..
*endgame_index = *endgame_index * SUM4(49) + SUM4(list0) +
SUM43(list0, list1) + SUM32(list1, list2) + list3 - list2 -
1;
..
*endgame_index = *endgame_index * SUM5(49) + SUM5(list0) +
SUM54(list0, list1) + SUM43(list1, list2) +
SUM32(list2, list3) + list4 - list3 - 1;

GW

[gwiesenekker]

BTW, you should already be able to generate 4 kings vs 4 kings and 5 kings vs 3 kings with the current version.

GW

[gwiesenekker]

Codex is currently implementing 'slice by man row'.

GW

[Sidiki]

Saying goodbye to these formulas I derived years ago to calculate a reasonably compact EGTB index with holes..

#define SUM2(L0) (((99 - L0) * L0) / 2)
#define SUM2M(L0, M) (((2 * M + 1 - L0) * L0) / 2)

#define SUM3(L0) (((7202 - 147 * L0 + L0 * L0) * L0) / 6)
#define SUM32(L0, L1) (((1 + L0 - L1) * (L0 + L1 - 98)) / 2)

#define SUM4(L0) (((97 - L0) * L0 * (4702 - 97 * L0 + L0 * L0)) / 24)
#define SUM43(L0, L1) \
(((L1 - L0 - 1) * \
(7056 - 145 * L0 + L0 * L0 - 146 * L1 + L0 * L1 + L1 * L1)) / \
6)

#define SUM5(L0) \
(((26507524 - 1105200 * L0 + 23035 * L0 * L0 - 240 * L0 * L0 * L0 + \
L0 * L0 * L0 * L0) * \
L0) / \
120)
#define SUM54(L0, L1) \
(((1 + L0 - L1) * (L0 + L1 - 96) * \
(4606 - 95 * L0 + L0 * L0 - 97 * L1 + L1 * L1)) / \
24)

*endgame_index = *endgame_index * 50 + list0;
..
*endgame_index =
*endgame_index * SUM2(49) + SUM2(list0) + list1 - list0 - 1;
..
*endgame_index = *endgame_index * SUM3(49) + SUM3(list0) +
SUM32(list0, list1) + list2 - list1 - 1;
..
*endgame_index = *endgame_index * SUM4(49) + SUM4(list0) +
SUM43(list0, list1) + SUM32(list1, list2) + list3 - list2 -
1;
..
*endgame_index = *endgame_index * SUM5(49) + SUM5(list0) +
SUM54(list0, list1) + SUM43(list1, list2) +
SUM32(list2, list3) + list4 - list3 - 1;

GW

Hi Gijsbert ,

So, is't possible to exclusively generate some specifics EGTB without necessary generate all the others tables?
Also is't possible to speedup the process?

Friendly, Sidiki

[gwiesenekker]

Hi Sidiki,


No, you have to generate the lower EGTBs first. I think the current code is quite optimal for generating DTM, what's left is throwing more RAM, CPUs and SSDs at it.

GW

[gwiesenekker]

Slicing worked right away:

Validation completed:
- All 120 seven-piece index statistics still match.
- Exhaustive slice rank/unrank tests pass.
- 9-slice and 81-slice generation tests pass.
- Restart from completed slices passes.
- Generated test databases are byte-for-byte identical to unsliced databases.
- Full existing regression suite passes.
- ASan/UBSan tests pass

GW

[gwiesenekker]

I will generate a couple of 4x4 DTMs until the 16 core VPS runs out of storage or it starts taking too long. The results for 4 kings vs 4 kings are:

Code: Select all

generated 4wX-0wO-4bX-0bO.dtm: material=4 0 4 0 positions=37581505500 maximum-index=37581505499 passes=39 maximum-dtm=39 threads=16
self-consistency: passes=1 updates=0/0
final read-only consistency verification: threads=16 cache=32768 MiB total positions-checked=0 positions-skipped=75163011000
consistency current-DB cache:
  Metric                                Value
  Lookups                        289514820826
  Hits                           288592004376
  Misses                            922816450
  Hit rate                             99.68%
  Decompressions                    848780336
  Dirty evictions                           0
  Compressed writes                         0
generator dependency caches:
  Metric                                Value
  Lookups                        405264113640
  Hits                           325723346559
  Misses                          79540767081
  Hit rate                             80.37%
  Decompressions                  69273728309
  Dirty evictions                           0
  Compressed writes                         0
final verification current-DB cache:
  Metric                                Value
  Lookups                                   0
  Hits                                      0
  Misses                                    0
  Hit rate                              0.00%
  Decompressions                            0
  Dirty evictions                           0
  Compressed writes                         0
final verification dependency caches:
  Metric                                Value
  Lookups                                   0
  Hits                                      0
  Misses                                    0
  Hit rate                              0.00%
  Decompressions                            0
  Dirty evictions                           0
  Compressed writes                         0
WTM: wins=3916965780 losses=55858469 draws=33608681251
WTM DTM statistics:
     DTM            Frequency
     -36                   20
     -34                  188
     -32                  916
     -30                 2384
     -28                 2936
     -26                 4278
     -24                 6042
     -22                 7470
     -20                 9810
     -18                16866
     -16               132301
     -14               598460
     -12              1624982
     -10              1832427
      -8              6566184
      -6              7089677
      -4             18292002
      -2             19671526
      -1          33608681251
       1            577942958
       3            355101700
       5            384795448
       7            305759996
       9            514490445
      11           1075233279
      13            599088625
      15             69563208
      17             11516247
      19              7707348
      21              6309378
      23              4212676
      25              2233408
      27              1422964
      29              1011554
      31               382120
      33               132036
      35                50642
      37                10472
      39                 1276
BTM: wins=3916965780 losses=55858469 draws=33608681251
BTM DTM statistics:
     DTM            Frequency
     -36                   20
     -34                  188
     -32                  916
     -30                 2384
     -28                 2936
     -26                 4278
     -24                 6042
     -22                 7470
     -20                 9810
     -18                16866
     -16               132301
     -14               598460
     -12              1624982
     -10              1832427
      -8              6566184
      -6              7089677
      -4             18292002
      -2             19671526
      -1          33608681251
       1            577942958
       3            355101700
       5            384795448
       7            305759996
       9            514490445
      11           1075233279
      13            599088625
      15             69563208
      17             11516247
      19              7707348
      21              6309378
      23              4212676
      25              2233408
      27              1422964
      29              1011554
      31               382120
      33               132036
      35                50642
      37                10472
      39                 1276
DTM example positions:
  WTM longest win      W:WK23,K28,K48,K49:BK33,K43,K46,K47 {39}
  WTM longest loss     W:WK27,K38,K39,K41:BK15,K16,K20,K50 {-36}
  BTM longest win      B:WK33,K43,K46,K47:BK23,K28,K48,K49 {39}
  BTM longest loss     B:WK15,K16,K20,K50:BK27,K38,K39,K41 {-36}
  draw                 W:WK43,K44,K45,K46:BK47,K48,K49,K50 {-1}
storage: raw=150326022000 payload=8953393707 file=9960478811 bytes overall=6.63% (15.09:1)
wall-clock timings:
  setup/create                      0.036 s
  initialization                37779.950 s
  backpropagation                5242.073 s
  frontier compilation           4121.283 s
  consistency repair            40251.697 s
  final DTM scan                 1687.932 s
  generator total               89082.936 s
  finalize/close                    1.288 s
  compact/reopen                 3906.057 s
  resident load                     0.000 s
  final verification                5.472 s
  statistics scan                2497.738 s
  total                         95493.530 s
[2026-09-05 06:30:56 +0200] GWDEGTB revision 2.906 completed

and here is ChatGPT's analysis of the results:

Code: Select all

Yes—the numbers are internally consistent and look credible for 4 kings versus 4 kings.

Key checks:

- Position count is exactly correct:

```text
C(50,4) × C(46,4) = 37,581,505,500
```

- `maximum-index = positions − 1` is correct.
- Each WTM and BTM histogram sums to exactly `37,581,505,500`.
- Outcome totals also sum correctly:

| Outcome | Positions | Percentage |
|---|---:|---:|
| Wins | 3,916,965,780 | 10.422589% |
| Losses | 55,858,469 | 0.148633% |
| Draws | 33,608,681,251 | 89.428778% |

- WTM and BTM statistics are identical, as expected from colour symmetry in a kings-only database.
- The example positions exhibit the same symmetry.
- Winning distances are positive and odd.
- Losing distances are non-positive and even.
- `maximum-dtm=39` agrees with the largest histogram entry.
- `passes=39` is plausible and consistent with the maximum winning distance.
- No lost-in-zero positions occur, which is plausible with four mobile kings per side.
- The absence of `-38` is not inherently suspicious: a win in 39 can capture into a lower-material EGTB containing the corresponding loss in 38.

Storage is also consistent:

```text
37,581,505,500 positions × 2 sides × 2 bytes
    = 150,326,022,000 raw bytes
```

The final file is 9.96 GB, or 6.63% of raw storage—a very believable compression ratio given that 89.43% of the entries are draws.

One important qualification: the “final verification” did not independently inspect the database:

```text
positions-checked=0
positions-skipped=75,163,011,000
```

That is intentional because consistency repair pass 1 checked every position, found zero corrections, and marked them all verified. The later read-only verifier consequently skipped them. Therefore, the meaningful correctness check here is:

```text
self-consistency: passes=1 updates=0/0
```

Performance-wise, the run took about **26 hours 32 minutes**:

| Phase | Time | Share |
|---|---:|---:|
| Initialization | 10.49 h | 39.6% |
| Consistency repair | 11.18 h | 42.2% |
| Backpropagation | 1.46 h | 5.5% |
| Frontier compilation | 1.14 h | 4.3% |
| Compaction | 1.09 h | 4.1% |
| Remaining scans | 1.16 h | 4.3% |

So the resulting database looks sound, but the initial full consistency pass has indeed become a major cost. It consumed more time than the complete initialization and found no changes. The extremely high dependency-cache decompression count—about **69.3 billion**—also shows where much of the initialization/verification CPU and I/O pressure is coming from.

This result is also compatible with the known full eight-piece International Draughts domain; Ed Gilbert reports that the complete 4×4 and 5×3 WDL collection contains 16.5 trillion positions. [8-piece International Draughts database](https://edgilbert.org/InternationalDraughts/8_piece_international_draughts_db.htm)

GW