A search enhancement?

[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

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.

I tried to fix up the check thing last night and got another nice little improvement. I put detection of 'safe' checks into my move generation routine and these are now scored the same as killers, so they will go into the list above the point where the search might be aborted. After 5000 games today, it seems this change is +11 (+8,-8 at 95% conf) better than the previous best implementation. Still haven't tried the more traditional LMP version of pruning each move individually, but I will get around to that.

- Dan

[dchoman]

As an update, I've continued to improve my implementation. The net improvement appears to be in the range 50-60 elo in my fast game testing.

Code: Select all

Rank Name                  Elo    +    - games score oppo. draws 
   1 GNU Chess 6.0.1       108    8    7  6000   60%    34   18% 
   2 EXchess v2012_05_03    57    8    8  5000   54%    33   24% 
   3 Crafty-21.6            55    8    7  6000   53%    34   22% 
   4 EXchess v2012_05_02    50    8    8  5000   53%    33   25% 
   5 Arasan 14.0 (1 cpu)    47    8    8  6000   52%    34   21% 
   6 EXchess v2012_05_01    42    8    8  5000   52%    33   23% 
   7 EXchess v2012_04_29    31    8    8  5000   50%    33   23% 
   8 EXchess v2012_04_28    24    8    8  5000   49%    33   24% 
   9 DoubleCheck 2.7        20    8    8  6000   48%    34   19% 
  10 EXchess vref            0    8    8  5000   46%    33   24% 
  11 EXchess v6.10         -64    7    7  6000   35%    34   39% 

Beyond my previous description, v2012_05_01 added the detection of safe checks to move generation and placed these in the movelist with the killer moves so they would fall above the abort point and be searched every time. v2012_05_02 tweaked the fraction of the movelist where the abort decision is made (using CLOP, although more can be done, I think) as a function of depth. v2012_05_03 adds safe pawn pushes to the 7th rank with killer moves in the movelist so they also will fall above the abort point and be searched every time.

I still haven't tried the more usual LMP implementation of still working through the entire movelist and pruning moves one by one. That is on my list to try. Although it would be slower, it would allow greater flexibility for keeping different types of moves under different conditions and wouldn't require the kind of movelist re-ordering I've been doing (although some of the above gain may be from broader impacts of this movelist re-odering... not sure).

I also want to see if this kind of idea can be applied at higher depths. At what depths do people usually do LMP? Currently, I am only trying this below depth 7.

- Dan

[jdart]

At what depths do people usually do LMP

I do this below depth == 3 ply currently, although I also do history pruning, which you can consider a form of the same thing with the extra condition of a low history score, and that is enabled up to depth 10 ply, although as usual the cutoff threshold changes with depth so that pruning at high depths is less frequent. I am not sure this is optimal though.

--Jon

[zamar]

I also want to see if this kind of idea can be applied at higher depths. At what depths do people usually do LMP? Currently, I am only trying this below depth 7.

I think that the maximum depth to apply LMP is somewhere between 3 and 6 plies. Higher than this, it's better to use aggressive LMR rather than prune move completely.

[Uri Blass]

I do not see a reason not to use LMP at depths that are bigger than 6 plies.

I think that even aggresive LMR can cost significant number of nodes in part of the cases because a move may fail high and after research fail low.

If you are practically almost sure that the final result is going to be fail low(for example based on the fact that you already tried this move 10000 times at depth 7 in the search and it never failed high after research)
then it may be better to use LMP at depth 7 and not aggresive LMR.

[zamar]

I think that even aggresive LMR can cost significant number of nodes in part of the cases because a move may fail high and after research fail low.

If move fails high at low depth, it's usually a strong indicator that move is worth considering and should not be pruned.

If you are practically almost sure that the final result is going to be fail low(for example based on the fact that you already tried this move 10000 times at depth 7 in the search and it never failed high after research)
then it may be better to use LMP at depth 7 and not aggresive LMR.

I think this revolunatiory insight is worth a Nobel Prize.

[Uri Blass]

I think that even aggresive LMR can cost significant number of nodes in part of the cases because a move may fail high and after research fail low.

If move fails high at low depth, it's usually a strong indicator that move is worth considering and should not be pruned.

Or it may be an indicator that the position is simply improving for the opponent so the score at small depth is always bigger
than the score at high depth.

It suggest the idea to use LMR with initiallty bigger beta that means that you do not use LMR for some moves but you do not use window (beta-1 beta) but window (beta+x-1 beta+x) for some positive x that may be dependent on the history of the search and only if it fails high you research at bigger depth with bounds beta-1 beta.

[F. Bluemers]

As an update, I've continued to improve my implementation. The net improvement appears to be in the range 50-60 elo in my fast game testing.

Code: Select all

Rank Name                  Elo    +    - games score oppo. draws 
   1 GNU Chess 6.0.1       108    8    7  6000   60%    34   18% 
   2 EXchess v2012_05_03    57    8    8  5000   54%    33   24% 
   3 Crafty-21.6            55    8    7  6000   53%    34   22% 
   4 EXchess v2012_05_02    50    8    8  5000   53%    33   25% 
   5 Arasan 14.0 (1 cpu)    47    8    8  6000   52%    34   21% 
   6 EXchess v2012_05_01    42    8    8  5000   52%    33   23% 
   7 EXchess v2012_04_29    31    8    8  5000   50%    33   23% 
   8 EXchess v2012_04_28    24    8    8  5000   49%    33   24% 
   9 DoubleCheck 2.7        20    8    8  6000   48%    34   19% 
  10 EXchess vref            0    8    8  5000   46%    33   24% 
  11 EXchess v6.10         -64    7    7  6000   35%    34   39% 

Beyond my previous description, v2012_05_01 added the detection of safe checks to move generation and placed these in the movelist with the killer moves so they would fall above the abort point and be searched every time. v2012_05_02 tweaked the fraction of the movelist where the abort decision is made (using CLOP, although more can be done, I think) as a function of depth. v2012_05_03 adds safe pawn pushes to the 7th rank with killer moves in the movelist so they also will fall above the abort point and be searched every time.

Try searching "bad" promotions too

I still haven't tried the more usual LMP implementation of still working through the entire movelist and pruning moves one by one. That is on my list to try. Although it would be slower, it would allow greater flexibility for keeping different types of moves under different conditions and wouldn't require the kind of movelist re-ordering I've been doing (although some of the above gain may be from broader impacts of this movelist re-odering... not sure).

I also want to see if this kind of idea can be applied at higher depths. At what depths do people usually do LMP? Currently, I am only trying this below depth 7.

- Dan

I tried depth 3 (for some moves atleast),but that seemed to hurt strength a bit,also playstyle became ugly.
Best,Fonzy

[ZirconiumX]

I tried a similar thing in FruitFly.

My previous LMP was based on the Rodent conditions, viz:

Code: Select all

            if &#40;UseHistory && new_depth < depth && !in_check && !move_is_check&#40;move,board&#41;) &#123;
               
               if &#40;node_type != NodePV&#41; &#123;
                  // late move pruning
                  if &#40;depth <= HistoryDepth && played_nb > 12&#41; &#123;
		     if &#40;played_nb > 20&#41; continue; 		// Move Count Based Pruning
		     if &#40;sort->value < HistoryValue&#41; continue;	// History Pruning
                  &#125;
               &#125; else &#123;
                  // PV late move pruning
                  if &#40;depth <= HistoryDepth && played_nb > 30 && sort->value < HistoryValue&#41; continue;
                  
                  // PV late move reductions for a quiet move
                  if &#40;depth > HistoryDepth && played_nb > 7 && sort->value < HistoryValue&#41; &#123;
                     reduction = lmr_reduction&#40;played_nb&#41; / 2;
                     new_depth -= reduction;
                     reduced = true;
                  &#125;

		  // PV late move reductions for a capture
                  if &#40;depth > HistoryDepth && played_nb > HistoryMoveNb &&
				  move_is_capture&#40;move,board&#41; && !capture_is_good&#40;move,board&#41;) &#123;
                     reduction = 1;
                     new_depth -= reduction;
                     reduced = true;
                  &#125;
               &#125;
            &#125;

Note that I reduce and even, dare I say it, prune in PV nodes.

The above implementation got me the following figures, courtesy of Sigma Chess:

Code: Select all

Score : +0.31
Depth : 14/4
Time  : 00:00:29
Nodes : 5770000
N/sec : 197377
1. d4 Nf6 2. Nc3 e6 3. Nf3 Bb4 4. Bd2 Nc6 5. e3

Adding the condition:

Code: Select all

...
		     if &#40;sort->value < HistoryValue&#41; continue;	// History Pruning

		     if &#40;100 * played_nb > &#40;100 - 10 * &#40;4 - depth&#41;) * 35&#41; continue; // <---
...

Ah, the joys of having a clueless Move Generator (it has no idea how many moves it has just generated...), so I have had to use the average branching factor of 35 for chess. (I should probably bump it to 40 just to be safe).

Gives me these figures:

Code: Select all

Score : +0.20
Depth : 14/1
Time  : 00:00:30
Nodes : 3830000
N/sec : 126891
1. Nc3 Nf6 2. d4 e6 3. Nf3 Bb4 4. Bg5 Nc6 5. e3 a5 6. Bd3 O-O 7. Bf4

Which is a third reduction in nodes. However NPS has taken a big hit as you would expect, and has somehow managed to fall behind in searching moves (I managed depth 15 in tests)

Matthew:out