Author: Carmelo Calzerano
Date: 05:37:31 02/14/01
Go up one level in this thread
On February 13, 2001 at 20:25:14, Larry Griffiths wrote:
>On February 13, 2001 at 08:55:23, Carmelo Calzerano wrote:
>
>>On February 13, 2001 at 06:09:02, Larry Griffiths wrote:
>>
>>
>>>It looks more like this, Bob.
>>>BestScoreSoFar=alpha
>>>
>>>for(do capture moves)
>>
>>[snip]
>>
>>> return BestScoreSoFar;
>>
>>
>>(It seems to be ok)
>>
>>>>>I see all three types added to my hash table, but it seems that the
>>>>>upper_bound entries never cause any cutoffs to occur when searching
>>>>>the hash table.
>>>>>
>>>>>If I do not add lower_bound hash table entries, then I see some
>>>>>upper_bound cutoffs occuring. It acts like the upper_bound entries
>>>>>get overlayed so often by lower_bound entries so that they never
>>>>>get seen when searching the hash table.
>>>>>Is this normal, or is something wrong with my code?
>>
>>I guess it's normal, although you should definitely see some upper_bound
>>cutoffs from time to time. Matter is that the number of fail-high nodes
>>(which stores lower bounds in the HT) is usually about one order of magnitude
>>_bigger_ than the number of fail-low nodes visited in search; so upper_bound
>>HT entries are often replaced by lower_bound ones.
>>
>>So it should be normal, IMHO, if lower_bound cutoffs occur more often (say
>>10 times, for example) than upper_bound ones; but the number of upper_bound
>>cutoffs should not be zero anyway...
>>:-)
>>
>>Bye,
>>Carmelo
>
>Thanks Carmelo,
>
>My program performs about the same with, or without this hash table. It hardly
>makes any impact on endgame positions.
>Seems like the only thing that really works well in my program are my killers.
I guess you mean "upper_bound cutoffs" hardly makes any impact on endgame
positions, right? Because if your _hash table_ doesn't make a significative
difference, then you definitely have a serious bug somewhere! :-)
BTW, I made some tests with my own program (Leila) on Fine70 position,
on a PII300MHz:
Leila (c) C. Calzerano 2001 - version 032 Jan 29 2001
========================================================
Main Hash: 5632 Kb [256 K Entries]
Pawn Hash: 1920 Kb [128 K Entries]
Depth Score Time Nodes Hash Cutoffs PV
(Ex, Up, Low)
With hashing fully enabled (default):
27 220 1.00 143795 (11, 5076, 50321) Ka1b1 Ka7b7 Kb1c1 (...)
28 220 1.35 199156 (11, 6234, 64222) Ka1b1 Ka7b7 Kb1c1 (...)
29 220 1.84 277330 (11, 7717, 79438) Ka1b1 Ka7b7 Kb1c1 (...)
30 215 2.33 357395 (11, 10241, 98278) Ka1b1 Ka7b7 Kb1c1 (...)
31 225 6.82 962578 (11, 18155, 156790) Ka1b1 Ka7b7 Kb1c1 (...)
32 225 9.42 1322837 (11, 26378, 199169) Ka1b1 Ka7b7 Kb1c1 (...)
33 237 18.34 2540465 (11, 45069, 306946) Ka1b1 Ka7b7 Kb1c1 (...)
Disabling lower_bound hash entries (hashing of Fail-High nodes):
27 192 2.92 474295 (346, 125379, 0) Ka1b1 Ka7b7 Kb1c1 (...)
28 194 4.31 674890 (403, 157353, 0) Ka1b1 Ka7b7 Kb1c1 (...)
29 195 6.61 1004746 (506, 205797, 0) Ka1b1 Ka7b7 Kb1c1 (...)
30 197 14.20 1992230 (567, 299101, 0) Ka1b1 Ka7b7 Kb1c1 (...)
31 198 31.01 4079230 (590, 444124, 0) Ka1b1 Ka7b7 Kb1c1 (...)
(Starts taking too many time to reach bigger depths)
Disabling upper_bound hash entries (hashing of Fail-Low nodes):
27 170 1.06 183374 (26, 0, 80064) Ka1b1 Ka7b7 Kb1c1 (...)
28 170 1.25 214642 (27, 0, 89500) Ka1b1 Ka7b7 Kb1c1 (...)
29 170 1.74 295273 (27, 0, 104765) Ka1b1 Ka7b7 Kb1c1 (...)
30 170 2.67 431549 (27, 0, 128501) Ka1b1 Ka7b7 Kb1c1 (...)
31 170 4.98 769909 (31, 0, 171119) Ka1b1 Ka7b7 Kb1c1 (...)
32 170 13.01 1851848 (32, 0, 256879) Ka1b1 Ka7b7 Kb1c1 (...)
33 205 33.51 4518067 (32, 0, 455010) Ka1b1 Ka7b7 Kb1c1 (...)
Disabling exact_score hash entries (hashing of exact nodes):
27 187 1.12 152807 ( 0, 5871, 53854) Ka1b1 Ka7b7 Kb1c1 (...)
28 190 1.52 217818 ( 0, 7030, 67968) Ka1b1 Ka7b7 Kb1c1 (...)
29 205 1.99 290677 ( 0, 8592, 82838) Ka1b1 Ka7b7 Kb1c1 (...)
30 215 2.99 444690 ( 0, 11414, 109538) Ka1b1 Ka7b7 Kb1c1 (...)
31 230 6.05 877523 ( 0, 17127, 150494) Ka1b1 Ka7b7 Kb1c1 (...)
32 225 9.28 1325740 ( 0, 25431, 193446) Ka1b1 Ka7b7 Kb1c1 (...)
33 225 13.59 1941013 ( 0, 36858, 261023) Ka1b1 Ka7b7 Kb1c1 (...)
So it seems that for Leila (the version tested uses a one-level hash table,
with simple deph-based replacement scheme), hash-based cutoffs hardly have
any impact on performance, when analysing Fine70.
In fact, when hashing of fail-high nodes is disabled, search is much less
efficient; but that's likely an effect of the worse move ordering (no info
on best move for FH nodes).
Moreover, you can notice that the number of lower_bound hash cutoffs at
depth = 31 is less than 20k (1/9 - 1/10 of total hash cutoffs) when full
hashing is enabled; but increases to about 450k when disabling FH hashing.
This seems to confirm that FL entries gets often overlayed by FH ones.
But I found something more interesting, which seems to confirm your own
data. I made some other tests, not disabling hashing of FH/FL nodes (to
not affect move ordering), but disabling _cutoffs_ on hash hits for FH/FL
nodes. IE, hash best move is still used for move ordering, while early
cutoffs based on hash bounds are disabled.
The results were interesting, although reasonable (in fact it behaved exactly
as expected!) :)
While disabling low_bound cutoffs _or_ upper_bound cutoffs did not changed
too much Fine70 solving time, disabling of *BOTH* low_bound AND upper_bound
cutoffs had a very big impact on search performance: effective branching
factor became so much bigger (about 2, till depth 16) that Leila was unable
to even reach depth 17 in 30 seconds on my PC.
The reason is simple, IMHO: when disabling only (say) low_bound cutoffs, you
won't get hash cutoff on an FH node, but you'll most likely get high_bound
hash cutoffs on almost every of its children nodes (which are FL nodes); and
vice versa: search performance won't decrease so much.
Instead, when disabling BOTH low and high bound cutoffs, you'll get no hash
cutoffs at all: that's why the search suffers a big penalty...
Well, Fine70 is a very interesting position for testing hash-related stuffs;
it behaves like a sort of "amplifier" of possible hash problems :-)
But the above should be true on a generic position too, although far less
noticeable; and that's why IMO you don't experience a big difference in
your program enabling or disabling upper_bound cutoffs. I suggest you to
do the same test I did: first, check what happens when hashing is disabled
alternatively on FH or FL or both FH/FL nodes; then, check what happens when
you don't disable hashing, but ignore upper or low or both upper/low bound
cutoffs.
I guess you'll find my same results:
- FL hashing disabled: --> no big changes
- FH hashing disabled: --> suffering due to worse move ordering
- FL/FH hashing disabled: --> bigger suffering (hash is nearly not used)
- FL cutoffs disabled: --> no big changes
- FH cutoffs disabled: --> no big changes
- FL/FH cutoffs disabled: --> suffering, bigger in endgame/Fine70-like positions
Hope you'll find something useful among these data...
:-)
Bye,
Carmelo
This page took 0.02 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.