Search Instability - precise definition/cause

[AndrewShort]

My impression of search instability is that the very act of re-searching a position can change the score to a different score than the first search, since the act of re-searching means writing to the hash table, replacing hash entries, etc., and any time you change the hash table, a different score could result. This is similar to the Heisenberg Uncertainty Principle - the very act of measuring something changes the measurement!

In an aspiration window example, suppose a search with (alpha, beta) fails high. Since we "know" that the real score is >=beta, a re-search with (beta - 1, INFINITY) should return an exact score. But because of search instability, the re-search can unexpectedly fail low.

So two questions:

(1) is my assumption of the cause and definition of search instability correct?

(2) are there other reasons for search instability? If so, are they also because of hashing, or is it possible to have an engine with no hash table still suffer from search instability?

Search instablity isn't really a big deal for me - I just widen my aspiration window to (-infinity, infinity) on re-searches (or I could step it in larger and larger increments, I suppose).

But it makes me wonder if PVS (where you hope a (alpha, alpha+1) window quickly fails low) and null-move (where you hope a (beta-1, beta) window quickly fails high), which rely on narrow windows, also suffer from search instability resulting in less efficiency than you would think.

[bob]

My impression of search instability is that the very act of re-searching a position can change the score to a different score than the first search, since the act of re-searching means writing to the hash table, replacing hash entries, etc., and any time you change the hash table, a different score could result. This is similar to the Heisenberg Uncertainty Principle - the very act of measuring something changes the measurement!

In an aspiration window example, suppose a search with (alpha, beta) fails high. Since we "know" that the real score is >=beta, a re-search with (beta - 1, INFINITY) should return an exact score. But because of search instability, the re-search can unexpectedly fail low.

So two questions:

(1) is my assumption of the cause and definition of search instability correct?

(2) are there other reasons for search instability? If so, are they also because of hashing, or is it possible to have an engine with no hash table still suffer from search instability?

Search instablity isn't really a big deal for me - I just widen my aspiration window to (-infinity, infinity) on re-searches (or I could step it in larger and larger increments, I suppose).

But it makes me wonder if PVS (where you hope a (alpha, alpha+1) window quickly fails low) and null-move (where you hope a (beta-1, beta) window quickly fails high), which rely on narrow windows, also suffer from search instability resulting in less efficiency than you would think.

Search instability comes from one place... if you can search the same node twice, and get different answers, then it will show up. How can this happen? Several ways... you prune based on alpha/beta values. If the alpha/beta values change, then you make different pruning decisions and search a different sub-tree with a different result. Another way is to have a deep-draft hash entry that says "score > 1.2" which makes you fail high. On the re-search, with a bigger beta bound, that entry can't be used, and the current search depth is not enough to see the good thing hinted at by the useless hash entry, so you originally fail high, but then can't find the reason why and fail low.

There are multiple variatons of that theme, but they all rely on an alpha/beta bound for the trigger...