Lazy eval

[lkaufman]

For some unknown reason, lazy eval doesn't work for us in Komodo, although we've tried several implementations. It fails to give any meaningful speedup and of course it costs elo points. I believe most other strong programs (perhaps only except Stockfish) use it. For example it gives about a 10% speedup in Critter; not for free of course but the tradeoff is clearly favorable.
So my question is what is the experience of others with it? How much speedup do you get in actual play if you use it (average time for N ply search)? Are there variants or implementation details that make the difference between whether it works or not? For those programs which have tried and rejected it, to what do you attribute this? Why does it work in Critter, Rybka, ... but not in Stockfish?

[mcostalba]

You are really a kind of black hole: anything goes in but nothing goes out. Don it is more fair I have to say at least sometimes he also _gives_ some idea instead of just keep asking for them.

[lkaufman]

You are really a kind of black hole: anything goes in but nothing goes out. Don it is more fair I have to say at least sometimes he also _gives_ some idea instead of just keep asking for them.

As we are a team, it hardly matters which of us gives out ideas. In general, if a topic is not chess-related, I leave it to Don to talk about what we do, as he can do so more precisely than I can. On chess-related ideas, I do sometimes talk about what we do.

[Evert]

There is a perfectly safe way to do lazy evaluation: if at some point the score caluclated up to that point is outside the alpha-beta bounds by a margin larger than the maximum value of the remaining evaluation terms, it's safe to return immediately.
Of course, in that case you probably don't break out early very often, so it's not a big plus. However, you can also treat that margin as a tunable parameter. Doing this gave me a bit of extra strength for Sjaak (10-20 elo or so), but that may well change as I tweak more terms in the evaluation/add more knowledge to it...

[zamar]

Why does it work in Critter, Rybka, ... but not in Stockfish?

I find it extremely difficult to understand how different pruning methods interact. Only a very wild guess of mine is: Compared to other engines, SF has aggressive late move pruning. This might overlap with lazy eval cutoffs idea.

[bob]

For some unknown reason, lazy eval doesn't work for us in Komodo, although we've tried several implementations. It fails to give any meaningful speedup and of course it costs elo points. I believe most other strong programs (perhaps only except Stockfish) use it. For example it gives about a 10% speedup in Critter; not for free of course but the tradeoff is clearly favorable.
So my question is what is the experience of others with it? How much speedup do you get in actual play if you use it (average time for N ply search)? Are there variants or implementation details that make the difference between whether it works or not? For those programs which have tried and rejected it, to what do you attribute this? Why does it work in Critter, Rybka, ... but not in Stockfish?

Question is, why doesn't it work? The idea is speed. If you do it well, you should be able to see a speed gain that more than offsets the minor accuracy loss. I've been using it in every program I've written since the 70's, The "heavier" the eval, the greater the potential gain... One can even do a "staged" lazy eval with multiple exits, rather than just one... Each exit placed before the next "heavier" piece of the evaluation...

[lkaufman]

Why does it work in Critter, Rybka, ... but not in Stockfish?

I find it extremely difficult to understand how different pruning methods interact. Only a very wild guess of mine is: Compared to other engines, SF has aggressive late move pruning. This might overlap with lazy eval cutoffs idea.

But most of the benefit of lazy eval should be at or near the leaf nodes, past the point where anyone does LMR. So this doesn't explain very much I think. Komodo is somewhere between the Ippo-related programs and Stockfish in terms of how aggressively we use LMR.
So why doesn't SF at least use lazy eval at the leaf nodes? Presumably it's been tried and rejected, but why didn't it work?

[lkaufman]

There is a perfectly safe way to do lazy evaluation: if at some point the score caluclated up to that point is outside the alpha-beta bounds by a margin larger than the maximum value of the remaining evaluation terms, it's safe to return immediately.
Of course, in that case you probably don't break out early very often, so it's not a big plus. However, you can also treat that margin as a tunable parameter. Doing this gave me a bit of extra strength for Sjaak (10-20 elo or so), but that may well change as I tweak more terms in the evaluation/add more knowledge to it...

Since we can have quite large king safety scores in Komodo, the perfectly safe margin would typically be so large as to make any benefit microscopic. Of course we have tried tuning this margin, but even very risky values don't give us more than a trivial speedup. This despite the fact that our evaluation is unusually slow compared to other top programs.

[zamar]

So why doesn't SF at least use lazy eval at the leaf nodes? Presumably it's been tried and rejected, but why didn't it work?

Another guess:
SF has very sophisticated (and expensive) king safety evaluation which can return high scores. If we used lazy eval, we would effectively get less accurate king safety eval.[/list]

[lkaufman]

So why doesn't SF at least use lazy eval at the leaf nodes? Presumably it's been tried and rejected, but why didn't it work?

Another guess:
SF has very sophisticated (and expensive) king safety evaluation which can return high scores. If we used lazy eval, we would effectively get less accurate king safety eval.[/list]

OK, this makes sense, since your comments about king safety in SF apply also to Komodo. But we should at least get a sizable speedup with a reasonable margin, even if it was not a favorable trade-off. But we don't. Did SF show the same behavior?