What causes search instabilty?

[Ross Boyd]

Hi all,
I thought it would be interesting to compile a list of all the known causes of search instability. I'm sure there are many, but maybe there are some that are lesser known, more subtle and therefore more evil....

Here is a starting list...

1. Hash Table inconsistencies.

An important hash entry gets overwritten during search... subsequent searches can't use the information.

2. You extend a move during shallow searches and then don't extend it during deeper searches. This happens typically when you do stuff like...

Code: Select all

if (remaining_search_depth < THREE_PLY && IsReCapture(move))
   extensions += RECAPTURE_EXTENSION;


3. TT/hashkey doesn't take into account 50 move rule. No real workaround for this... but its rare...

4. Hard Evaluation Edges... ie. sudden changes in evaluation when changing game phases. Usually crappy code like this causes it...

Code: Select all

if (value_of_enemy_pieces_remaining > VAL_Q+VAL_N)
    score += KingSafety();
else
    score += KingInEndgame();


I'm sure there are many, many more....

Would anyone like to add their favourites to the above list? Please do!

Cheers,

Ross

[Anonymous]

Here is a starting list...

2. You extend a move during shallow searches and then don't extend it during deeper searches. This happens typically when you do stuff like...

Code: Select all

if (remaining_search_depth < THREE_PLY && IsReCapture(move))
   extensions += RECAPTURE_EXTENSION;


I am not totally sure, how you define search instability. I am thinking of, search at depth n with a small window, get a fail high, research with a higher upper bound, and get a smaller score back than before. Or even a fail low. Also similar cases when a move at the root fails low. At the moment, I cannot see, how the above 2. can cause this search instability.

4. Hard Evaluation Edges... ie. sudden changes in evaluation when changing game phases. Usually crappy code like this causes it...

Code: Select all

if (value_of_enemy_pieces_remaining > VAL_Q+VAL_N)
    score += KingSafety();
else
    score += KingInEndgame();


Neither here. The sort of instabilities I described will often be caused by window dependent pruning/extensions.

Code: Select all

  if (alpha < -300)
    /* extend/prune */


One typical example of window dependent pruning is in qsearch, where many engines will have some code: if ((current material + material gain of this capture move + safety margin) < alpha) /* Futile to try this move */

Now assume you have something like KNNP vs K and you are the lone K, that just captures that pawn. Perhaps your alpha is -10 (you are searching for a draw). current material is -700, K captures P is material gain of +100. So above snippet will prune away K capture P when safety margin is smaller than ~600 (which it will be in any program, I guess). Now you did not find any way to draw. You fail low at the root, and research with an uppen lower bound. You get to that node again. Now alpha is -infinity. You will try the move, and eval in the recursive call of qsearch will return zero. It can give you a fail high followed by a fail low at the same depth.

Another thing worth to mention - very related to the HT point you had given: path dependent extensions (which for example recapture is). Typically your transition table entry was reached on a different path than the same position you are looking up now. This means, that you will often use a different set of extensions for the moves, even when the stored draft is exactly the same as the current remaining depth. This can yield in a different score from actual search without HT. At a possible later research time, that hash entry might be gone.

I can think of other more subtle points. When you handle some situation that you specifically remember somewhat different. THis could be by some flags in HTs, or perhaps you store the old PV, and search this first, while handling it slightly different than other paths.

Regards,
Dieter

[Ross Boyd]

Hi Dieter,

I am not totally sure, how you define search instability. I am thinking of, search at depth n with a small window, get a fail high, research with a higher upper bound, and get a smaller score back than before. Or even a fail low. Also similar cases when a move at the root fails low. At the moment, I cannot see, how the above 2. can cause this search instability.

Yes, I didn't define search stability at all. I should have.

There is the strict scientific definition which you describe where a fail high is followed by a fail low (or visa versa).

For the purpose of discussion I'm thinking of it in a broader sense, where the search not only returns unreliable/inconsistent scores, but where it gets bogged down, fails to find correct moves, or changes its mind over and over.

Perhaps the topic should be rephrased as 'What causes search 'blues'?

One typical example of window dependent pruning is in qsearch, where many engines will have some code: if ((current material + material gain of this capture move + safety margin) < alpha) /* Futile to try this move */

Now assume you have something like KNNP vs K and you are the lone K, that just captures that pawn. Perhaps your alpha is -10 (you are searching for a draw). current material is -700, K captures P is material gain of +100. So above snippet will prune away K capture P when safety margin is smaller than ~600 (which it will be in any program, I guess). Now you did not find any way to draw. You fail low at the root, and research with an uppen lower bound. You get to that node again. Now alpha is -infinity. You will try the move, and eval in the recursive call of qsearch will return zero. It can give you a fail high followed by a fail low at the same depth.

That's an excellent example!
So, delta pruning can be very dangerous without safeguards.
Its probably the reason why my engine is slow to solve this old Pierre Nolot position even with EGTBs...

FEN: 8/4N3/6p1/4n2p/7P/5kPK/8/8 b - - 0 1
Best Move is ... Ng4

[diag]8/4N3/6p1/4n2p/7P/5kPK/8/8 b - - 0 1 [/diag]


Would you agree that lazy eval can introduce similar effects, if it fails to detect a heavy score swing... like your example above?

Another thing worth to mention - very related to the HT point you had given: path dependent extensions (which for example recapture is). Typically your transition table entry was reached on a different path than the same position you are looking up now. This means, that you will often use a different set of extensions for the moves, even when the stored draft is exactly the same as the current remaining depth. This can yield in a different score from actual search without HT. At a possible later research time, that hash entry might be gone.

This is what I'm finding recently. Extensions/Reductions must be applied consistently throughout the search... if you extend a node differently to when previously visited, you get hash entries overwritten that shouldn't be... which leads to partial blindness in some lines... These kind of things are not search instability as such... but it makes the engine less 'sharp'.

Well Dieter, your delta pruning example was something I was yet to discover. Thanks for sharing that one. Much appreciated!!

Cheers,
Ross

[David Weller]

If I am understanding this correctly,

Basing any prunning[eg, Null-move] or extensions on bounds introduces search innconsistencies, all due to hashing

To me, SI is like a gasoline engine who's timming is off, or has water in the gasoline, or whose fuel mixture is way too lean or rich

It causes the engine to run 'rough' and prevents it from getting optimal 'RPM''s

IMHO

[Anonymous]

>Basing any prunning[eg, Null-move] or extensions on bounds introduces
>search innconsistencies,

Yes

>all due to hashing

No. Assume null move search without hashing. You search with some window, say beta = 0, and get a null move cutoff, because the recursive search returns >= 0. For some reason (fail high/low at the root for example) you have to visit this node again. Now with say beta = 100. null move search does not give a cutoff anymore. YOu do a normal search and get score = -50. Oops - it means that the first null move fail high was actually wrong, it shouldn't have failed high. You end with inconsistent results. Actually I think no HTs are needed at all to get inconsistencies when having any kind of window dependent pruning/extensions.

Cheers.
Dieter

[Anonymous]

>Would you agree that lazy eval can introduce similar effects, if it fails to
>detect a heavy score swing... like your example above?

Yes. I am very careful in Yace (which uses lazy eval and the "delta pruning") with this. For example capturing the last pawn is typically excluded from pruning. Similar in lazy eval, positions where one side has no pawns/pieces are handled carefully.

>This is what I'm finding recently. Extensions/Reductions must be applied
>consistently throughout the search...

It does not help in my example. Even when you do them consistently. You can reach the same position once with a capture (which now can trigger recapture extensions) and once with a silent move (and no recapture extensions now, of course). Transposition table cutoffs have no chance to handle this consistently.

Cheers,
Dieter

[David Weller]

Dieter,

Yes, thanks for clearing that up.

[Daniel Shawul]

you can find lots of things that cause instability
in bruce's page. i stopped worrying about it.
daniel