RAM use for computer chess engine

April 25, 2016 1:22 PM

A chess program I have allows users to build and customize their own engine, which is like the brain the computer uses when playing. Every time I open the engine to work on it, a box pops up that says "Hash Tables" on the top, then "1026 MB free memory" below it, then below that there's a box with a blank space for me to type in how many megabytes I want to use. Could someone please explain to me what "hash tables" are, and what effect(s), if any, allocating more or less free MB's to the engine will have?
posted by BadgerDoctor to Sports, Hobbies, & Recreation (3 answers total)

A hash table is a data structure that lets you store a bunch of {key, value} pairs, and look up a value very efficiently if you know the key. It works using a "hash function" that can turn any key into a number, such that 1) a given key always has the same number and 2) different keys _almost_ always have different numbers. (The numbers are then used as indices into an array which stores the values. If you have a "hash collision" -- where two distinct keys yield the same result from the hash function -- then you have to have a plan for how to deal with that.)

So, for example, you might make a hash table where the keys are chess board positions and the values are the best next move from that position. (That's a simplistic example, but it's useful because it illustrates that you can have keys and values that are more complex than just numbers or strings.)

Without knowing more about how your chess program works internally, it's impossible to say for sure how the hash table size impacts play. However, my educated guess would be that larger hash tables make the computer a stronger player (or, equivalently, let it choose moves more quickly for a given strength of play).
posted by sourcequench at 1:47 PM on April 25, 2016

Many storage types get slower to access as they get more and more items in them. With a hash table, you do have to compute the hash of the input, but from there it doesn't matter how much other stuff is in the table - it's basically instantaneous to look up your value, if it doesn't share a slot with other values. If your hash table's capacity is a lot more than the number of items you're actually storing, then collisions are rare, and don't affect performance much. But if collisions are common, performance gets bad.

I don't know what's being stored here in this context, but generally a bigger hash table will perform the same or better than a smaller one, unless you need that memory for something else.

If the amount of computation an engine gets to do is limited by a timer, then a hash table that's too small might reduce the a depth of analysis. Otherwise it'll just make it take longer to do the same thing.
posted by aubilenon at 1:58 PM on April 25, 2016

Best answer: The hash table in a chess engine is used to store and look up evaluations of positions so that it doesn't have to recompute them. This is supremely useful because the same position can be reached by different sequences of moves, and work that the engine does while analyzing possible opponent moves (and all of the possibilities that follow those moves) can be reused when the opponent makes one of those moves. As a result, the hash table is immensely important, and you should make it as big as you reasonably can. When someone asks what sort of computer they should get to run a chess engine on, I always tell them to get lots of RAM (and use it) for exactly this reason.
posted by dfan at 2:15 PM on April 25, 2016 [7 favorites]