consistency search

Consistency search was devised by Don Beal. It is a quiescence search which generalizes the capture search often used in chess programs.

A node of a search tree is “consistent” if its evaluation (win or loss) is the same as its backed-up value after a one-ply search. Consistency search is simple: it expands nodes which are not consistent. The idea is that if a node is consistent then it is quiescent, and the evaluation function can be trusted.

Since most performance programs have evaluation functions with more values than “win” and “loss”, the definition of “consistent” needs to be extended slightly. One way is to say that a node is consistent if its backed-up value is within a “consistency threshold” of its evaluation.

references

I read about consistency search in Michael Gherrity’s thesis on SAL, where Gheritty also discusses a modification to the algorithm.

An analysis of minimax. D.F. Beal.
In M.R.B. Clarke, editor, Advances in Computer Chess 2, pp103-109. Edinburgh University Press, Edinburgh, 1980.

Recent progress in understanding minimax search, D.F. Beal.
In Proceedings of the ACM Annual Conference, pp164-169, New York, 1983. Association for Computing Machinery.

my opinion

I haven’t tried it, but it sounds like a good idea to me. It’s simple and general. There may be some risk of the consistency search failing to find consistent nodes and getting out of hand; if that happened to me, I’d try giving deeper nodes a looser consistency threshold. I don’t know whether Gheritty’s modification is sensible or not.

another item by Don Beal

Don Beal also invented the null-move algorithm now widely used by chess programs. He called it a generalized quiescence search algorithm, but it’s not anything like that. It is good for chess and some other games, but not most games, so it’s not generalized. And it’s not a quiescence search either. Still an important paper, though!

A generalised quiescence search algorithm, D.F. Beal.