mate distance pruning

[Don]

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?

[Zach Wegner]

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]

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.

[hgm]

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.

[michiguel]

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 (alpha >= (MATE_VALUE-1)) {
		return adjust_out (alpha);
	}

	/* 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 (....)
{
	alpha = adjust_in (alpha);
	beta  = adjust_in (beta);

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

	if (alpha >= (MATE_VALUE-1)) {
		return adjust_out (alpha);
	}

	/* 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;

[michiguel]

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]

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]

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 (Score / Nodes)
	Pruning Enabled (Score / Nodes)
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.

[michiguel]

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

[michiguel]

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 (Score / Nodes)
	Pruning Enabled (Score / Nodes)
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