Replacement Scheme / Hash Hits

[Desperado]

Hi everyone !

I am searching for several days for bugs in my transpositiontable modul.
I cant find some.

So my question now is, can somebody give me some percent numbers
for the following position under following conditions...

1.Condition: always replace scheme (in hope the numbers are comparable then)
2.Condition: small hashsize of 1MB, so the replacement scheme gets work...

POS_1: r3k2r/p1ppqpb1/bn2pnp1/3PN3/1p2P3/2N2Q1p/PPPBBPPP/R3K2R w KQkq - 0 1

POS_2: 8/8/8/8/1k6/7K/7P/8 b - - 0 1

in position 2 all seems to work well (i get a hashhit number over 90% to 92% on depth 26)

BUT: position 1

the hit rate starts about 6% drops 2% on searchdepth 8 for example.

of course i am sure (so sure it is possible to be , that the hashnumbers are updated correct...)

Now the final question is, why there could be such a low hashhit number for pos1 (assuming all technical details are working correct) ? And are you able to post some numbers for position1(2) for depth 5 to let say depth 12 ?
it is so important to me because the branching factor is very worse if there arent moves from TT , because of no hash hit...) thx a lot.

[Desperado]

oh i forgot...

can somebody explain to me how "age" is handled in TT ?
(on iteration ? on new search ? how does a TT-entry ages or the TT itself or both ?) . Well, i dont think it is the same as depth-comparison, or is it?

[hgm]

My engines are not very representative for hash statistics, as they use IID in every node.

As to the aging: some people use a separate aging field in the hash, containing depth + searchNumber, and compare it against depth+searchNumber of a new entry to see if replacement should take place.

In Joker I use equidistributed-draft replacement, where aging is not so much of an issue, as entries tend to be flushed out of the hash table sooner or later anyway, usually even during the search they were created. This is basically the same as only replacing entries by deeper or equally deep entries, and sending the new entry to an always-replace slot (usually shared by number of entries in the same cache line) otherwise. But when the number of entries of a given draft (depth) in the depth-preferred part of the table gets larger than that of the lowest draft, entries of that 'overrepresented' draft will be replaced by whatever lands on them, like their draft was zero. This allows accumulation of deep entries untill they occupy more than their fair share of the hash table, and after that they start to be overwritten at the same rate as they are produced by the search.

[Stan Arts]

Hi Michael,

here are some of my engine's numbers. 4MB hash, of which 1MB has an always replace strategy, and 3MB depth and exact score preferred. My entries are 8 byte.

Your numbers are what I would expect, position 1 is a tactical position with most pieces on the board, great many moves per side and transpositions are quite rare because they are hard to make, also because chessengines typically will try a lot of captures first after which you can't transpose. Position 2 on the other hand is transposition heaven, but you'd typically only get such huge transposition numbers in pawn endings or completely locked positions and those are rare.

Ageing is important to be able to re-use hashentries in next searches, next moves in gameplay. If you'd have a depth preferred table and would not age or remove entries old entries with big depths would start to fill up the table and not get overwritten anymore.
You could set a bit to tell this entry is from an old search, then you could simply overwrite this entry with a new one of the new search even if it has less depth.
But after search I simply decrease depth of the depth preferred table with 1 ply, which loses some efficiency (made up a little by entries in the always replace table) but is a very simple way to "age"..

In fact, your percentages seem to be higher then mine.
Counters were reset between each iteration.

Stan

Position 1. :

Code: Select all

Legal moves: 48   Static score: 20
Ply Score  Time     Nodes      Best move and expected line
------------------------------------------------------------
hashprobes: 49 hashcutoffs: 0 %: 0
2   50     4        611        Bxa6 hxg2 Qxg2
hashprobes: 147 hashcutoffs: 0 %: 0
3   29     5        2654       Bxa6 bxc3 Bxc3 hxg2 Qxg2
hashprobes: 2436 hashcutoffs: 29 %: 1
4   29     7        6421       Bxa6 bxc3 Bxc3 hxg2 Qxg2
hashprobes: 3691 hashcutoffs: 117 %: 3
5   5      11       13621      Bxa6 < - > bxc3 Be3 exd5 Bxb6 cxb6
5   4      13       17446      Bxa6 bxc3 Bxc3 exd5 exd5 hxg2 Qxg2
hashprobes: 21433 hashcutoffs: 353 %: 1
6   4      33       77972      Bxa6 bxc3 Bxc3 exd5 exd5 hxg2 Qxg2
hashprobes: 24130 hashcutoffs: 898 %: 3
7   -20    68       162447     Bxa6 < - > bxc3 Bxc3 exd5 exd5 Nf6xd5 Rf1 Nxc3
7   -61    93       235526     Bxa6 bxc3 Bxc3 exd5 Bd3 Nxe4 Bxe4 Bxe5
hashprobes: 127815 hashcutoffs: 3909 %: 3
8   -85    216      570354     Bxa6 < - > bxc3 Bxc3 exd5 Bd3 Nxe4 gxh3 Nxc3 bxc3
8   -99    243      645641     Bxa6 bxc3 Bxc3 exd5 gxh3 Nxe4 Nc6 Bxc3+ Qxc3 Nxc3+ Nxe7
8   -98    355      936967     dxe6 < + > bxc3 exf7+ Kd8 Bxc3 Rf8
8   -93    411      1098672    dxe6 bxc3 exf7+ Kd8 Bxc3 Bxe2 Kxe2 hxg2 Qxg2 d5
hashprobes: 432658 hashcutoffs: 21984 %: 5
9   -114   813      2089499    dxe6 Qxe6 Bxa6 Qxe5 Nd1 hxg2 Qxg2 Nxe4 Be3
9   -113   847      2175794    Bxa6 < + > bxc3 Bxc3 exd5 gxh3 Nxe4 Nc6 Bxc3+
9   -47    1616     4435823    Bxa6 exd5 Nxg6 fxg6 Nb5 O-O Qxh3 Nxe4 O-O-O Nxf2
hashprobes: 1466983 hashcutoffs: 63647 %: 4
10  -56    3633     9685660    Bxa6 exd5 Nxd5 Nf6xd5 Nd3 f5 e5 Bxe5 O-O-O hxg2 Qxg2
hashprobes: 3775114 hashcutoffs: 171827 %: 4
11  -56    11425    32921932   Bxa6 exd5 Nxd5 Nf6xd5 Nd3 f5 e5 Bxe5 O-O-O hxg2 Qxg2
hashprobes: 13174275 hashcutoffs: 379850 %: 2
12  -41    40654    112764395  Bxa6 bxc3 Bxc3 exd5 Ng4 Nxg4 Bxg7 Rh4 gxh3 dxe4
hashprobes: 59232852 hashcutoffs: 2175828 %: 3
Total nodes:174730710 time:59591 n/sec:293200  (q-nodes:54% max depth:30) 

Position 2. :

Code: Select all

Legal moves: 8   Static score: -95
Ply Score  Time     Nodes      Best move and expected line
------------------------------------------------------------
hashprobes: 8 hashcutoffs: 0 %: 0
2   -98    0        13         Kc4 Kg4
hashprobes: 19 hashcutoffs: 0 %: 0
3   -98    0        43         Kc4 Kg4 Kd4
hashprobes: 77 hashcutoffs: 0 %: 0
4   -108   0        162        Kc4 Kg4 Kd4 h4
hashprobes: 131 hashcutoffs: 35 %: 26
5   -110   0        376        Kc4 Kg4 Kd4 h4 Ke4
hashprobes: 295 hashcutoffs: 48 %: 16
6   -122   1        861        Kc4 Kg4 Kd4 h4 Ke4 h5
hashprobes: 495 hashcutoffs: 171 %: 34
7   -124   1        1597       Kc4 Kg4 Kd4 h4 Ke4 h5 Kd4 Ke4 Kd4 Ke4
hashprobes: 796 hashcutoffs: 244 %: 30
8   -138   1        3005       Kc4 Kg4 Kd4 h4 Ke4 h5 Ke5 h6
hashprobes: 1414 hashcutoffs: 619 %: 43
9   -204   1        3816       Kc4 < - > Kg4 Kd4 h4 Ke4 h5 Ke5 h6 Kf6
9   -218   1        5326       Kc4 Kg4 Kd4 h4 Ke5 h5 Kf6 h6 Kg6
hashprobes: 2218 hashcutoffs: 961 %: 43
10  -204   3        11707      Kc4 Kg4 Kd4 Kf5 Kc5 h4 Kd6 h5 Ke7 h6
10  -202   3        14181      Kc5 < + > Kg3 Kd5 h4 Ke6 h5 Kf6 h6 Kg6 Kf2
10  -138   3        16693      Kc5 Kg4 Kd6 h4 Ke7 Kg5 Ke6 h5 Ke5 h6
hashprobes: 10774 hashcutoffs: 4078 %: 37
11  -204   3        18223      Kc5 < - > Kg4 Kd6 h4 Ke7 Kg5 Kd7 Kf5 Kd8 h5 Ke7 h6
11  -233   4        23339      Kc5 Kg4 Kd6 h4 Ke7 Kg5 Kf7 h5 Kg7 h6+ Kh7
hashprobes: 6748 hashcutoffs: 3159 %: 46
12  -233   6        34470      Kc5 Kg4 Kd6 h4 Ke7 Kg5 Kf7 h5 Kg7 h6+ Kh7 Kh5
hashprobes: 10239 hashcutoffs: 4309 %: 42
13  -242   9        48543      Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Ke8 h4 Kf8 h5 Kg8 h6 Kh8 Kg8 h7+ Kh8 Kxh7+
hashprobes: 13906 hashcutoffs: 7047 %: 50
14  -240   12       68786      Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Ke8 h4 Kf8 h5 Kg8 h6 Kh8 Kh5 Kg6 Kg8 h7+ Kh8 Kxh7+
hashprobes: 19410 hashcutoffs: 10027 %: 51
15  -261   17       104758     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 h4 Kg8 h5 Kh8 h6 Kg8 h7+ Kh8 Kxh7+
hashprobes: 41493 hashcutoffs: 23501 %: 56
16  -236   21       135766     Kc5 < + > Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 h4 Kg8 h5 Kh8 Kg5 Kg8 Kg6 Kh8 Kg5 Kg8
16  -235   25       158643     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 h4 Kg8 h5 Kh8 h6 Kg8 Kf6 Kh7 Kg5 Kg8 Kg6 Kh8 Kf7 Kh7 Ke7 Kg8 Kh7 Kg8 Kh7
hashprobes: 47486 hashcutoffs: 29170 %: 61
17  -260   26       168622     Kc5 < - > Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kg5 h6 Kf5 Kg8 Kf4
17  -273   29       189551     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Ke7 h7 Kd6
hashprobes: 30295 hashcutoffs: 18318 %: 60
18  -273   35       229437     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Ke7 h7 Kd6
hashprobes: 38696 hashcutoffs: 24387 %: 63
19  -277   42       278028     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Kf7 h7 Ke6 Kd5
hashprobes: 48253 hashcutoffs: 30455 %: 63
20  -277   50       336533     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h3 Kf8 h4 Kf7 Kh6 Kf8 Kh7 Kf7 Kh6 Kf8 Kh7
hashprobes: 56007 hashcutoffs: 36985 %: 66
21  -277   57       393299     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Kf7 Kh7 Kf8 Kh8 Kf7 Kh7
hashprobes: 55098 hashcutoffs: 36469 %: 66
22  -277   65       457723     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Kf7 Kh7 Kf8 Kh8 Kf7 Kh7
hashprobes: 62928 hashcutoffs: 43082 %: 68
23  -302   68       477962     Kc5 < - > Kg4 Kd6 Kf5 Kc6 h4 Kd6 h5 Kd7 h6 Kd6 h7 Kc6 Kg5 Kb6 Kf5 Kc5 Kg5 Kb4 Kf5 Kc4 Ke5 Kc5 Kf5
23  -291   76       537251     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Kf7 Kh7 Kf8 Kh8 Kf7 Kh7
23  -291   76       537256     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 h5 Kf7 h6 Kf8 Kh8 Kf7 Kh7 Kf8 Kh8 Kf7 Kh7
hashprobes: 76698 hashcutoffs: 51252 %: 66
24  -262   89       631978     Kc5 < + > Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
24  -261   100      715540     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 171772 hashcutoffs: 117491 %: 68
25  -236   123      880319     Kc5 < + > Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
25  -233   146      1046378    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 321506 hashcutoffs: 222122 %: 69
26  -233   157      1137467    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 88417 hashcutoffs: 59094 %: 66
27  -233   171      1237588    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 97659 hashcutoffs: 66327 %: 67
28  -233   187      1357410    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 116819 hashcutoffs: 79047 %: 67
29  -233   206      1494991    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 134373 hashcutoffs: 90320 %: 67
30  -233   229      1670011    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 170804 hashcutoffs: 114754 %: 67
31  -233   259      1885049    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 210705 hashcutoffs: 144747 %: 68
32  -233   298      2173128    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes: 281769 hashcutoffs: 190235 %: 67
33  -233   346      2532627    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 352496 hashcutoffs: 251714 %: 71
34  -233   409      3014460    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 472173 hashcutoffs: 335586 %: 71
35  -233   487      3606892    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 580820 hashcutoffs: 426017 %: 73
36  -233   589      4396905    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 773971 hashcutoffs: 569046 %: 73
37  -233   712      5348633    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 932869 hashcutoffs: 698194 %: 74
38  -233   878      6651793    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 1274916 hashcutoffs: 954780 %: 74
39  -233   1070     8156357    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 1471593 hashcutoffs: 1125809 %: 76
40  -233   1303     10040705   Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes: 1839734 hashcutoffs: 1413195 %: 76
Total nodes:10045152 time:1304 n/sec:770300  (q-nodes:0% max depth:49)

[Desperado]

hm,ok. let us see if i have understood what you wrote...(hg muller)

instead of partition the TT into "single" entries, i can partition it
into some kind of buckets including (let us say 2 entries) each bucket.
Before writing, i check all entries in the bucket and replace the worst
compared to some condition(depth for example, or other stuff or like...).

"number of entries of a given draft":

well, i think you mean remaining depth to horizon. if this is the case,
how can a "depth" be overrepresented ?
ex: 10 entries (rdp = remaining depth)

8 with rdp 6(or 3)
1 with rdp 7(or 6)
1 with rdp 3(or 7) (or any other rdp combination)

so, are the 8 entries overrpresented ?


-> Stan , thx for the numbers.

ok, i can see what i wanted to see, it doesnt seem to be an error (my numbers for the position1). Also i can see the same behavior, the higher the search the lower the percentage, and i think searching more deeply would continue dropping these values. Again, thx a lot

[Desperado]

Hi Stan,

as i replied before, my numbers are similar to your numbers.

But i recognized a big difference. When i said TT_hits, i thought of positions i can find in the TT. Then i saw your hashCUT numbers.

My HashHITS are similar to your HashCUTS (i have much lower cutrate).

I am using pvs-frame, and before storing a position i set the following flags.

if(bestvalue > alphaold && bestvalue<beta) flg_ex
if(bestvalue <=alphaold) flg_ub
if(bestvalue >=beta) flg_lb

something wrong? or what dificulties are included when using pvs and TT ?

[Stan Arts]

Hi Michael,

Ah I see, think I misunderstood.
Reran the test, this time counting hashhits, and percentages have gone up a bit, but the numbers are still in the ballpark, in fact the second position now returns very close to your percentages.

No difficulties with pvs and TT's as far as I'm aware of, besides almost always searching with a closed alpha-beta window (alpha=beta-1) which likely causes similair searches to search slightly different movepaths and scores causing fewer hashhits and cuts here and there. Nothing you can do about that I suppose. (computerchess.. win some here, lose some there) From what I've heard people are experiencing a similair problem when they go parallel by means of a shared hashtable. Where searching with wider windows can suddenly cause a bigger speedup..

Stan

Code: Select all

Position 1. : 
5   4      14       17446      Bxa6 bxc3 Bxc3 exd5 exd5 hxg2 Qxg2
hashprobes:21433 hashhits:1509 %:7
6   4      35       77972      Bxa6 bxc3 Bxc3 exd5 exd5 hxg2 Qxg2
hashprobes:24130 hashhits:3752 %:15
7   -61    95       235526     Bxa6 bxc3 Bxc3 exd5 Bd3 Nxe4 Bxe4 Bxe5
hashprobes:127815 hashhits:14393 %:11
8   -93    416      1098672    dxe6 bxc3 exf7+ Kd8 Bxc3 Bxe2 Kxe2 hxg2 Qxg2 d5
hashprobes:432658 hashhits:57442 %:13
9   -47    1631     4435823    Bxa6 exd5 Nxg6 fxg6 Nb5 O-O Qxh3 Nxe4 O-O-O Nxf2
hashprobes:1466983 hashhits:131820 %:8
10  -56    3669     9685660    Bxa6 exd5 Nxd5 Nf6xd5 Nd3 f5 e5 Bxe5 O-O-O hxg2 Qxg2
hashprobes:3775114 hashhits:347122 %:9
11  -56    11536    32921932   Bxa6 exd5 Nxd5 Nf6xd5 Nd3 f5 e5 Bxe5 O-O-O hxg2 Qxg2
hashprobes:13174275 hashhits:799040 %:6
12  -41    41111    112764395  Bxa6 bxc3 Bxc3 exd5 Ng4 Nxg4 Bxg7 Rh4 gxh3 dxe4
hashprobes:59232852 hashhits:3616174 %:6

Position 2. : 
14  -240   12       68786      Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Ke8 h4 Kf8 h5 Kg8 h6 Kh8 Kh5 Kg6 Kg8 h7+ Kh8 Kxh7+
hashprobes:19410 hashhits:14580 %:75
20  -277   50       336533     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h3 Kf8 h4 Kf7 Kh6 Kf8 Kh7 Kf7 Kh6 Kf8 Kh7
hashprobes:56007 hashhits:52217 %:93
24  -261   100      715540     Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes:171772 hashhits:167952 %:97
26  -233   158      1137467    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes:88417 hashhits:82974 %:93
30  -233   230      1670011    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf6 Kh6 Kf7 Kh7 Kf6 Kh6 Kf7 Kh7
hashprobes:170804 hashhits:153142 %:89
38  -233   873      6651793    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes:1274916 hashhits:1174815 %:92
39  -233   1066     8156357    Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes:1471593 hashhits:1384506 %:94
40  -233   1297     10040705   Kc5 Kg4 Kd6 Kf5 Ke7 Kg6 Kf8 Kh7 Kf7 h4 Kf8 h5 Kf7 Kh8 Kf6 Kh7 Kf7 Kh8 Kf6 Kh7 Kf7
hashprobes:1839734 hashhits:1721576 %:93

[bob]

oh i forgot...

can somebody explain to me how "age" is handled in TT ?
(on iteration ? on new search ? how does a TT-entry ages or the TT itself or both ?) . Well, i dont think it is the same as depth-comparison, or is it?

You have already gotten an answer on the node issue so I am skipping that. For aging, what I do is to use a variable that is updated like this at the start of each new search (not each new iteration, but each time the iterated search is started from a new position):

age = ++age & 7;

that gives me a value that goes up by one each new search until it reaches 7, where it then "wraps around" to zero again. This requires a 3-bit field in the hash entry. When I do a hash store, I store the current age value in the entry. When I have to make a decision on "do I overwrite this entry" I will always replace if the entry age is not the same as the current age, which means the hash entry I am about to replace came from an _earlier_ (older) search. If I replace in the depth-preferred table, I push the replaced entry to the always store table.

[hgm]

Draft is indeed the term used (by prof. Hyatt) for remaining search depth of a TT entry.

With 'overrepresented' I mean "outnumbering the rdp=d=0 entries". (If d=0 is the lowest depth you store in your depth-preferred entries; some people store d=0 only in the always-replace part or even not at all; in that case you would have to compare to the number of d=1 entries.)

The example you give is a bit too unnatural to comment on; it does not mention d=0 entries at all, while normally your TT would be swamped with them. Before you do any replacement, the occurrence of each draft is equal to the occurrence in the tree, i.e. d=N entries are typically 6-10 times more abundant than d=N-1, and for QS nodes there are even more. If you do replace-always, that ratio is preserved forever, as each draft is replaced at the same rate.

With a depth-preferred replacement, you get the opposite effect; at some point (which can occur early within a single search at log TC) the table is completely filled with high drafts, and intermediate depths can no longer find a place in it. So d=0 will be squeezed out. When that starts to happen, the other drafts will become overrepresented, and become replameet candidates again, to be replaced mostly by d=0, so that an equilibrium results in which each draft occupies an equal share of the hash table.

[bob]

Draft is indeed the term used (by prof. Hyatt) for remaining search depth of a TT entry.

With 'overrepresented' I mean "outnumbering the rdp=d=0 entries". (If d=0 is the lowest depth you store in your depth-preferred entries; some people store d=0 only in the always-replace part or even not at all; in that case you would have to compare to the number of d=1 entries.)

The example you give is a bit too unnatural to comment on; it does not mention d=0 entries at all, while normally your TT would be swamped with them. Before you do any replacement, the occurrence of each draft is equal to the occurrence in the tree, i.e. d=N entries are typically 6-10 times more abundant than d=N-1, and for QS nodes there are even more. If you do replace-always, that ratio is preserved forever, as each draft is replaced at the same rate.

With a depth-preferred replacement, you get the opposite effect; at some point (which can occur early within a single search at log TC) the table is completely filled with high drafts, and intermediate depths can no longer find a place in it. So d=0 will be squeezed out. When that starts to happen, the other drafts will become overrepresented, and become replameet candidates again, to be replaced mostly by d=0, so that an equilibrium results in which each draft occupies an equal share of the hash table.

Actually, for the record, "draft" is not my term. I believe Burt Wendroff coined that term when he wrote a paper on hashing for the JICCA back in the late 80's. It has become accepted, however, and has been used in every hash discussion I have seen since...