history pruning/ late move pruning

[Dann Corbit]

{snip}
Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

Fruit (and hence Toga) along with Glaurung are the pioneers of late move (history) reduction based pruning. It has been found in Fruit for a long time.

Movei is using late move reduction before fruit and glaurung so fruit and glaurung are not the first to try the idea and find that it is productive(my guess is that some commercial programs are also using it before movei).

I guess that doing late move reduction only based on evaluation and not based on history counters can be better and I may try it.

Uri

I have the idea to also use previous search as well (not just eval).

The notion is to see previous fail low nodes as likely candidates for reductions.

My criteria would be:
1. Search result + History
2. Eval + History
3. Eval only

Since we should know the current alpha/beta window, we should be able to see the approximate distance between this node and the best node (crude estimate of some kind anyway).

So if I have a current best move score of +100 centipawns and some other node has a fail-low hash score of -1000 centipawns, we can probably search it less deeply. The fun part will be to decide on a function to create the right reduction based on all of these variables.

[H.G.Muller]

A kind of general question:

Is it needed to make reduction decisions in alpha nodes at all? Reductions take effect only at the end of the tree, and before you reach that end, you will pass through beta nodes. Taking the decision to reduce the branch there would give you the same result.

So in particular, when reducing the late moves, because they do not seem to be very productive, presumably you will not reduce moves that achieve something that brings the static evaluation score above alpha, e.g. through capturing. So the following beta node will most likely be a good candidate for null-move pruning, and be reduced anyway. A late-move reduction would add to this, and might make that you can't afford as large a reduction on the null-move search as you would otherwise be able to apply.

One might argue that, if the null move fails low in that beta node, requiring you to do a normal search, at least you would be left with the late move reduction. But would you really want to reduce a move that could make the opponent's next null move fail low?

[Uri Blass]

I guess that big gain from late move reduction can be achieved only if you reduce a lot of moves that have some threat against the opponent.

I think that it may be interesting to get some statistics from tord in glaurung about the percentage of moves that have a threat against the opponent out of the moves that are reduced by late move reduction(so they are not pruned by null move pruning after being reduced).

Uri

[mjlef]

Several commericals program used this kind of reduction in various forms in the past. My program NOW, for example, was using it way back in 1991. What may have changed are the specific details of implementaion, which could now be better tuned. I was using "late move pruning" with lots of rules to control when it was safe to use. The addition of counters of sucessful moves seems like a good refinement to catch some of the moves not easily found from simpler tests. Other restrictions (not reducing capture moves, checks, passed pawn pushes...) were things we came up with many years ago. I know other programmers also used this type of pruning too.

Has anyone run tests of various conditions on this pruning (really depth reduction). How much does the probability counters help? I wouldlove to see a few hundred game match between late move pruning with and without this condition to see how much it helps.

Mark

[Tord Romstad]

One might argue that, if the null move fails low in that beta node, requiring you to do a normal search, at least you would be left with the late move reduction. But would you really want to reduce a move that could make the opponent's next null move fail low?

Perhaps not - at least not in all cases. I try to determine whether the move that refuted the null move is somehow connected to the move that was reduced, and cancel the reduced depth search when this happens. Let M1 be the reduced move, and M2 be the move that refuted the null move at the child node. I undo the reduction in the following cases:

• The 'from' square of M2 equals the 'to' square of M1.
• The 'to' square of M2 equals the 'from' square of M1.
• The ray between the 'from' and 'to' squares of M2 passes through the 'from' square of M1.
• The 'to' square of M2 is attacked by the piece on the 'to' square of M1.

The last public version of my program only uses the first of the above criterions. Adding the three other cases seems to have helped a little.

I have tried to only use these rules when the remaining depth is small. To my surprise, this doesn't seem to work well. I now use them at all depths.

Tord

[Tord Romstad]

Several commericals program used this kind of reduction in various forms in the past. My program NOW, for example, was using it way back in 1991. What may have changed are the specific details of implementaion, which could now be better tuned.

I don't think so. Until recently, the technique has received very little attention, and I don't think it has evolved much over the last 15-20 years.

I was using "late move pruning" with lots of rules to control when it was safe to use. The addition of counters of sucessful moves seems like a good refinement to catch some of the moves not easily found from simpler tests. Other restrictions (not reducing capture moves, checks, passed pawn pushes...) were things we came up with many years ago. I know other programmers also used this type of pruning too.

Has anyone run tests of various conditions on this pruning (really depth reduction). How much does the probability counters help?

In my experience, they don't help at all. On the contrary, the biggest recent leap in playing strength for my engine came when I stopped using history counters and replaced them with evaluation data and null move threat detection. My current reduction rules are very primitive and could certainly easily be improved, but they still clearly outperform the simple use of history counters.

As almost everything else, this probably depends to a great extent on the program. I think that using history counters might be a good idea for those who only evaluate leaf nodes, while those who evaluate internal nodes should try knowledge-based reductions instead.

Tord

[Tord Romstad]

I think that it may be interesting to get some statistics from tord in glaurung about the percentage of moves that have a threat against the opponent out of the moves that are reduced by late move reduction(so they are not pruned by null move pruning after being reduced).

OK, I'll run some tests. Stay tuned.

Tord

[Tord Romstad]

Has anyone tried tossing out null move and using late history reductions only for trimming branches?

Yes. Doesn't work for me. Strength drops by more than 100 Elo points.

Has anyone tried history reductions that scale smoothly from the worst to the best (instead of chuky drops in plies like falling off of a cliff)?

If you start at 0 and scale by small fractional amounts to 1 ply, I don't think it would work well; at least not if you do re-searches when the reduced move fails high (as most of us do). The cost of searching "early late moves" twice would be to high. Starting at 1 ply and scaling to even bigger amounts later in the move list is more interesting. I have done some experiments with this lately, scaling from a minimum of 1 ply to a maximum of 1.5 plies (but only when the remaing depth is at least 7 plies). At the moment I don't like it, but I plan to try it for a while before I drop the idea.

Tord

[Dann Corbit]

Has anyone tried tossing out null move and using late history reductions only for trimming branches?

Yes. Doesn't work for me. Strength drops by more than 100 Elo points.
{snip}
Tord

Was the reduction for history reductions equivalent to the reduction for null move (e.g. 3 plies typically) in those positions where null move applies?

I have a notion that the reduction should be proportional to the log of the difference in score.

So if you have two moves which appear about the same, there is no reduction and huge score differences get big reductions.

Something along the lines of:
c1*log(1 + c2*(best - worst))

where c1 and c2 are constants tuned for your program.
Of course, you could fetch the high bit of (best-worst) for a good estimate of logarithm.

[Tony van Roon-Werten]

Has anyone tried tossing out null move and using late history reductions only for trimming branches?

Yes. Doesn't work for me. Strength drops by more than 100 Elo points.

Has anyone tried history reductions that scale smoothly from the worst to the best (instead of chuky drops in plies like falling off of a cliff)?

If you start at 0 and scale by small fractional amounts to 1 ply, I don't think it would work well; at least not if you do re-searches when the reduced move fails high (as most of us do). The cost of searching "early late moves" twice would be to high. Starting at 1 ply and scaling to even bigger amounts later in the move list is more interesting. I have done some experiments with this lately, scaling from a minimum of 1 ply to a maximum of 1.5 plies (but only when the remaing depth is at least 7 plies). At the moment I don't like it, but I plan to try it for a while before I drop the idea.

Tord

I don't think Dan meant this. I understood he meant that by calculating fe the history percentage, you decide how much to reduce. Something like <50% is .5 ply <40% is 0.7 ply and maybe <10% 2 ply.

I've tried it, but couldn't get it working nicely.

Tony

[Ferdinand]

One might argue that, if the null move fails low in that beta node, requiring you to do a normal search, at least you would be left with the late move reduction. But would you really want to reduce a move that could make the opponent's next null move fail low?

Perhaps not - at least not in all cases. I try to determine whether the move that refuted the null move is somehow connected to the move that was reduced, and cancel the reduced depth search when this happens. Let M1 be the reduced move, and M2 be the move that refuted the null move at the child node. I undo the reduction in the following cases:

• The 'from' square of M2 equals the 'to' square of M1.
• The 'to' square of M2 equals the 'from' square of M1.
• The ray between the 'from' and 'to' squares of M2 passes through the 'from' square of M1.
• The 'to' square of M2 is attacked by the piece on the 'to' square of M1.

Hi Tord,
Please verify if the following setup from the opening game stage is valid for the first two case you mentioned above.

Code: Select all

case 1: from(M2)==to(M1)
1. e2e4 e7e5 2. Nb1c3 Bf8c5 3. d2d3 Qd8f6(reduced) 4. null Qf6xf2
M1=Qd8f6, M2=Qf6xf2

case 2: to(M2)==from(M1)
1. e2e4 e7e5 2. Ng1f3 Nb8c6 3. d2d3 d7d6 4. Nf3g5(reduced) null 5. Qd1f3
M1=Nf3g5, M2=Qd1f3


Best regards,
Ferdinand


The last public version of my program only uses the first of the above criterions. Adding the three other cases seems to have helped a little.

I have tried to only use these rules when the remaining depth is small. To my surprise, this doesn't seem to work well. I now use them at all depths.

Tord

[Tord Romstad]

Perhaps not - at least not in all cases. I try to determine whether the move that refuted the null move is somehow connected to the move that was reduced, and cancel the reduced depth search when this happens. Let M1 be the reduced move, and M2 be the move that refuted the null move at the child node. I undo the reduction in the following cases:

• The 'from' square of M2 equals the 'to' square of M1.
• The 'to' square of M2 equals the 'from' square of M1.
• The ray between the 'from' and 'to' squares of M2 passes through the 'from' square of M1.
• The 'to' square of M2 is attacked by the piece on the 'to' square of M1.

Hi Tord,
Please verify if the following setup from the opening game stage is valid for the first two case you mentioned above.

Code: Select all

case 1: from(M2)==to(M1)
1. e2e4 e7e5 2. Nb1c3 Bf8c5 3. d2d3 Qd8f6(reduced) 4. null Qf6xf2
M1=Qd8f6, M2=Qf6xf2

case 2: to(M2)==from(M1)
1. e2e4 e7e5 2. Ng1f3 Nb8c6 3. d2d3 d7d6 4. Nf3g5(reduced) null 5. Qd1f3
M1=Nf3g5, M2=Qd1f3


Yes, that looks correct. Similar examples for the third and fourth cases:

Code: Select all

case 3: from(M1) is on the ray from from(M2) to to(M2):
1. Ng1f3 b7b5 2. e2e4(reduced) null 3. Bf1xb5
M1=e2e4, M2=Bf1xb5

case 4: to(M2) is attacked by piece on to(M1):
1. e2e4 e7e5 2. Qd1h5 Nb8c6 3. Bf1c4(reduced) null 4. Qh5xf7
M1=Bf1c4, M2=Qh5xf7


The actual code I use looks like this:

Code: Select all

static bool connected_moves(const position_t *pos, move_t m1, move_t m2) {
  int f1, t1, f2, t2, p1;
  attack_data_t *a;

  // Case 1: Same piece
  f2 = FROM(m2); t1 = TO(m1);
  if(f2 == t1) return true;

  // Case 2: Destination square for m2 was vacated by m1:
  t2 = TO(m2); f1 = FROM(m1);
  if(t2 == f1) return true;

  // Case 3: Moving through the vacated square:
  if(PieceIsSlider(PIECE(m2))) {
    if(AttackData[f1 - t2].step == AttackData[f2 - t2].step &&
       (f1 - t2) * (f2 - t2) < 0)
      return true;
  }
  // Case 4: Destination square for m2 attacked by moving piece in m1:
  p1 = pos->board[t1];
  a = AttackData - t2;
  if(a[t1].may_attack & PieceMask[p1]) {
    if(!PieceIsSlider(p1)) return true;
    else {
      int sq, step = a[t1].step;
      for(sq = t1 + step; pos->board[sq] == EMPTY && sq != t2; sq += step);
      if(sq == t2) return true;
    }
  }
  return false;
}


Tord

[Tord Romstad]

I think that it may be interesting to get some statistics from tord in glaurung about the percentage of moves that have a threat against the opponent out of the moves that are reduced by late move reduction(so they are not pruned by null move pruning after being reduced).

OK, I'll run some tests. Stay tuned.

I've now played four blitz games and collected statistics. The percentage of reduced depth searches which were aborted because the reduced move was found to contain a threat was close to 3% in all four games. This is less than I expected.

Tord

[Ferdinand]

Perhaps not - at least not in all cases. I try to determine whether the move that refuted the null move is somehow connected to the move that was reduced, and cancel the reduced depth search when this happens. Let M1 be the reduced move, and M2 be the move that refuted the null move at the child node. I undo the reduction in the following cases:

• The 'from' square of M2 equals the 'to' square of M1.
• The 'to' square of M2 equals the 'from' square of M1.
• The ray between the 'from' and 'to' squares of M2 passes through the 'from' square of M1.
• The 'to' square of M2 is attacked by the piece on the 'to' square of M1.

Hi Tord,
Please verify if the following setup from the opening game stage is valid for the first two case you mentioned above.

Code: Select all

case 1: from(M2)==to(M1)
1. e2e4 e7e5 2. Nb1c3 Bf8c5 3. d2d3 Qd8f6(reduced) 4. null Qf6xf2
M1=Qd8f6, M2=Qf6xf2

case 2: to(M2)==from(M1)
1. e2e4 e7e5 2. Ng1f3 Nb8c6 3. d2d3 d7d6 4. Nf3g5(reduced) null 5. Qd1f3
M1=Nf3g5, M2=Qd1f3


Yes, that looks correct. Similar examples for the third and fourth cases:

Code: Select all

case 3: from(M1) is on the ray from from(M2) to to(M2):
1. Ng1f3 b7b5 2. e2e4(reduced) null 3. Bf1xb5
M1=e2e4, M2=Bf1xb5

case 4: to(M2) is attacked by piece on to(M1):
1. e2e4 e7e5 2. Qd1h5 Nb8c6 3. Bf1c4(reduced) null 4. Qh5xf7
M1=Bf1c4, M2=Qh5xf7


The actual code I use looks like this:

Code: Select all

static bool connected_moves(const position_t *pos, move_t m1, move_t m2) {
  int f1, t1, f2, t2, p1;
  attack_data_t *a;

  // Case 1: Same piece
  f2 = FROM(m2); t1 = TO(m1);
  if(f2 == t1) return true;

  // Case 2: Destination square for m2 was vacated by m1:
  t2 = TO(m2); f1 = FROM(m1);
  if(t2 == f1) return true;

  // Case 3: Moving through the vacated square:
  if(PieceIsSlider(PIECE(m2))) {
    if(AttackData[f1 - t2].step == AttackData[f2 - t2].step &&
       (f1 - t2) * (f2 - t2) < 0)
      return true;
  }
  // Case 4: Destination square for m2 attacked by moving piece in m1:
  p1 = pos->board[t1];
  a = AttackData - t2;
  if(a[t1].may_attack & PieceMask[p1]) {
    if(!PieceIsSlider(p1)) return true;
    else {
      int sq, step = a[t1].step;
      for(sq = t1 + step; pos->board[sq] == EMPTY && sq != t2; sq += step);
      if(sq == t2) return true;
    }
  }
  return false;
}


Tord

Thanks, I will try to look further and experiment with this.
Ferdinand

[Daniel Mehrmann]

{snip}
Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

Fruit (and hence Toga) along with Glaurung are the pioneers of late move (history) reduction based pruning. It has been found in Fruit for a long time.

Movei is using late move reduction before fruit and glaurung so fruit and glaurung are not the first to try the idea and find that it is productive(my guess is that some commercial programs are also using it before movei).

I guess that doing late move reduction only based on evaluation and not based on history counters can be better and I may try it.

Uri

i'm also using hp before fruit & Glaurung. I'm using it since febuary 2004.

daniel

[Uri Blass]

I think that it may be interesting to get some statistics from tord in glaurung about the percentage of moves that have a threat against the opponent out of the moves that are reduced by late move reduction(so they are not pruned by null move pruning after being reduced).

OK, I'll run some tests. Stay tuned.

I've now played four blitz games and collected statistics. The percentage of reduced depth searches which were aborted because the reduced move was found to **contain a threat** was close to 3% in all four games. This is less than I expected.

Tord

You probably mean:
"contain no threat" instead of "contain a threat" because in case of having a threat you do not abort reduced depth search.

Uri

[Dann Corbit]

{snip}
Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

Fruit (and hence Toga) along with Glaurung are the pioneers of late move (history) reduction based pruning. It has been found in Fruit for a long time.

Movei is using late move reduction before fruit and glaurung so fruit and glaurung are not the first to try the idea and find that it is productive(my guess is that some commercial programs are also using it before movei).

I guess that doing late move reduction only based on evaluation and not based on history counters can be better and I may try it.

Uri

i'm also using hp before fruit & Glaurung. I'm using it since febuary 2004.

daniel

It was (nontheless) popularized by Fruit and Glaurung.

I described the technique to a friend in 2000 (a Brazillian programmer who wrote a program called 'Adriano'), but that doesn't count either.