Measuring Hash Collisions (once again)
Posted: Thu Feb 27, 2020 4:47 pm
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.
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