mate distance pruning

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

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.

[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

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]

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]

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]

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]

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.

[hgm]

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.

[nanochess]

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]

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

Thanks,
Alvaro

[hgm]

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;