TalkChess.com

It's interesting, that agressive reductions even at the root node can't harm SmarThink playing strength. Below see code snippet for root search function.
I've runned test match between new version with the code above, and previous one (no pruning at the root). Currently it shows 1409.5:1398.5 — so, probably, no significant changes when I've expected some dropdown.
What is your expirience of forward pruning in PV-nodes? I think at least some moves can be reduced.

That is an interesting approach but it certainly seems risky.

There is a decent chance a move far down the root move list will actually start to fail high and be promoted to the PV. And if you are cutting off that move based on a reduced search you are going to push out to farther iterations the point where that happens.

As for PV pruning in general, I guess you can do it but by far the majority of nodes are non-PV nodes so turning on pruning for the PV nodes is not going to save you a lot in terms of nodes searched, I wouldn't think.

--Jon

jdart wrote:That is an interesting approach but it certainly seems risky.

There is a decent chance a move far down the root move list will actually start to fail high and be promoted to the PV. And if you are cutting off that move based on a reduced search you are going to push out to farther iterations the point where that happens.

Yes, but look — I've used reduction factor 4 * INCPLY and more and slightly small window — but anyway it works ok. I will try to tune it. Unfortunately I still haven't testing network like in the case of StockFish) But I hope it will be done in next few weeks.

I think that in PV nodes if the case you're several pawns below alpha you can safely reduce quiet moves excluding tactical ones — checks, forks, passed pawns pushes etc. In SmarThink I have some simple "optimism" score that includes only our passed pawns eval and opponent king safety. I think that it can be used to drive explore of promising "quiet" paths — but it's neccessary to perform some statistical analyse here...

Sergei S. Markoff wrote:It's interesting, that agressive reductions even at the root node can't harm SmarThink playing strength. Below see code snippet for root search function.
I've runned test match between new version with the code above, and previous one (no pruning at the root). Currently it shows 1409.5:1398.5 — so, probably, no significant changes when I've expected some dropdown.
What is your expirience of forward pruning in PV-nodes? I think at least some moves can be reduced.

Code: Select all

int reduction_bound[16] = {200, 200, 200, 200, 200, 200, 200, 150, 100, 75, 65, 50, 40, 35, 30, 25};
int reduction_num_bound[8] = {25, 25, 25, 20, 15, 10, 5, 0};

int RootSearch(int a, int b, int d)
{
	int min_value;
	int max_value;

	if (mate_moves > 0)
	{
		min_value = -&#40;INFINITY - &#40;mate_moves << 1&#41;);
		max_value = min_value + 1;
	&#125;
	else
	&#123;
		min_value = -INFINITY - 1;
		max_value = INFINITY + 1;
	&#125;

	if &#40;a < min_value&#41; a = min_value;
	if &#40;b > max_value&#41; b = max_value;
	if &#40;a >= b&#41; return &#40;a&#41;;

	if &#40;d >= 5 * INCPLY && b == a + 1&#41;
	&#123;
		int bound = reduction_bound&#91;MIN&#40;d / INCPLY, 15&#41;&#93; + reduction_num_bound&#91;MIN&#40;7, RootMoveNum&#41;&#93;;
		int res_reducted = Search&#40;a + bound, b + bound, d - 4 * INCPLY - (&#40;int&#41;(&#40;d / 6&#41; / INCPLY&#41;) * INCPLY, TRUE, &#40;b == a + 1&#41; ? NODE_TYPE_CUT &#58; NODE_TYPE_EXACT&#41;;
		if &#40;threads&#91;CURRENT_THREAD&#93;.board->stopped&#41; return 0;
		if &#40;res_reducted >= b + bound&#41; return res_reducted;
	&#125;

	&#123;
		int res = Search&#40;a, b, d, TRUE, &#40;b == a + 1&#41; ? NODE_TYPE_CUT &#58; NODE_TYPE_EXACT&#41;;
		// printf&#40;"&#91;%d;%d&#58; %d&#93;\n", min_value, max_value, res&#41;;
		return res;
	&#125;
&#125;

I've always reduced at the root. I don't see anything that makes it any different than any other node in that regard...

jdart wrote:That is an interesting approach but it certainly seems risky.

There is a decent chance a move far down the root move list will actually start to fail high and be promoted to the PV. And if you are cutting off that move based on a reduced search you are going to push out to farther iterations the point where that happens.

Think about that statement, and answer this question:

Is there any DIFFERENCE in the probability that (a) a move down in the root list will fail high; and (b) a move down in the ply=2 move list will fail high and change the PV?

I would say no. What makes the root move special in this case? A bad move at the root should be reduced just like a bad move at ply=2 or any other play.

As for PV pruning in general, I guess you can do it but by far the majority of nodes are non-PV nodes so turning on pruning for the PV nodes is not going to save you a lot in terms of nodes searched, I wouldn't think.

--Jon

I think that the main difference between a pv-node (including the root one) and non-pv is a much higher "price" of error. That's why most of the contemporary engines performing full search in pv-nodes without reductions, null-move etc. In pv-node you have more chances to promote error to the root.

r = s / (e * p1 * p2)

where
s — nodes number expected to be pruned by a reduction/pruning
e — nodes number that will be spent over the normal count to fix error if it will be promoted to the root
p1 — probability of the error
p2 — probability of the wrong score promotion to the root

If r > 1 we should perform reduction/pruning. You can also use the same formula to evaluate extensions.
Obviously, for pv nodes p2 in average is much higher, so that's why it's more risky to make pruning/reductions here.

I have a dream that someone will create a good way to predict s, e, p1 and p2 based on some good factors set and statistics. It can bring more science in search trees structure and keep our current shamanism away)

Sergei S. Markoff wrote:I think that the main difference between a pv-node (including the root one) and non-pv is a much higher "price" of error. That's why most of the contemporary engines performing full search in pv-nodes without reductions, null-move etc. In pv-node you have more chances to promote error to the root.

r = s / (e * p1 * p2)

where
s — nodes number expected to be pruned by a reduction/pruning
e — nodes number that will be spent over the normal count to fix error if it will be promoted to the root
p1 — probability of the error
p2 — probability of the wrong score promotion to the root

If r > 1 we should perform reduction/pruning. You can also use the same formula to evaluate extensions.
Obviously, for pv nodes p2 in average is much higher, so that's why it's more risky to make pruning/reductions here.

I have a dream that someone will create a good way to predict s, e, p1 and p2 based on some good factors set and statistics. It can bring more science in search trees structure and keep our current shamanism away)

That is a common argument. However, first question: "what is the point of doing iteration N+1?" Common answer: "about 1/6 of the time the program will change its mind." If you are more aggressive in non-PV moves, this becomes harder to do. Next question: "Which is more important, preserving the PV from the first move searched, or finding a new PV (best move) to replace the current one?"

I find it hard to justify treating the first move differently from the rest of the moves...

bob wrote:I find it hard to justify treating the first move differently from the rest of the moves...

I find it hard to argue against what all the top engines are doing, which is to treat PV and non-PV nodes differently.

bob wrote:That is a common argument. However, first question: "what is the point of doing iteration N+1?" Common answer: "about 1/6 of the time the program will change its mind." If you are more aggressive in non-PV moves, this becomes harder to do.

I think you just should have functions to predict s, e, p1 and p2 that will use some set of factors including flag "is it pv node?" These functions should be based on statistics. In this terms "what is the point of doing iteration N+1" should be presented as "what is the probability of iteration N+1 will fix error from the iteration N?" and "how much nodes at average will be spent to obtain new, correct, move?"
You can use, for example, search with relatively higher depth to obtain "correct" move and score to build nearly correct stats.
I think the best tech to create stats is to:
1) Create full search tree (only with correct prunings — only alpha/beta for the beginning) for some relatively high depths — d and d+1 for some set of randomly selected positions from real games. Then let's exclude positions where we have different best moves for d and d+1 search.
2) Let's decide that best move at the root for this tree — is "correct" move.
3) Then let's explore tree for depth d. Let's examine each possible reduce- by-one-ply descision inside this tree. If it will be resulted in best move change at the root — let's decide, that this reducing is "incorrect", otherwise — it's "correct".
4) Let's calculate "casualities" of this error — how much nodes will be searched over the case of tree with no reduction? And also number of nodes saved by reduction.
5) Finally we will have a set of potential reduction decisions with correct/incorrect flag and "cost of the error" value. Let's involve some set of factors for each case — depth, alpha - static_eval, in_check, move params — capture? promotion? checking etc? history score? killer1/killer2? etc. And then try to build function that will be a best predictor for correct decision. It can be some polymonial, for example.
6) It will be our first iteration) The next step it to include our reduction tech in tree as "correct pruning", extend d by one ply and repeat steps 1–5 until we will have no more progress (for example, significant changes in prediction polynomial coeffitients).

Of course, generalisation of the optimal search tree should answer to question — which node should be explored to remove max uncertainty? And which nodes should be stored in memory, but this is, of course, completely another tale...

syzygy wrote:

bob wrote:I find it hard to justify treating the first move differently from the rest of the moves...

I find it hard to argue against what all the top engines are doing, which is to treat PV and non-PV nodes differently.

That's not an argument. Fruit was a top engine, and applied LMR reductions solely based on the history counter values, not order or anything. Did that make it right? Does anybody do that today? (no).

Following that reasoning, nobody would be using LMR (none of the top engines are using any sort of reductions today and it is hard to argue against what they are doing...).

Just because the "crowd" does it, doesn't make it right. MIGHT be, but NOT for THAT reason... If I run across a technical argument that is convincing, I might think differently. But I am definitely not a "lemming".