mate distance pruning

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.
User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

mate distance pruning

Post by Don » Sat Mar 14, 2009 1:46 am

I was curious about mate distance pruning. It seems to be a big deal in all the open source programs, but does it really make any measurable difference in the strength of the program? Or is it just one of those deals that helps a lot in rare positions?

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: mate distance pruning

Post by Zach Wegner » Sat Mar 14, 2009 3:24 am

It generally is not a big difference, but in some mate-y positions it helps prevent search explosion.

I'm not sure what you mean by "big deal", but if you are thinking of Fruit, disregard it. Fruit's implementation is way too long. It only needs to be a few lines long (from one of those other open source programs ;)):

Code: Select all

        /* mate-distance pruning */
        sb->alpha = MAX(sb->alpha, -MATE + sb->ply);
        sb->beta = MIN(sb->beta, MATE - sb->ply - 1);
        if (sb->alpha >= sb->beta)
            RETURN(sb->alpha);

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

Re: mate distance pruning

Post by bob » Sat Mar 14, 2009 4:52 am

Don wrote:I was curious about mate distance pruning. It seems to be a big deal in all the open source programs, but does it really make any measurable difference in the strength of the program? Or is it just one of those deals that helps a lot in rare positions?
Didn't help me a bit and I dumped it.

User avatar
hgm
Posts: 23604
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: mate distance pruning

Post by hgm » Sat Mar 14, 2009 7:35 am

In my engines mate-distance pruning is an automatic side effect of stand-pat cutoff and the delayed-loss bonus (responsible for the engine's urge to go for the fastest mate, or longest to-be-mated line).

As soon as beta < -INFINITY, bestScore, which is initialzed to -INFINITY in the full-width search, is >= beta even before any moves have been searched, and causes a beta cutoff.

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: mate distance pruning

Post by michiguel » Sat Mar 14, 2009 3:37 pm

hgm wrote:In my engines mate-distance pruning is an automatic side effect of stand-pat cutoff and the delayed-loss bonus (responsible for the engine's urge to go for the fastest mate, or longest to-be-mated line).

As soon as beta < -INFINITY, bestScore, which is initialzed to -INFINITY in the full-width search, is >= beta even before any moves have been searched, and causes a beta cutoff.
From previous threads, we must be doing the same thing. I think you can further optimize it a bit if the position is not in check.

Code: Select all

	/*---------------------------*
		Unreachable Check Mates
	 *---------------------------*/

	if &#40;alpha >= &#40;MATE_VALUE-1&#41;) &#123;
		return adjust_out &#40;alpha&#41;;
	&#125;

	/* cut off, I cannot be mated on time faster than beta */	
	if &#40;beta <= (-MATE_VALUE + 2&#41; && !position_isincheck&#40;po&#41;) &#123;
		return adjust_out &#40;beta&#41;;	
	&#125;
The whole context is the following.
As well as you, I do not need to adjust mates values when I store or retrieve a value from the hash table.

Code: Select all

search (....)
&#123;
	alpha = adjust_in &#40;alpha&#41;;
	beta  = adjust_in &#40;beta&#41;;

	/*---------------------------*
		Unreachable Check Mates
	 *---------------------------*/

	if &#40;alpha >= &#40;MATE_VALUE-1&#41;) &#123;
		return adjust_out &#40;alpha&#41;;
	&#125;

	/* cut off, I cannot be mated on time faster than beta */	
	if &#40;beta <= (-MATE_VALUE + 2&#41; && !position_isincheck&#40;po&#41;) &#123;
		return adjust_out &#40;beta&#41;;	
	&#125;

	/*
	|
	|
	| DO SEARCH STUFF HERE
	|
	|
	*/

	return adjust_out &#40;best&#41;;	
&#125;


static eval_t
adjust_in &#40;eval_t x&#41;
&#123;
	ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE&#41;;
	if &#40;MATE100_VALUE < x && x < MATE_VALUE&#41; 
		return x + 1;
	if (-MATE_VALUE < x && x < -MATE100_VALUE&#41; 
		return x - 1;
	return x;
&#125;

static eval_t
adjust_out &#40;eval_t x&#41;
&#123;
	ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE&#41;;
	if &#40;MATE100_VALUE < x && x < INFINITY_VALUE&#41; 
		return x - 1;
	if (-INFINITY_VALUE < x && x < -MATE100_VALUE&#41; 
		return x + 1;
	return x;
&#125;


User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: mate distance pruning

Post by michiguel » Sat Mar 14, 2009 4:14 pm

bob wrote:
Don wrote:I was curious about mate distance pruning. It seems to be a big deal in all the open source programs, but does it really make any measurable difference in the strength of the program? Or is it just one of those deals that helps a lot in rare positions?
Didn't help me a bit and I dumped it.
If this is what I think it is, it is not supposed to "help" with ELO points. It is supposed to help in finding shorter mates quicker. It helps in having a better output when the engine is used for analysis.

That is why I believe is wrong to discard things based ONLY on ELO.

Miguel

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

Re: mate distance pruning

Post by bob » Sun Mar 15, 2009 3:09 am

michiguel wrote:
bob wrote:
Don wrote:I was curious about mate distance pruning. It seems to be a big deal in all the open source programs, but does it really make any measurable difference in the strength of the program? Or is it just one of those deals that helps a lot in rare positions?
Didn't help me a bit and I dumped it.
If this is what I think it is, it is not supposed to "help" with ELO points. It is supposed to help in finding shorter mates quicker. It helps in having a better output when the engine is used for analysis.

That is why I believe is wrong to discard things based ONLY on ELO.

Miguel
Any code you add to the main search loop anywhere has a tiny negative impact on performance. That's my approacch to this. I have lots of extra code that is outside the search, but inside the search it has to help or it doesn't stay.

Edmund
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: mate distance pruning

Post by Edmund » Sun Mar 15, 2009 8:21 am

Using the Chess Engine Glass 1.0 I did a quick test to see the effects of Mate Distance Pruning.

Testposition:
[D]8/7K/8/8/8/8/R7/7k w - - 0 1[/D]

Code: Select all

Depth
	Pruning Disabled &#40;Score / Nodes&#41;
	Pruning Enabled &#40;Score / Nodes&#41;
1
	1041 / 3
	1041 / 3
2
	1041 / 23
	1041 / 23
3
	1051 / 103
	1051 / 103
4
	1051 / 551
	1051 / 551
5
	1055 / 2151
	1055 / 2151
6
	1051 / 7638
	1051 / 7638
7
	1055 / 24353
	1055 / 24353
8
	1065 / 62692
	1065 / 62692
9
	1065 / 139241
	1065 / 139241
10
	1085 / 253338
	1085 / 253338
11
	1085 / 409101
	1085 / 409101
12
	1105 / 610285
	1105 / 610285
13
	1105 / 873959
	1105 / 873959
14
	1105 / 1417047
	1105 / 1417047
15
	1105 / 1907578
	1105 / 1907578
16
	M8 / 2846864
	M8 / 2547293
17
	M8 / 3715208
	M8 / 2819164
18
	M8 / 4842666
	M8 / 3092833
19
	M8 / 6181827
	M8 / 3368068
20
	M8 / 7774698
	M8 / 3643489
... so no difference upto Depth 15, but the actual Matingline was found 10% earlier. And afterwards, going deeper is much faster with Mate Distance Pruning.

The cost: 2 if conditions per node.

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: mate distance pruning

Post by michiguel » Mon Mar 16, 2009 1:32 am

bob wrote:
michiguel wrote:
bob wrote:
Don wrote:I was curious about mate distance pruning. It seems to be a big deal in all the open source programs, but does it really make any measurable difference in the strength of the program? Or is it just one of those deals that helps a lot in rare positions?
Didn't help me a bit and I dumped it.
If this is what I think it is, it is not supposed to "help" with ELO points. It is supposed to help in finding shorter mates quicker. It helps in having a better output when the engine is used for analysis.

That is why I believe is wrong to discard things based ONLY on ELO.

Miguel
Any code you add to the main search loop anywhere has a tiny negative impact on performance. That's my approacch to this. I have lots of extra code that is outside the search, but inside the search it has to help or it doesn't stay.
Two well predicted "if" will give you any sort of impact?

Miguel

User avatar
michiguel
Posts: 6387
Joined: Thu Mar 09, 2006 7:30 pm
Location: Chicago, Illinois, USA
Contact:

Re: mate distance pruning

Post by michiguel » Mon Mar 16, 2009 1:34 am

Codeman wrote:Using the Chess Engine Glass 1.0 I did a quick test to see the effects of Mate Distance Pruning.

Testposition:
[D]8/7K/8/8/8/8/R7/7k w - - 0 1[/D]

Code: Select all

Depth
	Pruning Disabled &#40;Score / Nodes&#41;
	Pruning Enabled &#40;Score / Nodes&#41;
1
	1041 / 3
	1041 / 3
2
	1041 / 23
	1041 / 23
3
	1051 / 103
	1051 / 103
4
	1051 / 551
	1051 / 551
5
	1055 / 2151
	1055 / 2151
6
	1051 / 7638
	1051 / 7638
7
	1055 / 24353
	1055 / 24353
8
	1065 / 62692
	1065 / 62692
9
	1065 / 139241
	1065 / 139241
10
	1085 / 253338
	1085 / 253338
11
	1085 / 409101
	1085 / 409101
12
	1105 / 610285
	1105 / 610285
13
	1105 / 873959
	1105 / 873959
14
	1105 / 1417047
	1105 / 1417047
15
	1105 / 1907578
	1105 / 1907578
16
	M8 / 2846864
	M8 / 2547293
17
	M8 / 3715208
	M8 / 2819164
18
	M8 / 4842666
	M8 / 3092833
19
	M8 / 6181827
	M8 / 3368068
20
	M8 / 7774698
	M8 / 3643489
... so no difference upto Depth 15, but the actual Matingline was found 10% earlier. And afterwards, going deeper is much faster with Mate Distance Pruning.

The cost: 2 if conditions per node.
Does this engine analyze only 3 nodes at ply one and 23 at ply 2?
It does not sound right.

Miguel

Post Reply