Create a piece-type | square history table.
static int H [ 12 ] [ 64 ]; // declare history table H [piece] [destination square]
Table is cleared at the start of the search.
During search the history table H is updated for each move as follows:
if (ply <= 8 && move_is_no_capture)
{ if (move produces a better score) H[piece][square] += depth*depth;
else H[piece][square] -= depth;
if (abs(H[piece][square]) >= 2000) H[piece][square] /= 2; }
And so the values will always be in the range of -2000 | +2000.
Then LMR becomes really simple.
void lmr()
{ if (depth < 3) return; // no LMR in the last 3 plies before the horizon
if (move_count <= 3) return; // no LMR for the first 3 moves
if (TT move) return; // no LMR when TT move
if (capture) return;
if (queen promotion) return;
if (king_in_check) return;
if (move_gives_check) return;
if (white_pawn_moves_to_sixth_row_or_beyond) return;
if (black_pawn_moves_to_third_row_or_beyond) return;
reduction(); // reduce the search by one ply.
if (we_are_at_the_root) return; // we reduce root moves only once.
conditions for double and triple LMR
value = H [piece] [square];
if (value < -500) reduction(); // reduce double
if (value < -1500) reduction(); // reduce triple
}
Note: This simple approach should be good for some 30-50 elo.
As one can see from the code the history table is only updated for the first 8 plies because research from the past (somewhere in the 90's) learned me that using higher values the level of noise rapidly contaminates the values in the table.
__________________________________________________________________________________________________
LMR
advanced
There a practically a zillion of possibilities to improve on the above simple system and I will describe those additions to the above I am currently working on and things rapidly become complicated in the sense of finding the right combinations as most of the below instructions (marked with a *) are controlled by an on or off option.
void lmr()
{ if (depth < 3) return; // no LMR in the last 3 plies before the horizon
// Root moves:
// we maintain a list with the best moves during search. From iteration 8 and on moves that have been best
// are never reduced.
if (TT move) return; // no LMR when TT move
if (king_in_check) return;
if (queen promotion) return;
if (white_pawn_moves_to_sixth_row_or_beyond) return;
if (black_pawn_moves_to_third_row_or_beyond) return;
if (good capture) return; // SEE >=0
* if (bad capture) { reduce one ply; return; } // SEE <0
if (move_gives_check && good) return;
* if (move_gives_check && bad) { reduce one ply; return; }
// Evaluate R (the number of reductions)
// Step-1: get the initial R from a table [depth] [movecount], view, copy&paste the table from here.
a=depth; b=movecount; if (b>63) b=63;
R=lmr_tab[a][b];
// Step-2: get the value of the history table and based on the value modify R
value = H [piece] [square];
* if (value > 0) R--; // reduce less if the history move is positive
* if (value > 500) R--; // reduce less
* if (value > 1000) R--; // reduce less
* if (value > 1500) R--; // reduce less
* if (value < 0) R++; // reduce more if the history move is bad
* if (value < -500) R++; // reduce more
* if (value < -1000) R++; // reduce more
* if (value < -1500) R++; // reduce more
// Step-3: reduce less if the evaluation score of the position - a (small) margin is (still) better than ALPHA.
* if (evaluation score > ALPHA+margin) R--;
// Step-4: reduce less if the evaluation score - the board material is greater than a margin, currently set to 0.50.
// The idea is that if the color to move has a positional advantage of half a pawn then maybe it's not a
// good idea to reduce the move too much despite the material on the board.
* if (evaluation score - board_material > margin) R--;
// Step-5: reduce less if the current move itself creates a new threat such as h3 attacking the black knight on
// G4 with the white pawn. Attacking pawns don't count, only major pieces (N,B,R,Q). The move itself
// should not be bad (SEE<0)
* if (new_attacking_move) R--;
// Step-6: reduce less if the move escapes from a threat such as the example in step-5. Subtracting moves
// like Nf6 or moves that simply eliminate the threat on G4 should not be reduced too much. Pawns
// don't count, only major pieces (N,B,R,Q). The move itself should not be bad (SEE<0)
* if (hanging piece resolved) R--;
// Step-7: reduce less if the passed pawn evaluation has increased with a considerable margin in comparison
// to the previous ply, currently set to 0.25.
* if (passed_pawn_eval [current ply] - passed_pawn_eval [previous ply] >= margin) R--;
// Step-8: Do the same for King Safety, reduce less if the KS evaluation has increased with a considerable margin
// in comparison to the previous ply, currently set to 0.25.
* if (KS_eval [current ply] - KS_eval [previous ply] >= margin) R--;
// Step-9: reduce less if the overall evaluation (thus evaluation score - board material) has increased with a
// considerable margin in comparison to the previous ply, currently set to 0.50. Note the correlation
// with step 7 and 8.
* if (evaluation score [current ply] - evauation scorel [previous ply] >= margin) R--;
// Step-10: reduce more if the overall evaluation has decreased with a considerable margin in comparison to
// the previous ply, currently set to 0.50. Note the reverse correlation with step-9.
* if (evaluation score [previos ply] - evauation scorel [current ply] >= margin) R++;
// Step-11: reduce less if the current move is a killer move.
* if (move = killer_one || killer_two) R--;
// Step-12: reduce less if move has an excellent PST score.
* if (PST [piece_type] [to] - PST [piece_type] [from] >= margin) R--;
// We finally are there for the last step to calculate the final number of reductions for this move. We apply a
// percentage (P) for R currently set to 50% which makes R flexible.
P=50;
if (R>0) { printf("Reduce this move with %d plies", (R*P)/100);
That's it.
And a lot to test.
Notes:
The system can be improved by applying priorities for each of the 12 ingredients (steps). Instead of using R-- or R++ one can use R+=10 or R-=6 based on a multiply factor of 10 and then in the final calculation use (R*P)/1000);
The if (R>0) is actually needed else if R would end up negative the move will be extended instead of reduced. It would be fun to try that anyway.
__________________________________________________________________________________________________
LMR
expert
Mail me your LMR pseudo code and I will create a separate page for it.
or use the contact form to contact me.
LMR for starters
pseudo code