How to manage the size of your hash in UCI

Code, algorithms, languages, construction...

How to manage the size of your hash in UCI

Postby Pepperfudge » Mon Nov 07, 2016 8:29 pm

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!
Pepperfudge
 
Posts: 5
Joined: Mon Nov 07, 2016 8:11 pm

Re: How to manage the size of your hash in UCI

Postby hyatt » Tue Nov 08, 2016 5:07 am

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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: How to manage the size of your hash in UCI

Postby Pepperfudge » Tue Nov 08, 2016 7:01 pm

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!
Pepperfudge
 
Posts: 5
Joined: Mon Nov 07, 2016 8:11 pm

Re: How to manage the size of your hash in UCI

Postby hyatt » Wed Nov 09, 2016 12:11 am

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.
hyatt
 
Posts: 1242
Joined: Thu Jun 10, 2010 2:13 am
Location: University of Alabama at Birmingham

Re: How to manage the size of your hash in UCI

Postby Pepperfudge » Wed Nov 09, 2016 1:27 am

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.
Pepperfudge
 
Posts: 5
Joined: Mon Nov 07, 2016 8:11 pm

Re: How to manage the size of your hash in UCI

Postby H.G.Muller » Wed Nov 09, 2016 8:57 pm

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.
H.G.Muller
 
Posts: 176
Joined: Sun Jul 14, 2013 10:00 am

Re: How to manage the size of your hash in UCI

Postby Pepperfudge » Thu Nov 10, 2016 4:44 am

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.
Pepperfudge
 
Posts: 5
Joined: Mon Nov 07, 2016 8:11 pm

Re: How to manage the size of your hash in UCI

Postby sandermvdb » Wed Nov 16, 2016 1:52 pm

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 :) )
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm

Re: How to manage the size of your hash in UCI

Postby Pepperfudge » Thu Nov 17, 2016 7:39 pm

Cool sandermvdb! We should be friends :D

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.
Pepperfudge
 
Posts: 5
Joined: Mon Nov 07, 2016 8:11 pm

Re: How to manage the size of your hash in UCI

Postby sandermvdb » Fri Nov 18, 2016 11:16 am

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 :) )
sandermvdb
 
Posts: 24
Joined: Wed Jun 01, 2016 3:52 pm


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: CarstenL, Google [Bot] and 2 guests