Null Move in Quiescent search

[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.

[Michel]

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.

True but the point I would like to make is a little different.

People have been trying to construct statistically correct evaluation functions for chess with somewhat mixed success. The intrinsic value of a statistically correct evaluation function is slightly dubious since for minimax only the ordering of the evaluation values matters, not the evaluation itself.

But what your simple model seems to show is that besides singular moves, correlations between node evaluations is a second factor limiting the effectivity of minimax. In other words a good static evaluation function should satisfy a kind of second order statistical correctness. The evaluation errors should be independently distributed even in closely related nodes. Probably this is the mathematical interpretation of a "well rounded" evaluation function.

Concretely: if an evaluation function misses a passed pawns term, it will only to a limited extent be possible to overcome this by search. Note that it is perfectly possible for an evaluation function without a passed pawn term to be statistically correct.

It could be that the evaluation functions of today's top engines such as Komodo and Stockfish are so good that they do satisfy this second order statistical correctness.