PVS and reduction

[lucasart]

I'm wondering if I'm doing this right:

Code: Select all

		// reduced PVS
		if (!is_pv || first) {
			// search full window at reduced depth
			score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);
			
			// verify reduced beta cutoff
			if (si->reduction && score >= beta)
				score = -search(B, -beta, -alpha, new_depth, ply+1, is_pv, si+1);
		}
		else /* if (is_pv && !first) */ {
		   // try zero window at reduced depth
		   score = -search(B, -alpha-1, -alpha, new_depth-si->reduction, ply+1, false, si+1);
		   
/*		   // reduced zero window search doesn't fail low: re-search zero window w/o reduction
		   if (si->reduction && score > alpha)
			   score = -search(B, -alpha-1, -alpha, new_depth, ply+1, false, si+1);*/
		   
		   // non-reduced zero window search doesn't fail low: re-search full window w/o reduction
		   if (score > alpha)
			   score = -search(B, -beta, -alpha, new_depth, ply+1, true, si+1);
		}

[lucasart]

Perhaps I should clarify a little bit. This is not the code of my official release DoubleCheck 2.3.1, but a test I've been doing as it makes sense intuitively (but performs *horribly bad* at least in node count terms). I'm just trying to figure out why it's wrong and explodes the node count. So here's the reasoning:

Case 1first move of a PV node or any move of a non PV node
1/ search the full window (which is a zero window for a non PV node) at reduced depth
2/ if we get a fail high with a reduced search, then do a verification search w/o reduction
I think we'll agree on that?
(note that the reduction is either 0, 1 or 2)

Case 2PV node, not the first move
1/ try a zero window search at reduced depth, and hope for a fail low
2/ it doesn't fail low and was indeed reduced: re-search zero window w/o reduction
3/ it still doesn't fail low: search full window w/o reduction
it seems to make sense, but explodes my node count completely :S

[mcostalba]

I'm wondering if I'm doing this right:

Code: Select all

		// reduced PVS
		if (!is_pv || first) {
			// search full window at reduced depth
			score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);
			
			// verify reduced beta cutoff
			if (si->reduction && score >= beta)
				score = -search(B, -beta, -alpha, new_depth, ply+1, is_pv, si+1);
		}
		else /* if (is_pv && !first) */ {
		   // try zero window at reduced depth
		   score = -search(B, -alpha-1, -alpha, new_depth-si->reduction, ply+1, false, si+1);
		   
/*		   // reduced zero window search doesn't fail low: re-search zero window w/o reduction
		   if (si->reduction && score > alpha)
			   score = -search(B, -alpha-1, -alpha, new_depth, ply+1, false, si+1);*/
		   
		   // non-reduced zero window search doesn't fail low: re-search full window w/o reduction
		   if (score > alpha)
			   score = -search(B, -beta, -alpha, new_depth, ply+1, true, si+1);
		}

Conditions seems wrong, you may want to write:

Code: Select all

if (is_pv && first)) 
    full windowsearch
else
    zero window search

[lucasart]

thanks marco. i guess i was getting lost there. So here's my new code, it should be better (I hope)

Code: Select all

		if (is_pv && first) {
			// search full window
			score = -search(B, -beta, -alpha, new_depth, ply+1, is_pv, si+1);
		} else {
			// zero window search (reduced)
			score = -search(B, -alpha-1, -alpha, new_depth-si->reduction, ply+1, false, si+1);
			
			// doesn't fail low: re-search full window (reduced)
			if (score > alpha)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);
			
			// fails high: verify the beta cutoff with a non reduced search
			if (score >= beta && si->reduction)
				score = -search(B, -beta, -alpha, new_depth, ply+1, is_pv, si+1);
		}

What do you think?

[mcostalba]

What do you think?

Better. Now that you have written the correct code you may want to negate the condition and reshuffle a bit:

Code: Select all

 if (!is_pv || !first) {
			// zero window search (reduced)
			score = -search(B, -alpha-1, -alpha, new_depth-si->reduction, ply+1, false, si+1);
			
			// doesn't fail low: re-search full window (reduced)
			if (score > alpha && si->reduction)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);
} else 
      score = beta;
			
// Full window, full depth search
if (score >= beta)
	score = -search(B, -beta, -alpha, new_depth, ply+1, is_pv, si+1);
		

[lucasart]

but there's still a mistery... If is_pv is false, then the following re-search should be useless:

Code: Select all

			// doesn't fail low: re-search full window (reduced)
			if (score > alpha)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);

since beta already equals alpha+1.

However when I try instead

Code: Select all

			// doesn't fail low: re-search full window (reduced)
			if (is_pv && score > alpha)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);

it explodes my node count :S

[mcostalba]

However when I try instead

Code: Select all

			// doesn't fail low: re-search full window (reduced)
			if (is_pv && score > alpha)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);

it explodes my node count :S

Did you forgot the "si->reduction" ?

Code: Select all

			// doesn't fail low: re-search full window (reduced)
			if (is_pv && score > alpha && si->reduction)
				score = -search(B, -beta, -alpha, new_depth-si->reduction, ply+1, is_pv, si+1);