'undercut' hash-replacement scheme

[hgm]

I have conceived a new hash replacement scheme. Rather than 'depth-preferred', which only replaces if the new result is deeper or equal in depth than the stored entry, the 'undercut' scheme also replaces when the stored entry is exactly one deeper than the new one.

This makes the life time of entries of any draft in the table approximately proportional to the frequency with which which such drafts are generated, as the number of entries with draft N-1 in a tree is proportional to that of draft N (as they are the direct daughters of the latter).

A more detailed numerical analyses shows that for a tree of branching ratio B, the equilibrium distribution has a ratio between the number of draft-N entries vs that of draft-(N-1) entries of B/(B-1). For large B (such as in perft trees) this is approaches 1, leading to an equal presence of every draft in the table. Such a distribution would be the theoretical optimum. In the 'equidistributed draft' replacement I am using now, this flat distribution has to be enforced by explicitly keeping track of the draft distribution in the table. Updating the required histogram causes some overhead there. But with 'undercut' replacement, such a distribution emerges naturally.

For smaller B, say 4, draft N is favored wrt draft N-1 by a factor much smaller than B: 4/3 in stead of 4. So the larger drafts are still favored, but not to an extent that they will bleed the table dry for low drafts (as pure depth-preferred would).

The scheme is also very easy to combine with an always-replace strategy for entries that were rejected from the depth-preferred section, so that all recent entries remain available. A popular way to implement such combined tables is 'shallowest-of-M replacement': this uses 'buckets' of M entries, replacing the entry with the lowest draft amongst those M. (Popular numbers for M are 2 or 4.) Invoking the undercut principle here would lead to a scheme where you replace the entry to which you primarily hash if its draft is one higher than that of the new entry, but replace the shallowest of the bucket to which the primary entry belongs otherwise. This would cause a healthy turnover of entries with a large draft, without the overhead of maintaining a histogram.

[bob]

The question has to be "why" however. One ply represents a significant amount of work, yet it gets tossed out more frequently. That seems pretty ad hoc. I don't see how it is going to beat the old Belle (2-table) approach, which is even better about "always storing" an entry to make sure that local searches are more efficient.

[hgm]

The question has to be "why" however.

Because of this:



The graph shows that shallowest-of-4 replacement, which is effectively an implementation of the Bell scheme with a depth-preferred table 3 times the size of the always-replace table, performs significantly worse than a scheme which throws out deep entries at the expense of less deep drafts.

This is also what theory predicts: a hit on a deeper draft might save more work per hit, but as the hit-rate decreases with tme, the total amount of work saved by keeping the position will be less than using the same table location for successively storing a large number of less deep drafts during the short time that they have a high hit frequency.

[bob]

The question has to be "why" however.

Because of this:



The graph shows that shallowest-of-4 replacement, which is effectively an implementation of the Bell scheme with a depth-preferred table 3 times the size of the always-replace table, performs significantly worse than a scheme which throws out deep entries at the expense of less deep drafts.

This is also what theory predicts: a hit on a deeper draft might save more work per hit, but as the hit-rate decreases with tme, the total amount of work saved by keeping the position will be less than using the same table location for successively storing a large number of less deep drafts during the short time that they have a high hit frequency.

A wrong assumption: "hit rate goes down with time." What if you have enough memory to make the table a reasonable size? I can easily do 1/2 billion entries. And I don't hash in the q-search, which means I can search a tree of over one billion nodes without having significant overwriting going on. At 10M nodes per second, that takes a pretty good search to just fill the table, much less run into significant overwriting issues...

The other thing I don't particularly like is the depth-1. Seems arbitrary. After tons of testing, I've already discovered that simple extensions are not optimal using 1.0 plies. That makes this sound arbitrary as well.

If it works for you, forge ahead. But not having a way to protect those "huge effort" nodes seems wrong, assuming we are just talking about entries stored in the current search, not entries from several moves earlier in the game that are kept around because of their draft (which I don't do).

[hgm]

Well, that seems a lot like 'battering down an open door': if the table can hold the tree, it doesn't matter much what replacement scheme one uses, as replacement doesn't take place.

I tried not hashing QS in both Joker and uMax, and in both cases it gave a large slowdown. But even if you make that design choice, the problem doesn't really change. You just get the same overload factor at somewhat longer time control. I participate in plenty tournaments where hash is limited to 128MB (14M entries), and where searches of 100 sec at 1-2 Mnps are normal.

Which replacement scheme is best is determined by how they perform with increasing overload, not by the fact that you can reduce the overload by other means.

The depth-1 is indeed arbitrary.It is in fact not ideal, it is just a poor-man's trick to get an event that happens at a higher rate as the storing of positions with draft N, but is not too sensitive for the branching ratio B. And that brought the bucket in cache anyway, so that no separate memory access is needed.

The scheme I currently use takes any access to the bucket, even those done for storing an entry of lowest possible draft, as an oppotunity to erase an overrepresented deep entry from the table. (And of course the entry that had to be stored then replaces it, as it finds an empty slot.) But now I explicitly have to keep track of the arrival of every draft, to know when there are enough to start erasing them again. All, indeed, within a single search.

[bob]

My only comment is this. Given the choice of replacing one of N entries, I can't imagine a circumstance where I would choose to replace with a deeper draft as opposed to replacing one with a shallower draft.

The two-tiered table (Belle approach) addresses two main issues. (1) keep the deep draft entries to save work effort and (b) keep the "local" entries (the entries used in the current sub-tree) to reduce the work there.

I assume you believe that the two "groups" grow far enough apart that there is a huge gap in the middle, entries that don't have enough draft to overwrite depth-preferred entries, and these same entries get rapidly overwritten in the always-store table.

As far as q-search hashing goes, I stopped doing it in 1996. At the same time Bruce and I (Ferret) went to a simple q-search without checks or anything other than reasonable captures. I found the tree size increased about 10%, but the NPS also increased about 10% making this a wash. Except that when not hashing q-search nodes, suddenly smaller hash tables still worked quite well for small memory machines.

I have occasionally re-tested with hashing in the q-search but it just doesn't help my search since captures tend to make transpositions much less likely than with checking moves included.

[hgm]

I assume you believe that the two "groups" grow far enough apart that there is a huge gap in the middle, entries that don't have enough draft to overwrite depth-preferred entries, and these same entries get rapidly overwritten in the always-store table.

Yes this is exactly what happens at very large overloads.

But even at moderate overload factors, replacing the shallowest of 2 leads to a very unequal, and thus suboptimal distribution of drafts in the table. With a branching of 4 and a depth of 12 the tree will have 16M horizon nodes. A 0.5M-entry table, used half as depth-pref, half as always-replace, will saturate the depth-pref part with just the first 9 plies, and ply 10-12 will always be deferred to the always-replace part. There they will be present there in proportion to their occurrence in the tree, so 75% will be horizon nodes, 19% d=1, and 5% d=2. And d=3 (ply 9) will make 75% of the always-replace half of the table. So d=1 and (especially) d=2 will be strongly under-represented compared to d=0 and d=3.

One would get significantly more hits if by alowing d=0-3 equal space, i.e. 44% of a half-table (as the graph shows). For this purpose the d=3 entries have to be curtailed, to give part of the space they would llike to occupy to d=2. But one woul have to prevent that they are mostly taken by d=0 in stead, as would happen when you merely increase the always-replace table size. This was the idea behind undercut, allow d=2 entries to eat space that would otherwise be monopolized by d=3, but don't allow d=1 or d=0 to do that.

[bob]

my only quibble here is the term "distribution" as if that can be sub-optimal. The distribution of nodes by draft is not a uniform distribution, so I'm not sure how we can conclude this distribution is better than that distribution, unless you first search the tree, then compare the tree to the stuff stored to see how they match up...

Note that I don't believe that a raw search time is a good measure here. Quite often a larger hash makes the search take longer, because you get better qualitative information from larger tables, but this can make the tree size grow at the same time. So you get a bigger (slower) tree, but then the result is actually more accurate, which makes it harder to evaluate whether the slower time is better or worse.

[Pradu]

A quick test for Buzz with a 64kb hash table showed that "undercut" scheme performed worse than "depth-preferred" scheme. Of course, nothing can be said from a single position. All statistics are shown with respect to the depth from the root. For example if HashHit% was 1% at depth 9, it means that 1% of all the nodes at depth 9 had a hash hit. I'll try to understand your mathematics of it in a bit...

(Times are off, I had stuff running in the background, look at nodes)

Code: Select all

"depth-preferred"
hash 64 kb
analyze
1 63 0 22 e4
Qsearch Nodes/Nodes = 0.00%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1 100.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
2 0 1 91 e4 e5
Qsearch Nodes/Nodes = 0.00%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1  28.99   0.00     0.00  95.00       0.00    89.47    -1.#J
|   2  71.01   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
3 56 1 668 d4 Nf6 e3
Branching Factor = 1.94
Qsearch Nodes/Nodes = 11.83%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   4.22   0.00   100.00  85.71       0.00    94.74    -1.#J
|   2  16.67   0.00    27.71  66.27       0.00    63.64     0.00
|   3  75.30   1.33     0.53   0.27       0.00    50.00   100.00
|   4   2.41   0.00     0.00   8.33       0.00     0.00    -1.#J
|   5   1.41   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
4 8 6 2933 e4 Nf6 e5 Nd5
Branching Factor = 2.00
Qsearch Nodes/Nodes = 9.61%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   1.07   0.00   100.00  77.27       0.00    78.95    -1.#J
|   2   6.98   0.00    44.44  83.33       0.00    93.81    39.47
|   3  34.24   0.14    18.56  76.91       0.00    93.24    53.85
|   4  55.48   0.52     0.26   1.05       0.00    77.78    66.67
|   5   1.99   2.44     0.00   0.00       0.00    -1.#J   100.00
|   6   0.24   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
5 56 15 12810 e3 Nf6 Qf3 e5 Nc3
Branching Factor = 2.52
Qsearch Nodes/Nodes = 12.40%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.26   0.00   100.00  77.27       0.00    89.47    -1.#J
|   2   1.66   0.00    65.49  80.28       0.00    86.67    56.67
|   3  10.42   0.56    45.80  88.69       0.00    97.53    48.87
|   4  31.77   0.04    22.18  67.24       0.00    85.03    72.92
|   5  48.28   3.38     1.40   4.42       0.00    88.89    84.85
|   6   4.90   0.24     0.00   7.14       0.00    81.48    66.67
|   7   2.63   2.22     0.00   0.89       0.00   100.00   100.00
|   8   0.07   0.00     0.00  16.67       0.00   100.00    -1.#J
|   9   0.01   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
6 -3 46 51163 Nc3 Nc6 Nf3 Nf6 h3
Branching Factor = 3.01
Qsearch Nodes/Nodes = 15.94%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.07   0.00   100.00  85.71       0.00    84.21    -1.#J
|   2   0.32   0.00    80.39  76.47       0.00    84.78    45.71
|   3   2.14   0.15    43.59  89.84       0.00    89.53    60.66
|   4   7.01   0.18    25.37  71.98       0.00    92.11    45.20
|   5  40.10   0.49    20.03  79.62       0.00    93.40    43.75
|   6  41.18   1.63     0.11   2.54       0.00    83.38    85.71
|   7   7.75   1.83     0.12   5.08       0.00    92.91    76.47
|   8   1.12   1.97     0.00   1.40       0.00    83.33   100.00
|   9   0.31   2.00     0.00   1.00       0.00   100.00   100.00
|  10   0.01   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
7 29 120 153655 Nf3 d5 d4 h6 Qd3 Qd6
Branching Factor = 2.57
Qsearch Nodes/Nodes = 16.11%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.02   0.00   100.00  85.71       0.00    94.74    -1.#J
|   2   0.10   0.00    54.12  71.76       0.00    87.04    78.26
|   3   0.78   0.00    36.36  90.16       0.00    85.27    45.54
|   4   2.69   0.26    28.19  72.15       0.00    90.24    42.94
|   5   8.82   0.42     7.09  77.98       0.00    95.13    51.92
|   6  35.75   0.55     8.14  54.72       0.00    91.87    63.46
|   7  41.43   1.22     0.15   4.46       0.00    88.29    77.78
|   8   8.30   2.26     0.27   3.77       0.00    83.21    93.33
|   9   1.73   1.48     0.20   4.92       0.00    94.52   100.00
|  10   0.29   3.23     0.00   1.21       0.00    60.00   100.00
|  11   0.06   0.00     0.00   3.85       0.00    -1.#J    33.33
|  12   0.03   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
8 6 720 1002139 e3 e6 Nc3 Nc6 Qh5
Branching Factor = 5.99
Qsearch Nodes/Nodes = 18.29%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00   100.00  77.27       0.00    78.95    -1.#J
|   2   0.02   0.00    77.08  84.03       0.00    93.94    39.47
|   3   0.10   0.15    39.14  83.31       0.00    87.71    80.39
|   4   0.52   0.03    14.09  86.22       0.00    92.62    46.98
|   5   2.33   0.73    10.24  71.70       0.00    94.33    49.40
|   6   4.89   0.48     2.97  56.11       0.00    91.79    62.03
|   7  41.82   0.91     2.00  49.34       0.00    94.53    67.65
|   8  36.96   1.66     0.07   3.23       0.00    84.94    89.78
|   9  11.04   2.22     0.05   6.50       0.00    92.68    86.12
|  10   1.85   1.06     0.04   2.10       0.00    92.96    94.81
|  11   0.42   3.49     0.03   4.46       0.00    90.37    87.50
|  12   0.05   0.60     0.00   1.49       0.00   100.00    33.33
|  13   0.01  11.11     0.00  11.11       0.00   100.00    -1.#J
|  14   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
9 24 2534 3494677 Nf3 d5 d4 Nf6 Qd3 Nc6
Branching Factor = 3.52
Qsearch Nodes/Nodes = 18.53%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00   100.00  85.71       0.00    94.74    -1.#J
|   2   0.00   0.00    61.80  74.16       0.00    92.98    66.67
|   3   0.03   0.29    42.98  88.89       0.00    93.05    49.07
|   4   0.13   0.00    19.54  77.99       0.00    89.07    58.67
|   5   0.92   0.60     6.56  88.12       0.00    94.31    55.35
|   6   2.87   0.56     5.03  43.53       0.00    91.65    55.32
|   7   6.44   1.25     1.19  57.07       0.00    93.57    57.73
|   8  33.57   0.85     0.48  50.95       0.00    92.86    71.78
|   9  42.21   2.80     0.03   6.55       0.00    91.40    90.26
|  10  10.14   1.37     0.01   4.67       0.00    94.01    88.31
|  11   3.09   2.18     0.00   4.51       0.00    96.01    95.92
|  12   0.44   2.13     0.00   2.36       0.00    91.67    86.78
|  13   0.11   2.72     0.00   3.47       0.00    97.40    91.49
|  14   0.04   0.51     0.00   1.15       0.00    80.00     0.00
|  15   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
10 5 9457 12999939 Nc3 Nc6 Nf3 Nf6 e4
Branching Factor = 3.73
Qsearch Nodes/Nodes = 20.56%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00   100.00  85.71       0.00    94.74    -1.#J
|   2   0.00   0.00    67.35  79.59       0.00    98.25    47.37
|   3   0.01   0.18    47.25  86.15       0.00    87.83    86.89
|   4   0.03   0.00    12.30  84.24       0.00    92.00    48.53
|   5   0.19   0.54     8.21  85.88       0.00    90.71    51.62
|   6   0.93   0.42     1.98  77.40       0.00    93.30    62.19
|   7   4.00   0.94     1.04  38.44       0.00    95.29    51.48
|   8   3.71   1.04     0.33  45.77       0.00    88.64    67.43
|   9  44.38   1.04     0.14  40.68       0.00    95.25    65.02
|  10  30.79   2.50     0.01   5.72       0.00    89.88    90.20
|  11  12.14   2.29     0.00   8.73       0.00    95.53    90.01
|  12   2.92   2.57     0.00   2.94       0.00    92.11    94.64
|  13   0.73   2.40     0.00   4.37       0.00    92.73    83.37
|  14   0.11   3.88     0.00   4.82       0.00    87.79    82.73
|  15   0.04   5.29     0.00   5.43       0.00    94.41    59.52
|  16   0.01   3.50     0.00   3.08       0.00    91.30    75.00
|  17   0.00   3.64     0.00   0.00       0.00     0.00    -1.#J
|  18   0.00   0.00     0.00 100.00       0.00    -1.#J     0.00
|  19   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------

Code: Select all

"undercut"
1 63 0 22 e4
Qsearch Nodes/Nodes = 0.00%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1 100.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
2 0 1 91 e4 e5
Qsearch Nodes/Nodes = 0.00%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1  28.99   0.00     0.00  95.00       0.00    89.47    -1.#J
|   2  71.01   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
3 56 3 668 d4 Nf6 e3
Branching Factor = 2.07
Qsearch Nodes/Nodes = 11.83%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   4.22   0.00   100.00  85.71       0.00    94.74    -1.#J
|   2  16.67   0.00    27.71  66.27       0.00    63.64     0.00
|   3  75.30   1.33     0.53   0.27       0.00    50.00   100.00
|   4   2.41   0.00     0.00   8.33       0.00     0.00    -1.#J
|   5   1.41   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
4 8 7 2936 e4 Nf6 e5 Nd5
Branching Factor = 2.52
Qsearch Nodes/Nodes = 9.64%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   1.07   0.00   100.00  77.27       0.00    78.95    -1.#J
|   2   6.98   0.00    43.75  83.33       0.00    93.88    39.47
|   3  34.30   0.14    18.64  76.84       0.00    93.24    53.85
|   4  55.43   0.52     0.26   1.05       0.00    77.78    66.67
|   5   1.99   2.44     0.00   0.00       0.00    -1.#J   100.00
|   6   0.24   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
5 56 17 12795 e3 Nf6 Qf3 e5 Nc3
Branching Factor = 2.19
Qsearch Nodes/Nodes = 12.42%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.26   0.00   100.00  77.27       0.00    89.47    -1.#J
|   2   1.66   0.00    61.97  80.28       0.00    86.67    56.67
|   3  10.44   0.56    45.13  88.69       0.00    97.55    48.87
|   4  31.88   0.04    22.81  67.18       0.00    84.84    72.92
|   5  48.18   3.42     1.41   4.44       0.00    88.89    84.85
|   6   4.85   0.24     0.00   7.47       0.00    82.14    66.67
|   7   2.64   2.21     0.00   0.88       0.00   100.00   100.00
|   8   0.07   0.00     0.00  16.67       0.00   100.00    -1.#J
|   9   0.01   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
6 -3 46 51061 Nc3 Nc6 Nf3 Nf6 h3
Branching Factor = 2.74
Qsearch Nodes/Nodes = 15.87%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.07   0.00   100.00  85.71       0.00    84.21    -1.#J
|   2   0.32   0.00    80.39  76.47       0.00    84.78    45.71
|   3   2.14   0.15    39.91  89.84       0.00    88.84    60.66
|   4   7.02   0.18    25.00  71.90       0.00    92.06    44.96
|   5  40.35   0.49    22.01  79.69       0.00    93.22    43.84
|   6  40.85   1.65     0.12   2.51       0.00    84.33    86.32
|   7   7.65   1.81     0.12   6.22       0.00    94.12    75.00
|   8   1.18   1.86     0.00   1.33       0.00    83.33   100.00
|   9   0.40   2.34     0.00   1.56       0.00   100.00   100.00
|  10   0.02   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
7 29 123 156485 Nf3 d5 d4 h6 Qd3 Qd6 Ne5
Branching Factor = 2.64
Qsearch Nodes/Nodes = 16.32%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.02   0.00    95.24  85.71       0.00    94.74    -1.#J
|   2   0.10   0.00    51.16  69.77       0.00    84.62    78.26
|   3   0.81   0.00    38.87  90.85       0.00    85.31    44.90
|   4   2.62   0.39    24.48  72.48       0.00    89.89    43.89
|   5   8.93   0.38     6.49  76.35       0.00    95.18    52.59
|   6  35.66   0.55    10.78  56.79       0.00    92.19    61.88
|   7  40.48   1.55     0.25   5.19       0.00    87.83    78.02
|   8   8.75   2.44     0.29   3.94       0.00    82.75    94.92
|   9   2.21   1.90     0.00   2.98       0.00    92.86    84.21
|  10   0.25   3.17     0.00   1.36       0.00    42.86   100.00
|  11   0.12  16.67     0.00  18.52       0.00   100.00    20.00
|  12   0.05   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
8 1 931 1319852 e3 Nc6 Bb5 Nf6
Branching Factor = 7.55
Qsearch Nodes/Nodes = 19.64%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00    68.18  77.27       0.00    78.95    -1.#J
|   2   0.02   0.00    32.03  84.31       0.00    87.85    39.47
|   3   0.08   0.13    28.52  81.77       0.00    83.21    70.15
|   4   0.46   0.42    15.99  86.65       0.00    88.42    45.25
|   5   2.14   0.57    13.26  71.49       0.00    92.22    46.03
|   6   5.22   0.66     3.71  63.68       0.00    91.77    56.15
|   7  37.46   0.79     7.57  57.48       0.00    93.89    64.13
|   8  38.08   2.39     0.46   5.79       0.00    88.89    89.34
|   9  13.33   1.70     0.37   6.45       0.00    93.09    82.70
|  10   2.57   2.21     0.12   2.14       0.00    91.30    98.85
|  11   0.58   1.58     0.02   2.99       0.00    93.04    61.90
|  12   0.05   5.23     0.00   5.00       0.00    81.82    42.86
|  13   0.01   3.75     0.00   5.00       0.00   100.00     0.00
|  14   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
9 22 2862 4021138 Nf3 d5 d4 Nc6 Qd3 Qd6
Branching Factor = 3.07
Qsearch Nodes/Nodes = 18.96%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00    95.45  77.27       0.00    84.21    -1.#J
|   2   0.01   0.00    51.13  82.71       0.00    91.92    59.26
|   3   0.03   0.26    29.77  85.38       0.00    91.10    48.66
|   4   0.17   0.05    20.57  83.20       0.00    90.12    56.69
|   5   0.94   0.61    11.61  85.13       0.00    93.26    57.87
|   6   3.48   0.47     6.03  45.80       0.00    94.00    53.19
|   7   6.40   0.98     2.74  57.34       0.00    94.01    61.24
|   8  39.77   0.65     4.52  48.12       0.00    94.50    69.32
|   9  37.38   2.04     0.64   7.52       0.00    91.92    87.10
|  10   9.01   1.47     0.31   6.60       0.00    94.24    85.92
|  11   2.29   1.69     0.07   2.12       0.00    92.00    97.50
|  12   0.41   2.36     0.18   4.95       0.00    96.12    90.54
|  13   0.07   1.77     0.00   1.58       0.00    95.00    89.80
|  14   0.04   1.06     0.00   1.18       0.00   100.00     0.00
|  15   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------
10 4 10478 14575488 Nc3 Nc6 d4 d5
Branching Factor = 3.66
Qsearch Nodes/Nodes = 20.48%
Depth  Node%   Ext% HashHit%   Cut% Reduction% CUTpred% ALLpred%
|   1   0.00   0.00    90.48  85.71       0.00    84.21    -1.#J
|   2   0.00   0.00    66.67  80.95       0.00    95.16    42.11
|   3   0.01   0.00    23.60  86.01       0.00    85.25    79.10
|   4   0.03   0.19    14.37  84.12       0.00    89.54    47.98
|   5   0.18   0.35     8.62  87.08       0.00    90.16    50.37
|   6   0.82   0.56     7.20  77.12       0.00    92.31    58.68
|   7   3.57   0.79     3.51  44.51       0.00    94.71    51.44
|   8   3.98   1.02     2.18  47.89       0.00    88.75    66.04
|   9  43.82   1.00     3.23  42.74       0.00    94.72    66.21
|  10  31.37   3.11     0.29   5.23       0.00    88.30    92.19
|  11  12.65   1.76     0.38   8.40       0.00    95.78    88.18
|  12   2.71   3.44     0.14   3.20       0.00    92.26    96.97
|  13   0.71   1.43     0.09   4.12       0.00    96.02    84.32
|  14   0.11   3.11     0.29   4.29       0.00    91.22    90.37
|  15   0.03   3.32     0.09   4.45       0.00    95.83    72.73
|  16   0.01   3.08     0.48   3.32       0.00    85.71   100.00
|  17   0.00   2.08     0.00   2.08       0.00   100.00    -1.#J
|  18   0.00   0.00     0.00   0.00       0.00    -1.#J    -1.#J
\---------------------------------------------------------------

[MartinBryant]

FWIW I played a 1000 game match between the normal Colossus 2007b and a version with 'Undercut'.

The undercut version won the match +298/=428/-274 for a gain of +8 ELO

Although this is not significantly better it is also not significantly worse.

Colossus 2007b uses the traditional depth replacement criteria, with a single overflow entry and ageing. It does not dedicate any of the hash table to an 'always-replace' scheme.