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?
Lazy eval
Moderators: hgm, Rebel, chrisw
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Lazy eval
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.
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Lazy eval
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.mcostalba wrote: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.
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Lazy eval
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...
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...
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Lazy eval
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.lkaufman wrote:Why does it work in Critter, Rybka, ... but not in Stockfish?
Joona Kiiski
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Lazy eval
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 wrote: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?
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Lazy eval
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.zamar wrote: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.lkaufman wrote:Why does it work in Critter, Rybka, ... but not in Stockfish?
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?
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Lazy eval
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.Evert wrote: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...
-
- Posts: 613
- Joined: Sun Jan 18, 2009 7:03 am
Re: Lazy eval
Another guess:lkaufman wrote: 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?
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]
Joona Kiiski
-
- Posts: 5960
- Joined: Sun Jan 10, 2010 6:15 am
- Location: Maryland USA
Re: Lazy eval
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?zamar wrote:Another guess:lkaufman wrote: 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?
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]