hashtables

[flok]

Hi,

According to http://chessprogramming.wikispaces.com/ ... s%20Stored you need to store not only hash, depth and score but some other parameters well.

Apart from the "age", why would I do that? Shouldn't it work as well to when I enter a node, either look-up the hash for that node and then return the coupled score for that node (if the depth for that tt-entry is bigger than what can be reached now) or calculate the tree below it and store the hash/score(/age)?

regards

[Daniel Shawul]

The score you store is never exact except when you are searching the PV. In other places you search with null windows so you have to store in the TT whether score is exact (in PV), an upper bound, or a lower bound. Basically you are storing bounds alpha or beta most of the time, instead of the real score of a position!

Later when you check your TT for cutoffs, you compare the stored score with your current alpha-beta bounds and make cutoffs accordingly. If the stored score of a position that is a lower bound is greater than our current beta, we make a cut off because we don't really need to know how good a position is but that it is good enough to make a cutoff using the current beta. That is how alpha-beta works. Similarly if the stored score which is an upper bound is less than alpha, here again you make cut off. This is a deliberately verbose way of explaining why you need to store bounds information, but there is a three lines code in Wiki that shows how this works.

If you find this answer informative, don't forget to click the non-existent button on your left to add to my reputation

[Robert Pope]

And you need depth so you don't pull the results of a 3 ply search from hash, when you need a 6 ply search. Otherwise your search will think no threat exists, when in reality, it just never checked.

[flok]

Thanks people.

Fwiw: I gave a TT that only stores the score a try (just to see what that does). For a match 6 games (tried that two times) it always loses from the non-TT version.

[rtitle]

It's your engine, so you don't "have to" follow someone else's recipe. Make your own judgments.

There's a tradeoff: The more you store in each TT entry, the fewer of them you can have. Also it's desirable to squeeze the entries into 64 bits because then they can be read and written atomically (assuming your engine is multithreaded).

With this in mind, I do the following in my engine. (Note: I wrote this info in another thread already, but copying it here):

I manage to squeeze my TT entries into 64 bits as follows:

- The 64-bit position hash is divided into a 31-bit index (into a 2 billion TT-entry table) and 32 of the remaining 33 bits go into the TT entry itself to detect hash collisions. (Note you do not need to store the entire hash in the TT entry, only the portion not used for indexing) (eventually I'll get a machine with enough memory for a 4 billion TT-entry table, at which point I'll be using all 64 bits of the hash - 32 for the index, and the other 32 stored in the TT entries).
- The "best move" (recorded by a previous search of the same position) is encoded into an 8-bit index into the movelist. This relies on the fact that from a given position, the move generator will generate the moves in a deterministic order (i.e. it's sufficient to remember "move index idx was the best-move last time I analyzed this position"; I don't have to store the full move representation of best-move).
- The only other information I store is depth info (what depth search the existing best-move info in this TT entry is based on); this is to help decide when to replace a TT entry. I actually store 2 depths: distance from the root, and distance from the leaves, in 8 bits each. Using this info, I try to keep higher-quality TT entries in the table when deciding whether to replace, i.e. keep those based on deeper searches.
- This still leaves me 8 bits to spare in each TT entry.

The above assumes my transposition table is used for one purpose only - to remember best-move info from previous iterations of the iterative-deepening search (thus improving alpha-beta efficiency). I do not store evaluations in the TT entry; I decided it's too tricky to figure out when they're reusable (i.e. because of fail-highs and fail-lows, it's complex to figure out if a stored evaluation is actually reusable in the current context). Anyway, optimizing the alpha-beta search is far more useful than optimizing away transpositions. So I'd rather have a larger transposition table just for the former than a smaller one that serves both purposes. Also I do not use my transposition table for repetition detection; for that I simply do a backward walk through the move history back to the last irreversible move, comparing hash values to detect repetition.

As Daniel Shawul correctly pointed out in his earlier reply, one could store evals along with fail-high/fail-low information, and use this info to establish upper/bounds when you reach the same position via transposition. However, I am arguing that this is not worth it. Not every optimization you can think of is worth doing; there are trade-offs. So, I just use my hashtable for remembering best-move.

Richard Title

[jdart]

As Daniel Shawul correctly pointed out in his earlier reply, one could store evals along with fail-high/fail-low information, and use this info to establish upper/bounds when you reach the same position via transposition. However, I am arguing that this is not worth it. Not every optimization you can think of is worth doing; there are trade-offs. So, I just use my hashtable for remembering best-move.

At first I thought you were talking about static evals. But it appears you also don't store the computed eval after the search at the current node has completed. This makes no sense. Sure it is a little complex to handle fail-high/fail-low conditions. You also need some logic to handle mate scores properly. But if you do this, and you get a hash hit, in many cases you can cut off searching the whole sub-tree below the current node. That is an enormous benefit and will hugely reduce the size of the search tree. If you are only using the move info you are not getting that benefit.

Also it does not make sense to me to store the move index instead of the move. Doesn't this mean you have to call the move generator to obtain the move that is represented by the index? If you had the move itself you could skip calling the move generator. And since the hash move often causes cutoff, that means in many of your nodes no move generator would be necessary.

--Jon

[rtitle]

Right, I don't store the computed evals, just the information about what was selected as best-move when this same position was previously searched.

I am arguing that the primary benefit of the TT is to give you better move-ordering, thus improving alpha-beta efficiency. This assumes you are doing iterative-deepening search:

for (int d = 1; d < maxDepth; d++)
search(1 /* current depth */, d /*depth to search*/);

Each iteration remembers in the TT its best-move choice for each position encountered.

Within search, one is doing something like (simplified pseudo-code):

search(int currentDepth, int targetDepth, int alpha, int beta)
{
generateMoves(movelist /* ordered list by move value */);
for (Move m : movelist)
makeMove(m)
if (currentDepth < targetDepth)
eval = search(currentDepth + 1, targetDepth, beta, alpha);
else
eval = static_eval();
unMakeMove(m);
/* check if eval is best-so-far, update alpha if needed */
/* check for beta cutoff */

It is well-known that you get vastly improved alpha-beta pruning if you can search the best-move first. The remembered best-move selection from the previous time you searched the position (i.e. in the previous iteration of the iterative deepening search) is likely still the best move now. So, at move-generation time, I give that move a big boost in sort-value, ensuring it comes at the head of the movelist. My observation is that to do this, you only need to remember best-move index. I.e., in generate_moves, I have code that says "this is the Nth move I'm putting on the movelist, and the TT table said that the previous time I generated moves in this position, the Nth move was best, so I'll put this move at the head of the movelist.

By squeezing TT entries into 64 bits, I can store at least a billion of them (assuming I have at least 8G), so I can remember best-move info for all positions in about the first 15 ply of the search tree.

Thus my TT is not "useless", it is just used for a single purpose (better move ordering).

You're correct that by not storing the computed eval, I lose the benefit of detecting actual transpositions and reusing old evals. You're also correct that were I to add this info and use the TT this way, I'd want to store the actual move (not just its index) in order to not call the move generator.

It's a conscious trade-off I'm making, to have a larger TT (in terms of # of entries) but used for a narrower purpose. I'm not sure it's the right trade-off. Just saying what I do.

Rich

[jdart]

Trust me, using the hashtable to cut off nodes completely based on scores would greatly increase your search speed and overall strength, if it is done correctly.

--Jon

[Sven]

You're also correct that were I to add this info and use the TT this way, I'd want to store the actual move (not just its index) in order to not call the move generator.

No. Even with your "use TT for move ordering only" approach you need to store the best move in the TT to avoid calling the move generator. I think you can get a nice performance improvement that way.

As already mentioned, adding TT cutoffs would give another boost, of course.

Sven

[rtitle]

No. If I'm using it only for move ordering, I'm calling the move generator anyway, so storing the index is sufficient. Similarly if I were storing evals and using the stored eval for improved alpha/beta bounds, I'd be calling the move generator anyway. The only case where you can *save* a call to the move generator by storing the full move is when you can actually re-use the previously computed eval and *not* do the search (i.e. the previous eval was from a search to the appropriate depth and its fail-high/fail-low flags don't prevent you from re-using it). I don't think this is as common a scenario as you guys think.

I actually used to do it the more common way, then I switched to my "minimal TT entry" approach as an experiment. Experimentation revealed it is beneficial in some situations and detrimental in others. It's not as clear-cut as you are claiming. It depends on the position. In an endgame where there are a lot of transpositions, a TT that stores rich information is beneficial. In a complex middlegame position, it doesn't pay off that much, i.e. you don't have as many true transpositions. Also it depends how deep you're searching. In fast time controls, you probably won't fill up a billion-entry TT table anyway, so a smaller-number-of-entries/richer-entries approach is better. But for deep analysis you do want to keep billions of entries and my "minimal TT entry" approach starts to pay off.

Rich