MTD(f) experiments with Crafty

[Eric Stock]

Vincent, I just sent you a quick e-mail.

Thanks for your help!

I will be able to test the positions you send me using 7 minutes per move and I will record the search depths reached.

Currently, I have 3 versions of Crafty.
1. Crafty 23.0 unmodified
2. Crafty 23.0 null-move pruning disabled
3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

Tomorrow, I will create a 4th version of Crafty. I am going to modify null-move pruning to work with MTD(f) by preventing null moves to be included in the principal-variation which causes the fail-high or fail-low. If this cannot be done, then I will simply use null-move as it currently is in Crafty.

Aske Plaat mentions several variants of MTD in his thesis. I am aware of the idea of increasing the step size when repeatedly failing in one direction. Thus, you are jumping around to converge on the minmax value. I am very interested to try this.

You mention a technique of using a "bunch of windows" and that this technique is used by parSOS. I am a bit confused by this. I will look at Aske's thesis to see if he mentions this technique.

Lastly, I have now played over 800 games at 1 second per move with Crafty with no null-move vs MTD(f) Crafty with no null-move. The MTD(version) is at 51% to 49% for the PVS version.

Eric Stock

[Dann Corbit]

Vincent, I just sent you a quick e-mail.

Thanks for your help!

I will be able to test the positions you send me using 7 minutes per move and I will record the search depths reached.

Currently, I have 3 versions of Crafty.
1. Crafty 23.0 unmodified
2. Crafty 23.0 null-move pruning disabled
3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

Tomorrow, I will create a 4th version of Crafty. I am going to modify null-move pruning to work with MTD(f) by preventing null moves to be included in the principal-variation which causes the fail-high or fail-low. If this cannot be done, then I will simply use null-move as it currently is in Crafty.

Aske Plaat mentions several variants of MTD in his thesis. I am aware of the idea of increasing the step size when repeatedly failing in one direction. Thus, you are jumping around to converge on the minmax value. I am very interested to try this.

You mention a technique of using a "bunch of windows" and that this technique is used by parSOS. I am a bit confused by this. I will look at Aske's thesis to see if he mentions this technique.

Lastly, I have now played over 800 games at 1 second per move with Crafty with no null-move vs MTD(f) Crafty with no null-move. The MTD(version) is at 51% to 49% for the PVS version.

Eric Stock

It may also be interesting to see what an ultra-aggressive LMR does in MTD(f) as a replacement for null move pruning.

Generally, null move pruning just tosses out real stinkers (those moves worse than doing nothing).

LMR could possible be given a sliding or exponential scale to reduce depths for various moves that look bad.
For example:
reduction = constant * log(pv_node_ce - cadidate_ce);
or perhaps:
reduction = constant * cbrt(pv_node_ce - cadidate_ce);

where the pv node ce is from the current search and candidate ce is from the previous search.

I have always had a problem with the theory of null move pruning:
It is like falling off of a cliff. If a move is horrible, then we prune the heck out of it. But if it is slightly better than horrible, then we do nothing to it. And if it is truly an abomination, we do not prune it any more than if it were simply horrible. Other pruning methods (such as LMR) might prove a smoother gradient for thinning out bad moves.

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

[Eric Stock]

Dann, thanks for the suggestion. I do not have much knowledge of LMR other than a very basic overview of how it works. Crafty 23.0 has a simple implementation of it also. Actually, I think I read that Crafty 23.1 improved its LMR implementation.

reduction = constant * log(pv_node_ce - cadidate_ce);

Ok, I am a little unsure of what you mean here. I am guessing that pv_node_ce is the current best move at a given position in the search.

So candidate_ce would be retrieved from the hash table before searching? Or is this a static evaluation score?

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

A little confused here also. This code would keep the reduction factor within a min and max value. Could you explain this further? Crafty always R=3 reduction in null-move everywhere. What do you mean by "choppy"?

Thanks,
Eric Stock

[Dann Corbit]

Dann, thanks for the suggestion. I do not have much knowledge of LMR other than a very basic overview of how it works. Crafty 23.0 has a simple implementation of it also. Actually, I think I read that Crafty 23.1 improved its LMR implementation.

reduction = constant * log(pv_node_ce - cadidate_ce);

Ok, I am a little unsure of what you mean here. I am guessing that pv_node_ce is the current best move at a given position in the search.

So candidate_ce would be retrieved from the hash table before searching? Or is this a static evaluation score?

Hash score. If we do not already have a score at depth or cannot quickly create a good estimate, then we don't have a score to prune with. And I don't think we win anything at ply zero that I can imagine anyway.

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

A little confused here also. This code would keep the reduction factor within a min and max value. Could you explain this further? Crafty always R=3 reduction in null-move everywhere. What do you mean by "choppy"?

Thanks,
Eric Stock

By choppy, null move reduction typically has one or a few simple stair step values that go from perhaps a reduction of 1.5 to 3.5 plies in some search engines to a fixed value of 2 in some others.

I am just thinking that if null move fails in MTD(f), perhaps another pruning technique can work as well or better. And null move has a strange, non-continuous effect in almost all implementations, so another pruning attempt might even be better.

For instance, here is what Beowulf uses:

Code: Select all

   /*
    The formula below is from Ernst A. Heinz's book "Scalable Search in Computer Chess"
    It comes from pages 35-37 and is described elsewhere in the book.
    This method is called 'Adaptive Null Move Pruning' with R(adapt) = 3(6)~2.
    In English, the NULL move depth reduction is equal to two ply by default.  However,
    if either (a) both sides have fewer than 3 pieces and the current depth is 8 ply or
    more or (b) at least one side has greater than 2 pieces and the current depth is
    6 ply or more then increase the depth reduction to 3 full ply.
   */
//   return TWOPLY + (&#40;depth&#41; > (&#40;6*ONEPLY&#41; + ((&#40;cwp < 3 && cbp < 3&#41; ? TWOPLY &#58; 0&#41;)) ? ONEPLY &#58; 0&#41;;
  
   /* This is my own formula, offering scaleable search depth reduction between one and
    * 2.5 ply depending on the depth to which you are searching */
   return ONEPLY + &#40;depth > &#40;ONEPLY*8&#41; ? &#40;ONEPLY&#41; &#58; &#40;depth / ONEPLY&#41;) + (&#40;depth > ONEPLY&#41; ? &#40;HALFPLY&#41; &#58; &#40;0&#41;);

[diep]

Vincent, I just sent you a quick e-mail.

Thanks for your help!

I will be able to test the positions you send me using 7 minutes per move and I will record the search depths reached.

Currently, I have 3 versions of Crafty.
1. Crafty 23.0 unmodified
2. Crafty 23.0 null-move pruning disabled
3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

Tomorrow, I will create a 4th version of Crafty. I am going to modify null-move pruning to work with MTD(f) by preventing null moves to be included in the principal-variation which causes the fail-high or fail-low. If this cannot be done, then I will simply use null-move as it currently is in Crafty.

Aske Plaat mentions several variants of MTD in his thesis. I am aware of the idea of increasing the step size when repeatedly failing in one direction. Thus, you are jumping around to converge on the minmax value. I am very interested to try this.

You mention a technique of using a "bunch of windows" and that this technique is used by parSOS. I am a bit confused by this. I will look at Aske's thesis to see if he mentions this technique.

Lastly, I have now played over 800 games at 1 second per move with Crafty with no null-move vs MTD(f) Crafty with no null-move. The MTD(version) is at 51% to 49% for the PVS version.

Eric Stock

1. Crafty 23.0 unmodified

this is of course important.
also then 1.b crafty 23.0 unmodified with as only change MTD.

2. Crafty 23.0 null-move pruning disabled

Useless.

3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

you modified also someting to lazy eval and futility.
so to objectively compare you also need the exact same version with PVS.

if you'd compare the 3 crafty versions you just listed with each other that says absolutely nothing. for each version you need both a MTD version as well as the PVS equivalent of it.

If you toss out algorithms that much, instead of only pvs for mtd, then the only way to test your changes is by playing games against different opponents (so not crafty-crafty) and quite a lot and preferably not at 1 second a move, but really at least blitz level.

Probably differences are that big that a couple of hundreds is enough to measure the differences, as what you seem to modify is worth dozens, if not more, elopoints.

A very bad thing you want to avoid at all costs is to modify from 23.0 some things that work for 23.1 or newer very well; then modify pvs to mtd, and claim the improved elo is because of MTD.

Vincent

[diep]

Vincent, I just sent you a quick e-mail.

Thanks for your help!

I will be able to test the positions you send me using 7 minutes per move and I will record the search depths reached.

Currently, I have 3 versions of Crafty.
1. Crafty 23.0 unmodified
2. Crafty 23.0 null-move pruning disabled
3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

Tomorrow, I will create a 4th version of Crafty. I am going to modify null-move pruning to work with MTD(f) by preventing null moves to be included in the principal-variation which causes the fail-high or fail-low. If this cannot be done, then I will simply use null-move as it currently is in Crafty.

Aske Plaat mentions several variants of MTD in his thesis. I am aware of the idea of increasing the step size when repeatedly failing in one direction. Thus, you are jumping around to converge on the minmax value. I am very interested to try this.

You mention a technique of using a "bunch of windows" and that this technique is used by parSOS. I am a bit confused by this. I will look at Aske's thesis to see if he mentions this technique.

Lastly, I have now played over 800 games at 1 second per move with Crafty with no null-move vs MTD(f) Crafty with no null-move. The MTD(version) is at 51% to 49% for the PVS version.

Eric Stock

It may also be interesting to see what an ultra-aggressive LMR does in MTD(f) as a replacement for null move pruning.

Generally, null move pruning just tosses out real stinkers (those moves worse than doing nothing).

LMR could possible be given a sliding or exponential scale to reduce depths for various moves that look bad.
For example:
reduction = constant * log(pv_node_ce - cadidate_ce);
or perhaps:
reduction = constant * cbrt(pv_node_ce - cadidate_ce);

where the pv node ce is from the current search and candidate ce is from the previous search.

I have always had a problem with the theory of null move pruning:
It is like falling off of a cliff. If a move is horrible, then we prune the heck out of it. But if it is slightly better than horrible, then we do nothing to it. And if it is truly an abomination, we do not prune it any more than if it were simply horrible. Other pruning methods (such as LMR) might prove a smoother gradient for thinning out bad moves.

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

I feel your response is something for a different thread; but generally spoken i feel it is such an idiotic posting that i don't even need to react onto it.

Vincent

[Eric Stock]

Vincent, I forgot to include in the list Crafty 23.0 using MTD(f)

1. Crafty 23.0 unmodified

this is of course important.
also then 1.b crafty 23.0 unmodified with as only change MTD.

I have test results from these two versions. The Regular Crafty version is stronger. 54% vs 46% over 1000 games 1 second per move.

2. Crafty 23.0 null-move pruning disabled

Useless.

3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

you modified also someting to lazy eval and futility.
so to objectively compare you also need the exact same version with PVS.

Ok, I forgot to mention that both of these versions have null move pruning disabled. I had to modify the MTD(f) version since Crafty does not use Fail Soft return values in all situations and MTD(f) needs this.
Also, since MTD(f) does not search with a "window" around the minmax score I think the lazy eval cutoff value needs to be increased to avoid errors. I also think the futility pruning margins should be increased, but I haven't done this yet. So all the modifications to the MTD(f) version are ones I made only to allow the current algorithms in Crafty to work with MTD.

My thinking behind performing these tests is to see if null-move pruning works better with PVS compared with MTD(f) in Crafty.

Ok, today I am going to work on modifying null-move to work with MTD(f). If I have any luck with this I can test the full Crafty version against the MTD(f) version with modified null move.

Eric Stock

[bob]

Dann, thanks for the suggestion. I do not have much knowledge of LMR other than a very basic overview of how it works. Crafty 23.0 has a simple implementation of it also. Actually, I think I read that Crafty 23.1 improved its LMR implementation.

reduction = constant * log(pv_node_ce - cadidate_ce);

Ok, I am a little unsure of what you mean here. I am guessing that pv_node_ce is the current best move at a given position in the search.

So candidate_ce would be retrieved from the hash table before searching? Or is this a static evaluation score?

Hash score. If we do not already have a score at depth or cannot quickly create a good estimate, then we don't have a score to prune with. And I don't think we win anything at ply zero that I can imagine anyway.

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

A little confused here also. This code would keep the reduction factor within a min and max value. Could you explain this further? Crafty always R=3 reduction in null-move everywhere. What do you mean by "choppy"?

Thanks,
Eric Stock

By choppy, null move reduction typically has one or a few simple stair step values that go from perhaps a reduction of 1.5 to 3.5 plies in some search engines to a fixed value of 2 in some others.

I am just thinking that if null move fails in MTD(f), perhaps another pruning technique can work as well or better. And null move has a strange, non-continuous effect in almost all implementations, so another pruning attempt might even be better.

For instance, here is what Beowulf uses:

Code: Select all

   /*
    The formula below is from Ernst A. Heinz's book "Scalable Search in Computer Chess"
    It comes from pages 35-37 and is described elsewhere in the book.
    This method is called 'Adaptive Null Move Pruning' with R(adapt) = 3(6)~2.
    In English, the NULL move depth reduction is equal to two ply by default.  However,
    if either (a) both sides have fewer than 3 pieces and the current depth is 8 ply or
    more or (b) at least one side has greater than 2 pieces and the current depth is
    6 ply or more then increase the depth reduction to 3 full ply.
   */
//   return TWOPLY + (&#40;depth&#41; > (&#40;6*ONEPLY&#41; + ((&#40;cwp < 3 && cbp < 3&#41; ? TWOPLY &#58; 0&#41;)) ? ONEPLY &#58; 0&#41;;
  
   /* This is my own formula, offering scaleable search depth reduction between one and
    * 2.5 ply depending on the depth to which you are searching */
   return ONEPLY + &#40;depth > &#40;ONEPLY*8&#41; ? &#40;ONEPLY&#41; &#58; &#40;depth / ONEPLY&#41;) + (&#40;depth > ONEPLY&#41; ? &#40;HALFPLY&#41; &#58; &#40;0&#41;);

The comment above sounds backward. You normally want to use R=3, unless you are within a few plies of the tip, or there is little material left where zugzwang becomes more of a problem. Not R=3 near the tips and R=2 farther away.

[bob]

Vincent, I just sent you a quick e-mail.

Thanks for your help!

I will be able to test the positions you send me using 7 minutes per move and I will record the search depths reached.

Currently, I have 3 versions of Crafty.
1. Crafty 23.0 unmodified
2. Crafty 23.0 null-move pruning disabled
3. Crafty 23.0 Modified to use MTD(f) (Fail soft modifications, modifications to lazy-eval and futility pruning).

Tomorrow, I will create a 4th version of Crafty. I am going to modify null-move pruning to work with MTD(f) by preventing null moves to be included in the principal-variation which causes the fail-high or fail-low. If this cannot be done, then I will simply use null-move as it currently is in Crafty.

Aske Plaat mentions several variants of MTD in his thesis. I am aware of the idea of increasing the step size when repeatedly failing in one direction. Thus, you are jumping around to converge on the minmax value. I am very interested to try this.

You mention a technique of using a "bunch of windows" and that this technique is used by parSOS. I am a bit confused by this. I will look at Aske's thesis to see if he mentions this technique.

Lastly, I have now played over 800 games at 1 second per move with Crafty with no null-move vs MTD(f) Crafty with no null-move. The MTD(version) is at 51% to 49% for the PVS version.

Eric Stock

It may also be interesting to see what an ultra-aggressive LMR does in MTD(f) as a replacement for null move pruning.

Generally, null move pruning just tosses out real stinkers (those moves worse than doing nothing).

LMR could possible be given a sliding or exponential scale to reduce depths for various moves that look bad.
For example:
reduction = constant * log(pv_node_ce - cadidate_ce);
or perhaps:
reduction = constant * cbrt(pv_node_ce - cadidate_ce);

where the pv node ce is from the current search and candidate ce is from the previous search.

I have always had a problem with the theory of null move pruning:
It is like falling off of a cliff. If a move is horrible, then we prune the heck out of it. But if it is slightly better than horrible, then we do nothing to it. And if it is truly an abomination, we do not prune it any more than if it were simply horrible. Other pruning methods (such as LMR) might prove a smoother gradient for thinning out bad moves.

This misses the _main_ point of null-move. If a position is very good for me, so that even if I allow you to make two moves in a row and the position is _still_ good for me, then this position really is good for me and bad for you. Except when there is zugzwang. I'd be willing to play Kasparov if he would let me make two moves in a row a couple of times. Probably even once is enough. He would suddenly have to completely change the way he evaluates position since at any instant, I can choose to make two moves in a row. So he can leave no pieces open to a two-move threat, which is a real challenge. If I can attack any of your pieces in one move, I can win it if I so choose.

If it turns out that the null move reduction factors have a reason for excellence formulate the way that they are, perhaps it could be made choppy like null move with:
reduction = max(reduction, min_allowed_reduction);
reduction = min(reduction, max_allowed_reduction);

I don't follow the use of "null-move reduction vs null-move" in the above.

[adieguez]

This misses the _main_ point of null-move. If a position is very good for me, so that even if I allow you to make two moves in a row and the position is _still_ good for me, then this position really is good for me and bad for you. Except when there is zugzwang. I'd be willing to play Kasparov if he would let me make two moves in a row a couple of times. Probably even once is enough. He would suddenly have to completely change the way he evaluates position since at any instant, I can choose to make two moves in a row. So he can leave no pieces open to a two-move threat, which is a real challenge. If I can attack any of your pieces in one move, I can win it if I so choose.

hi, you have mentioned this in the past too several times. But this is not very accurate. Nullmove is saying there must be a move better than pass and nothing else. The prunning is at the middle of the two moves
you mention. The position which is really good for you that you mention may not even exist. Explainning nullmove that way looks not correct, it's just something curious while thinking about it.. imo