Lazy eval

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
lkaufman
Posts: 3757
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Lazy eval

Post by lkaufman » Sun Nov 27, 2011 4:41 pm

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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Lazy eval

Post by mcostalba » Sun Nov 27, 2011 4:59 pm

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
Posts: 3757
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Lazy eval

Post by lkaufman » Sun Nov 27, 2011 5:21 pm

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.
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.

User avatar
Evert
Posts: 2923
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Lazy eval

Post by Evert » Sun Nov 27, 2011 5:38 pm

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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Lazy eval

Post by zamar » Sun Nov 27, 2011 5:39 pm

lkaufman wrote: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.
Joona Kiiski

bob
Posts: 20642
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Lazy eval

Post by bob » Sun Nov 27, 2011 6:28 pm

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?
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
Posts: 3757
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Lazy eval

Post by lkaufman » Sun Nov 27, 2011 6:32 pm

zamar wrote:
lkaufman wrote: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
Posts: 3757
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Lazy eval

Post by lkaufman » Sun Nov 27, 2011 6:37 pm

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...
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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Lazy eval

Post by zamar » Sun Nov 27, 2011 7:24 pm

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?
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]
Joona Kiiski

lkaufman
Posts: 3757
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Lazy eval

Post by lkaufman » Sun Nov 27, 2011 7:45 pm

zamar wrote:
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?
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?

Post Reply