Measuring Hash Collisions (once again)

[Rebel]

To detect hash collisions the only good way is to store the whole internal board into the HT. Instead of storing the whole board into the HT I calculate a checksum for the board, 64 squares, piece type * square number and store that value as a checksum in the HT. With a HT lookup the checksum should match, else collision.

Just like one can incremental update the hash key in "move_do", the same can be done to update the checksum.

First question to answer, how many collision do occur.
Second question, do I need a collision checker.

Part one : how many collision do occur

Conditions:
HT size 128 Mb
HT is split into 2 parts, 64 Mb for odd plies, 64 Mb for even plies.
Hash Key size (just) 48 bits
Bucket size 4 slots
Replacement scheme by depth
Entry length 16 bytes.

Test positions: 500 from the STS set.
First 100 at 30 seconds
Second 100 at 1 minute
Third 100 at 2:30
Fourth 100 at 5:00
Last 100 at 10:00

Probes means number of HT lookups
Found keys, those match the position in the HT
Coll, collisions
TP, in case the collision is a transposition and thus has the potential to cause harm.

First 100 at 30 seconds per move. 20 collisions of which 13 transpositions.

Code: Select all

       Probes          Found Keys     Coll   TP
     15.708.253      2.451.861 (15%)     0    0
     17.786.894      2.877.969 (16%)     2    2
     17.002.583      2.261.897 (13%)     0    0
     19.172.410      3.698.957 (19%)     0    0
     22.055.680      5.569.780 (25%)     0    0
     20.247.514      4.618.226 (22%)     0    0
     18.648.606      2.582.235 (13%)     0    0
     17.990.221      2.473.495 (13%)     0    0
     16.944.258      2.400.943 (14%)     0    0
     19.569.871      2.525.649 (12%)     0    0
     20.723.537      3.875.531 (18%)     0    0
     22.114.911      3.234.268 (14%)     0    0
     18.119.229      2.656.125 (14%)     0    0
     16.401.223      1.979.946 (12%)     0    0
     20.347.874      4.546.725 (22%)     0    0
     16.588.564      2.736.373 (16%)     1    1
     22.080.157      3.952.163 (17%)     0    0
     23.742.664      3.536.947 (14%)     0    0
     22.886.758      5.946.657 (25%)     0    0
     17.502.757      2.770.054 (15%)     0    0
     18.461.098      2.436.395 (13%)     0    0
     25.265.608      5.419.638 (21%)     0    0
     21.225.435      4.139.089 (19%)     0    0
     23.365.571      4.130.027 (17%)     1    1
     16.891.814      2.330.492 (13%)     1    0
     16.887.244      3.371.409 (19%)     0    0
     22.892.556      3.732.848 (16%)     0    0
     17.485.622      2.802.948 (16%)     0    0
     20.112.662      4.170.295 (20%)     0    0
     16.842.545      2.465.090 (14%)     0    0
     18.230.852      2.374.021 (13%)     0    0
     18.497.973      2.882.729 (15%)     0    0
     16.059.760      2.880.054 (17%)     0    0
     22.871.140      5.119.680 (22%)     0    0
     19.977.250      3.445.492 (17%)     0    0
     17.857.349      2.440.920 (13%)     0    0
     16.533.635      2.107.979 (12%)     0    0
     20.022.200      3.781.403 (18%)     0    0
     17.431.843      3.131.102 (17%)     1    0
     20.011.543      3.114.406 (15%)     0    0
     20.558.669      2.996.039 (14%)     2    1
     18.953.070      2.702.890 (14%)     0    0
     19.760.054      3.483.652 (17%)     0    0
     17.966.764      3.480.242 (19%)     0    0
     22.691.710      4.824.762 (21%)     0    0
     26.541.331      7.162.938 (26%)     0    0
     19.977.882      3.426.015 (17%)     0    0
     22.408.617      4.786.573 (21%)     0    0
     17.197.878      2.237.960 (13%)     2    1
     22.331.088      4.235.397 (18%)     0    0
     24.123.290      5.434.076 (22%)     0    0
     21.218.709      4.605.075 (21%)     1    1
     20.950.233      3.702.643 (17%)     0    0
     20.562.674      3.957.659 (19%)     0    0
     20.411.578      3.633.875 (17%)     0    0
     23.749.954      3.530.708 (14%)     1    1
     17.559.989      2.460.171 (14%)     0    0
     19.064.927      3.707.974 (19%)     0    0
     19.573.506      3.200.948 (16%)     0    0
     26.125.677      6.990.136 (26%)     0    0
     18.523.700      2.695.777 (14%)     0    0
     20.856.950      3.586.884 (17%)     1    0
     25.300.452      4.611.175 (18%)     1    0
     17.303.255      3.005.826 (17%)     0    0
     19.873.124      3.232.224 (16%)     0    0
     19.293.430      3.536.106 (18%)     0    0
     19.064.185      3.216.010 (16%)     0    0
     23.277.802      3.957.564 (17%)     0    0
     24.193.241      6.010.303 (24%)     0    0
     21.114.189      4.071.833 (19%)     0    0
     20.741.350      3.572.927 (17%)     1    1
     19.379.385      3.337.443 (17%)     0    0
     22.180.720      6.150.667 (27%)     0    0
     21.624.838      4.207.473 (19%)     0    0
     21.967.179      4.853.402 (22%)     0    0
     18.432.731      3.114.884 (16%)     1    0
     19.250.583      4.254.427 (22%)     0    0
     20.556.278      3.714.631 (18%)     1    1
     20.562.305      4.698.648 (22%)     0    0
     20.302.775      4.374.173 (21%)     0    0
     23.071.204      3.617.612 (15%)     0    0
     17.106.654      2.446.673 (14%)     0    0
     17.141.058      2.467.106 (14%)     0    0
     17.960.827      2.886.650 (16%)     0    0
     17.992.248      2.712.582 (15%)     0    0
     19.187.041      3.450.448 (17%)     0    0
     21.903.327      3.814.130 (17%)     0    0
     18.028.073      2.143.395 (11%)     0    0
     19.528.982      2.875.116 (14%)     0    0
     19.122.584      3.753.892 (19%)     0    0
     18.423.714      3.294.996 (17%)     0    0
     17.505.090      2.708.692 (15%)     0    0
     18.504.489      2.730.105 (14%)     0    0
     17.717.061      2.254.488 (12%)     0    0
     18.278.367      3.337.586 (18%)     0    0
     18.451.235      2.264.715 (12%)     0    0
     23.776.056      4.925.944 (20%)     2    2
     18.417.504      2.675.981 (14%)     0    0
     18.569.066      3.303.984 (17%)     0    0
     23.398.836      4.576.620 (19%)     1    1

[Rebel]

Second 100 positions at 1 minute average, 35 collisions of which 19 were transpositions.

Code: Select all

POS           Probes          Found Keys     Coll   TP
Pos   1     52.514.597     12.939.788 (24%)     0    0
Pos   2     37.676.955      6.021.529 (15%)     2    2
Pos   3     41.047.846      6.482.236 (15%)     0    0
Pos   4     33.567.669      4.146.110 (12%)     0    0
Pos   5     54.796.442     11.543.862 (21%)     1    0
Pos   6     51.747.632      8.817.236 (17%)     0    0
Pos   7     38.620.720      5.928.758 (15%)     0    0
Pos   8     38.358.863      5.669.026 (14%)     0    0
Pos   9     35.754.489      3.790.764 (10%)     0    0
Pos  10     39.040.937      4.923.850 (12%)     1    0
Pos  11     31.773.060      3.322.386 (10%)     1    0
Pos  12     47.549.871      8.198.815 (17%)     0    0
Pos  13     37.500.549      6.243.936 (16%)     1    1
Pos  14     56.183.924     18.835.839 (33%)     0    0
Pos  15     42.854.481      6.190.557 (14%)     0    0
Pos  16     36.333.289      5.059.056 (13%)     0    0
Pos  17     50.298.623      7.404.941 (14%)     0    0
Pos  18     45.324.811      5.737.753 (12%)     2    1
Pos  19     39.706.568      5.911.151 (14%)     0    0
Pos  20     42.782.377      5.830.720 (13%)     0    0
Pos  21     38.890.432      5.605.851 (14%)     0    0
Pos  22     46.174.747      7.153.463 (15%)     0    0
Pos  23     51.686.776     11.959.844 (23%)     0    0
Pos  24     50.395.119     10.038.836 (19%)     1    1
Pos  25     49.115.351      5.675.422 (11%)     1    1
Pos  26     44.875.969      9.979.956 (22%)     0    0
Pos  27     43.369.823      8.509.308 (19%)     0    0
Pos  28     43.251.191      6.283.336 (14%)     1    0
Pos  29     48.680.057      7.233.228 (14%)     1    0
Pos  30     46.815.788      7.602.312 (16%)     0    0
Pos  31     46.707.060      8.460.691 (18%)     0    0
Pos  32     53.066.742     10.699.771 (20%)     0    0
Pos  33     36.444.343      3.998.228 (10%)     0    0
Pos  34     42.359.325      7.278.919 (17%)     0    0
Pos  35     41.488.787      6.982.160 (16%)     1    1
Pos  36     39.700.029      4.631.297 (11%)     0    0
Pos  37     57.589.735     23.484.380 (40%)     0    0
Pos  38     53.035.298     12.917.510 (24%)     0    0
Pos  39     40.027.247      6.574.372 (16%)     1    1
Pos  40     41.031.564      5.575.701 (13%)     1    1
Pos  41     41.670.988      7.004.160 (16%)     0    0
Pos  42     36.578.461      5.126.614 (14%)     0    0
Pos  43     42.725.517      7.174.897 (16%)     0    0
Pos  44     40.788.902      8.179.691 (20%)     1    1
Pos  45     51.664.300     14.613.117 (28%)     0    0
Pos  46     42.608.844      6.392.563 (15%)     0    0
Pos  47     49.216.818     11.573.844 (23%)     0    0
Pos  48     42.179.662      8.824.204 (20%)     0    0
Pos  49     38.206.897      6.540.285 (17%)     0    0
Pos  50     47.812.073     10.832.518 (22%)     0    0
Pos  51     43.053.959      6.932.528 (16%)     0    0
Pos  52     42.080.063      6.474.479 (15%)     1    1
Pos  53     53.560.169     12.117.698 (22%)     0    0
Pos  54     51.344.352      9.011.809 (17%)     0    0
Pos  55     48.620.654     10.652.884 (21%)     1    0
Pos  56     50.239.059     10.960.633 (21%)     0    0
Pos  57     46.931.404      8.646.640 (18%)     0    0
Pos  58     48.426.297      7.822.995 (16%)     2    0
Pos  59     43.346.942      7.513.919 (17%)     1    0
Pos  60     40.966.936      6.417.196 (15%)     0    0
Pos  61     55.201.662     12.297.903 (22%)     0    0
Pos  62     53.678.353     10.704.908 (19%)     0    0
Pos  63     46.742.111     11.696.233 (25%)     0    0
Pos  64     48.262.717      7.148.684 (14%)     1    0
Pos  65     41.473.948      7.797.669 (18%)     1    0
Pos  66     38.379.572      4.241.459 (11%)     0    0
Pos  67     52.538.083     10.448.965 (19%)     0    0
Pos  68     52.246.738     12.078.198 (23%)     0    0
Pos  69     46.185.322      6.305.963 (13%)     1    1
Pos  70     47.811.281      9.836.050 (20%)     0    0
Pos  71     40.140.970      5.718.667 (14%)     1    1
Pos  72     41.672.988      7.511.963 (18%)     0    0
Pos  73     39.542.738      7.192.520 (18%)     0    0
Pos  74     50.146.549      7.153.735 (14%)     0    0
Pos  75     38.736.129      5.790.858 (14%)     0    0
Pos  76     48.422.485      9.170.024 (18%)     0    0
Pos  77     42.449.802      5.801.246 (13%)     1    1
Pos  78     46.650.786      7.033.805 (15%)     0    0
Pos  79     51.274.493      7.590.495 (14%)     3    1
Pos  80     45.589.681      7.091.136 (15%)     0    0
Pos  81     54.954.546     10.202.377 (18%)     0    0
Pos  82     44.325.417      6.784.175 (15%)     1    1
Pos  83     42.927.286      6.654.825 (15%)     0    0
Pos  84     48.461.159     11.196.059 (23%)     0    0
Pos  85     50.962.413      9.462.713 (18%)     0    0
Pos  86     50.011.584     11.338.126 (22%)     0    0
Pos  87     50.345.117     19.041.350 (37%)     0    0
Pos  88     51.369.558      9.980.427 (19%)     0    0
Pos  89     46.612.256      7.340.355 (15%)     1    0
Pos  90     36.593.839      5.291.020 (14%)     1    1
Pos  91     30.528.643      3.133.381 (10%)     0    0
Pos  92     32.999.318      4.103.803 (12%)     0    0
Pos  93     44.391.298      6.232.462 (14%)     0    0
Pos  94     33.268.102      3.599.365 (10%)     0    0
Pos  95     38.953.081      4.662.341 (11%)     0    0
Pos  96     40.145.460      6.659.027 (16%)     0    0
Pos  97     54.281.728     11.376.267 (20%)     0    0
Pos  98     35.954.439      4.202.612 (11%)     3    2
Pos  99     34.703.293      5.671.065 (16%)     0    0
Pos 100     34.487.270      4.920.569 (14%)     0    0

[hgm]

The checksum should be good enough for taking collision statistics; it doesn't really matter whether you detect 100% or only 99% (or even 90%) of those.

The reason that in my tests in the other thread I did store (a packed version of) the entire board was that I wanted to know what the positions were that had collided, so that I could see which dependencies in the basis keys were most harmful.

What do you mean by 'transposition'?

[Edit] Ah, OK, I see you answered that in the other thread now. So it means the stored entry had sufficient depth to cause a cutoff.

[hgm]

Oh, one detail that so far escaped my attention: you use separate tables for wtm and btm! So effectively each hash probe compares the hash key with only 64M/15 = 4M = 2^22 entries. With a probability of 1 in 2^48 for each of these to be accidentally the same, that would give a probability of getting a collision with a stored entry to 1 in 2^26 = 1 in 64M. You seem to get about 1 in 100M, which might be due to the hash table not being entirely filled in the beginning. Do you clear the TT before every position?

[Rebel]

Third set of 100 positions at 2½ minutes, 87 collisions of which 57 were transpositions.

Code: Select all

POS           Probes          Found Keys     Coll   TP
Pos   1     89.820.473      9.248.366 (10%)     1    1
Pos   2     92.324.516      9.705.500 (10%)     1    1
Pos   3     93.386.296     12.585.864 (13%)     0    0
Pos   4     94.361.866     12.917.043 (13%)     1    1
Pos   5     85.263.424      9.282.649 (10%)     0    0
Pos   6    102.547.009     16.763.362 (16%)     1    0
Pos   7     81.876.433     10.265.341 (12%)     2    1
Pos   8    109.414.539     20.385.037 (18%)     0    0
Pos   9     89.594.013     11.940.853 (13%)     1    1
Pos  10    100.574.117     17.493.702 (17%)     1    0
Pos  11     83.911.595     10.256.485 (12%)     0    0
Pos  12     77.530.539      7.801.358 (10%)     0    0
Pos  13     91.171.064     12.248.501 (13%)     2    2
Pos  14    104.942.662     18.665.013 (17%)     2    2
Pos  15     88.801.741      9.828.157 (11%)     0    0
Pos  16    101.144.536     18.070.477 (17%)     0    0
Pos  17     90.281.369     12.577.046 (13%)     0    0
Pos  18     93.708.543     11.103.455 (11%)     0    0
Pos  19     88.485.785      9.812.914 (11%)     0    0
Pos  20     89.648.850     10.532.612 (11%)     1    1
Pos  21     86.203.474     11.797.032 (13%)     3    2
Pos  22     95.513.351     13.733.640 (14%)     2    2
Pos  23     86.281.507     10.164.737 (11%)     0    0
Pos  24    105.326.370     13.996.762 (13%)     3    1
Pos  25     92.911.319     14.667.710 (15%)     1    1
Pos  26     94.224.095     10.657.341 (11%)     1    1
Pos  27     92.637.485     11.508.251 (12%)     2    2
Pos  28     90.454.900     10.010.469 (11%)     0    0
Pos  29     90.283.749     11.933.087 (13%)     0    0
Pos  30     81.615.555      8.493.034 (10%)     0    0
Pos  31     87.930.816     10.695.992 (12%)     0    0
Pos  32     94.200.174     12.325.046 (13%)     2    2
Pos  33     91.690.525     12.638.316 (13%)     0    0
Pos  34     99.224.442     13.676.679 (13%)     1    0
Pos  35    104.632.484     14.355.981 (13%)     0    0
Pos  36    113.866.940     22.157.166 (19%)     0    0
Pos  37     95.295.844     11.306.175 (11%)     0    0
Pos  38    109.255.975     11.916.234 (10%)     0    0
Pos  39     96.664.208     15.751.814 (16%)     3    2
Pos  40     98.741.539     15.212.697 (15%)     2    2
Pos  41    109.837.204     23.886.085 (21%)     1    1
Pos  42    104.062.955     13.211.809 (12%)     3    2
Pos  43    108.340.866     17.288.665 (15%)     0    0
Pos  44     85.652.818      9.776.683 (11%)     1    0
Pos  45     89.535.088     11.745.043 (13%)     2    0
Pos  46     98.771.082     18.755.692 (18%)     0    0
Pos  47    121.787.556     17.699.280 (14%)     0    0
Pos  48     88.620.877     11.071.292 (12%)     0    0
Pos  49     97.362.601     10.824.222 (11%)     4    3
Pos  50    113.432.035     23.045.078 (20%)     2    0
Pos  51     95.540.858     12.813.288 (13%)     0    0
Pos  52     99.476.649     12.782.947 (12%)     1    0
Pos  53     93.398.028      8.977.528 ( 9%)     1    0
Pos  54     94.709.828     13.028.674 (13%)     2    2
Pos  55     91.548.158     11.177.901 (12%)     0    0
Pos  56     92.970.002     11.592.267 (12%)     0    0
Pos  57     79.563.108      9.528.484 (11%)     0    0
Pos  58     92.964.239     10.355.454 (11%)     1    1
Pos  59    102.678.043     17.120.125 (16%)     0    0
Pos  60    112.440.723     21.060.969 (18%)     3    3
Pos  61    114.774.450     23.622.607 (20%)     0    0
Pos  62    111.620.807     20.457.654 (18%)     1    0
Pos  63    101.379.654     16.196.353 (15%)     2    2
Pos  64    100.455.239     18.802.712 (18%)     0    0
Pos  65    124.044.696     18.070.553 (14%)     1    1
Pos  66    111.986.851     27.552.178 (24%)     1    0
Pos  67    124.503.657     21.735.297 (17%)     0    0
Pos  68    103.394.669     14.059.852 (13%)     0    0
Pos  69     80.296.310      9.910.135 (12%)     6    1
Pos  70     98.381.726     14.510.490 (14%)     1    1
Pos  71     81.493.786      8.527.057 (10%)     1    1
Pos  72     82.595.835     10.880.990 (13%)     0    0
Pos  73     77.133.372      9.591.092 (12%)     0    0
Pos  74     87.185.549     10.846.234 (12%)     0    0
Pos  75     80.389.693      8.261.784 (10%)     0    0
Pos  76     93.132.896     10.728.416 (11%)     2    1
Pos  77     85.557.249      7.570.116 ( 8%)     0    0
Pos  78     95.349.065     11.257.570 (11%)     0    0
Pos  79    104.130.713     18.694.479 (17%)     0    0
Pos  80     94.039.850     11.490.035 (12%)     1    1
Pos  81     90.354.202     11.547.645 (12%)     1    1
Pos  82    101.644.729     17.680.072 (17%)     0    0
Pos  83     96.149.713     13.942.589 (14%)     0    0
Pos  84     84.603.435      9.351.530 (11%)     0    0
Pos  85     89.690.974     10.594.493 (11%)     1    1
Pos  86     94.650.817     10.713.104 (11%)     0    0
Pos  87    105.446.028     16.201.709 (15%)     7    4
Pos  88     99.579.503      9.872.380 ( 9%)     0    0
Pos  89    104.659.129     11.152.094 (10%)     1    1
Pos  90     94.877.178     12.174.160 (12%)     1    0
Pos  91     84.417.172      9.279.157 (10%)     0    0
Pos  92    109.963.984     18.298.205 (16%)     2    2
Pos  93     93.868.095     12.781.405 (13%)     0    0
Pos  94     78.498.249      7.752.755 ( 9%)     0    0
Pos  95     94.016.056     11.501.448 (12%)     2    1
Pos  96     89.341.389     10.834.298 (12%)     1    1
Pos  97     94.171.454     12.101.004 (12%)     0    0
Pos  98     88.786.035     13.505.088 (15%)     0    0
Pos  99     85.552.827      9.483.595 (11%)     1    1
Pos 100     88.977.691     10.645.001 (11%)     0    0

[Rebel]

Oh, one detail that so far escaped my attention: you use separate tables for wtm and btm! So effectively each hash probe compares the hash key with only 64M/15 = 4M = 2^22 entries. With a probability of 1 in 2^48 for each of these to be accidentally the same, that would give a probability of getting a collision with a stored entry to 1 in 2^26 = 1 in 64M. You seem to get about 1 in 100M, which might be due to the hash table not being entirely filled in the beginning. Do you clear the TT before every position?

Yes, I am using Chesspartner -> Analyze EPD which reloads the engine after each position.

[Rebel]

The checksum should be good enough for taking collision statistics; it doesn't really matter whether you detect 100% or only 99% (or even 90%) of those.

We have different goals, so it matters to me. I want to know the numbers and later find out if it makes sense (elo wise) to add the checksum mechanism to my engine.

[Rebel]

Forth set of 100 positions at 5 minutes, 192 collisions of which 144 were transpositions.

Code: Select all

POS           Probes          Found Keys     Coll   TP
Pos   1    186.416.259     16.674.523 ( 8%)     2    1
Pos   2    156.148.112     13.249.291 ( 8%)     1    1
Pos   3    180.820.433     18.536.572 (10%)     3    2
Pos   4    156.800.085     12.507.071 ( 7%)     0    0
Pos   5    179.614.438     19.336.463 (10%)     1    1
Pos   6    174.940.669     17.521.327 (10%)     2    2
Pos   7    158.932.520     12.012.636 ( 7%)     1    1
Pos   8    228.991.185     27.829.608 (12%)     3    1
Pos   9    174.852.194     15.770.784 ( 9%)     0    0
Pos  10    172.536.984     14.868.454 ( 8%)     3    1
Pos  11    162.939.403     13.206.161 ( 8%)     4    4
Pos  12    164.123.800     14.754.240 ( 8%)     3    2
Pos  13    157.823.006     11.736.229 ( 7%)     3    1
Pos  14    189.351.527     21.309.052 (11%)     2    2
Pos  15    199.724.756     19.964.562 ( 9%)     3    2
Pos  16    167.368.220     15.427.806 ( 9%)     2    2
Pos  17    169.040.152     13.538.363 ( 8%)     1    1
Pos  18    192.984.591     22.128.376 (11%)     2    2
Pos  19    161.204.489     13.347.014 ( 8%)     2    2
Pos  20    189.831.815     21.725.489 (11%)     3    3
Pos  21    155.990.797     13.748.219 ( 8%)     2    2
Pos  22    161.795.029     17.767.988 (10%)     3    1
Pos  23    188.726.227     17.309.582 ( 9%)     2    1
Pos  24    158.982.137     13.797.051 ( 8%)     1    1
Pos  25    197.300.320     25.565.837 (12%)     3    3
Pos  26    166.303.760     17.139.850 (10%)     0    0
Pos  27    178.581.683     13.895.075 ( 7%)     0    0
Pos  28    185.064.059     20.162.147 (10%)     1    1
Pos  29    176.847.041     13.152.083 ( 7%)     2    1
Pos  30    161.289.601     14.989.243 ( 9%)     1    1
Pos  31    169.986.536     12.556.649 ( 7%)     2    2
Pos  32    197.994.493     22.778.736 (11%)     3    2
Pos  33    183.692.021     17.059.399 ( 9%)     5    5
Pos  34    201.483.785     26.320.335 (13%)     0    0
Pos  35    177.756.922     20.591.027 (11%)     1    1
Pos  36    164.404.473     15.027.253 ( 9%)     0    0
Pos  37    178.392.625     14.478.173 ( 8%)     1    1
Pos  38    170.540.233     14.292.455 ( 8%)     0    0
Pos  39    196.622.311     20.870.069 (10%)     1    1
Pos  40    183.943.885     16.980.285 ( 9%)     3    3
Pos  41    243.397.969     30.599.426 (12%)     2    2
Pos  42    177.230.514     18.918.942 (10%)     2    2
Pos  43    178.710.201     17.798.893 ( 9%)     0    0
Pos  44    161.415.179     10.783.877 ( 6%)     3    0
Pos  45    186.993.718     18.629.238 ( 9%)     1    1
Pos  46    220.611.048     34.221.851 (15%)     1    0
Pos  47    250.368.816     32.202.830 (12%)     3    3
Pos  48    188.936.275     20.695.788 (10%)     0    0
Pos  49    184.913.426     20.921.269 (11%)     2    1
Pos  50    213.327.343     24.259.766 (11%)     1    1
Pos  51    171.097.580     19.444.194 (11%)     3    3
Pos  52    179.463.967     15.717.231 ( 8%)     0    0
Pos  53    171.490.686     21.422.688 (12%)     4    2
Pos  54    168.707.165     15.705.863 ( 9%)     3    0
Pos  55    175.020.636     14.667.887 ( 8%)     2    1
Pos  56    173.888.565     16.916.401 ( 9%)     1    1
Pos  57    174.911.774     20.797.664 (11%)     2    1
Pos  58    176.641.157     14.867.470 ( 8%)     1    1
Pos  59    177.308.287     16.594.781 ( 9%)     1    1
Pos  60    178.558.934     16.056.319 ( 8%)     1    1
Pos  61    171.942.203     14.400.378 ( 8%)     2    2
Pos  62    176.565.279     16.608.489 ( 9%)     2    2
Pos  63    175.326.097     12.662.651 ( 7%)     1    1
Pos  64    169.461.926     14.714.707 ( 8%)     0    0
Pos  65    170.397.633     13.334.918 ( 7%)     1    1
Pos  66    191.701.142     20.014.215 (10%)     4    4
Pos  67    175.877.221     14.965.447 ( 8%)     2    1
Pos  68    161.615.151     12.347.774 ( 7%)     3    3
Pos  69    186.593.148     15.878.320 ( 8%)     2    1
Pos  70    190.532.206     19.310.112 (10%)     3    2
Pos  71    180.943.157     15.709.999 ( 8%)     0    0
Pos  72    185.732.008     19.791.931 (10%)     1    1
Pos  73    204.825.937     23.741.277 (11%)     2    2
Pos  74    174.388.642     15.526.175 ( 8%)     1    1
Pos  75    163.235.799     14.045.633 ( 8%)     1    1
Pos  76    163.229.179     12.898.778 ( 7%)     1    0
Pos  77    182.411.511     33.831.789 (18%)     3    3
Pos  78    163.192.784     15.235.042 ( 9%)     2    1
Pos  79    172.086.749     16.669.921 ( 9%)     1    0
Pos  80    162.135.007     11.318.921 ( 6%)     6    5
Pos  81    188.593.446     16.321.031 ( 8%)     2    1
Pos  82    183.928.825     20.003.785 (10%)     1    1
Pos  83    163.174.672     13.586.284 ( 8%)     2    0
Pos  84    165.275.579     13.422.599 ( 8%)     3    2
Pos  85    171.144.580     13.900.195 ( 8%)     2    2
Pos  86    166.319.979     12.649.057 ( 7%)     2    1
Pos  87    189.155.257     19.504.689 (10%)     3    1
Pos  88    219.553.212     46.181.993 ( 1%)     4    4
Pos  89    195.287.277     19.518.075 ( 9%)     0    0
Pos  90    211.183.691     30.873.433 (14%)     2    2
Pos  91    242.042.314     27.150.254 (11%)     3    2
Pos  92    209.813.658     32.487.490 (15%)     2    2
Pos  93    191.506.811     24.534.732 (12%)     2    1
Pos  94    203.613.015     19.764.179 ( 9%)     1    1
Pos  95    239.259.138     25.727.281 (10%)     6    4
Pos  96    210.145.774     22.824.743 (10%)     3    3
Pos  97    194.684.002     19.861.040 (10%)     0    0
Pos  98    225.035.089     25.074.819 (11%)     4    2
Pos  99    178.091.927     16.962.716 ( 9%)     4    3
Pos 100    202.475.768     22.332.660 (11%)     3    3

[Rebel]

PART-TWO

Moving from a 48 bit hash key to a 56 bit hash key and repeat the 4 x 100 runs.

So far:

Code: Select all

KEY = 48 bit           KEY = 56 bit
POS  Time    Coll  TP    Coll  TP
100  0:30      20  13       0   0
100  1:00      35  19
100  2:30      87  57
100  5:00     192 144

[hgm]

Yes, I am using Chesspartner -> Analyze EPD which reloads the engine after each position.

OK, that explains why you are seeing somewhat fewer collisions that the expected 1 per 64M probes.

We have different goals, so it matters to me. I want to know the numbers and later find out if it makes sense (elo wise) to add the checksum mechanism to my engine.

This can be easily answered:

A checksum as you calculate it is in fact just a special case of a Zobrist encoding scheme (an additive one instead of an XOR one, but that doesn't make much difference), where you set the basis piece-square keys to squareNumber*pieceType. But this is a quite poor set of keys: you would for instance not be able to see the difference between a single Rook on square 16, or a pair of Rooks on squares 7 and 9. In other words, the Zobrist keys you use for the checksum have the worst possible dependency that any set of unequal keys would have: three of them ((R,16), (R,7), (R,9), and in fact many similar groups of three) add/subtract to zero.

The checksum with its 'product keys' is thus on average a much less reliable detector of collisions than a set of randomly chosen piece-square keys of equally many bits. (Which would then be logically equivalent to just extra bits in the Zobrist key, so that you don't have to update anything separately, but could update them together with the bits of the Zobrist key you already had, without any extra code, as long as the total number of bits does not exceed 64.) So if you can spare the bits, just use a longer key / signature, never a checksum. It is both faster and more reliable.

BTW, there is a method to effectively use more than 64 bits of key without extra work for updating it. And you already sort of use that by having separate tables for wtm and btm! The trick is to not use plain hash-key bits for the TT index, but use some extra info to derive it. This way more bits of the key become significant and can be stored in the entry as signature. E.g. one can XOR the stm key and possible e.p. keys only to the index, but not to the signature; it offers no advantage to update these incrementally anyway, (actually that would be detrimental, as these conditions expire after one ply, so that you would both have to apply and then remove them), so you can just do that before every probe. In KingSlayer I XOR the index with the incremental evaluation, (in addition to stm and e.p.-square info), which is somewhat like a checksum using the evaluation PST codes as (additive) Zobrist keys (which is especially distinguishing if the PST also includes the piece values). KingSlayer then stores the original 64-bit hash key as signature, and all 64 bits are significant, as the fact that the index mapped you to that entry no longer implies any subset of the bits must match: collisions between positions that had the same 64-bit board key are no longer possible when they had different incremental evaluation, (or stm, e.p. status), as these would map to different buckets. Of course this is only helpful if all these bits are indeed stored in the entry as signature, but it drives up the supply of bits you could tap from to do that. With current memory sizes the number of buckets can be so large that the number of bits that are not used for calculating the index, and thus usable as independent signature, can be as low as 32. So some extra free key bits could be welcome.