Add a ttable

A "transposition table" or "ttable" is a data structure that remembers the values of states. When a remembered state is found again—because two chains of moves give the same state—the value is taken from the ttable rather than re-searching with negamax. Like alpha-beta, this pruning can make for a huge speedup.

The ttable remembers the depth to which the search that produced the value of each state was done. If more depth is needed when the state is hit again, you may need to re-search. In this case, the transposition table is still helpful in sorting moves for alpha-beta. Even though the value may be a bit off because the search was a bit too shallow, it will still be a big win over using just the state score in the sort.

There is never enough memory to remember the values of all the states. It turns out that it works quite well just to replace a random state in the ttable when adding a new state. This makes older states more likely to be replaced (they get many chances) as well as states near the bottom of the tree that would be cheap to re-search (there are many of them). Random replacement is done by hashing the state and replacing the array entry at the hash.

Define a TTable class with a field that is an array of TTableEntry. The TTableEntry class should have a long (64-bit) hash member, int members a, b, and value, and a Boolean valid member. The TTable constructor should initialize all the valid members to false. The size of the entry array is hard to pick. Make it large, but not so large that the machine thrashes. Make it a power of two, so that the next step will work.

Add a method to TTable that returns the TTableEntry with the given hash, or null if there is no valid entry with this hash. This can be done by simply masking off however many bits of the hash you need and using it as an array index. Also add a method to save a TTableEntry with a given hash.

Now you are ready to start using the ttable. There are a few steps.

Once you have the ttable implemented, you should update the move ordering to look for a better value in the ttable. This can really improve the chances of early alpha-beta cutoff.