Author: Eugene Nalimov
Date: 12:27:59 11/17/97
Go up one level in this thread
On November 17, 1997 at 10:44:54, Robert Hyatt wrote:
>On November 17, 1997 at 10:00:14, Chris Carson wrote:
>
>>Here are the results:
>>
>>Constants:
>>
>>Pentium 133 (non-mmx)
>>Windows 95
>>Crafty 13.10
>>Book off
>>Pondering off
>>Set Depth 11
>>Move 1. a3 (opening)
>>
>>Results:
>>
>>Hash Ply=9 Ply=10 Ply=11
>>---- ----- ------ ------
>>3MB 00:43 02:32 27:33
>>6MB 00:42 02:28 14:05
>>12MB 00:43 02:26 13:33
>
>very good data. Let's see what this means:
>
>first, hash entries are 16 bytes per entry, so 12mb = 3/4 million
>entries,
>6mb = 3/8 million entries, and 3mb = 3/16 million entries.
>
>Second, on a P5/133, crafty should search around 30K nodes per second,
>typical.
>
>Let's take each test one at a time:
>
>ply=9. 43 seconds = 43 x 30 x 1000 = 1,290,000 nodes. Since Crafty
>does
>not hash quiescence nodes, I'll guestimate that 2/3 of the nodes
>searched
>never make it to the hash table, so 400,000 nodes will be stored, and
>only
>12mb is enough to store all of them. However, since the times are
>identical,
>we can assume that the replacement strategy is good enough so that even
>with the smallest size (187,500 entries) the 2:1 over-utilization is not
>a
>problem. The next size is close to the size of the tree that was
>searched
>(non-qsearch nodes, 375,000 entries) while the last is obviously
>overkill at
>750,000 entries)
>
Maybe I'm wrong, but:
1. In the 'a3' test hash table will be used mainly for move ordering -
that's not endgame.
(But that's also not an middlegame either - maybe things are
different here? It's easy
to make an experiment - just remove HT cutoff and alpha/beta bounds
modification
from Crafty),
2. So, if we are searching to ply N, we have to store entire tree at ply
N-1. Of course,
Crafty will store results at ply N too, but (hopefully) hash table
replace strategy is
good enough - at least it will not overrite hash entry with depth 2
from ply N-1 by
hash entry with depth 1 from ply N.
3. So, for middlegame search to ply N, 'sufficient' hash table size is
not sizeof (tree),
but sizeof(tree)/(branching factor), e.g. sizeof(tree)/2.5.
Eugene
>ply=10 again has no differences, although the size of the tree is up to
>roughly 150 x 30 x 1000 = 4,500,000 nodes. Lets keep the 33%
>non-qsearch
>guess, so we now are going to search 1.5M nodes that need to be stored.
>This is over 10x the size of the smallest table, 5x the size of the
>middle
>test you ran, and 2x the size of the largest table. yet there is no
>real
>difference, which says that 10X over-utilization is not harmful due to
>the
>replacement strategy I use.
>
>ply=11 begins to find the breaking-point of the small hash table, since
>the
>times jump sharply. The simplest conclusion to draw from this case is
>that
>3M is too small, while 6M/12M are close enough to be considered
>equivalent.
>27 minutes should turn into 27 x 60 x 30 x 1000 = 48,600,000 nodes.
>This
>is *way* over any of the sizes. Again take 1/3 which is 16M nodes.
>This
>is a poor fit for 187,500 entries, and would seem to be a poor fit for
>375,000
>entries, but this size does better. The 750,000 entries is better still
>and
>it would be nice to know if this trend continues for 1.5M entries and
>beyond.
>
>It's interesting that the very simple two-level probe algorithm I use
>(which
>I generally call the "Belle hash algorithm" since it was first used in
>Belle
>nearly 20 years ago) works so well here. It would obviously be worse if
>I
>hashed q-search nodes. This is likely one of the things that led me to
>get
>rid of hashing capture search stuff, because performance tests were
>always
>better when I had it disabled... I eventually removed the call to
>LookUp()
>in Quiesce() and have only tried putting it back once and didn't like
>the
>result. Note that the difference between hashing and not hashing the
>q-search
>seems to be a total "wash"... ie qsearch is faster without hashing, but
>the
>tree is slightly larger. In my case it was maybe 2% faster overall
>without
>hashing so I left it out. However, in severe cases, it can be much
>better
>because it is harder to over-utilitize the hash table now than it was
>when I
>was hashing qsearch stuff. So in small memory big search cases, this is
>probably a big win.
>
>
>
>>
>>I will try the same test with the middle game position
>>later, for comparison. :)
>>
>>Best Regards,
>>Chris Carson
This page took 0 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.