A pre-calculated pawn hash table ?

[chrisw]

Just did some stats ....

I have files consisting of millions of comp-comp epds, totally randomly mixed up.
For each epd, I created a pawn structure signature.

Stop counting data after this:

with 100 million epds processed, every time I add another 5 million epds, the addition created fewer than 1% new unique pawn signatures (0.7% to be more precise).

So, if you have a 100 million or so entry pawn hash, you should find any random pawn structure in it, about 99% of the time. Which looks worth doing.

Whoops, edit:

100 million EPDs, give 37 million unique pawn signatures and subsequent EPD adds have a 3.7% of being found in the 37 million unique signature list.
Program slows down with length of signature list.

I'll leave it running ....

[hgm]

So how many different Pawn structures were in these 100M processed EPDs? And 0.7% of what? Of the 5M?

[chrisw]

So how many different Pawn structures were in these 100M processed EPDs? And 0.7% of what? Of the 5M?

see edit above

more whoops: 96% chance of being found

[Joost Buijs]

BTW, a sharper bound on the number of Pawn constellations than 3^48 (which also counts cases like having 48 black Pawns) is 2^64. (3^48 = (1.5*2)^48 = 1.5^48 * 2^48 = 2.25^24 * 2^48 > 2^24 * 2^48 = 2^72.) Uri Brass once pointed out that you need 48 bits to indicate Pawn occupation of the 48 Pawn-accessible squares, and that an additional 16 bits are then enough to flag which of the 16 Pawns that can maximally be in there are black. An even more accurate estimate, which takes account of the fact that you can have at most 8 white and 8 black Pawns, is 2^55. For exactly 16 Pawns it is 2^54.68 (= 48!/(16!*32!) * 16!/(8!*8!)), but the number decreases very fast when there are fewer Pawns.) This still does not take account of the fact that most of the Pawn constellations would be unreachable from the initial position.

Of course you are right, I just made a small bike trip and while I was biking and thinking about this I already noticed my error.

I have about 5.5 million computer games from the last 6 years, when I make a small modification to my book-generator I can count all the unique pawn configurations that occurred during these games. For me it is not so important, but if somebody is interested it is not too difficult to count them.

Basically it consists of a binary tree with hashes, I only have to replace the hash with the 64 bit pawn-hash, I don't think that collisions will play a big role.

[chrisw]

Python code, knocked up in a few minutes, hardly tested for bugs, but seems okay ....

NB the EPDs are game EPDs not search EPDs, search EPDs may have greater variance because searches look at a lot of junk positions.

example epd: 2q5/4r1p1/5p1k/4pP1p/r1P5/2R1Q2P/1R3P1K/8 b - - 8 44
pawn signature: 86p15p24pP1p2P57P5P28

epds: 5000000 unique: 3385882 add_rate: 0.3228
epds: 10000000 unique: 6210726 add_rate: 0.2175
epds: 15000000 unique: 8766386 add_rate: 0.163
epds: 20000000 unique: 11134944 add_rate: 0.1316
epds: 25000000 unique: 13354590 add_rate: 0.1112
epds: 30000000 unique: 15450996 add_rate: 0.0968
epds: 35000000 unique: 17447165 add_rate: 0.0858
epds: 40000000 unique: 19352106 add_rate: 0.0774
epds: 45000000 unique: 21175012 add_rate: 0.0706
epds: 50000000 unique: 22927028 add_rate: 0.065
epds: 55000000 unique: 24614327 add_rate: 0.0602
epds: 60000000 unique: 26242834 add_rate: 0.0562
epds: 65000000 unique: 27814799 add_rate: 0.0527
epds: 70000000 unique: 29336680 add_rate: 0.0497
epds: 75000000 unique: 30811604 add_rate: 0.047
epds: 80000000 unique: 32243467 add_rate: 0.0446
epds: 85000000 unique: 33633023 add_rate: 0.0425
epds: 90000000 unique: 34982272 add_rate: 0.0406
epds: 95000000 unique: 36293713 add_rate: 0.0388
epds: 100000000 unique: 37572503 add_rate: 0.0372
epds: 105000000 unique: 38817771 add_rate: 0.0358

still running, but getting slow .....

Edit: hey-ho, spot the deliberate error.
at 100x10^6 EPDs, if I try to add 5x10^6 EPDs, I get about 1.3x10^6 new unique pawn signatures, which is an add rate of 1.3 in 5 or 23%.

which is not so good

[Joost Buijs]

When I want to count unique pawn configurations I have to add a database of human games too. Most computer games consist of the same few openings over and over again.

[hgm]

The fraction of new unique positions seems to behave approximately ike (7e5*ln(N) - 9.1e6)/N, i.e. log(N)/N convergence. (Which is pretty slow).

[chrisw]

The fraction of new unique positions seems to behave approximately ike (7e5*ln(N) - 9.1e6)/N, i.e. log(N)/N convergence. (Which is pretty slow).

NB positions I used are all previously tested unique, and all shuffled. They are about as randomly ordered as random can be.
In a search, the positions are much more correlated.
So, basically, my results are from taking a random position dataset and comparing it to a larger random pool.

After lunch, longer results run ...
285mn epds, 70mn unique
last batch if 5mn epds added, increased the unique count by 0.64mn. which I calculate to be a unique add rate of 0.64 in 5 or about 13%. eg 87% positions are found in the 285mn pool.

310mn epds, 73mn unique, unique count increased by 0.6mn, 12%

at 16 bytes per hash entry, best case position spread in hash, that’s just over 1GB of pawnhash RAM

I guess that could be cut back by pre-preparing 16 pawnhash arrays and using pawn count as index into which array to use.

Edit: so far btw, program in using about 16GB of 32GB PC memory, so I can leave it for a while before run out of RAM

ignore add_rate column
epds: 5000000 unique: 3385882 add_rate: 0.3228
epds: 10000000 unique: 6210726 add_rate: 0.2175
epds: 15000000 unique: 8766386 add_rate: 0.163
epds: 20000000 unique: 11134944 add_rate: 0.1316
epds: 25000000 unique: 13354590 add_rate: 0.1112
epds: 30000000 unique: 15450996 add_rate: 0.0968
epds: 35000000 unique: 17447165 add_rate: 0.0858
epds: 40000000 unique: 19352106 add_rate: 0.0774
epds: 45000000 unique: 21175012 add_rate: 0.0706
epds: 50000000 unique: 22927028 add_rate: 0.065
epds: 55000000 unique: 24614327 add_rate: 0.0602
epds: 60000000 unique: 26242834 add_rate: 0.0562
epds: 65000000 unique: 27814799 add_rate: 0.0527
epds: 70000000 unique: 29336680 add_rate: 0.0497
epds: 75000000 unique: 30811604 add_rate: 0.047
epds: 80000000 unique: 32243467 add_rate: 0.0446
epds: 85000000 unique: 33633023 add_rate: 0.0425
epds: 90000000 unique: 34982272 add_rate: 0.0406
epds: 95000000 unique: 36293713 add_rate: 0.0388
epds: 100000000 unique: 37572503 add_rate: 0.0372
epds: 105000000 unique: 38817771 add_rate: 0.0358
epds: 110000000 unique: 40033000 add_rate: 0.0344
epds: 115000000 unique: 41220118 add_rate: 0.0332
epds: 120000000 unique: 42377906 add_rate: 0.032
epds: 125000000 unique: 43510162 add_rate: 0.0309
epds: 130000000 unique: 44616451 add_rate: 0.03
epds: 135000000 unique: 45697923 add_rate: 0.029
epds: 140000000 unique: 46755119 add_rate: 0.0282
epds: 145000000 unique: 47789895 add_rate: 0.0273
epds: 150000000 unique: 48804569 add_rate: 0.0266
epds: 155000000 unique: 49798023 add_rate: 0.0258
epds: 160000000 unique: 50770063 add_rate: 0.0252
epds: 165000000 unique: 51724695 add_rate: 0.0245
epds: 170000000 unique: 52662208 add_rate: 0.0239
epds: 175000000 unique: 53581312 add_rate: 0.0233
epds: 180000000 unique: 54483146 add_rate: 0.0228
epds: 185000000 unique: 55367223 add_rate: 0.0222
epds: 190000000 unique: 56236627 add_rate: 0.0217
epds: 195000000 unique: 57090707 add_rate: 0.0213
epds: 200000000 unique: 57930653 add_rate: 0.0208
epds: 205000000 unique: 58754292 add_rate: 0.0204
epds: 210000000 unique: 59566849 add_rate: 0.0199
epds: 215000000 unique: 60364193 add_rate: 0.0195
epds: 220000000 unique: 61147735 add_rate: 0.0192
epds: 225000000 unique: 61918921 add_rate: 0.0188
epds: 230000000 unique: 62678861 add_rate: 0.0184
epds: 235000000 unique: 63426347 add_rate: 0.0181
epds: 240000000 unique: 64162383 add_rate: 0.0178
epds: 245000000 unique: 64888583 add_rate: 0.0174
epds: 250000000 unique: 65602674 add_rate: 0.0171
epds: 255000000 unique: 66306106 add_rate: 0.0168
epds: 260000000 unique: 66999841 add_rate: 0.0166
epds: 265000000 unique: 67685312 add_rate: 0.0163
epds: 270000000 unique: 68359213 add_rate: 0.016
epds: 275000000 unique: 69025103 add_rate: 0.0158
epds: 280000000 unique: 69680905 add_rate: 0.0155
epds: 285000000 unique: 70327796 add_rate: 0.0153
epds: 290000000 unique: 70967935 add_rate: 0.015
epds: 295000000 unique: 71598075 add_rate: 0.0148
epds: 300000000 unique: 72219157 add_rate: 0.0146
epds: 305000000 unique: 72833053 add_rate: 0.0144
epds: 310000000 unique: 73439381 add_rate: 0.0142
epds: 315000000 unique: 74037100 add_rate: 0.014
epds: 320000000 unique: 74627278 add_rate: 0.0138
epds: 325000000 unique: 75210376 add_rate: 0.0136
epds: 330000000 unique: 75786380 add_rate: 0.0134
epds: 335000000 unique: 76356362 add_rate: 0.0132
epds: 340000000 unique: 76918907 add_rate: 0.0131
epds: 345000000 unique: 77474484 add_rate: 0.0129
epds: 350000000 unique: 78024536 add_rate: 0.0127
epds: 355000000 unique: 78567173 add_rate: 0.0126
epds: 360000000 unique: 79104758 add_rate: 0.0124
epds: 365000000 unique: 79635503 add_rate: 0.0122

[dragontamer5788]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

Memory continues to get slower relative to the CPU. DDR4 has limited bandwidth, and if we keep adding more and more cores (4-core, 6-core, 12-core... even "cheap" 16-core will be out within a month), we have less and less DDR4 bandwidth to play with.

IIRC, DDR4 memory latency is roughly 50ns to 200ns, depending on the machine. (Server-class CPUs have more latency, because LRDIMMs go up to 1TB+ of RAM but the tradeoff is slower access). Modern CPUs are 4GHz+, so 50ns to 200ns is 200 cycles to 800 cycles.

PEXT and PDEP execute in 3-cycles of latency, with a throughput of 1-per-cycle on Intel machines: https://www.agner.org/optimize/instruction_tables.pdf

So the question to me is: how many cycles does a typical pawn-evaluation take? Because if its less than 200 cycles, then the single DDR4 memory load you're proposing might be slower. And if you are using a server-class computer with LRDIMMs, it might be an 800 cycle delay instead. And this is best-case: if the other cores use up all the DDR4 memory bandwidth, DDR4 will get even slower.

[chrisw]

I'll probably turn this off at some point, or else run out either RAM or EPDs
Again ignore add_rate column.

with 780mn epds, there are 110mn discrete pawn signatures.
Addition of 5mn more positions results in 0.27n more unique signatures, so it's now picking up about about 95%

2q5/4r1p1/5p1k/4pP1p/r1P5/2R1Q2P/1R3P1K/8 b - - 8 44
86p15p24pP1p2P57P5P28
epds: 5000000 unique: 3385882 add_rate: 0.3228
epds: 10000000 unique: 6210726 add_rate: 0.2175
epds: 15000000 unique: 8766386 add_rate: 0.163
epds: 20000000 unique: 11134944 add_rate: 0.1316
epds: 25000000 unique: 13354590 add_rate: 0.1112
epds: 30000000 unique: 15450996 add_rate: 0.0968
epds: 35000000 unique: 17447165 add_rate: 0.0858
epds: 40000000 unique: 19352106 add_rate: 0.0774
epds: 45000000 unique: 21175012 add_rate: 0.0706
epds: 50000000 unique: 22927028 add_rate: 0.065
epds: 55000000 unique: 24614327 add_rate: 0.0602
epds: 60000000 unique: 26242834 add_rate: 0.0562
epds: 65000000 unique: 27814799 add_rate: 0.0527
epds: 70000000 unique: 29336680 add_rate: 0.0497
epds: 75000000 unique: 30811604 add_rate: 0.047
epds: 80000000 unique: 32243467 add_rate: 0.0446
epds: 85000000 unique: 33633023 add_rate: 0.0425
epds: 90000000 unique: 34982272 add_rate: 0.0406
epds: 95000000 unique: 36293713 add_rate: 0.0388
epds: 100000000 unique: 37572503 add_rate: 0.0372
epds: 105000000 unique: 38817771 add_rate: 0.0358
epds: 110000000 unique: 40033000 add_rate: 0.0344
epds: 115000000 unique: 41220118 add_rate: 0.0332
epds: 120000000 unique: 42377906 add_rate: 0.032
epds: 125000000 unique: 43510162 add_rate: 0.0309
epds: 130000000 unique: 44616451 add_rate: 0.03
epds: 135000000 unique: 45697923 add_rate: 0.029
epds: 140000000 unique: 46755119 add_rate: 0.0282
epds: 145000000 unique: 47789895 add_rate: 0.0273
epds: 150000000 unique: 48804569 add_rate: 0.0266
epds: 155000000 unique: 49798023 add_rate: 0.0258
epds: 160000000 unique: 50770063 add_rate: 0.0252
epds: 165000000 unique: 51724695 add_rate: 0.0245
epds: 170000000 unique: 52662208 add_rate: 0.0239
epds: 175000000 unique: 53581312 add_rate: 0.0233
epds: 180000000 unique: 54483146 add_rate: 0.0228
epds: 185000000 unique: 55367223 add_rate: 0.0222
epds: 190000000 unique: 56236627 add_rate: 0.0217
epds: 195000000 unique: 57090707 add_rate: 0.0213
epds: 200000000 unique: 57930653 add_rate: 0.0208
epds: 205000000 unique: 58754292 add_rate: 0.0204
epds: 210000000 unique: 59566849 add_rate: 0.0199
epds: 215000000 unique: 60364193 add_rate: 0.0195
epds: 220000000 unique: 61147735 add_rate: 0.0192
epds: 225000000 unique: 61918921 add_rate: 0.0188
epds: 230000000 unique: 62678861 add_rate: 0.0184
epds: 235000000 unique: 63426347 add_rate: 0.0181
epds: 240000000 unique: 64162383 add_rate: 0.0178
epds: 245000000 unique: 64888583 add_rate: 0.0174
epds: 250000000 unique: 65602674 add_rate: 0.0171
epds: 255000000 unique: 66306106 add_rate: 0.0168
epds: 260000000 unique: 66999841 add_rate: 0.0166
epds: 265000000 unique: 67685312 add_rate: 0.0163
epds: 270000000 unique: 68359213 add_rate: 0.016
epds: 275000000 unique: 69025103 add_rate: 0.0158
epds: 280000000 unique: 69680905 add_rate: 0.0155
epds: 285000000 unique: 70327796 add_rate: 0.0153
epds: 290000000 unique: 70967935 add_rate: 0.015
epds: 295000000 unique: 71598075 add_rate: 0.0148
epds: 300000000 unique: 72219157 add_rate: 0.0146
epds: 305000000 unique: 72833053 add_rate: 0.0144
epds: 310000000 unique: 73439381 add_rate: 0.0142
epds: 315000000 unique: 74037100 add_rate: 0.014
epds: 320000000 unique: 74627278 add_rate: 0.0138
epds: 325000000 unique: 75210376 add_rate: 0.0136
epds: 330000000 unique: 75786380 add_rate: 0.0134
epds: 335000000 unique: 76356362 add_rate: 0.0132
epds: 340000000 unique: 76918907 add_rate: 0.0131
epds: 345000000 unique: 77474484 add_rate: 0.0129
epds: 350000000 unique: 78024536 add_rate: 0.0127
epds: 355000000 unique: 78567173 add_rate: 0.0126
epds: 360000000 unique: 79104758 add_rate: 0.0124
epds: 365000000 unique: 79635503 add_rate: 0.0122
epds: 370000000 unique: 80160083 add_rate: 0.0121
epds: 375000000 unique: 80678957 add_rate: 0.0119
epds: 380000000 unique: 81192267 add_rate: 0.0118
epds: 385000000 unique: 81700377 add_rate: 0.0117
epds: 390000000 unique: 82202462 add_rate: 0.0115
epds: 395000000 unique: 82699558 add_rate: 0.0114
epds: 400000000 unique: 83191444 add_rate: 0.0113
epds: 405000000 unique: 83678571 add_rate: 0.0111
epds: 410000000 unique: 84160843 add_rate: 0.011
epds: 415000000 unique: 84637848 add_rate: 0.0109
epds: 420000000 unique: 85110205 add_rate: 0.0108
epds: 425000000 unique: 85576818 add_rate: 0.0107
epds: 430000000 unique: 86039544 add_rate: 0.0106
epds: 435000000 unique: 86497247 add_rate: 0.0104
epds: 440000000 unique: 86951215 add_rate: 0.0103
epds: 445000000 unique: 87400526 add_rate: 0.0102
epds: 450000000 unique: 87845876 add_rate: 0.0101
epds: 455000000 unique: 88286955 add_rate: 0.01
epds: 460000000 unique: 88722756 add_rate: 0.0099
epds: 465000000 unique: 89155356 add_rate: 0.0098
epds: 470000000 unique: 89585003 add_rate: 0.0097
epds: 475000000 unique: 90009458 add_rate: 0.0096
epds: 480000000 unique: 90429996 add_rate: 0.0095
epds: 485000000 unique: 90846260 add_rate: 0.0095
epds: 490000000 unique: 91259023 add_rate: 0.0094
epds: 495000000 unique: 91668311 add_rate: 0.0093
epds: 500000000 unique: 92075204 add_rate: 0.0092
epds: 505000000 unique: 92477679 add_rate: 0.0091
epds: 510000000 unique: 92876327 add_rate: 0.009
epds: 515000000 unique: 93271982 add_rate: 0.0089
epds: 520000000 unique: 93664625 add_rate: 0.0089
epds: 525000000 unique: 94054139 add_rate: 0.0088
epds: 530000000 unique: 94439637 add_rate: 0.0087
epds: 535000000 unique: 94821854 add_rate: 0.0086
epds: 540000000 unique: 95200444 add_rate: 0.0086
epds: 545000000 unique: 95576794 add_rate: 0.0085
epds: 550000000 unique: 95949801 add_rate: 0.0084
epds: 555000000 unique: 96319978 add_rate: 0.0083
epds: 560000000 unique: 96687075 add_rate: 0.0083
epds: 565000000 unique: 97051448 add_rate: 0.0082
epds: 570000000 unique: 97413452 add_rate: 0.0081
epds: 575000000 unique: 97771706 add_rate: 0.0081
epds: 580000000 unique: 98126949 add_rate: 0.008
epds: 585000000 unique: 98480362 add_rate: 0.0079
epds: 590000000 unique: 98830360 add_rate: 0.0079
epds: 595000000 unique: 99178547 add_rate: 0.0078
epds: 600000000 unique: 99523674 add_rate: 0.0078
epds: 605000000 unique: 99865874 add_rate: 0.0077
epds: 610000000 unique: 100206630 add_rate: 0.0076
epds: 615000000 unique: 100544608 add_rate: 0.0076
epds: 620000000 unique: 100879646 add_rate: 0.0075
epds: 625000000 unique: 101212476 add_rate: 0.0075
epds: 630000000 unique: 101542344 add_rate: 0.0074
epds: 635000000 unique: 101870719 add_rate: 0.0074
epds: 640000000 unique: 102196226 add_rate: 0.0073
epds: 645000000 unique: 102519883 add_rate: 0.0073
epds: 650000000 unique: 102840960 add_rate: 0.0072
epds: 655000000 unique: 103160361 add_rate: 0.0071
epds: 660000000 unique: 103477748 add_rate: 0.0071
epds: 665000000 unique: 103792995 add_rate: 0.007
epds: 670000000 unique: 104106080 add_rate: 0.007
epds: 675000000 unique: 104416783 add_rate: 0.0069
epds: 680000000 unique: 104724858 add_rate: 0.0069
epds: 685000000 unique: 105031499 add_rate: 0.0069
epds: 690000000 unique: 105336612 add_rate: 0.0068
epds: 695000000 unique: 105638532 add_rate: 0.0068
epds: 700000000 unique: 105938769 add_rate: 0.0067
epds: 705000000 unique: 106236793 add_rate: 0.0067
epds: 710000000 unique: 106533953 add_rate: 0.0066
epds: 715000000 unique: 106829376 add_rate: 0.0066
epds: 720000000 unique: 107122061 add_rate: 0.0065
epds: 725000000 unique: 107413638 add_rate: 0.0065
epds: 730000000 unique: 107703029 add_rate: 0.0065
epds: 735000000 unique: 107990174 add_rate: 0.0064
epds: 740000000 unique: 108276081 add_rate: 0.0064
epds: 745000000 unique: 108559218 add_rate: 0.0063
epds: 750000000 unique: 108841710 add_rate: 0.0063
epds: 755000000 unique: 109122938 add_rate: 0.0063
epds: 760000000 unique: 109401693 add_rate: 0.0062
epds: 765000000 unique: 109679395 add_rate: 0.0062
epds: 770000000 unique: 109954959 add_rate: 0.0061
epds: 775000000 unique: 110230238 add_rate: 0.0061
epds: 780000000 unique: 110502408 add_rate: 0.0061