A pre-calculated pawn hash table ?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
chrisw
Posts: 2142
Joined: Tue Apr 03, 2012 2:28 pm

Re: A pre-calculated pawn hash table ?

Post by chrisw » Sat Jul 06, 2019 9:55 am

Final run (if anyone is interested)
Ignore broken add_rate column.

epds are from comp-comp games, no duplicate epds, fully shuffled/randomised.

iteration N-1, epds: 1235000000; unique pawn structure signatures: 130439104
iteration N, epds: 1240000000; unique pawn structure signatures: 130619353

last line, shows 5mn positions added, of which 0.18mn were unique (eg not found in the dataset of 1235mn epds), giving 3.6% failure rate.

possibly somebody might like to extrapolate the unique column to give some sort of upper bound on count of unique pawn structures arising in 'normal' play.

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
epds: 785000000 unique: 110773230 add_rate: 0.006
epds: 790000000 unique: 111042940 add_rate: 0.006
epds: 795000000 unique: 111310082 add_rate: 0.006
epds: 800000000 unique: 111576825 add_rate: 0.0059
epds: 805000000 unique: 111840959 add_rate: 0.0059
epds: 810000000 unique: 112104019 add_rate: 0.0058
epds: 815000000 unique: 112366339 add_rate: 0.0058
epds: 820000000 unique: 112627503 add_rate: 0.0058
epds: 825000000 unique: 112886678 add_rate: 0.0057
epds: 830000000 unique: 113144584 add_rate: 0.0057
epds: 835000000 unique: 113400647 add_rate: 0.0057
epds: 840000000 unique: 113655779 add_rate: 0.0056
epds: 845000000 unique: 113908777 add_rate: 0.0056
epds: 850000000 unique: 114160253 add_rate: 0.0056
epds: 855000000 unique: 114410175 add_rate: 0.0056
epds: 860000000 unique: 114659236 add_rate: 0.0055
epds: 865000000 unique: 114907863 add_rate: 0.0055
epds: 870000000 unique: 115155011 add_rate: 0.0055
epds: 875000000 unique: 115399946 add_rate: 0.0054
epds: 880000000 unique: 115644462 add_rate: 0.0054
epds: 885000000 unique: 115887306 add_rate: 0.0054
epds: 890000000 unique: 116128721 add_rate: 0.0053
epds: 895000000 unique: 116369630 add_rate: 0.0053
epds: 900000000 unique: 116609466 add_rate: 0.0053
epds: 905000000 unique: 116847893 add_rate: 0.0053
epds: 910000000 unique: 117084360 add_rate: 0.0052
epds: 915000000 unique: 117319713 add_rate: 0.0052
epds: 920000000 unique: 117554092 add_rate: 0.0052
epds: 925000000 unique: 117787581 add_rate: 0.0052
epds: 930000000 unique: 118019848 add_rate: 0.0051
epds: 935000000 unique: 118251469 add_rate: 0.0051
epds: 940000000 unique: 118480784 add_rate: 0.0051
epds: 945000000 unique: 118710180 add_rate: 0.005
epds: 950000000 unique: 118938205 add_rate: 0.005
epds: 955000000 unique: 119165199 add_rate: 0.005
epds: 960000000 unique: 119391851 add_rate: 0.005
epds: 965000000 unique: 119616564 add_rate: 0.0049
epds: 970000000 unique: 119840017 add_rate: 0.0049
epds: 975000000 unique: 120062493 add_rate: 0.0049
epds: 980000000 unique: 120284718 add_rate: 0.0049
epds: 985000000 unique: 120504981 add_rate: 0.0049
epds: 990000000 unique: 120724936 add_rate: 0.0048
epds: 995000000 unique: 120943805 add_rate: 0.0048
epds: 1000000000 unique: 121161573 add_rate: 0.0048
epds: 1005000000 unique: 121378798 add_rate: 0.0048
epds: 1010000000 unique: 121594443 add_rate: 0.0047
epds: 1015000000 unique: 121809405 add_rate: 0.0047
epds: 1020000000 unique: 122023189 add_rate: 0.0047
epds: 1025000000 unique: 122236344 add_rate: 0.0047
epds: 1030000000 unique: 122448114 add_rate: 0.0046
epds: 1035000000 unique: 122660101 add_rate: 0.0046
epds: 1040000000 unique: 122870096 add_rate: 0.0046
epds: 1045000000 unique: 123079215 add_rate: 0.0046
epds: 1050000000 unique: 123287925 add_rate: 0.0046
epds: 1055000000 unique: 123495738 add_rate: 0.0045
epds: 1060000000 unique: 123703231 add_rate: 0.0045
epds: 1065000000 unique: 123908719 add_rate: 0.0045
epds: 1070000000 unique: 124113342 add_rate: 0.0045
epds: 1075000000 unique: 124317779 add_rate: 0.0045
epds: 1080000000 unique: 124520906 add_rate: 0.0044
epds: 1085000000 unique: 124722768 add_rate: 0.0044
epds: 1090000000 unique: 124924824 add_rate: 0.0044
epds: 1095000000 unique: 125125382 add_rate: 0.0044
epds: 1100000000 unique: 125325737 add_rate: 0.0044
epds: 1105000000 unique: 125524666 add_rate: 0.0043
epds: 1110000000 unique: 125722469 add_rate: 0.0043
epds: 1115000000 unique: 125919561 add_rate: 0.0043
epds: 1120000000 unique: 126115592 add_rate: 0.0043
epds: 1125000000 unique: 126311022 add_rate: 0.0043
epds: 1130000000 unique: 126505969 add_rate: 0.0043
epds: 1135000000 unique: 126700213 add_rate: 0.0042
epds: 1140000000 unique: 126894078 add_rate: 0.0042
epds: 1145000000 unique: 127086023 add_rate: 0.0042
epds: 1150000000 unique: 127277847 add_rate: 0.0042
epds: 1155000000 unique: 127469784 add_rate: 0.0042
epds: 1160000000 unique: 127660901 add_rate: 0.0041
epds: 1165000000 unique: 127851613 add_rate: 0.0041
epds: 1170000000 unique: 128040138 add_rate: 0.0041
epds: 1175000000 unique: 128229396 add_rate: 0.0041
epds: 1180000000 unique: 128417022 add_rate: 0.0041
epds: 1185000000 unique: 128603954 add_rate: 0.0041
epds: 1190000000 unique: 128789588 add_rate: 0.004
epds: 1195000000 unique: 128975693 add_rate: 0.004
epds: 1200000000 unique: 129160832 add_rate: 0.004
epds: 1205000000 unique: 129345300 add_rate: 0.004
epds: 1210000000 unique: 129529269 add_rate: 0.004
epds: 1215000000 unique: 129712556 add_rate: 0.004
epds: 1220000000 unique: 129895137 add_rate: 0.0039
epds: 1225000000 unique: 130077685 add_rate: 0.0039
epds: 1230000000 unique: 130258257 add_rate: 0.0039
epds: 1235000000 unique: 130439104 add_rate: 0.0039
epds: 1240000000 unique: 130619353 add_rate: 0.0039

DustyMonkey
Posts: 56
Joined: Wed Feb 19, 2014 9:11 pm

Re: A pre-calculated pawn hash table ?

Post by DustyMonkey » Thu Jul 11, 2019 6:27 pm

Food for thought:

Pawn structures where a player has a "bad" formation maybe arent important to cache because the "elo cost" of the "extra work" might be made up for by the fact that one side already has a "bad position" and the game is likely already heading towards a non-draw result.

D Sceviour
Posts: 458
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: A pre-calculated pawn hash table ?

Post by D Sceviour » Thu Jul 11, 2019 7:03 pm

DustyMonkey wrote:
Thu Jul 11, 2019 6:27 pm
Pawn structures where a player has a "bad" formation maybe arent important to cache because the "elo cost" of the "extra work" might be made up for by the fact that one side already has a "bad position" and the game is likely already heading towards a non-draw result.
Yes. This is the basis of the Poor Man's KP bitbase. If a table result is reduced to one of three known categories of Win/Loss or Draw then the size of any table can be reduced. This is not of much use for root analysis, but it can really crunch those nodes on the horizon. I am thinking of creating a lot more poor man type bitbases since they take so little space. The next one might be a KRKP reduced to White King and Black Pawn positions.

User avatar
hgm
Posts: 23728
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: A pre-calculated pawn hash table ?

Post by hgm » Thu Jul 11, 2019 8:57 pm

You cannot guess the game outcome from the Pawn structure. A Pawn structure can be awful, like two isolated Pawns aganst 6, where 4 of the latter are connected passers. But if the side with the 2 Pawns is a Queen ahead, it would still be a trivial win. However bad a Pawn structure, it can always be compensated by piece material.

DustyMonkey
Posts: 56
Joined: Wed Feb 19, 2014 9:11 pm

Re: A pre-calculated pawn hash table ?

Post by DustyMonkey » Fri Jul 12, 2019 4:50 am

hgm wrote:
Thu Jul 11, 2019 8:57 pm
You cannot guess the game outcome from the Pawn structure. A Pawn structure can be awful, like two isolated Pawns aganst 6, where 4 of the latter are connected passers. But if the side with the 2 Pawns is a Queen ahead, it would still be a trivial win. However bad a Pawn structure, it can always be compensated by piece material.
The examples you give are STILL ones where the game is heading towards a non-draw result. It doesnt matter which side is winning.

User avatar
hgm
Posts: 23728
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: A pre-calculated pawn hash table ?

Post by hgm » Fri Jul 12, 2019 6:59 am

DustyMonkey wrote:
Fri Jul 12, 2019 4:50 am
The examples you give are STILL ones where the game is heading towards a non-draw result. It doesnt matter which side is winning.
Well, so don't give him an extra Queen but an extra Rook. Point is that differences in piece material, like the exchange, Rook vs 2 minors, Bishop pair vs B+N can always be exactly compensated by 2 Pawns, 1 Pawn, or just a positional Pawn advantage, which from the POV of the Pawns alone would seem a winning advantage.

dragontamer5788
Posts: 141
Joined: Thu Jun 06, 2019 6:05 pm
Full name: Percival Tiglao

Re: A pre-calculated pawn hash table ?

Post by dragontamer5788 » Fri Jul 12, 2019 6:12 pm

It seems like the main use of this is to perhaps "unlock" more difficult pawn-constellation algorithms.

Imagine if pawn-calculations were 100x harder or 1000x "harder" than they were today. This pawn-hash table concept would be able to store most of the work and recycle it during search. So even if a particular pawn algorithm took 1000x more time to calculate with only maybe... 100x improvement to positional play, the hash table would make such a calculation worth doing (ex: 95% hit-ratio mean that an algorithm with 1000x more effort would on the average only be 50x more effort).

DustyMonkey
Posts: 56
Joined: Wed Feb 19, 2014 9:11 pm

Re: A pre-calculated pawn hash table ?

Post by DustyMonkey » Sat Jul 13, 2019 4:52 am

hgm wrote:
Fri Jul 12, 2019 6:59 am
DustyMonkey wrote:
Fri Jul 12, 2019 4:50 am
The examples you give are STILL ones where the game is heading towards a non-draw result. It doesnt matter which side is winning.
Well, so don't give him an extra Queen but an extra Rook. Point is that differences in piece material, like the exchange, Rook vs 2 minors, Bishop pair vs B+N can always be exactly compensated by 2 Pawns, 1 Pawn, or just a positional Pawn advantage, which from the POV of the Pawns alone would seem a winning advantage.
No, and saying it doesnt make it so. You are confusing games heading towards a draw with games where a player has compensation. Unbalanced games are much more likely to end decisively. They might score 50%, but thats a different thing entirely.

User avatar
hgm
Posts: 23728
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: A pre-calculated pawn hash table ?

Post by hgm » Sat Jul 13, 2019 7:25 am

So what? That would make it all the more important to have an accurate evaluation of the total position, and thus of the Pawn structure. The attitude "this game will not be a draw, so it doesn't matter much anymore what I play" seems a good recipe for a certain loss.

Post Reply