mate distance pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
mate distance pruning
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?
-
- Posts: 1922
- Joined: Thu Mar 09, 2006 12:51 am
- Location: Earth
Re: mate distance pruning
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 ):
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);
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: mate distance pruning
Didn't help me a bit and I dumped it.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?
-
- Posts: 27816
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: mate distance pruning
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.
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.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: mate distance pruning
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.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.
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 (beta <= (-MATE_VALUE + 2) && !position_isincheck(po)) {
return adjust_out (beta);
}
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 (beta <= (-MATE_VALUE + 2) && !position_isincheck(po)) {
return adjust_out (beta);
}
/*
|
|
| DO SEARCH STUFF HERE
|
|
*/
return adjust_out (best);
}
static eval_t
adjust_in (eval_t x)
{
ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE);
if (MATE100_VALUE < x && x < MATE_VALUE)
return x + 1;
if (-MATE_VALUE < x && x < -MATE100_VALUE)
return x - 1;
return x;
}
static eval_t
adjust_out (eval_t x)
{
ASSERT (-INFINITY_VALUE <= x && x <= INFINITY_VALUE);
if (MATE100_VALUE < x && x < INFINITY_VALUE)
return x - 1;
if (-INFINITY_VALUE < x && x < -MATE100_VALUE)
return x + 1;
return x;
}
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: mate distance pruning
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.bob wrote:Didn't help me a bit and I dumped it.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?
That is why I believe is wrong to discard things based ONLY on ELO.
Miguel
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: mate distance pruning
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.michiguel wrote: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.bob wrote:Didn't help me a bit and I dumped it.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?
That is why I believe is wrong to discard things based ONLY on ELO.
Miguel
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: mate distance pruning
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]
... 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.
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
The cost: 2 if conditions per node.
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: mate distance pruning
Two well predicted "if" will give you any sort of impact?bob wrote: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.michiguel wrote: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.bob wrote:Didn't help me a bit and I dumped it.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?
That is why I believe is wrong to discard things based ONLY on ELO.
Miguel
Miguel
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: mate distance pruning
Does this engine analyze only 3 nodes at ply one and 23 at ply 2?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]
... 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.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
The cost: 2 if conditions per node.
It does not sound right.
Miguel