futility pruining, razoring question

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
elcabesa
Posts: 806
Joined: Sun May 23, 2010 11:32 am
Contact:

futility pruining, razoring question

Post by elcabesa » Wed Apr 04, 2012 6:21 pm

I was trying to implement some new feature inside my engine and I can't make futility and razoring work inside my engine.

Today I have noticed that Cheng engine does futility and razoring only inside Null Windows search, is this approach correct??

bob
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: futility pruining, razoring question

Post by bob » Thu Apr 05, 2012 7:07 pm

elcabesa wrote:I was trying to implement some new feature inside my engine and I can't make futility and razoring work inside my engine.

Today I have noticed that Cheng engine does futility and razoring only inside Null Windows search, is this approach correct??
It should work everywhere if it works anywhere. You might tune/refine it later, but it should work everywhere and produce an improvement, unless you have other issues...

Karlo Bala
Posts: 301
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: futility pruining, razoring question

Post by Karlo Bala » Thu Apr 05, 2012 7:59 pm

bob wrote:
elcabesa wrote:I was trying to implement some new feature inside my engine and I can't make futility and razoring work inside my engine.

Today I have noticed that Cheng engine does futility and razoring only inside Null Windows search, is this approach correct??
It should work everywhere if it works anywhere. You might tune/refine it later, but it should work everywhere and produce an improvement, unless you have other issues...
What are your latest findings about the futility and/or razoring?
Best Regards,
Karlo Balla Jr.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: futility pruining, razoring question

Post by diep » Thu Apr 05, 2012 11:47 pm

bob wrote:
elcabesa wrote:I was trying to implement some new feature inside my engine and I can't make futility and razoring work inside my engine.

Today I have noticed that Cheng engine does futility and razoring only inside Null Windows search, is this approach correct??
It should work everywhere if it works anywhere. You might tune/refine it later, but it should work everywhere and produce an improvement, unless you have other issues...
You're razoring the mainline nowadays?

That'll get you quickly to 100 ply search depth i bet :)

p.s. if you razor at random, can you claim then having added MonteCarlo+UCT to your program in an 'optimized manner'?

User avatar
lucasart
Posts: 3036
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: futility pruining, razoring question

Post by lucasart » Fri Apr 06, 2012 3:34 am

here's my razoring code. it's a little uncommon as I reduce instead of pruning (and prune when horizon reached). but this seems to work much better than pruning

razor parameters

Code: Select all

const bool UseRazoring = true;
static const int RazorDepth = 3;
static inline int RazorMargin(int depth) {
	assert&#40;1 <= depth && depth <= RazorDepth&#41;;
	return 2*MP + &#40;depth-1&#41;*MP/4;
&#125;
MP is the value of a pawn in the middlegame. the RazorMargin formula is just a guess (no optimization done). And given that constraint, it appeared that RazorDepth == 3 was best.

in the main search

Code: Select all

	// Razoring
	if &#40;UseRazoring && depth <= RazorDepth
		&& !is_pv && !is_mate_score&#40;beta&#41; && !in_check&#41;
	&#123;
		if &#40;current_eval + RazorMargin&#40;depth&#41; <= alpha&#41; &#123;
			const int score = qsearch&#40;B, alpha, beta, 0, ply+1, is_pv, si+1&#41;;
			if &#40;score <= alpha && --depth <= 0&#41;
				return score;
		&#125;
	&#125;
as for futility pruning, I don't think what I do is really good. I need to do more experiment on it.
Last edited by lucasart on Fri Apr 06, 2012 3:36 am, edited 1 time in total.

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: futility pruining, razoring question

Post by mar » Fri Apr 06, 2012 3:35 am

elcabesa wrote:I was trying to implement some new feature inside my engine and I can't make futility and razoring work inside my engine.

Today I have noticed that Cheng engine does futility and razoring only inside Null Windows search, is this approach correct??
Yes it's true. Note that I recently fixed a bug in razoring. For no elo gain as usual of course. qsearch alpha-razormargin, beta-razormargin then compare to beta-razormargin is correct (fixed tactical blindness in some testpositions).
Honestly cheng is NOT a good reference of how things should be done (bugs, source not readable) but in general you don't want to do futility/nullmove in PV nodes. I also recently removed upper/lower (alpha/beta) TT pruning in PV nodes. Null window search in cheng => non-PV => All/Cut nodes.

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: futility pruining, razoring question

Post by mar » Fri Apr 06, 2012 4:10 am

PS I believe this (common?) razoring mistake (scouting around alpha instead of alpha-razormargin) comes from chessprogramming wiki and should be fixed. When I think about it it doesn't make sense. First compare eval to beta-margin then scout around alpha?!!
Why no elo gain (for me at least) => I guess because fixing it will razor much less nodes. Btw. I certainly wouldn't want to analyse a position with this bug :)

mar
Posts: 1986
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: futility pruining, razoring question

Post by mar » Fri Apr 06, 2012 5:15 am

As for futility: never had problem with that and seems pretty stable.
Futility simply prunes (ignores) certain moves at nodes where eval+margin is below beta in scout search.
In general:
-never do futility when evading a check
-don't skip potentially good/dangerous moves: hashmove, captures, promotions, castling, checks, killers and in general any moves you want to extend
perhaps good history moves shouldn't be skipped as well but i don't do that in cheng; i also don't prune passer pushes

PS hashmove, captures, castling and killers boil down to "do futility after the killers phase in movegen"

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: futility pruining, razoring question

Post by mcostalba » Fri Apr 06, 2012 5:45 am

Well, clearly razoring has no sense in PV (even theoretically) . Near leaves of PV you expect value to be above alpha, and in case you find a fail low at next iteration you really don't want to find it through razoring. But I suspect Bob was referring to something else than all of us: normally I use chessprogramming as a name reference, but I think he is using other references and probably with 'razoring' he is referring to forward pruning or something like that.

Regarding Luca's code I find this:

Code: Select all

const int score = qsearch&#40;B, alpha, beta, 0, ply+1, is_pv, si+1&#41;; 
a really optimistic assumption, normally you want to verify with a reduced margin, not with alpha. If this was also in your original code, perhaps could be a reason why it didn't work for you and so you switched to a kind of reduction instead of pruning.

User avatar
lucasart
Posts: 3036
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: futility pruining, razoring question

Post by lucasart » Fri Apr 06, 2012 7:22 am

mcostalba wrote:Well, clearly razoring has no sense in PV (even theoretically) . Near leaves of PV you expect value to be above alpha, and in case you find a fail low at next iteration you really don't want to find it through razoring. But I suspect Bob was referring to something else than all of us: normally I use chessprogramming as a name reference, but I think he is using other references and probably with 'razoring' he is referring to forward pruning or something like that.

Regarding Luca's code I find this:

Code: Select all

const int score = qsearch&#40;B, alpha, beta, 0, ply+1, is_pv, si+1&#41;; 
a really optimistic assumption, normally you want to verify with a reduced margin, not with alpha. If this was also in your original code, perhaps could be a reason why it didn't work for you and so you switched to a kind of reduction instead of pruning.
You're right. As pointed out by Martin, I got fooled by the chess programming wiki :wink:
I'm currently testing this alternative:

Code: Select all

	if &#40;UseRazoring && depth <= RazorDepth
		&& !is_pv && !is_mate_score&#40;beta&#41; && !in_check&#41;
	&#123;
		if &#40;current_eval + RazorMargin&#40;depth&#41; <= alpha&#41; &#123;
			const int score = qsearch&#40;B, alpha, beta, 0, ply+1, is_pv, si+1&#41;;
			if &#40;score + RazorMargin&#40;depth&#41; <= alpha&#41;	//**
				return score;
		&#125;
	&#125;
I've just ran 1000 games in 6"+0.1", and it scored 52% against my previous code. Thanks for the tip!

Post Reply