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.
bob
Posts: 20471
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: mate distance pruning

Post by bob » Mon Mar 16, 2009 1:59 am

michiguel wrote:
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
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.

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 2:15 am

bob wrote:
michiguel wrote:
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
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.
It may be difficult to get a better prediction on those. The "if" are always "false". When they become true, the game is decided.

Miguel

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

Re: mate distance pruning

Post by bob » Mon Mar 16, 2009 4:13 am

michiguel wrote:
bob wrote:
michiguel wrote:
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
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.
It may be difficult to get a better prediction on those. The "if" are always "false". When they become true, the game is decided.

Miguel
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...

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: mate distance pruning

Post by Dirt » Mon Mar 16, 2009 6:20 am

michiguel wrote:
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
...
Does this engine analyze only 3 nodes at ply one and 23 at ply 2?
It does not sound right.
Maybe it's really black's move?

Tord Romstad
Posts: 1808
Joined: Wed Mar 08, 2006 8:19 pm
Location: Oslo, Norway

Re: mate distance pruning

Post by Tord Romstad » Mon Mar 16, 2009 6:47 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?
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.

Tord

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

Re: mate distance pruning

Post by Edmund » Mon Mar 16, 2009 7:14 am

michiguel wrote: Does this engine analyze only 3 nodes at ply one and 23 at ply 2?
It does not sound right.
Miguel
My mistake... I was posting the nodecount at the time the pv was found.

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 7:16 am, edited 1 time in total.

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

Re: mate distance pruning

Post by hgm » Mon Mar 16, 2009 7:15 am

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.

User avatar
nanochess
Posts: 64
Joined: Thu Feb 19, 2009 4:34 pm
Location: Mexico, Mexico
Contact:

Re: mate distance pruning

Post by nanochess » Mon Mar 16, 2009 3:59 pm

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.

Cardoso
Posts: 292
Joined: Thu Mar 16, 2006 6:39 pm

Please post some short coding examples, thanks.

Post by Cardoso » Sat Mar 21, 2009 10:52 am

Could you please post the shortest code possible to achieve mate distance pruning?

Thanks,
Alvaro

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

Re: Please post some short coding examples, thanks.

Post by hgm » Sat Mar 21, 2009 11:03 am

Code: Select all

#define MATE 10000

Search(alpha, beta, depth)
{
  int bestScore = dept >0 ? -MATE : Evaluate();

  alpha -= &#40;alpha < -MATE+100&#41;;
  beta -= &#40;beta <= -MATE+100&#41;;
  if&#40;bestScore >= beta&#41; goto cutoff; // stand pat

  // rest of alpha-beta search routine
  ...

cutoff&#58;
  bestScore += &#40;bestScore < -MATE+100&#41;;
  return bestScore;
&#125;

Post Reply