PVS re-search at PV nodes

[lucasart]

for PV nodes, here's what I do:
- first move: full depth, full window (obviously)
- other moves:
(i) zero window, reduced depth
(II) if (i) doesn't fail low, full window, reduced depth
(iii) if (II) doesn't fail low (and reduction was != 0), search full depth full window
In other words, I extend the window first, before extending the depth.

In testing, this proved to work significantly better than the reverse (extend depth before extending window).

When comparing to other codes, it seems (if I understood correctly) that:
- Fruit 2.1 does the same
- Glaurung / Stockfish do the opposite

Any idea what you think is best, and why ?

[Eelco de Groot]

This sounds a bit like Houdini's reducing the depth feature, with the difference that Houdiní's trick is what you describe but solely for the Root node, where you reduce the depth in a re-search for every Fail High in a PV node. For Stockfish the Houdini reduced search did not seem to work immediately (I am not sure anymore who tried that without looking it up, maybe Gary). Maybe it hinges a bit on

(i) zero window, reduced depth

In Stockfish I think of this search as not so much reduced as very much thinned out, with only very few moves actually searched (by Late Move Pruning). Of course it also has nullmove reduction, and LMR reduction on top of LMR. The funny thing about LMR in Stockfish is IMO that even PV moves are LMR reduced, and it makes no difference if a node is an ALL node or CUT node, a CUT node is reduced and only searched to full depth if it fails high again. Maybe that partly explains the difference you see, the reduction you apply is really hidden in the Stockfish LMR block. That was not even called LMR until recently when Marco added that description again. I only recently realized the block in question is not really LMR anymore

But after a Fail High in LMR search, the search is depth extended, not widened, that much is true. Of course the windows in plain Stockfish are also very narrow which leads to FHs and FLs that are jumping around a bit (much). Searching with wider windows in Stockfish does not do a lot because even in PV nodes it is almost a zero-width window. In Rainbow Serpent the windows are programmed wider, to reduce the Fail Lows the user sees.

Eelco

[jdart]

This sounds plausible, because you are basically treating the reduced-depth node that didn't fail low as a PV node (just with reduced depth), with presumably different extensions and other logic.

I have tried a couple of times the "zero-width with more depth first" method of two-stage LMR re-search, but it didn't improve anything for me.

--Jon

[diep]

hi Eelco,

it's not the same as the trick as houdini3 has.

First of all we're already in the PV here and in case of the houdini trick we speak of a root move that wasn't pv yet where you have to extend the entire tree for, which is total different from the situation here.

In this case we speak of a research in a PV node.

That's total different, but i bet no one is willing to post why.

As i'm doing in Diep the same thing since end 90s with improvements in 2001 which explains why it is different (the first trick i invented in 90s and houdini somehow also has it and rybka3 as well, and the second trick i did not invent it and rybka3 and houdini have it, besides Diep and a few other engines like DeepSjeng Cluster), it is interesting how only some copycats took over those tricks. In general very few things leak to CCC which work great when used in combination.

So the result for most engines won't be much different, yet for houdini it's total different what he describes searching from root completely new and fresh versus toying within PV where you already have all those facilities in place and already did do it.

Crafty doesn't have this so it's logical Bob doesn't understand this, as he doesn't have preconditions A B C which explain why it is different and it's obvious no one is willing to post about it. I already posted too much here.

Note this also gives the problem why copycats are so strong with their engines and why guys who are honest must do way more effort to get there.

It's easy to miss a trick here or a trick there.

[hgm]

It depends on how stable your search is. If an open-window search almost always returns the same result as a null-window search of the same depth, doing the one at reduced depth seems a waste of time.

[diep]

It depends on how stable your search is. If an open-window search almost always returns the same result as a null-window search of the same depth, doing the one at reduced depth seems a waste of time.

All modern searches are instable.

[Eelco de Groot]

But, Vincent I don't really see that, because the Rootnode is as much a PV node as all the other PV nodes. And you find a move in that PV node that fails high. The re-search then may take long because the move was searched with both a zero window and with all the opportunistic reductions (LMP, LMR, null move). Now the move has to be searched without those reductions (where Crafty will still do nullmove in a PV node, Stockfish will still do LMR, only less), AND with a wider window. The really only difference I see is that at the root, the new move can do a bigger jump over alpha, because there is no real beta there (it is +Infinite) Further up the PV, if the new move is too good, it will cross beta and the higher up in the PV, the bigger the chance that the opponent will just choose another move below your Fail High move. But that at the root is not really a big problem I think, you probably just have found a winning move there or at least much better, if you Fail High at the root. The PV you had, you can throw away. So Houdini's trick is a form of IID mainly but the only real difference I see with what Lucas describes is that there is no real beta at the root.

Possibly Houdini does much the same trick in every PV node as it does at the root? I would not be surprised at all. If you, Houdini, does very large PV move extensions, which I kind of suspect it does, it makes more sense to do some extra IID in PV nodes.

Eelco

[diep]

But, Vincent I don't really see that, because the Rootnode is as much a PV node as all the other PV nodes. And you find a move in that PV node that fails high. The re-search then may take long because the move was searched with both a zero window and with all the opportunistic reductions (LMP, LMR, null move). Now the move has to be searched without those reductions (where Crafty will still do nullmove in a PV node, Stockfish will still do LMR, only less), AND with a wider window. The really only difference I see is that at the root, the new move can do a bigger jump over alpha, because there is no real beta there (it is +Infinite) Further up the PV, if the new move is too good, it will cross beta and the higher up in the PV, the bigger the chance that the opponent will just choose another move below your Fail High move. But that at the root is not really a big problem I think, you probably just have found a winning move there or at least much better, if you Fail High at the root. The PV you had, you can throw away. So Houdini's trick is a form of IID mainly but the only real difference I see with what Lucas describes is that there is no real beta at the root.

Possibly Houdini does much the same trick in every PV node as it does at the root? I would not be surprised at all. If you, Houdini, does very large PV move extensions, which I kind of suspect it does, it makes more sense to do some extra IID in PV nodes.

Eelco

No it's not the same.

The hard statement you have is 2 folded.

a) someone who claims that if he researches with houdini the iterations again new as it's a new rootmove starting 1,2,3,4,5... until current iteration depth, that this is better than to do a research that can take hours.

b) me acking that it makes sense to do this as one can explain why, however that crafty doesn't have these algorithms/tricks which explain why it makes sense for him and maybe not for crafty

You are busy at the crafty level now.

It's like someone from a couple of hundreds of years ago who doesn't know FFT who then gets asked to prove that you can solve any equation.

So if you say: "it doesn't make sense under assumptions XYZ with algorithms ABC", then you are correct.

The thing i acked however is THE FACT that it makes sense what was posted as your assumptions XYZ are wrong as algorithms ABCD get used in this case.

[lucasart]

It depends on how stable your search is. If an open-window search almost always returns the same result as a null-window search of the same depth, doing the one at reduced depth seems a waste of time.

All modern searches are instable.

Yeah, I think you both summarized it well.
- if search is stable then what I do is a waste of time
- but all modern search are unstable

Well, at least Fabien did it in Fruit, so it can't be plain stupid. I'll just keep it as it is, as it works best for me in testing. Although this testing was conducted at fast time control, I don't see any reason why it would suddenly reverse at long time control.

[Rebel]

Vincent is right. I remember the pre-reduction era you could count the plies to proof your program playing the correct move. Reductions (Nullmove, LMR etc) and pruning (futility, LMP) create an unstable search. Nevertheless it works.