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