TalkChess.com

dchoman wrote: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

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

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

syzygy wrote:

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

dchoman wrote: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

Ferdy wrote:

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