Can a transposition table cause search instability

Question

I'm writing a chess engine and recently added a transposition table.

When running a few tests, I found that although the search still returned the same best move, the value of the move (how good it is for the maximizing player) fluctuated.

Is this normal behavior for a transposition table? I remember reading that a transposition table can cause search instability. Is this what that means? So is this a normal occurrence or a serious bug in my code?

Customer

Answer 1

Yes, transposition tables introduce search instability.

Fortunately, it occurs rarely enough that the advantages of transposition tables outweigh that complication by far.

1. What is the function of a transposition table?

After adding transposition tables (TT) to your program, you should notice two main differences:

1. Improve move ordering: The move from TT is generally the best possible move
2. Early cutoffs: When you reach a position again, which has been already searched with a greater distance, you can stop and use the value stored in the TT entry

In chess, the improved move ordering is the most important factor. Only in endgames, the likelihood of transposition increased, and you will see more early cutoffs.

So, what does search instability mean? It means that when you search one position with a given distance and later repeat the same search (same position, same distance), you will get the identical result.

2. Simple minimax/alpha beta search algorthm

Let us first ignore search extension and start with a simple minimax or alpha-beta search.

Note that you search will have the property that searches are repeatable, and will see no search instabilities. Even if you improve your move ordering with a move from a transposition table, you will still get the same result for every search. However, after adding TT, the extra cutoffs from a deeper search will in general break that property and introduce instabilities.

For instance, consider a position containing a deep tactic:

• A search with a low distance may not see it, but a search with a greater distance will.
• After that result is stored in the TT, a re-search with the low distance will see the tactic, too. It now behaves differently compared to the original search.
• Even worse, when the TT entry is overwritten, the improved knowledge gets lots again.

So, using extra knowledge to force early cutoffs is a factor that leads to instability. (But in practice, it is worth it, as it is more a theoretical problem.)

3. Search extensions

When applied to a simple alpha beta search, the improved move ordering itself does not lead to search instabilities. The situation is more complicated in real-world search algorithms which implement many extensions. Some of these extensions are sensitive to the move ordering, too.

One prominent example is called Late Move Reduction (LMR). It uses the fact, that the quality of move ordering is generally so high that only the first few moves have to be searched thoroughly, while the other moves are most likely bad ones and will only be searched with a reduced distance.

LMR is only one example where move ordering makes search less repeatable. But again, the advantages predominate.

4. How much search instability is normal?

There is no clear answer. In practice, you cannot eliminate instabilities completely but if the instability gets out of control, your search will become inefficient.

Of course, bugs can be the reason behind instabilities, too. So, is it a bug in your search? Well, I don't know. Could be. :-)

Oestrone

Note a better technical term for "distance" is "depth". – Aguedaaguero

So if you store separate values for each depth, and don't get overwrites, you eliminate the instabilities. – Rochester

@ThomasAhle If you never overwrite values, and only use stored results where the current distance is an exact match to the store distance, you will eliminate instabilities. Having said that, both assumptions are not practical. First, you will eventually run of out memory, and second, entries which were searched deeper are just to useful to ignore. – Bathymetry

Do you get instabilities just from deleting old entries? I think that should be fine, since you'll just re-search them and get the same value as before. But yeah, the high depth nodes are useful. You can however keep the move found for ordering. – Rochester

@ThomasAhle Oh yes, you are right. Deletion should be OK as long as you only use entries with the exact depth. Then it should produce exactly the same result. So, if you repeat a search and delete some entries that were accessed before, it should still compute the same result. And yes, you can use all entries for move ordering without compromising stability. – Bathymetry

Answer 2

Is this normal behavior for a transposition table? I remember reading that a transposition table can cause search instability. Is this what that means?

Yes.

So is this a normal occurrence or a serious bug in my code?

Jonathan Schaeffer's advice (under "Plan Of Attack"):

If you initially restrict a TT lookup to be valid only if the table depth exactly matches the depth that you need, then the TT will not change the result of a fixed-depth alpha-beta search. It should, however, reduce the number of nodes searched. Verify that this is working correctly.

Add in iterative deepening and move ordering. If you do this right, it should not change the final result of the search but, again, it should reduce the number of nodes searched.

Only when you are sure all the above is 100% working should you move on to more search enhancements and a better evaluation function.

Schutzstaffel