LMR and PVS

[thevinenator]

I saw some code that added LMR to an alpha/beta search and the approach made sense, but unfortunately, I've implemented PVS and I haven't seen a good example of the proper way to add LMR to the PVS framework.

Here is how I implemented PVS. I've taken out the extemporary stuff to make it readable.

Code: Select all

	if (PVFound)	// we already found the PV
		{
		score = -ABTT( depth - 1, -alpha - 1, -alpha, NO_PV, DO_NULL);		
		if ((score > alpha) && (score < beta))
			score = -ABTT( depth - 1, -beta, -alpha, IS_PV, DO_NULL);
		}
	else	// PV code goes here
		score = -ABTT( depth - 1, -beta, -alpha, IsPV, DO_NULL);

From the CPW pages, a set of rules to control LPR as when NOT to use LMR follows:


•Still working on the first few moves
•Tactical moves (captures and promotions)
•Moves while in check
•Moves which give check
•Moves that cause a search extension
•Anytime in a PV-Node in a PVS search
•Depth < 3 (sometimes depth < 2)

I interpreted the rule "Anytime in a PV-Node in a PVS search" to mean, don't do a reduction in the above code shown here..

Code: Select all

else	// PV code goes here
		score = -ABTT( depth - 1, -beta, -alpha, IsPV, DO_NULL);

if that is correct, then that means the only places to the reduction are in the narrow window search or the research if the narrow window search fails. Or does it mean you have to scrap this model and use a different calling sequence.

Reducing the narrow search by 1-ply didn't seem to do much in way of speeding up my searches, so I'm a loss to know where to insert the reduction.

I don't just want to try stuff willy/nilly, I want to understand why I'm doing it.

any insight is appreciated.

[H.G.Muller]

Inprinciple LMR and PVS are independent techniques. PVS is just a search optimization, which tries to prove moves fail low in a cheaper way, by using the window {alpha,alpha+1} instead of {alpha, beta}. This backfires if the move did not fail low,as you have then to re-search with window {alpha, beta} anyway, and the time spent on the cheap null-window search was wasted. But if that happensonly rarely, PVS pays off.

LMR is superficially similar, because you also do a cheaper pilot search there, with the expectation that it will fail low, and then leave it at that. And in case the faillow did not materialize, you perform a re-search as originally required. The difference with PVS is that in LMR you make the pilot search cheaper by reducing the search depth, rather than narrowing the window.

To combine these techniques, you do the pilot search both with reduced depth and collapsed window, and if it fails low, you are done. If not, you could immediately do a re-search with the full depth and the fully opened window. In non-PV nodes the windowis a null window to start with,so there is nothing to open there, so a re-search at fulldepth is all you can do.

In PV nodes you have a choice. You can immediately do the most elaborate re-search, or you can do a number of progressively more expensive re-searches, in the hope that a favorable result (i.e. fail low) in one of those would allow you to bail out before doing the maximally expensive one. E.g. first do an unreduced null-window search, and only when that fails high too, re-search again unreduced with open window. Or first try to confirm the fail low at reduced depth with open window, before you do the latter two re-searches.

What works best dependson the stability of your search. In a completely stable search a null-window search that would fail high (i.e. score > alpha) would guarantee that the open-window search would also get a score > alpha (which might or might not be < beta, and would give you the exact score you need if it was). In that case an unreduced re-search with open window would be a waste of time, because the result was fully predictable, and would then require an unreduced search. But transposition table and window-dependent pruning techniques can cause search instability, so that searches that failed high on a null window often fail low when you open the window. If that happens too often,it might pay to speculate that it will, and do the reduced search with open window (which is the next cheapest) first.

[thevinenator]

Thanks for your insightful explanation. I can see that I have a lot of options to try!

I'm not sure how to quantify "stable search", another fuzzy term, but I'll try some of your recommendations and see which one(s) works the best.

thanks,

Vince

"Baby steps, always baby steps"