Diary
LMR in REBEL
edition 1 & 2
LMR is known to work best with a good move ordering, the better the move ordering the more safe the reductions will be and so before describring the LMR pseudo code I will first describe the current move ordering.
In short, move ordering is based on the PST score and updated with the result of the History Table. In C this gives the following structure:
struct move_gen
{ char from;
char to;
char flags;
unsigned char score;
} moves [MAX_MOVES];
Step-1 (move generation)
During move generation for each move the PST score is calculated and stored in score + 100. Since the PST's for move generation can not exceed a value of abs(100) we have created a range of 0-200 for move ordering based on PST. Values above 200 are reserved for move ordering (TT move, killers etc.)
Step-2 (move ordering)
After move generation all moves are ordered in a way that is pretty much standard in computer chess.
Value 255 - for the TT move
Value 252 - Killer move that produced a mate value in search
Value 246 - moves that capture the highest SEE value >0 (also known as winning capture)
Value 244 - moves that capture the second highest SEE value >0
Value 242 - moves that capture the third highest SEE value >0
Note-1: special care is taken in case 2 or more moves have a SEE > 0 value on the same square and the move that captures with the lowest piece will be searched first. From the 80's I remember this was good for some 5% speed-up.
Note-2: SEE (during move ordering) is cheap in REBEL since the evaluation function generates the 3 hanging pieces ordered by their SEE value as well as the sorted SEE value of the pieces it attacks. On the latter see the EFS project.
Value 241 - queen promotion (value already assigned in move generation)
Equal captures (SEE=0)
Value 236 - QxQ (values already assigned in move generation)
Value 235 - RxR
Value 234 - NxB
Value 233 - BxB
Value 232 - BxN
Value 231 - PxP
Note: Making a distinction between the possible equal captures (highest first) is good for move ordering.
Killers (REBEL uses 4)
Value 226 - Killer one
Value 224 - Killer two
Value 222 - Killer one from 2 plies back
Value 220 - Killer two from 2 plies back
Value 210 - castle short (value already assigned in move generation)
Value 209 - castle long (value already assigned in move generation)
Value 208 - mini promotion (value already assigned in move generation)
The quiet move part (generated moves with a PST value below 200)
They are updated with the value found in the [piece_type][to] history table resulting in a value between -20 and +20 that is added to score.
A bonus of 32 is added to score is given when a piece under attack (since we have that information from EVAL) moves.
As last step all quiet moves (including the 4 killer moves) are checked if they move to a safe square. If that's not the case score is penalized with 32. Again, this can be done because we have the needed information from EVAL available.
All in all we end up with a resonable well ordered move list. And score (instead of the usual move count) becomes an essential part of LMR.
LMR
pseudo code
If you have understood the move-ordering part and its numbers above the actual LMR code (I think) hardly needs further explanation.
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 (score >= 231) return; // no LMR when TT move | good captures etc. see above
if (king_in_check) return;
if (move_gives_check) return;
if (capture) 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 LMR
if (score >= 121) return; // move looks good
if (score >= 120 && depth>=7) return; // move too good for double LMR
if (score >= 115 && depth==6) return;
if (score >= 110 && depth==5) return;
if (score >= 105 && depth==4) return;
if (score >= 100 && depth==3) return;
reduction(); // reduce double
if (score < 90) reduction(); // reduce triple
}
Note, it's brandnew code. There is room for improvement, tuning the 100-121 numbers for double LMR and perhaps moving one step further, doing triple LMR. Furthermore it's high time to introduce fractional reductions and become more flexible as one full ply is pretty crude.
__________________________________________________________________________________________________
LMR
Another approach
edition 3
Instead of doing LMR via move-ordering as described above we try the values of the history table only.
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; }
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 (score >= 231) return; // no LMR when TT move | good captures etc. see above
if (king_in_check) return;
if (move_gives_check) return;
if (capture) 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:
As one can see from the code I only update the history table 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. However this is 2015 and some new research would be the right thing to do. But I must be patient, the idea needs to be fully tested first.
__________________________________________________________________________________________________
LMR
edition 4
Same as edition 3 with one change.
conditions for double, triple and quad LMR
value = H [piece] [square];
if (value < -500) reduction(); // reduce double
if (value < -1000) reduction(); // reduce triple
if (value < -1500 && depth >= 1) reduction(); // reduce quad
Ain't working. literally one bridge too far. Will have a look later.