Author: Christophe Theron
Date: 06:35:31 11/22/03
Go up one level in this thread
On November 21, 2003 at 23:05:38, K. Burcham wrote:
>
>Chris, thank you for information. This clears up some of my thoughts.
>
>a follow up question.
>
>"It is possible that this advice would not work for another chess program, for
>example one that "clears" its hash table before it starts thinking. In this
>case, clearing 1Gb of hash table when playing bullet games would lead the
>program to use almost all its time for "clearing the hash table".
>
>this is what I understand from your information.
>if we are in a tournament with Tiger and permanent brain is on, then we can say
>that with x amount of hash, if we use more than this then Tiger will have hash
>collisions.
Due to the way hashing works, you can get a hash table collision in the very
first second of the search.
Actually the second position you search might very well end up in the same hash
slot as the first (because the hashed value of the second board position gives
the same number as the first one), so it is possible to get a collision at the
second position searched even if you have a 1Gb table.
So collisions happen all the time. You cannot say that above a given time with
some amount of hash table you will start having collisions.
You get collisions all the time, even in the first hundreds of second of the
search.
Naturally after a long search you get more of them than in the first second.
But I want to stress out that this is not an all black or all white problem.
This is why I don't like the term "full" when talking about the hash table
state. Implying that the hash table might get full at some point gives you a
very misleading idea of how it works. It is never full because at any time it is
still possible to add data into it. Adding data might erase older data, but it
is possible that the older data would not have been be used anymore.
The hash tables allow a program to have a lower "branching factor". If you
select a hash table size that is too low, what you will see is that the
branching factors of the first iterations are going to be good. Then at some
point they will start to degrade a little bit. Eventually the branching factor
of the next iterations will stabilize to a higher value (=less performance).
It is not possible to say exactly when the hash table is "full", so let's forget
about this concept. However it is possible to notice the degradation in
performance and deduce that the program would benefit from a bigger hash table.
As I said in my previous message, every program will differ in behaviour on this
matter. The only thing you can do is ask the programmer for advice, or better,
measure the performance degradation by yourself for the time controls you intent
to use and empirically try to find the smallest hash table size that will
provide better performance.
>If we are in a tournament with another program why would it ever clear its hash
>during the game? it would seem this would be valuable information for the
>search.
I think Russel has answered your question.
Christophe
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.