Page 1 of 1
How to manage the size of your hash in UCI
Posted: Mon Nov 07, 2016 8:29 pm
by Pepperfudge
Hi! I've just started working on a chess engine, and I'm trying to add a hash table.
I don't know how to make sure the hash table doesn't get too big. I know you can set the hash size, and you're also supposed to send information about how full the hash is.
But I don't know how to tell how full the hash is. I'm writing the engine in Java. Is there some feature of Java to see how much memory you have left? Or do you just manually keep track of the size, based on how many entries there are and how much space they take up?
Thanks!
Re: How to manage the size of your hash in UCI
Posted: Tue Nov 08, 2016 5:07 am
by hyatt
if you store some recognizable value in each entry (such as using the common "age" field) then you can look at all entries at the end of the search and look at the age value to see which entries were just written this search and which were left over from last search (and which were therefore not used). Percent used simply becomes 100 * # written this search / total entries.
Re: How to manage the size of your hash in UCI
Posted: Tue Nov 08, 2016 7:01 pm
by Pepperfudge
Thanks hyatt! Just a few followup questions.
So I thought the hashfull indicated how much of your designated memory for the hash was used up, but it's actually the percentage of the hash that is being used in this search?
Also how do you avoid getting an out of memory error? I figure you have to delete entries from the hash every so often but I don't know how to know when you're about to run out of memory.
Thanks again!
Re: How to manage the size of your hash in UCI
Posted: Wed Nov 09, 2016 12:11 am
by hyatt
A hash table doesn't grow as you add entries. You just pick one, using some sort of hashing function, which selects a specific entry that you are going to write to. you can probably get to 100% utilization but it is very difficult. But 99+% utilization is quite common. With hashing, you are never adding something new and growing the table, you are always overwriting something that is already there, whether it is worthwhile or not.
Re: How to manage the size of your hash in UCI
Posted: Wed Nov 09, 2016 1:27 am
by Pepperfudge
So I'm using a Hashtable from Java which says "Note that the hash table is open: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially" which means that the hash can grow as more entries are added. Do you recommend using a hash of fixed size? I'm not sure if it exists in Java.
Re: How to manage the size of your hash in UCI
Posted: Wed Nov 09, 2016 8:57 pm
by H.G.Muller
I don't know Java, but it seems a bad idea to use a pre-cooked language feature for this. It will almost certainly not do what is needed. Hash tables as used in Chess engines are 'lossy'. They have to be, because engines search so fast that they would fill all available memory in just a few seconds, while games, or even single moves, take minutes. So when the memory has filled up you have the choice between stopping adding new entries to it (which would be crippling, as the recent entries are the most relevant and most useful), using disk storage (even more crippling, as it slows down the engine by a factor 1000 or so), or overwrite the least useful etries stored before. So people do the latter. To decide what is least useful requires knowledge that a general-purpose compiler could never have.
So just use a fixed-size array, and some algorithm for a replacement scheme to decide which entry to overwrite, as during 99% of the game the array will be completely filled.
Re: How to manage the size of your hash in UCI
Posted: Thu Nov 10, 2016 4:44 am
by Pepperfudge
Thanks H.G.Muller! That makes a lot of sense. It did seem really tough to decide which entries to delete.
OK I'll use a "lossy" hash.
Re: How to manage the size of your hash in UCI
Posted: Wed Nov 16, 2016 1:52 pm
by sandermvdb
To keep track of the usage of the TT, I am using a counter which is updated when an entry is added: if(currentHashValue==0) counter++;
If I need the usage statistics, I use this counter and the total number of elements in the array.
(btw, I am currently also working on a chessengine in Java
![Smile :)](./images/smilies/icon_e_smile.gif)
)
Re: How to manage the size of your hash in UCI
Posted: Thu Nov 17, 2016 7:39 pm
by Pepperfudge
Cool sandermvdb! We should be friends
Do you (or anyone else) know how much memory you have in total for your program? Like Arena tells me I have 128MB hash size, but do I have additional memory for the rest of the program?
I calculated how much space my TranspositionTable takes up, and the rest of the memory used shouldn't be too significant, but I just want to be accurate.
Re: How to manage the size of your hash in UCI
Posted: Fri Nov 18, 2016 11:16 am
by sandermvdb
If you want accurate results about the memory usage, you should use VisualVM which is in the bin folder of the JDK.
This tool is also very useful for profiling.
You could also install the plugin VisualGC to see the garbage collection activity which should be minimal for optimal performance (new = evil
![Smile :)](./images/smilies/icon_e_smile.gif)
)