Null Move in Quiescent search

[hgm]

After some more thinking I started to realize that the whole tree model used by Beal is pathologic. The fraction of lost positions (side-to-move point of view) k is in equilibrium if it obeys (1-k)^b = k. But it is not a stable equilibrium! If you work your way down from the leaves with the recursion

k_(d+1) = (1 - k_d)^b = F(k_d)

where k_d is the fraction of lost positions at remaining depth d, it diverges away from the equilibrium, because dF/dk < -1 at the equilibrium point K:

F'(K) = -b*(1-K)^(b-1) = -b*F(K)/(1-K) = -b*K/(1-K)

Now b = ln(K)/ln(1-K), so F'(K) = -K*ln(K)/((1-K)*ln(1-K)), which is < -1 for 0 < K < 1/2 due to the assymmetry of x*ln(x), which starts steeper at x=0 and reaches its maximum at x = 1/e. So only for b=1, where K = 0.5, you would reach the stability margin.

Now the factor b*K/(1-K) happens to be exactly the same factor as which the errors blow up per level of minimaxing. So I think this just reflects the general instability of the tree. The slightest deviation from the equilibrium fraction of k at the leaves would exponentially amplify towards the root, and jump around (chaotically?) when it gets of order 1. Starting with random result assignment at the leaves is just not a viable prescription for generating a homogeneous tree.

[D Sceviour]

Why minimax search works so well in chess like games remains somewhat of a mystery (not solved in this thesis AFAICS).

I don't think it is that much of a mystery. The thesis uses a tree model where the probability that a node is a win or a loss is independent for all nodes. This leads to a rather high fraction of singular moves. E.g. to have 1 out of every 16 nodes a loss for the side to move requires a branching ratio b = ln(1/16)/ln(15/16) = 43 (which is reasonable for Chess). But the fraction of won positions where the winning move is singular is b*(1/15)^2 = 19%.

In Chess singular moves are much rarer than that. One factor contributing to this is that the the probability that a node is a win is not independent. The game-theoretical result of especially sibbling nodes will be highly correlated. Many positions are quiet, and most moves then won't affect the result much, so that many of the daughter nodes will inherit the result from the parent.

I agree. My empirical estimate is singularity occurs less than 2%. I wish I could contribute further but it has been too long since I calculated stability functions.

[Michel]

After some more thinking I started to realize that the whole tree model used by Beal is pathologic. The fraction of lost positions (side-to-move point of view) k is in equilibrium if it obeys (1-k)^b = k. But it is not a stable equilibrium! If you work your way down from the leaves with the recursion

k_(d+1) = (1 - k_d)^b = F(k_d)

where k_d is the fraction of lost positions at remaining depth d, it diverges away from the equilibrium, because dF/dk < -1 at the equilibrium point K:

F'(K) = -b*(1-K)^(b-1) = -b*F(K)/(1-K) = -b*K/(1-K)

Now b = ln(K)/ln(1-K), so F'(K) = -K*ln(K)/((1-K)*ln(1-K)), which is < -1 for 0 < K < 1/2 due to the assymmetry of x*ln(x), which starts steeper at x=0 and reaches its maximum at x = 1/e. So only for b=1, where K = 0.5, you would reach the stability margin.

Now the factor b*K/(1-K) happens to be exactly the same factor as which the errors blow up per level of minimaxing. So I think this just reflects the general instability of the tree. The slightest deviation from the equilibrium fraction of k at the leaves would exponentially amplify towards the root, and jump around (chaotically?) when it gets of order 1. Starting with random result assignment at the leaves is just not a viable prescription for generating a homogeneous tree.

Yes I have seen computations like that before. If you generate a tree by assigning a certain win probability to leaf nodes then in the limit (preserving parity of depth) the root position is either always won or always lost depending on a certain threshold.

Generating from the root appears to give more natural results. But theoretically it seems a bit weird.

[hgm]

To me it is generating random outcomes at the leaves that seems wierd. Like all preceding moves did not have any effect on the outcome at all. You play a number of moves, and at the end you flip a coin to determine the outcome, and the probability does depend in no way on what you played. The moves only serve to alter your luck. What kind of game is that?

As to the binomial distribution:
If you suppose all sibbling nodes are equivalent, i.e. that the frequency of ++-++ is equal to that of -++++, +-+++ etc., then a binomial distribution fixes the frequency of any individual outcome in a way to make them independent. Only if you assume non-equivalence you could still get a binomial outcome with dependent win probabilities. E.g. that a + implies all its 'older' sibblings must also be +.

[Michel]

To me it is generating random outcomes at the leaves that seems wierd. Like all preceding moves did not have any effect on the outcome at all. You play a number of moves, and at the end you flip a coin to determine the outcome, and the probability does depend in no way on what you played. The moves only serve to alter your luck. What kind of game is that?

I agree that the leaf outcomes should not be independent. But ultimately the value at the root is determined by the value at the leaves, not the other way round.

Of course this has the effect that the leaf values depend conditionally on the root value (in a probabilistic sense). This is why generating from the root may make sense.

As to the binomial distribution:
If you suppose all sibbling nodes are equivalent, i.e. that the frequency of ++-++ is equal to that of -++++, +-+++ etc., then a binomial distribution fixes the frequency of any individual outcome in a way to make them independent. Only if you assume non-equivalence you could still get a binomial outcome with dependent win probabilities. E.g. that a + implies all its 'older' sibblings must also be +.

Your model did not include such an ordering!

Concerning the model: it seems to yield the counter intuitive conclusion that in tactical situations (lots of singular moves) one should not search at all (actually depth 1 to get a move) and in quiet positions one should search as deeply possible.

One can probably fix this by including hard wins/losses (E=0). I recall reading an article once which showed that enough hard scores also have a negative effect on pathology (this is intuitively clear, if all scores are hard then there is no pathology).

[hgm]

In Chess we do quiescence search to get out of the tactical situation. If the tactical situation could continue forever this would not be possible. In that case it might indeed be more accurate to use a good statical eval than to do a QS. Some Shogi programs, for example, use 'super SOMA', a sort of global SEE.

Your model did not include such an ordering!

Indeed, I tacitly assumed sibblings would be equivalent. This is why I associated a binomial distribution with independence.

[Michel]

In Chess we do quiescence search to get out of the tactical situation.

There are many other types of tactical situations (like a king attack) which are not covered by QS search. But perhaps such situations do not last long enough to lead to pathology. I.e. they are ultimately overcome by deeper search.

[hgm]

Indeed, it is all a matter of statistics. Singular moves do occur in Chess, and they might even cluster in some areas of the game tree. But the frequency with which they occur is low. And most of them are recaptures, and these cannot go on forever.

Mini-Shogi, however, is quite another matter. It is basically a perpetual King attack. Virtually all moves are captures or drops that threaten to make a favorable capture (or check). 10-20 singular moves in a row is not uncommon, in the PV. (Although my definition of singular is a bit relaxed: I analyze by evaluation, and define a move as singular if there is no other move within a +/- 100cP window from it.)

[Michel]

If you want every node to have b children, and the probability that a won node has n = 1, ..., b lost children equal to f_n, the fraction of errors remaining after two levels of minimaxing is b*(f_1*E + f_2*E*E + ... + f_b*N^b), if E is the original error rate << 1. In the limit of low error rate this becomes pathological when b*f_1 > 1. When f_1=0 it would even be quadratically convergent.

This last conclusion seems to be an artifact of the assumption that errors in sibling nodes are independent (note: I am not talking about the true values of positions, but about the errors made in evaluating them).

It is not clear to me how realistic this assumption is.

[hgm]

True. It is clear that modeling a tree can be done in many ways, and that real games are unlikely to have a tree that can be described by a simplistic model. Both considering the normal statistics, and the probability of errors.