LMR questions

[lucasart]

I'm trying to figure out what tha "correct" way of doing LMR actually is. I read again and again my code on LMR, and the more I read it, the less I understand it. So I rewrote it from scratch, and here's what I did. I also tried to make this code as clear as possible, because I don't want to spend hours again trying to figure out what I wrote and why...

Code: Select all

// move properties for reduction decision
const bool is_first = msl.idx == 1;
const bool is_capture = move_is_cop(ms->m);
const bool is_bad_see = ms->see < 0;
const int hscore = get_history&#40;B, ms->m&#41;;

// reduction decision
const bool is_bad_capture = is_capture && is_bad_see;
const bool is_bad_quiet = !is_capture && &#40;hscore < 0 || &#40;hscore == 0 && is_bad_see&#41;);
const bool reduce = !is_first && &#40;is_bad_capture || is_bad_quiet&#41;;

// reduced PVS
if (!is_pv || is_first&#41;
	// search full window
	score = -search&#40;B, -beta, -alpha, new_depth-reduce, ply+1, is_pv, si+1&#41;;
else /* if &#40;is_pv && !is_first&#41; */ &#123;
	// try zero window first
	score = -search&#40;B, -alpha-1, -alpha, new_depth-reduce, ply+1, false, si+1&#41;;
	if &#40;score > alpha&#41;
		score = -search&#40;B, -beta, -alpha, new_depth-reduce, ply+1, true, si+1&#41;;
&#125;
// verify LMR predicted beta cutoffs at PV nodes
if &#40;reduce && is_pv && score >= beta&#41;
	score = -search&#40;B, -beta, -alpha, new_depth, ply+1, is_pv, si+1&#41;;

So I basically reduce all moves after the first one, treating PV and non PV nodes the same way. Exceptions are (note that the word capture means actually capture or promotion here):
* captures with >= 0 SEE. In other words, bad captures are reduced, others aren't. In a way this also encompasses a kind of recapture extension, in the sense that recaptures (see > 0) are not reduced which, comparatively to bad captures, is an extension.
* non-captures are considered bad when
- they have a < 0 history score
- they have a zero history score, but a < 0 see. Indeed a quiet move, such as just putting a piece "en-prise", if it hasn't been searched before may not have an history score, but is generally a blunder when it has an see < 0.
* bad non-captures are reduced
* obviously the first move is not reduced, and there's a min depth condiotion,

Then I do a classical PVS with reduced depth. If a beta cutoff is predicted, I do a non-reduced verification search. The verification search should be rather fast because the reduced search has prepared the hash table, so at least the move ordering will perform well on that subtree.

I'm wondering if all that makes sense, and whether I should do PV dependant conditions such as:
* reduce after the i-th move where i is different for PV and non PV nodes
* do the verification search only at PV nodes

As usual, thoughts and constructive comments are welcome!
Thank you

[Desperado]

I'm trying to figure out what tha "correct" way of doing LMR actually is. I read again and again my code on LMR, and the more I read it, the less I understand it. So I rewrote it from scratch, and here's what I did. I also tried to make this code as clear as possible, because I don't want to spend hours again trying to figure out what I wrote and why...

Code: Select all

// move properties for reduction decision
const bool is_first = msl.idx == 1;
const bool is_capture = move_is_cop(ms->m);
const bool is_bad_see = ms->see < 0;
const int hscore = get_history&#40;B, ms->m&#41;;

// reduction decision
const bool is_bad_capture = is_capture && is_bad_see;
const bool is_bad_quiet = !is_capture && &#40;hscore < 0 || &#40;hscore == 0 && is_bad_see&#41;);
const bool reduce = !is_first && &#40;is_bad_capture || is_bad_quiet&#41;;

// reduced PVS
if (!is_pv || is_first&#41;
	// search full window
	score = -search&#40;B, -beta, -alpha, new_depth-reduce, ply+1, is_pv, si+1&#41;;
else /* if &#40;is_pv && !is_first&#41; */ &#123;
	// try zero window first
	score = -search&#40;B, -alpha-1, -alpha, new_depth-reduce, ply+1, false, si+1&#41;;
	if &#40;score > alpha&#41;
		score = -search&#40;B, -beta, -alpha, new_depth-reduce, ply+1, true, si+1&#41;;
&#125;
// verify LMR predicted beta cutoffs at PV nodes
if &#40;reduce && is_pv && score >= beta&#41;
	score = -search&#40;B, -beta, -alpha, new_depth, ply+1, is_pv, si+1&#41;;

So I basically reduce all moves after the first one, treating PV and non PV nodes the same way. Exceptions are (note that the word capture means actually capture or promotion here):
* captures with >= 0 SEE. In other words, bad captures are reduced, others aren't. In a way this also encompasses a kind of recapture extension, in the sense that recaptures (see > 0) are not reduced which, comparatively to bad captures, is an extension.
* non-captures are considered bad when
- they have a < 0 history score
- they have a zero history score, but a < 0 see. Indeed a quiet move, such as just putting a piece "en-prise", if it hasn't been searched before may not have an history score, but is generally a blunder when it has an see < 0.
* bad non-captures are reduced
* obviously the first move is not reduced, and there's a min depth condiotion,

Then I do a classical PVS with reduced depth. If a beta cutoff is predicted, I do a non-reduced verification search. The verification search should be rather fast because the reduced search has prepared the hash table, so at least the move ordering will perform well on that subtree.

I'm wondering if all that makes sense, and whether I should do PV dependant conditions such as:
* reduce after the i-th move where i is different for PV and non PV nodes
* do the verification search only at PV nodes

As usual, thoughts and constructive comments are welcome!
Thank you

Hello Lucas,

just some hints (thoughts) to think about.


1. how do you handle already _extended_ moves ?
2. how do you handle special moves (transMove,killers). Ok transMove is
clear because it should be the first move, but killers ? (hint, dont reduce them)
3. researching the fullwindow in pvs codeblock, is reduction needed at all.
if(value > alpha) research(-beta,-alpha,new_depth - _reduction_)
you may decide to _research immediatelly the full depth if alpha raises.
So you can merge this research with the lmr-research.
4. I guess you have a constant reduction. But if you use dynamic ones take
a closer look on the reduction depths of bad captures. They are mainly
at the end of the movelists, but may not be reduced stronger because of their
forced nature attributes. It _may_ hurt.
5. What you currently do looks more like a _badMove_ reduction instead of
_late_ move reduction. There arent any conditions neither to choose moves
later in the list nor to reduce later moves more aggressively. Because
it is neither nor, or in simple other words there is no parameter reflecting the
move count (late count) in any way (depth reduction amount nor the movecount number)

I didnt look too intensivley at you code, so maybe i missed sth.
But i think some of the points are worth to think about.

Michael


Edit:

6. Maybe PV-Nodes should imho be handled _more_ sensitive with respect
to the reduction condition or/and the reduction depth.

[lucasart]

Hello Lucas,

just some hints (thoughts) to think about.

1. how do you handle already _extended_ moves ?
2. how do you handle special moves (transMove,killers). Ok transMove is
clear because it should be the first move, but killers ? (hint, dont reduce them)
3. researching the fullwindow in pvs codeblock, is reduction needed at all.
if(value > alpha) research(-beta,-alpha,new_depth - _reduction_)
you may decide to _research immediatelly the full depth if alpha raises.
So you can merge this research with the lmr-research.
4. I guess you have a constant reduction. But if you use dynamic ones take
a closer look on the reduction depths of bad captures. They are mainly
at the end of the movelists, but may not be reduced stronger because of their
forced nature attributes. It _may_ hurt.
5. What you currently do looks more like a _badMove_ reduction instead of
_late_ move reduction. There arent any conditions neither to choose moves
later in the list nor to reduce later moves more aggressively. Because
it is neither nor, or in simple other words there is no parameter reflecting the
move count (late count) in any way (depth reduction amount nor the movecount number)

I didnt look too intensivley at you code, so maybe i missed sth.
But i think some of the points are worth to think about.

Michael

1. oops, thanks for that! I'll fix it asap. I had it in mind all along, so much that I forgot to write it when I coded
2. the trans move is not reduced, since it is always the first one. killer moves won't be reduced if they have a good history score, which is likely but not certain. i don't trust killers so much (except for move ordering), preferring instead the history heuristic. history and killer only apply to non captures in my code. I'll try excluding killer moves too.
3. good point!
4. I'll try with and without the bad capture stuff. Will see.
5. true. the move count condition is binary: reduce by 1 ply if not first move. that's it. I'd rather keep it simple to begin with, and be sure all the above points are adresses, then I'll experiment on this.

Thanks for your help. I'll go back to my testing with that

PS: I'm running a test with the above code, and it beats the previous version, despite point 1. Which either means it's not that bad reduce extended moves, or that my old code was completely wrong... or both !

[Evert]

I reduce moves based on the score they get after sorting the moves. In practice, that means I do not reduce hash moves, killers, winning captures, counter moves and queen promotions. I reduce everything else, but not if I'm in check.
If a reduced move fails high, it is re-searched without reductions.

I don't know whether that is "correct", but it seemed reasonable to me and it does seem to work.

[lucasart]

I reduce moves based on the score they get after sorting the moves. In practice, that means I do not reduce hash moves, killers, winning captures, counter moves and queen promotions. I reduce everything else, but not if I'm in check.
If a reduced move fails high, it is re-searched without reductions.

I don't know whether that is "correct", but it seemed reasonable to me and it does seem to work.

it makes perfect sense.

But thanks to my previous mistake, I've discovered that reducing extended moves is actually performing quite good!?
I need more testing though, as it seems very awkward.

[lkaufman]

I reduce moves based on the score they get after sorting the moves. In practice, that means I do not reduce hash moves, killers, winning captures, counter moves and queen promotions. I reduce everything else, but not if I'm in check.
If a reduced move fails high, it is re-searched without reductions.

I don't know whether that is "correct", but it seemed reasonable to me and it does seem to work.

What do you mean exactly by "counter moves"?

[Evert]

What do you mean exactly by "counter moves"?

It's a hybrid between a killer and the history heuristic. Whenever a move fails high, you store that move in a table indexed by the last move of the opponent. Then whenever the opponent plays that move again, you try the counter move before other quiet moves. If it fails high again, it becomes a killer at that ply.
Basically it's a way to transmit killers from one part of the tree to another part. It's not a big plus, but it helped a little when I tested it a year or so ago (possibly longer). I haven't re-tested it since.

[bob]

I reduce moves based on the score they get after sorting the moves. In practice, that means I do not reduce hash moves, killers, winning captures, counter moves and queen promotions. I reduce everything else, but not if I'm in check.
If a reduced move fails high, it is re-searched without reductions.

I don't know whether that is "correct", but it seemed reasonable to me and it does seem to work.

What do you mean exactly by "counter moves"?

Think this was an old idea from the 80's maybe. Think of a counter move as a "killer move" but it is associated with a single move for the opponent. If the opponent plays move m1, at the next ply you try m1c first. More specific than killers. Never worked for me, although regular killers are a significant win.

[lucasart]

Thought I should share some of my experimental results:
* PV condition: I have found that not reducing PV nodeas and reducing non PV nodes is harmful. This was to be expected, since any PV condition is theoretically unsound. However, I'm amazed to see how many programs do thias. Even Fruit ! So I reduce PV and non PV nodes exactly the same way
* My extensions are:
- forced move (1 legal move)
- in check
- pawn moving to the 7th rank with a non negative SEE (1)
* A move is reduced if:
- it is not extended
- it's not a killer move
- it's not a bad capture or a bad quiet move. bad capture = capture or promotion with < 0 SEE. bad quiet move = not(capt or prom) and (negative history score, or null history and negative SEE)
- the move number is > X
* testing suggest that the best value is X = 1 !

I'd be curious to know, what everyone thinks of that, and whether your experience concurs with my empirical results

(1) once I've finished, I'll try moving this condition to a non reduction rather than an extension.

[bob]

Thought I should share some of my experimental results:
* PV condition: I have found that not reducing PV nodeas and reducing non PV nodes is harmful. This was to be expected, since any PV condition is theoretically unsound. However, I'm amazed to see how many programs do thias. Even Fruit ! So I reduce PV and non PV nodes exactly the same way
* My extensions are:
- forced move (1 legal move)
- in check
- pawn moving to the 7th rank with a non negative SEE (1)
* A move is reduced if:
- it is not extended
- it's not a killer move
- it's not a bad capture or a bad quiet move. bad capture = capture or promotion with < 0 SEE. bad quiet move = not(capt or prom) and (negative history score, or null history and negative SEE)
- the move number is > X
* testing suggest that the best value is X = 1 !

I'd be curious to know, what everyone thinks of that, and whether your experience concurs with my empirical results

(1) once I've finished, I'll try moving this condition to a non reduction rather than an extension.

matches my cluster testing perfectly. Only thing different for me is I extend checks and nothing else...