Lazy eval on pv nodes

[hyatt]

I found it easy. Run enough games to measure Elo accurately, and then tune the value up and down to reach the max point... I didn't find "lots of local maxima" points. Just one. I don't see why there would be many. If you are too conservative, you don't get the speed gain and slowing down too much hurts. If you are too optimistic your eval becomes more unstable and it hurts.

So how much is enough games that you ran when you've concluded that doing lazy eval everywhere is better than just doing it in non-pv nodes???
Could you tell us that please?

I don't remember the elo difference. it was very small. To get to +/-1 Elo accuracy, you need something like 100,000 games. To get down to +/- 4 elo, you need 30,000 games. This is certainly not a +10 Elo change, although lazy eval overall is certainly worth move than that since it is a significant speed up if your eval is "heavy".

[marcelk]

Elsewhere I read that Houdini improves upon ippo* in part by implementing lazy eval on pv nodes rather than just on cut and all. It doesn't seem that that would be very difficult to implement in Ivanhoe's pv_node.c.

Do other engines typically do lazy on pv nodes? Why would that or how could that speed up search? Would this be beneficial for all engines or is it something that could hurt some engines and help others because it's nonlinear? If you put lazy on pv nodes do you need to change ordering?

Just trying to understand these things ...

Since evals in pv nodes are typically within the search window, a lazy eval there does the same as a full eval.
Lazy makes sense when you are (far) outside the window. I doubt you can measure a difference.
Besides, pv nodes are extremely rare.

Not even close. I use an aspiration window, so that beta - alpha is < 1.00 unless I see a fail high or a fail low. The only time your statement would be correct in Crafty would be if the first move failed low several times to drop the aspiration alpha to -inf, and then another move failed high repeatedly to raise aspiration beta to +inf. Normally they are "close" and lazy eval pays off big.

They are not as rare as you think. Remember, for CUT nodes, 90% of the time we get 'em right, but 10% we don't. That 10% introduces a lot of hidden PV nodes.

Maybe you are doing something else. I use PVS. PV nodes are rare in PVS, way below 0.1%. A cycle gain in PV is not measurable in time to depth as it gets swamped by the time spent in nodes for Qsearch, CUT and ALL nodes (in that order).

[hyatt]

Elsewhere I read that Houdini improves upon ippo* in part by implementing lazy eval on pv nodes rather than just on cut and all. It doesn't seem that that would be very difficult to implement in Ivanhoe's pv_node.c.

Do other engines typically do lazy on pv nodes? Why would that or how could that speed up search? Would this be beneficial for all engines or is it something that could hurt some engines and help others because it's nonlinear? If you put lazy on pv nodes do you need to change ordering?

Just trying to understand these things ...

Since evals in pv nodes are typically within the search window, a lazy eval there does the same as a full eval.
Lazy makes sense when you are (far) outside the window. I doubt you can measure a difference.
Besides, pv nodes are extremely rare.

Not even close. I use an aspiration window, so that beta - alpha is < 1.00 unless I see a fail high or a fail low. The only time your statement would be correct in Crafty would be if the first move failed low several times to drop the aspiration alpha to -inf, and then another move failed high repeatedly to raise aspiration beta to +inf. Normally they are "close" and lazy eval pays off big.

They are not as rare as you think. Remember, for CUT nodes, 90% of the time we get 'em right, but 10% we don't. That 10% introduces a lot of hidden PV nodes.

Maybe you are doing something else. I use PVS. PV nodes are rare in PVS, way below 0.1%. A cycle gain in PV is not measurable in time to depth as it gets swamped by the time spent in nodes for Qsearch, CUT and ALL nodes (in that order).

My problem is that the evaluation in Crafty burns about 50% of the total search time. Lazy eval cuts out the expensive parts of that for all of the oddball positions where the score is way outside the alpha/beta window.

I see more PV nodes than that in Crafty. (any node where alpha != beta - 1). But I have not measured it in a few months. Last time I did was when I was doing the PV path hashing stuff since I only save the path when the above alpah != beta - 1 condition is satisfied. It is remarkable how many hash entries that can require at times...

[UncombedCoconut]

You can't gain more than 2-3% of speed by applying lazy eval on PV nodes. An you can loose much more than 2-3 elo on that. Bad idea in general.

If you do it right, and it indeed does help in non-pv nodes, I see no reason why it would hurt along the PV (but maybe it is engine-specific).

Would you please elaborate more on theory why it would made a difference doing it only in non-pv nodes vs doing it everywhere? Did you run any tests?

If you do it right, indeed. The problem is, chances are quite high you won't do it right. It's all about the margin for lazy eval. I don't know how much experience you have with tuning it but what I can claim is that it's certainly not an easy task. The dependence (of strength on the margin size) is neither simple nor monotonic. The curve has a lot of local maxima and finding the best one is quite difficult.
The thing is if you setup your margin too low, it will hurt you much more in PV nodes than in non-PV. On the other hand the total benefit in speed is 2-3% (at least what I've tested) which is in the best case 2 Elo and practically unmeasurable even with Bob's cluster.
So, correctly speaking you can't know if it helps or hurts, but you can know if you don't do it right that it will hurt.

So you're saying that enabling lazy eval at PV nodes helps if you've done it right, and makes it clearer in test results if you haven't? That sounds like an unqualified win in the long term. Another reasonable approach, of course, is not to use lazy eval at all.

[hyatt]

I am not quite sure what you wrote that you thought I said.

Lazy eval is a winner. The more places you use it, the bigger the win. Turning it off in Crafty is a significant loss. I can run the test and report the result if it is an interesting topic...

The point of lazy eval is to save time. Every time you exit eval early, you win, unless your exit test is too optimistic and you start to produce eval errors. But that's the critical idea. Save time. Play better. This nonsense about "let's reduce error in the PV and allow it to run rampant in non-PV nodes" is an unsound idea. The goal of the search is to find the best move possible. If you screw up on the non-PV nodes, how can they _ever_ become PV nodes when you need to change your mind?

[UncombedCoconut]

I am not quite sure what you wrote that you thought I said.

That makes sense, because I was quoting somebody else.

[Sentinel]

So you're saying that enabling lazy eval at PV nodes helps if you've done it right, and makes it clearer in test results if you haven't? That sounds like an unqualified win in the long term. Another reasonable approach, of course, is not to use lazy eval at all.

No I am not saying that.
I've said that if you do it right you will not notice any difference to version where lazy eval is done only on non-PV nodes.
If you don't do it right it'll be noticeably weaker.
Hopefully you understand it now.

[mcostalba]

Lazy eval is a winner. The more places you use it, the bigger the win. Turning it off in Crafty is a significant loss. I can run the test and report the result if it is an interesting topic...

Yes please, run the test because it would be very interesting to have the real numbers. When we tried lazy eval in SF we didn't get any gain....

..of course this just means that our implementation was not good, but I am interesting to see how much you get from an assumed (by his author) proper implementation.