You can actually measure the effect. They may or may not be "well predicted" depending on how heavily loaded the branch prediction data becomes... And the cost here is not only the branches, but the data to test might not be handy in a register either.michiguel wrote: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
mate distance pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: mate distance pruning
-
- Posts: 6401
- Joined: Thu Mar 09, 2006 8:30 pm
- Location: Chicago, Illinois, USA
Re: mate distance pruning
It may be difficult to get a better prediction on those. The "if" are always "false". When they become true, the game is decided.bob wrote:You can actually measure the effect. They may or may not be "well predicted" depending on how heavily loaded the branch prediction data becomes... And the cost here is not only the branches, but the data to test might not be handy in a register either.michiguel wrote: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
Miguel
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: mate distance pruning
Entries in the branch prediction hardware table are indexed by program counter, so it is quite common for multiple branches to share a single "predictor slow" both for the correlated predictor side and the local predictor side. As well as the tournament predictor itself for machines that have the most sophisticated branch prediction logic. That was what I was talking about, any unnecessary branches can be mis-predicted at times. But for code that is only used "when the game is decided" I don't see much point in it myself...michiguel wrote:It may be difficult to get a better prediction on those. The "if" are always "false". When they become true, the game is decided.bob wrote:You can actually measure the effect. They may or may not be "well predicted" depending on how heavily loaded the branch prediction data becomes... And the cost here is not only the branches, but the data to test might not be handy in a register either.michiguel wrote: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
Miguel
-
- Posts: 2851
- Joined: Wed Mar 08, 2006 10:01 pm
- Location: Irvine, CA, USA
Re: mate distance pruning
Maybe it's really black's move?michiguel wrote: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
Code: Select all
Depth Pruning Disabled (Score / Nodes) Pruning Enabled (Score / Nodes) 1 1041 / 3 1041 / 3 2 1041 / 23 1041 / 23 ...
It does not sound right.
-
- Posts: 1808
- Joined: Wed Mar 08, 2006 9:19 pm
- Location: Oslo, Norway
Re: mate distance pruning
From the point of view of playing strength, I don't even think it helps in rare positions. It's a purely cosmetic little trick, that helps the engine search and move more quickly when a mate has been found. The engine appears a little more intelligent to the user, and wastes slightly less of the user's time, but it won't play even a single Elo point stronger.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?
Tord
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: mate distance pruning
My mistake... I was posting the nodecount at the time the pv was found.michiguel wrote: Does this engine analyze only 3 nodes at ply one and 23 at ply 2?
It does not sound right.
Miguel
Nodecounts for the whole depth are:
1: 20
2: 78
3: 443
Edit: anyway for practical purposes I consider this measure more relevant - especially when it comes to detecting at what nodecount exactly the Mate in 8 was found.
Last edited by Edmund on Mon Mar 16, 2009 8:16 am, edited 1 time in total.
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: mate distance pruning
There are some differences that you cannot measure even if you ave a cluster. How moch would a single branch in the beginning of search cost you, speedwise? 0.1%? That would result in 0.1 Elo. Undetectably small gain in strength could easily offset that.
Branch-Target Buffers usually cache the branch history per instruction prefetch block (16 or 32 bytes), and if there are no other branches in the block this branch would have a slot reserved for it, which could not be overwritten by anything as long as the branch stays in cache. Remember that branch prediction does not take place at the level of individual instructions: (except perhaps in the P-IV with its trace cache), the first stage of the pipeline has to be fed with aligned prefetch blocks, and the purpose of branch prediction is to speculate which prefetch block will have to be fetched next. The predition logic for normal branches can hold one alternative follow-up to each prefetch block. If the branch is 'silent', the slot would effectvely be used only by other possible braches in the same prefetch block.
Branch-Target Buffers usually cache the branch history per instruction prefetch block (16 or 32 bytes), and if there are no other branches in the block this branch would have a slot reserved for it, which could not be overwritten by anything as long as the branch stays in cache. Remember that branch prediction does not take place at the level of individual instructions: (except perhaps in the P-IV with its trace cache), the first stage of the pipeline has to be fed with aligned prefetch blocks, and the purpose of branch prediction is to speculate which prefetch block will have to be fetched next. The predition logic for normal branches can hold one alternative follow-up to each prefetch block. If the branch is 'silent', the slot would effectvely be used only by other possible braches in the same prefetch block.
-
- Posts: 64
- Joined: Thu Feb 19, 2009 5:34 pm
- Location: Mexico, Mexico
Re: mate distance pruning
On the latest version of Toledo Nanochess the mate pruning is done as a very high score 131072 points minus depth multiplied by 1024, this does a nice effect of doing fast mate, although it doesn't help playing strength.
On an early version of my IOCCC entry (circa 2005, still available from the IOCCC), I used a small constant, with the effect that the chess program starts to eat piece after piece while the mate is in the horizon, it was not kind for the player.
On an early version of my IOCCC entry (circa 2005, still available from the IOCCC), I used a small constant, with the effect that the chess program starts to eat piece after piece while the mate is in the horizon, it was not kind for the player.
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Please post some short coding examples, thanks.
Could you please post the shortest code possible to achieve mate distance pruning?
Thanks,
Alvaro
Thanks,
Alvaro
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Please post some short coding examples, thanks.
Code: Select all
#define MATE 10000
Search(alpha, beta, depth)
{
int bestScore = dept >0 ? -MATE : Evaluate();
alpha -= (alpha < -MATE+100);
beta -= (beta <= -MATE+100);
if(bestScore >= beta) goto cutoff; // stand pat
// rest of alpha-beta search routine
...
cutoff:
bestScore += (bestScore < -MATE+100);
return bestScore;
}