A search enhancement?

[dchoman]

I've been testing an idea for pruning or aborting a search in the middle of the movelist on a given node. I am not sure if this is a new idea... In fact, it is so simple, I would be surprised if it is new. A quick search of the chess progamming wiki shows a similar idea, "uncertainty cutoffs", which is more precise about when to terminate a node. The idea I tested makes no use of uncertainty and simply makes the decision of whether to abort based on position in the movelist.

The idea applies to nodes where we have searched a significant fraction of the moves already, so there is high probability the node will fail low. At this point, we simply abort the search and return alpha rather than continue trying the rest of the moves.

This seems quite drastic, and I expected it to be one of the many ideas that fail miserably, but I was pleasantly surprised that it seemed to be worth about +20 to +30 elo....

Code: Select all

Rank Name                  Elo    +    - games score oppo. draws 
   1 GNU Chess 6.0.1       100   10   10  3000   61%    19   18% 
   2 Arasan 14.0 (1 cpu)    57   10   10  3000   55%    19   21% 
   3 Crafty-21.6            56   10   10  3000   55%    19   22% 
   4 EXchess v2012_04_29    31    8    8  5000   50%    33   23% 
   5 EXchess v2012_04_28    24    8    8  5000   49%    33   24% 
   6 DoubleCheck 2.7        20   10   10  3000   50%    19   18% 
   7 EXchess vref            0    8    8  5000   46%    33   24% 
   8 EXchess v6.10         -66   10   10  3000   37%    19   40% 

EXchess vref is the current best version of my engine without this idea implemented. v2012_04_28 and v2012_04_29 have less and more agressive implementations of the idea respectively. The other engines are my current test opponents. The test games here are very fast (6s + 0.1s per move per side). The error bars here are 2 sigma (95% confidence).

The implementation is absolutely straight forward... essentially we wait until we get to the part of the movelist where we would normally be testing for LMR and pruning (after all good captures and killer moves), and we simply check what fraction of the moves have been played... if that fraction is larger than a certain amount, abort the search.

v2012_04_28 applies this with the equivalent of the following pseudo-code...

Code: Select all

// Search Abort Test
if&#40;depth < 5
   && !first_move_searched
   && !pos.check            // we are not in check
   && !next->pos.check      // current move doesn't cause check 
   && move.score < 2000000  // move scored below good captures & killers
   && alpha == beta - 1     // zero-window node 
   && alpha > -MATE/2       // not during a MATE resolution
   && 100*mcount > &#40;100-10*&#40;5-depth&#41;)*total_moves&#41;) 
&#123;
  clean-up and abort search by returning alpha
&#125;

v2012_04_29 applies it in the same way but at depth < 7 using

Code: Select all

if(100*mcount > (100-10*(7-depth))*total_moves))
 

which is quite a bit more agressive.

It is surprising to me that this works as well as it seems to... especially the more agressive version. Other than the two versions above, I've made no serious attempt to tune this up or try variations on the conditions, so it is possible there is more gain here to be had. Does anyone have experience with this type of idea? My best guesses for its apparent success are...

(1) Something about my implementation of LMR or pruning is not optimal, so this idea exploits some of the potential gain there.

(2) It somehow is covering up a bug in my engine

(3) It is actually an enhancement.

- Dan

[F. Bluemers]

I've been testing an idea for pruning or aborting a search in the middle of the movelist on a given node. I am not sure if this is a new idea... In fact, it is so simple, I would be surprised if it is new. A quick search of the chess progamming wiki shows a similar idea, "uncertainty cutoffs", which is more precise about when to terminate a node. The idea I tested makes no use of uncertainty and simply makes the decision of whether to abort based on position in the movelist.

The idea applies to nodes where we have searched a significant fraction of the moves already, so there is high probability the node will fail low. At this point, we simply abort the search and return alpha rather than continue trying the rest of the moves.

This seems quite drastic, and I expected it to be one of the many ideas that fail miserably, but I was pleasantly surprised that it seemed to be worth about +20 to +30 elo....

Code: Select all

Rank Name                  Elo    +    - games score oppo. draws 
   1 GNU Chess 6.0.1       100   10   10  3000   61%    19   18% 
   2 Arasan 14.0 (1 cpu)    57   10   10  3000   55%    19   21% 
   3 Crafty-21.6            56   10   10  3000   55%    19   22% 
   4 EXchess v2012_04_29    31    8    8  5000   50%    33   23% 
   5 EXchess v2012_04_28    24    8    8  5000   49%    33   24% 
   6 DoubleCheck 2.7        20   10   10  3000   50%    19   18% 
   7 EXchess vref            0    8    8  5000   46%    33   24% 
   8 EXchess v6.10         -66   10   10  3000   37%    19   40% 

EXchess vref is the current best version of my engine without this idea implemented. v2012_04_28 and v2012_04_29 have less and more agressive implementations of the idea respectively. The other engines are my current test opponents. The test games here are very fast (6s + 0.1s per move per side). The error bars here are 2 sigma (95% confidence).

The implementation is absolutely straight forward... essentially we wait until we get to the part of the movelist where we would normally be testing for LMR and pruning (after all good captures and killer moves), and we simply check what fraction of the moves have been played... if that fraction is larger than a certain amount, abort the search.

v2012_04_28 applies this with the equivalent of the following pseudo-code...

Code: Select all

// Search Abort Test
if&#40;depth < 5
   && !first_move_searched
   && !pos.check            // we are not in check
   && !next->pos.check      // current move doesn't cause check 
   && move.score < 2000000  // move scored below good captures & killers
   && alpha == beta - 1     // zero-window node 
   && alpha > -MATE/2       // not during a MATE resolution
   && 100*mcount > &#40;100-10*&#40;5-depth&#41;)*total_moves&#41;) 
&#123;
  clean-up and abort search by returning alpha
&#125;

v2012_04_29 applies it in the same way but at depth < 7 using

Code: Select all

if(100*mcount > (100-10*(7-depth))*total_moves))
 

which is quite a bit more agressive.

It is surprising to me that this works as well as it seems to... especially the more agressive version. Other than the two versions above, I've made no serious attempt to tune this up or try variations on the conditions, so it is possible there is more gain here to be had. Does anyone have experience with this type of idea? My best guesses for its apparent success are...

(1) Something about my implementation of LMR or pruning is not optimal, so this idea exploits some of the potential gain there.

(2) It somehow is covering up a bug in my engine

(3) It is actually an enhancement.

- Dan

Depends a bit on your moveordering if this is an good idea.
If you still have (bad SEE) captures or promotions in the tail of the list,this might not work so well.

Also:

Code: Select all

&& !next->pos.check      // current move doesn't cause check 

there might still be some (good) checking moves up next in your movelist...

[syzygy]

I've been testing an idea for pruning or aborting a search in the middle of the movelist on a given node. I am not sure if this is a new idea... In fact, it is so simple, I would be surprised if it is new. A quick search of the chess progamming wiki shows a similar idea, "uncertainty cutoffs", which is more precise about when to terminate a node. The idea I tested makes no use of uncertainty and simply makes the decision of whether to abort based on position in the movelist.

I think this is called Late Move Pruning (LMP) or Move Count Based Pruning. Here is a long thread on it.

[lucasart]

I've been testing an idea for pruning or aborting a search in the middle of the movelist on a given node. I am not sure if this is a new idea... In fact, it is so simple, I would be surprised if it is new. A quick search of the chess progamming wiki shows a similar idea, "uncertainty cutoffs", which is more precise about when to terminate a node. The idea I tested makes no use of uncertainty and simply makes the decision of whether to abort based on position in the movelist.

I think this is called Late Move Pruning (LMP) or Move Count Based Pruning. Here is a long thread on it.

Indeed, it's not new. But thanks for reminding me about it. I'm currently testing it in DoubleCheck, and it seems to be working quite well. Haven't run enough tests to measure a precise elo improvement but so far, the results are clear as day.

[zamar]

As others have pointed out, this is called "late move pruning" or "move count based pruning".

Used in all top programs nowadays.

[jdart]

Yes, this is pretty well-known and is used in quite a few programs. I have tried it recently and also gotten some improvement.

My logic currently is:

Code: Select all

       if&#40;depth <= 3*DEPTH_INCREMENT &&
          moveIndex > 3 + depth*depth/8 &&
          GetPhase&#40;move&#41; == MoveGenerator&#58;&#58;HISTORY_PHASE&#41; &#123;
          return PRUNE;
       &#125;

but this is also gated by a variable "pruneOk" that takes into account various other pruning conditions: i.e., side to move not in check, and move must not be a check, be a capture or non-standard move (castling or promotion), must not defend against a null move threat, etc.

In addition I also have history pruning which works at higher depths than this.

--Jon

[dchoman]

Thanks everyone for the reference to LMP. It indeed appears to be essentially the same idea. I do have one question. In LMP, does one make every move and then prune them each individually... or does the whole remainder of the movelist get pruned in one go after a certain point.... or do different implementations do it differently? The former (move by move) might be safer than what I was trying (remainder in one go). I was worrying about missing a good check or something late in the movelist (as another poster also pointed out) and the move by move approach would avoid that, although it would be slower.

Is there a preferred approach?

- Dan

[jdart]

The "move by move" approach is more usual, and required if you are checking per-move pruning conditions, which I would say is state of the art nowadays. Another issue is that frequently the estimated losing captures are at the end of the move list (at least I do it that way) and you may not want to prune captures except near very low depths. As usual though experimentation is needed to see exactly what pruning conditions are most effective.

--Jon

[Ferdy]

Thanks everyone for the reference to LMP. It indeed appears to be essentially the same idea. I do have one question. In LMP, does one make every move and then prune them each individually... or does the whole remainder of the movelist get pruned in one go after a certain point.... or do different implementations do it differently? The former (move by move) might be safer than what I was trying (remainder in one go). I was worrying about missing a good check or something late in the movelist (as another poster also pointed out) and the move by move approach would avoid that, although it would be slower.

Is there a preferred approach?

- Dan

I guess your idea is new, I have seen others just doing move prunning only, but yours is shall I say late move iteration prunning because you are prunning the whole iteration.
I tried your idea at higher depths and very late moves in move list without even bothering the depth specific value and got encouraging result.
There are some positions in the search that even a check move would not be able to do anything, so this approach is the solution.

[diep]

Thanks everyone for the reference to LMP. It indeed appears to be essentially the same idea. I do have one question. In LMP, does one make every move and then prune them each individually... or does the whole remainder of the movelist get pruned in one go after a certain point.... or do different implementations do it differently? The former (move by move) might be safer than what I was trying (remainder in one go). I was worrying about missing a good check or something late in the movelist (as another poster also pointed out) and the move by move approach would avoid that, although it would be slower.

Is there a preferred approach?

- Dan

I guess your idea is new, I have seen others just doing move prunning only, but yours is shall I say late move iteration prunning because you are prunning the whole iteration.
I tried your idea at higher depths and very late moves in move list without even bothering the depth specific value and got encouraging result.
There are some positions in the search that even a check move would not be able to do anything, so this approach is the solution.

Implementation technical you're correct, but that doesn't count as a 'new prunings idea' IMHO, as otherwise every different way to implement something also must be seen as a 'new algorithm', which is a simple way to total refute it as a new idea.

Note that i'd take the +30 elo.

Bit amazed he doesn't except for giving checks either.

For Diep any of this doesn't work currently, though i retest things like this every few years though.

A problem there is always that for example a move like Na6-c5, a simple shuffle move is going to improve the evaluation always more than what most pawncaptures add to the evaluation.