Lazy eval

[lkaufman]

[quote="bobQuestion 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...[/quote]

I take it that Crafty does get a decent speedup for lazy eval. Do you get about the same as the 10% figure I quote for Critter, or perhaps more? We can't get more than 2% with any reasonable margin, clearly not enough to use it. The question is whether this is due to redundancy with other pruning techniques, or to some implementation detail? Of course you won't know as you don't work on Komodo, but perhaps you can suggest a way to tell. Sure we do a lot of heavy pruning near the leaf nodes, but so does Critter and it gets a very nice speedup from lazy eval.

[zamar]

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?

It has been so long time since we tested this, that I can't remember.

But "speed-up" is a bit ambiguous concept. I think you definitely should see higher nodes/second ratio. However my experience is that worse eval often leads to bigger search trees, so "go depth x" might require more nodes.

P.S. Of course if you flood-fill your eval with "if"-statements to check lazy-eval everywhere, you might increase branching which could cause slowdown, but I don't think that this could realistically be an issue in any sensible implementation.

[Eelco de Groot]

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.

I suggest you are giving yourself the answer there Larry Because Komodo has an expensive evaluation the whole point is to get it as accurate as possible. Once you have decided to make an expensive full eval and there is even a small risk of more inaccuracy if you terminate early, it is better to just finish it. Across a node, the differences in eval are sometimes minute and the smallest things matter. You never get the feel of a grandmaster in a simple eval but the small differences between different moves in a node are nevertheless important, I think sometimes much more than small time savings near the horizon from lazy eval.

Also even if you think you made a safe exit because the eval can't possibly reach alpha, all that changes if alpha falls. Different programs have different behaviour in how accurate and stable alpha is I think. Because of small search windows, volatile nullwindow searches, large speculative evals you can see for yourself for Stockfish those might be another reason why lazy eval might not work so well there.

Tord mentioned something similar to what you are saying: the eval terms that cost the most cycles are also the ones that can give larger eval changes, in Glaurung/Stockfish, especially the king safety and I think also the passed pawn terms. Those terms are not safe to exclude from the eval result when doing lazy eval and also for king safety you need attack information that you don't have at the start, so king safety calculations have to be done almost last. The biggest terms coming in last is also not ideal if you want to do lazy eval. Maybe I'm not getting the technical details right here but those are some of the possible reasons why I think lazy eval is not always possible or does not seem to work as advertized by others but as you say Larry different programs seem to react differently here.

Regards, Eelco

[lkaufman]

OK, you have almost convinced me that lazy eval just won't work in a program with big eval scores for king safety and pawn structure. However, it seems to me that we should still get the usual gain in nodes per second, even if the increased size and inaccuracy of the tree makes it a bad deal. But we only get at most 2-3% more nodes per second, while at least Critter gets 10% or so. Why should our nodes per second gain depend much on the eval details?

[mcostalba]

Do you get about the same as the 10% figure I quote for Critter

Now it's my time to ask. How can you know the speed up of lazy eval for Critter.

Do you have the Critter sources ?

[tvrzsky]

OK, you have almost convinced me that lazy eval just won't work in a program with big eval scores for king safety and pawn structure. However, it seems to me that we should still get the usual gain in nodes per second, even if the increased size and inaccuracy of the tree makes it a bad deal. But we only get at most 2-3% more nodes per second, while at least Critter gets 10% or so. Why should our nodes per second gain depend much on the eval details?

Did you make some statistics how often is your eval really lazy and did you measure how many CPU cycles you can save with it? This should give you answer after all?

[lkaufman]

Yes, as mentioned some time ago, Richard Vida was nice enough to send Critter source code to us. We did learn a bit from it, but very little proved to improve Komodo, as the ideas (but not the code) in Critter were mostly too similar to Ippo.

[lkaufman]

OK, you have almost convinced me that lazy eval just won't work in a program with big eval scores for king safety and pawn structure. However, it seems to me that we should still get the usual gain in nodes per second, even if the increased size and inaccuracy of the tree makes it a bad deal. But we only get at most 2-3% more nodes per second, while at least Critter gets 10% or so. Why should our nodes per second gain depend much on the eval details?

Did you make some statistics how often is your eval really lazy and did you measure how many CPU cycles you can save with it? This should give you answer after all?

Yes, we took some statistics, and they indicated that it didn't kick in very often unless the margin was very small. I'm just not sure why it didn't kick in more often.

[Alessandro Damiani]

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.

Have you tried Ed Schröder's way? http://www.top-5000.nl/authors/rebel/ch ... AZY%20EVAL

[lkaufman]

[quote="Alessandro DamianiHave you tried Ed Schröder's way? http://www.top-5000.nl/authors/rebel/ch ... AZY%20EVAL[/quote]

Actually, that description seems to match what we tried very closely! Ed reports a 3.2 speedup (i.e. 220%) while we get barely over 2%! So it works 100 times better for him than for us, even though we both have complex king safety with large possible scores. Very, very strange!! If we could get even Critter's 10% out of it (never mind Ed's 220%!) we would be quite close to Houdini at longer time controls.

I ran off 30,000 games at 8 ply of Critter with and without lazy eval, and the speedup was 12%, and the lazy version actually came out (narrowly) ahead! At 12 ply the speedup drops a bit below 10%, and there is no way to get the cost without tieing up the computer for days. I find the 8 ply result to be remarkable.