OpenChess

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!

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.

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!

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.

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.

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.

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.

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 )

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.

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 )