transposition table implementation help

[lazyguy123]

I have a basic search using alpha beta (negamax). I want to implement a transposition table, but I'm not sure if I am doing it correctly. Here's what I have in mind:


At the root:
- Store the depth, score, node type (PV), and best move
- When generating moves, look for the entry in the table
.....-if found and (entry depth) = (depth - 1), retrieve the move and make it first

At the leaves:
- When evaluating, look for the entry in the table
.....-If found and (entry depth) = 0, return the score from the table
.....-If not found, calculate the score and return the score
........-Store the depth(0), score, and node type (PV) in the table

At the interior nodes:
- When evaluating, look for entry in the table
....-If found and (entry depth) >= depth
........-If it is a PV node, return the score from the table
........-If it is a CUT node, return score from the table if it is greater than current beta

- When generating moves, look for entry in the table
....-If found and (entry depth) = (depth -1)
........-If it is a PV node or a CUT node, make that move first

- When storing the entry in the table
....-If alpha was raised but no beta cutoff, store the depth, score that raised alpha, node type (PV), and best move
....-If beta cutoff occurred, store the depth, score that exceeded beta, node type (CUT), and refutation move


Is the stuff above correct?

If no move exceeds alpha, should I still keep tract of the score of the best move and store it as an ALL-node? (so that when evaluating interior nodes, I can see if the table score is less than the current alpha, and if so return the score stored in the table)

Any help is appreciated. Thanks in advance.

[hyatt]

Think of the trans/ref table like this: It's purpose is two-fold. (1) to avoid searching the same position over and over and wasting the effort; (2) to provide a good move (when available) to increase search efficiency.

When you do a search, at any ply you reach, the first step is to do a hash probe to see if you have searched this position to a depth that would let you use that result here and not search at all. If so, then you deal with the technical issue of what to do here. If the ttable entry says this is a "lower bound" that means you failed high when you searched this position and stored the result. And you have a score that represents the worst-possible score you would expect, knowing that the real score is probably even higher. If this lower bound is >= current beta value in search, you just "fail high" here and return with no searching. Otherwise you continue below. If the ttable entry says this is an "upper bound" that means you failed low when you searched this position and stored the result. And you have a score that represents the best-possible score you would expect, again knowing that the real score is probably even lower. If this upper bound <= current alpha, you just "fail low" here and you are done. In rare cases, you will get an EXACT type of entry that says this is a true score, not a bound. If that true score is < alpha, you fail low. If it is > beta, you fail high, otherwise you just return this true score as if you had done a real search.

If you fall through the above, two of the three cases give you a best move to try, at least. A fail high (lower bound) position gives the move that failed high or was best the last time you searched this position, an exact score gives you the best move you found. The depth for these was not enough to trust the results, but you can certainly trust the best move.

If you keep that simple explanation firmly in mind, it is hard to screw up the hash table stuff so long as you don't screw up the hash signatures so that you get false matches and such.

[lazyguy123]

Thanks for your reply.

Is it worth probing the hash table at the leaf nodes to see if you can find a score? (I haven't implemented move ordering or probing the hash table at interior nodes yet).

Right now I have a very basic evaluation function (just material and PSQ), and it takes almost no time at all.

Without the hash table probing at the leaves, the evaluation method is called 77,000,000 times when I search to depth 7 from the starting position, and it takes 16 seconds. With the hash table probing at the leaves, the evaluation method is only called 22,000,000 times when I evaluate to depth 7, but it takes 23 seconds. When I profiled, I see that the probing takes a lot of time, but I hardly save any time on the evaluation. When I improve on the evaluation, will the time savings be worth it?

Thanks.

[hyatt]

Probing in the q-search is an interesting question that you have to test. In Crafty, I do not. I found that probing in the q-search reduced the size of the tree (nodes searched) by about 10%. But I also found that it slowed the search down by about 10%. Which is a wash. I decided to not probe in the q-search, because this reduces the "stress" on the hash table (probes done) by 90% or so (most nodes searched are in the q-search). This means that you can either use a smaller hash table which reduces TLB thrashing and makes memory accesses a bit faster, or you can survive when running on a machine with less than the usual amount of memory, because you can survive with a smaller hash table where a q-search prober will begin to have trouble due to replacement issues.

I have this on my "to do" list to test again, since our trees have gotten quite a bit deeper and narrower and the answer might well be different today. Hence my mantra "test when you don't know, and even if you think you do..."

[BB+]

With memory access, there is also an issue of how you test, especially with parallel code. I would not be surprised if the memory management subsystem (waiting for cache misses) was a nontrivial time component of a SMP search with many cores nowadays. I would not hazard a guess as to what "many" means though (probably one 8-core Xeon is OK, with two of them you are already conflating with a possible NUMA factor).

If you want to compare hash-access rates as in the given qsearch case, you probably need to be careful even in the 1-core case that you don't have N threads on the same box all contending for memory.