Is a Lazy Eval a Good Thing?
Lazy evaluation is a technique often used to save time when evaluating chess position. If a position’s true score is much higher than beta or lower than alpha the full evaluation is really unnecessary. For example, if you’re a queen down it’s a waste of time checking to see if you have a weak double pawn on a4. So in the right situation this approach can save a lot of time and speed up an engine. Of course there is the risk that the lazy evaluation is way-off and the position is incorrectly evaluated. The technique was quite popular in the 80’s (and probably the 90’s). Ed Shoeder noted it gave him an enormous speed increase in Rebel.
I’ve been giving the issue some thought and I’ve come to the conclusion I will not add a lazy evaluation in Maverick. My reason is simple – I’d like the leaf nodes to be evaluated as accurately as possible. My hunch is that by evaluating the leaf nodes as accurately as possible I’ll be able to be more selective in positions closer to the root (which will dramatically reduce the tree size). This type of decision is part of the design philosophy of Maverick.
I also suspect the lazy evaluation technique is less relevant in modern programs which use null move and late-move-reduction. Back in the 80’s there was still a battle between the Spracklen’s brute force approach and Lang’s selective search. In those days it was common to only evaluate at the leaf nodes (i.e. not evaluate the interior nodes). In this situation the leaf nodes evaluation could have a wide range of values, some much higher than beta and others much lower than alpha. So lazy evaluation worked well. In contrast null move and late-move-reduction have the effect of keeping the search tree closer to alpha and beta. Null move reductions are good at quickly weeding out obvious fail high moves (i.e. very good positions) and late-move-reductions reduce the tree size for obvious fail low positions (i.e. very bad position). So by utilizing these techniques lazy evaluation becomes less relevant and more risky.
Of course this is just theory – let’s see how it works in practice.
What are your thoughts on Lazy Evaluation?