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