Razoring / Lazy eval question

[lucasart]

Hi,

I have a question:

When Razoring, I understand some programs (such as Toga II) call the evaluation and check whether it is less than (beta - RazorMargin) as one condition.

Lazy Evaluation is done (as in Toga) by passing alpha & beta to the evaluation and checking whether lazy value > beta + margin or < alpha + margin.

When calling eval() for razoring, should (alpha, beta) be passed into the eval() function as normal, or does it make sense to pass (beta - RazorMargin, beta - RazorMargin+1)?

It seems that the evaluation value found here is not used again, and if we are only using the evaluation to decide whether or not to use razoring, I would have thought that if

lazy value > beta - RazorMargin + margin
or
lazy value < beta - RazorMargin - margin

it should be safe to return from eval() here as we already know what the decision will be. Am I right or horribly mistaken?

Thanks for all your help.

Jerry

In any pruning decision at the leaves - lazy evaluation doesn't work for Diep.

Suppose that you search 30 plies deep. then the entire decision after that 30 plies is based upon lazy evaluation. That means that a few generic rules overrule a huge sophisticated evaluation function - which is not acceptable.

Same for me. I've never been able to see an improvement from lazy eval. It's a typical compromise speed/accuracy. Perhaps at hyper bullet games it can improve something (although even that I never managed to measure), but I doubt that such a dubious idea really makes an elo difference at long time controls.

One thing is certain however: if you use lazy eval, it's very easy to either (i) screw things up completely for a negligible speed gain (ii) make your code illegible and messy. And that is reason enough not to use lazy eval, IMO.

It's amazing how many amateurish chess engines try to mess around with lazy eval. There are so many low hanging fruits to grab, before one even thinks of lazy eval and raw speed optimizations... It's the computer equivalent of a human 1200 elo player, trying to memorize deep lines of complicated opening books, when he doesn't even see a basic fork or mate in 1 in obvious situations.

[Rebel]

Hi,

I have a question:

When Razoring, I understand some programs (such as Toga II) call the evaluation and check whether it is less than (beta - RazorMargin) as one condition.

Lazy Evaluation is done (as in Toga) by passing alpha & beta to the evaluation and checking whether lazy value > beta + margin or < alpha + margin.

When calling eval() for razoring, should (alpha, beta) be passed into the eval() function as normal, or does it make sense to pass (beta - RazorMargin, beta - RazorMargin+1)?

It seems that the evaluation value found here is not used again, and if we are only using the evaluation to decide whether or not to use razoring, I would have thought that if

lazy value > beta - RazorMargin + margin
or
lazy value < beta - RazorMargin - margin

it should be safe to return from eval() here as we already know what the decision will be. Am I right or horribly mistaken?

Thanks for all your help.

Jerry

In any pruning decision at the leaves - lazy evaluation doesn't work for Diep.

Suppose that you search 30 plies deep. then the entire decision after that 30 plies is based upon lazy evaluation. That means that a few generic rules overrule a huge sophisticated evaluation function - which is not acceptable.

Same for me. I've never been able to see an improvement from lazy eval. It's a typical compromise speed/accuracy. Perhaps at hyper bullet games it can improve something (although even that I never managed to measure), but I doubt that such a dubious idea really makes an elo difference at long time controls.

One thing is certain however: if you use lazy eval, it's very easy to either (i) screw things up completely for a negligible speed gain (ii) make your code illegible and messy. And that is reason enough not to use lazy eval, IMO.

It's amazing how many amateurish chess engines try to mess around with lazy eval. There are so many low hanging fruits to grab, before one even thinks of lazy eval and raw speed optimizations... It's the computer equivalent of a human 1200 elo player, trying to memorize deep lines of complicated opening books, when he doesn't even see a basic fork or mate in 1 in obvious situations.

I can imagine LE the CPW way (margin around alpha and beta) not working. Just try a margin for alpha only.

[syzygy]

Same for me. I've never been able to see an improvement from lazy eval. It's a typical compromise speed/accuracy. Perhaps at hyper bullet games it can improve something (although even that I never managed to measure), but I doubt that such a dubious idea really makes an elo difference at long time controls.

Lazy eval is completely sound if the margin is big enough. And there is no fixed rule on what you put into the lazy part. The basic idea is just to skip work that is not going to impact the end result anyway.

Anyway, how is futility pruning less dubious?

[jd1]

In Toga II lazy eval is worth at least 20 elo. I suspect this is because:
1. Toga does not have a complex evaluation. I can understand why it would be impractical for Diep, but in Toga we can use a relatively small margin.
2. Toga's mobility calculation is quite expensive, as any profiler will show.

These factors make the gain from lazy eval significantly more important than the losses in Toga. I think most engines have a margin which is less than the true upper bound of evaluation changes from the cutoff, though surely, as Ronald said, there is no risk with a large enough margin.

Jerry

[lucasart]

Same for me. I've never been able to see an improvement from lazy eval. It's a typical compromise speed/accuracy. Perhaps at hyper bullet games it can improve something (although even that I never managed to measure), but I doubt that such a dubious idea really makes an elo difference at long time controls.

Lazy eval is completely sound if the margin is big enough. And there is no fixed rule on what you put into the lazy part. The basic idea is just to skip work that is not going to impact the end result anyway.

Anyway, how is futility pruning less dubious?

Laze eval is *theoretically* unsound because:
- idea is: if you know that eva() will be < alpha (or > beta) then it doesn't matter what you return, so long as it's < alpha (or > beta)
- reality is: this reasoning is correct in a fail hard framework, but is already wrong in fail soft, and any decent program uses fail soft these days.
- besides, when you stop the eval depends on the bounds (alpha, beta). often the same position will be searched with a different (alpha, beta) window, and you'll get different eval, even if it stays on the same side of alpha and beta. so you can't even rely on storing the eval in the hash table anymore, which (i) surrenders some of the eval() speed gains that you achieved, or (ii) make your code even more messy by having to deal with an eval hash with a score type lbound/ubound/exact.
- to be able to see any significant speed gain, you basically *have* to screw things up and use a low margin and enter in a compromise speed/accuracy

Feel free to add items to the list...

Morality: the road to hell is paved with good intentions. Lazy eval being one of them

[diep]

Same for me. I've never been able to see an improvement from lazy eval. It's a typical compromise speed/accuracy. Perhaps at hyper bullet games it can improve something (although even that I never managed to measure), but I doubt that such a dubious idea really makes an elo difference at long time controls.

Lazy eval is completely sound if the margin is big enough. And there is no fixed rule on what you put into the lazy part. The basic idea is just to skip work that is not going to impact the end result anyway.

Anyway, how is futility pruning less dubious?

Well i'm not a big fan of futility either.

Yet you ask why it's less dangerous, imagine this,
with a..z being the moves/positions just passed:

a b c d e f g h .... x y z <lazy eval>

a b c d e f g h ... x y <real evaluation> z <estimate>

So in position y we have a real evaluation and some *cliue* on the real score of the position. Now we gamble with futility that we do not need move z in this position P. So with futility we at least have estimate Eval(Y) for position Y.

On the other hand in case of lazy eval we have completely NOTHING. We only have our lazy eval score that judges a big huge long 26 ply line in this case.

So there is no *sense* of what the real score is in this position. Not even remote sense. Just a very primitive estimate of our score.

This doesn't make 'futility' a correct way of doing things - it just shows how bad lazy evaluation is.

I sense that when used in a safe manner - i see no harm in using futility last ply of search. It's not the thing i'd prefer using.

Like what Ed is saying, if something is some pawns above beta, then it's safer to prune (in rebel pruning happens the ply before so alfa is in fact beta and beta is alfa - yet Ed said it correct here, just because he uses it integrated sooner saving him the function call it works that way).

So what i'd be preferring is a replacement search. I still feel this can be very effective last couple of plies.

It's in between razoring and doing a full blown nullmove.

Yet it might only be interesting for Diep - as diep's search is that slow.

At top of a position:

if( depth >= 3 ply depthleft && eval(position) >= beta + 3 pawns ) {
score = simplereplacementsearch(beta+3pawns-1,beta+3pawns);
if( score >= beta+3pawns )
return eval(position);
}

Now this might not be so attractive to you if your program already gets millions of nps a core.

Diep gets however 200k nps single core 2.5Ghz core2 Xeon and that's with PGO.

And in middlegame over 90% of all positions last 3 plies seen are 3 pawns away from alfa or beta.

So a big bunch of positions we can save out doing a qsearch nullmove in this manner and/or replacement search.

Very effective. I experimented with it in the year 2005 up to 5 ply depthleft or so and it was really promising but i never fully got it to work.

I guess the quick and dirty replacement search that is searching at 2.5 million nps single core K7 2.1Ghz (not to mention a 2.5Ghz core2), that it needs to know a tad more like passed pawns and some sense of kingsafety. Combining 2 different searches is just really complicated.

The thing is we already have a real good full evaluation done estimating this position at 3 pawns above beta. So that's pretty strong. A lot stronger than lazy eval... ...and a qsearch nullmove on average wastes 7 nodes here from which obviously some will be fully evaluated. In 70% of the cases it gives a cutoff then so arguably those 7 nodes aren't wasted - just it's very slow nodes.

So i'm kind of looking for something that's in between razoring and doing a slow qsearch nullmove kind of

So far nothing of all that worked for Diep - but i have good hopes

[Sven]

Laze eval is *theoretically* unsound because:
- idea is: if you know that eva() will be < alpha (or > beta) then it doesn't matter what you return, so long as it's < alpha (or > beta)
- reality is: this reasoning is correct in a fail hard framework, but is already wrong in fail soft, and any decent program uses fail soft these days.

Can you show why you think that this reasoning is wrong in fail soft?

If abs(FullEval - LE) <= LEMargin then
a) (LE + LEMargin <= Alpha) implies (FullEval <= Alpha) and
b) (LE - LEMargin) >= Beta) implies (FullEval >= Beta)
independent from "fail hard" or "fail soft". "Fail soft" only means that values returned from a search can be < Alpha or > Beta, but this is not in contradiction to the above logic.

EDIT: I would assume that lazy eval should return "LE + LEMargin" resp. "LE - LEMargin", not just LE itself. This would be the conservative way, returning only what you are sure about. In my view, with fail soft the implications of returning bounds that are closer to the AB window than necessary by using LE as described will show up nowhere in the whole tree except for the root node, and there only when using aspiration windows and failing high or low.

- besides, when you stop the eval depends on the bounds (alpha, beta). often the same position will be searched with a different (alpha, beta) window, and you'll get different eval, even if it stays on the same side of alpha and beta. so you can't even rely on storing the eval in the hash table anymore, which (i) surrenders some of the eval() speed gains that you achieved, or (ii) make your code even more messy by having to deal with an eval hash with a score type lbound/ubound/exact.

The latter would not be "messy" when simply reusing the same "lbound/ubound/exact" type of code that you already have for other hash tables like the main transposition table. It is simply the necessary and most appropriate solution.

Sven

[lucasart]

Laze eval is *theoretically* unsound because:
- idea is: if you know that eva() will be < alpha (or > beta) then it doesn't matter what you return, so long as it's < alpha (or > beta)
- reality is: this reasoning is correct in a fail hard framework, but is already wrong in fail soft, and any decent program uses fail soft these days.

Can you show why you think that this reasoning is wrong in fail soft?

If abs(FullEval - LE) <= LEMargin then
a) (LE + LEMargin <= Alpha) implies (FullEval <= Alpha) and
b) (LE - LEMargin) >= Beta) implies (FullEval >= Beta)
independent from "fail hard" or "fail soft". "Fail soft" only means that values returned from a search can be < Alpha or > Beta, but this is not in contradiction to the above logic.

EDIT: I would assume that lazy eval should return "LE + LEMargin" resp. "LE - LEMargin", not just LE itself. This would be the conservative way, returning only what you are sure about. In my view, with fail soft the implications of returning bounds that are closer to the AB window than necessary by using LE as described will show up nowhere in the whole tree except for the root node, and there only when using aspiration windows and failing high or low.

- besides, when you stop the eval depends on the bounds (alpha, beta). often the same position will be searched with a different (alpha, beta) window, and you'll get different eval, even if it stays on the same side of alpha and beta. so you can't even rely on storing the eval in the hash table anymore, which (i) surrenders some of the eval() speed gains that you achieved, or (ii) make your code even more messy by having to deal with an eval hash with a score type lbound/ubound/exact.

The latter would not be "messy" when simply reusing the same "lbound/ubound/exact" type of code that you already have for other hash tables like the main transposition table. It is simply the necessary and most appropriate solution.

Sven

I don't use lazy eval. And yes, you're right: there's nothing wrong in
- returning lazy_eval +/- margin
- theoretically sound if margin is always more than the neglected terms

But you don't seem to understand my point:
- people do not return lazy_eval +/- margin, because they are typically focused on improving their time to depth or node count, instead of improving their elo. have a look at toga, it's a great example of what NOT to do
- to be able to use lazy eval and get any measurable speed gain, you need to use a low margin. Let's have a look at what Toga does:
- it basically calculates the material score only (+few negligible things) and calls that lazy_eval
- if if lazy_eval is outside [alpha,beta] by a distance >= margin, it returns lazy_eval.
Now wait a minute, what is eval margin ?
answer: 200
And do you think that Thomas has tested if/when abs(eval-lazy_eval) > 200 ? I'm pretty sure with passed pawns (unstoppable passers?) + king safety only, you can easily exceed that.
The problem is that it's very hard to put an absolute maximum to the value of eval components. And if you did, it would be so large, that lazy eval would never be used anyway.
So I persist in saying that lazy eval is a bloody stupid idea, for the reasons that I've already explained, and certainly more that I forgot to mention.

Besides, people who want to learn computer chess algorithms, should really NOT look at Toga as an example.
I've just had a quick glance at it: almost everything that Toga added in the search, on top of the Fruit base, is utter crap (with the exception of SMP). Examples are:
- defective razoring as I already explained
- defective lazy eval as I've just explained
- extended futility pruning: the one in Fruit is clean and theoretically sound to some degree. Increasing the depth from 1 to 3 and using some random big margin to compensate for errors w/o any serious testing, anyone can do that... So when I hear people talking about "Toga extended futility pruning", as if it was some brilliant concept, I really laugh! Stockfish uses a subtile mechanism of dynamic evalMargin in order to be able to use extended futility pruning in a much more reliable way. Now that is a real idea.

[lucasart]

Laze eval is *theoretically* unsound because:
- idea is: if you know that eva() will be < alpha (or > beta) then it doesn't matter what you return, so long as it's < alpha (or > beta)
- reality is: this reasoning is correct in a fail hard framework, but is already wrong in fail soft, and any decent program uses fail soft these days.

Can you show why you think that this reasoning is wrong in fail soft?

If abs(FullEval - LE) <= LEMargin then
a) (LE + LEMargin <= Alpha) implies (FullEval <= Alpha) and
b) (LE - LEMargin) >= Beta) implies (FullEval >= Beta)
independent from "fail hard" or "fail soft". "Fail soft" only means that values returned from a search can be < Alpha or > Beta, but this is not in contradiction to the above logic.

EDIT: I would assume that lazy eval should return "LE + LEMargin" resp. "LE - LEMargin", not just LE itself. This would be the conservative way, returning only what you are sure about. In my view, with fail soft the implications of returning bounds that are closer to the AB window than necessary by using LE as described will show up nowhere in the whole tree except for the root node, and there only when using aspiration windows and failing high or low.

- besides, when you stop the eval depends on the bounds (alpha, beta). often the same position will be searched with a different (alpha, beta) window, and you'll get different eval, even if it stays on the same side of alpha and beta. so you can't even rely on storing the eval in the hash table anymore, which (i) surrenders some of the eval() speed gains that you achieved, or (ii) make your code even more messy by having to deal with an eval hash with a score type lbound/ubound/exact.

The latter would not be "messy" when simply reusing the same "lbound/ubound/exact" type of code that you already have for other hash tables like the main transposition table. It is simply the necessary and most appropriate solution.

Sven

I don't use lazy eval. And yes, you're right: there's nothing wrong in
- returning lazy_eval +/- margin
- theoretically sound if margin is always more than the neglected terms

But you don't seem to understand my point:
- people do not return lazy_eval +/- margin, because they are typically focused on improving their time to depth or node count, instead of improving their elo. have a look at toga, it's a great example of what NOT to do
- to be able to use lazy eval and get any measurable speed gain, you need to use a low margin. Let's have a look at what Toga does:
- it basically calculates the material score only (+few negligible things) and calls that lazy_eval
- if if lazy_eval is outside [alpha,beta] by a distance >= margin, it returns lazy_eval.
Now wait a minute, what is eval margin ?
answer: 200
And do you think that Thomas has tested if/when abs(eval-lazy_eval) > 200 ? I'm pretty sure with passed pawns (unstoppable passers?) + king safety only, you can easily exceed that.
The problem is that it's very hard to put an absolute maximum to the value of eval components. And if you did, it would be so large, that lazy eval would never be used anyway.
So I persist in saying that lazy eval is a bloody stupid idea, for the reasons that I've already explained, and certainly more that I forgot to mention.

Besides, people who want to learn computer chess algorithms, should really NOT look at Toga as an example.
I've just had a quick glance at it: almost everything that Toga added in the search, on top of the Fruit base, is utter crap (with the exception of SMP). Examples are:
- defective razoring as I already explained
- defective lazy eval as I've just explained
- extended futility pruning: the one in Fruit is clean and theoretically sound to some degree. Increasing the depth from 1 to 3 and using some random big margin to compensate for errors w/o any serious testing, anyone can do that... So when I hear people talking about "Toga extended futility pruning", as if it was some brilliant concept, I really laugh! Stockfish uses a subtile mechanism of dynamic evalMargin in order to be able to use extended futility pruning in a much more reliable way. Now that is a real idea.

Also, returning lazy_eval +/- margin is conservative, so it will most likely increase your node count, compared to returning the eval and not use lazy eval...

[Michel]

(with the exception of SMP).

Funny that you say this since Toga's SMP implementation is generally regarded as being crappy as well... (it is a simple shared hash).

Nonetheless Toga 1CPU is I believe about 150 Elo stronger than Fruit 2.1 on which it is based. So it is interesting to see that sometimes a few simple changes can give substantial Elo gain.