function qsearch(pos, alpha, beta):
eval = evaluate(pos)
if (eval >= beta) return eval
for move in good captures():
...
if (eval + inverse_delta_margin[ SEE(move) ] >= beta) return beta
...
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation. (At the obvious risk that you miss a counter move from the opponent, but that trade-off is all in the game).
Any prior art for this?
Marcel
PS: I also noted that Crafty doesn't have futility pruning / delta pruning at all anymore in qsearch. Is that correct or am I looking at the wrong place? In my case the regular futility pruning in qsearch gives me a 10% node reduction.
function qsearch(pos, alpha, beta):
eval = evaluate(pos)
if (eval >= beta) return eval
for move in good captures():
...
if (eval + inverse_delta_margin[ SEE(move) ] >= beta) return beta
...
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation. (At the obvious risk that you miss a counter move from the opponent, but that trade-off is all in the game).
Any prior art for this?
Marcel
PS: I also noted that Crafty doesn't have futility pruning / delta pruning at all anymore in qsearch. Is that correct or am I looking at the wrong place? In my case the regular futility pruning in qsearch gives me a 10% node reduction.
It still doesn't search captures with bad SEE values, but this is deferred until we actually decide to make the move and search it, rather than when initially sorting the moves...
marcelk wrote:
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation.
What moves qualify for this? The situation where you get up a queen + epsilon?
marcelk wrote:
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation.
What moves qualify for this? The situation where you get up a queen + epsilon?
Yes. Score just below alpha & SEE says you can win something big.
marcelk wrote:
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation.
What moves qualify for this? The situation where you get up a queen + epsilon?
Where the alpha = +300, material = -200, and you are looking at NxP, as an example. material + 100 won't get anywhere near alpha.
Why prune good moves with SEE > 0? My experience is that even SEE pruning of bad moves gives minimal gain compared to MVV/LVA move ordering & no pruning except null move. So if there are benefits from pruning good looking moves it should be very minimal.
Note that qsearch has always null move pruning, the rest are shallow prunings which use materialistic score (lazy score) to prune with risk.
So if you do lazy evaluation as most do, there is really no need for delta pruning as it only saves a makemove. Also doing the cutoff before you make the move (delta pruning) pretty much constrains you to a lazy score which looks at the material only, but with the later it is easier to add a lot more logic to the lazy score. I do Standpat + SEE + Lazy in my engine.
Daniel Shawul wrote:Why prune good moves with SEE > 0?
Because you speculate with some degree of confidence that some of these moves beat beta and you don't want to spend the effort to verify that. Instead you get out and search other parts of the tree. It is the classical trade-off and I agree that it would be a small fish. But if the fish is there why not try to catch it.
Daniel Shawul wrote:Why prune good moves with SEE > 0? My experience is that even SEE pruning of bad moves gives minimal gain compared to MVV/LVA move ordering & no pruning except null move. So if there are benefits from pruning good looking moves it should be very minimal.
Note that qsearch has always null move pruning, the rest are shallow prunings which use materialistic score (lazy score) to prune with risk.
So if you do lazy evaluation as most do, there is really no need for delta pruning as it only saves a makemove. Also doing the cutoff before you make the move (delta pruning) pretty much constrains you to a lazy score which looks at the material only, but with the later it is easier to add a lot more logic to the lazy score. I do Standpat + SEE + Lazy in my engine.
If you are a queen down, capturing a pawn safely is not going to help...
I get how delta pruning works. But my question was why pruning good moves would bring a significant benefit if pruning bad ones didn't ? It is _not_ that pruning good looking moves is not a bad idea. And if i have to guess why crafty do not use delta pruning now is because it has been doing redundunt staff with the lazy eval and pretty much saves only a makemove.
marcelk wrote:
With some suitably high values in the inverse_delta_margin[] table it can shave off a few nodes that otherwise would fail low after make move + eval at the next invocation.
What moves qualify for this? The situation where you get up a queen + epsilon?
Where the alpha = +300, material = -200, and you are looking at NxP, as an example. material + 100 won't get anywhere near alpha.
