Dragon v4.7

[Joost Buijs]

The per-thread egdb cache is an interesting idea. I didn't realize you could read a small block from an SSD in 5 us. The last time I benchmarked this stuff was quite a while ago. I have a single egdb cache and use locks to protect critical regions.

I devised a benchmark using 40 million binary EGDB positions from real games. This shows that the very first cache miss can take substantially longer than 5 microseconds. Because both SSDs and Windows utilize caching, Windows will eventually cache the entire compressed 7P EGDB, assuming there is enough memory.

The numbers I have shown are averages across these 40 million positions: approximately 35 to 40 nanoseconds for a cache hit, and 5 microseconds for a cache miss. Since different threads analyse different variations anyway, I chose to use thread-local caches to avoid the locks required to synchronize a global cache.

Joost

[Joost Buijs]

not 100% sure, can you verify:

Format: configuration all_win all_draw all_lose, noncapture_win noncapture_draw noncapture_lose

1221 678795283 1395118040 7606227 86768707 568453887 260

Bert, thanks! I will compare these numbers with what I've got here.

Edit:

The numbers compare nicely. Now the depth figures are still missing, this is not very important.

Joost

[Krzysztof Grzelak]

Ed,
I have a question. As you wrote, you have 2 versions of the databases. Which one is better and more accurate.

[Ed Gilbert]

Krzysztof, in my tests kingsrow performed the same with either db in engine matches, and in test positions of 12 to 16 pieces measuring search time to obtain an egdb win or loss score. However version 1 is 389 GB vs 56 GB for version 2, so version 2 is much easier to manage on your internal drive and for archival storage, and it initializes much faster at startup. There is an advantage for version 1 if you are running a different kind of program that needs to lookup the WLD value of every position in a db, but an alphabeta engine search doesn't need that kind of functionality.

[Krzysztof Grzelak]

Krzysztof, in my tests kingsrow performed the same with either db in engine matches, and in test positions of 12 to 16 pieces measuring search time to obtain an egdb win or loss score. However version 1 is 389 GB vs 56 GB for version 2, so version 2 is much easier to manage on your internal drive and for archival storage, and it initializes much faster at startup. There is an advantage for version 1 if you are running a different kind of program that needs to lookup the WLD value of every position in a db, but an alphabeta engine search doesn't need that kind of functionality.

Thanks for the reply Ed. Can you tell me how much space a 10 figure database would take in GB? Of course, in draughts 10x10.

[Ed Gilbert]

Thanks for the reply Ed. Can you tell me how much space a 10 figure database would take in GB? Of course, in draughts 10x10.

I have not worked out the details for 10 pieces. Building that requires more computing hardware than is available to the typical draughts programmer. AFAIK no one has yet built even a full 9-piece db. I have built about 1/3 of it, but I paused it this summer and not sure when I will start it up again. It needs almost 1 year of additional computer time. If you want to know about sizes,

2 through 8 pieces with a max 5 pieces on a side is 17.5e12 positions, and 55.6 GB on disk
2 through 9 pieces with a max 6 pieces on a side is 359.7e12 positions

If the size on disk is proportional to the number of positions, then 9 pieces will be 55.6 x 359.7 / 17.5 = 1143 GB. It might be a little smaller because there is probably a higher percentage of lopsided positions in 9 pieces, and those compress better.