I'll try to "digest" that and run a test. Right now I am running some long games just to confirm that the last batch of LMR changes are no good regardless of the time control.hgm wrote:OK, I have a suggestion:
The main disadvantage of LMR seems to be that it tends to make the engine blind against threats in side branches. This is particularly bad in combination with null moves: if the opponent can mount a dangerous attack with a sequence of late moves, while I am null-moving all the time, there is a reduction of 2 or 3 for each of my moves, and a reduction of 1 (or 2) for each of his moves, and you need excessive nominal depth before you start to see the trouble coming.
The deminishing returns of combining null-move pruning and LMR might not only be from that they partly do the same, but from that together they actually overdo it.
So my suggestion is: do not apply the LMR reduction to the null-move search of the daughter. E.g. if you use null move with R=2, when a node is reached through a late move, you would normally reduce the null move by R=3, and when it fails low, reduce the other moves by 1, and only if all these fail low too, you would search them unreduced (because the late move below you now fails high, and you take the reduction away.)
What I propose is to keep the reduction of the null move at R=2, but when it fails low, reduce all the normal moves still by 1.
This should make you much less blind. And my suspicion is that it would be comparatively cheap, because I already did try the opposite: only reduce the null move one extra after a late move, and switch to normal depth immediately when it fails low. This hardly produced any reduction of the tree size for the same nominal depth. Apparently the branches with null moves are already so much reduced, that they hrdly contribute to the node count of the tree, and reducing them further has no measurable effect on tree size, but a very detrimental effect on playing strength! So you might as well extend them, in the hope that the opposite will hold.
LMR revisited.
Moderators: hgm, Rebel, chrisw
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR revisited.
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR revisited.
I've tested this every which way. Including calling static eval and double-reduce when the static eval is _way_ below alpha. Made no difference at all in the actual performance, short or long time controls...Don wrote:It works for me. As I said before, I reduce by 1 until I'm later in the list then I reduce by 2. So each move gets 0, 1 or 2 reductions.bob wrote:That is the L in LMR in fact, although I have tried this as well. So far, nothing significant has happened with the idea of reducing "later" moves more.Kempelen wrote:More ideas: The tree searched is like a triangle. What about if we based reductions deph based on how far are we from the left side (that is, the pv). More far more reduction....
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR revisited.
I am also toying with an LMR search using an offset window. Lower the window and reduce the depth. The lowered window has the opportunity to find that a reduced move still wants to fail high, then the normal re-search with normal depth will see if it is really better. Seems interesting, has some plusses, has to pass the "match test" first...bob wrote:I'll try to "digest" that and run a test. Right now I am running some long games just to confirm that the last batch of LMR changes are no good regardless of the time control.hgm wrote:OK, I have a suggestion:
The main disadvantage of LMR seems to be that it tends to make the engine blind against threats in side branches. This is particularly bad in combination with null moves: if the opponent can mount a dangerous attack with a sequence of late moves, while I am null-moving all the time, there is a reduction of 2 or 3 for each of my moves, and a reduction of 1 (or 2) for each of his moves, and you need excessive nominal depth before you start to see the trouble coming.
The deminishing returns of combining null-move pruning and LMR might not only be from that they partly do the same, but from that together they actually overdo it.
So my suggestion is: do not apply the LMR reduction to the null-move search of the daughter. E.g. if you use null move with R=2, when a node is reached through a late move, you would normally reduce the null move by R=3, and when it fails low, reduce the other moves by 1, and only if all these fail low too, you would search them unreduced (because the late move below you now fails high, and you take the reduction away.)
What I propose is to keep the reduction of the null move at R=2, but when it fails low, reduce all the normal moves still by 1.
This should make you much less blind. And my suspicion is that it would be comparatively cheap, because I already did try the opposite: only reduce the null move one extra after a late move, and switch to normal depth immediately when it fails low. This hardly produced any reduction of the tree size for the same nominal depth. Apparently the branches with null moves are already so much reduced, that they hrdly contribute to the node count of the tree, and reducing them further has no measurable effect on tree size, but a very detrimental effect on playing strength! So you might as well extend them, in the hope that the opposite will hold.
-
diep
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: LMR revisited.
I tried this extensively in 2004/2005 for like 6 months in all kind of ways and different ideas. Whatever i tried there, never could get it to work.bob wrote:I am also toying with an LMR search using an offset window. Lower the window and reduce the depth. The lowered window has the opportunity to find that a reduced move still wants to fail high, then the normal re-search with normal depth will see if it is really better. Seems interesting, has some plusses, has to pass the "match test" first...bob wrote:I'll try to "digest" that and run a test. Right now I am running some long games just to confirm that the last batch of LMR changes are no good regardless of the time control.hgm wrote:OK, I have a suggestion:
The main disadvantage of LMR seems to be that it tends to make the engine blind against threats in side branches. This is particularly bad in combination with null moves: if the opponent can mount a dangerous attack with a sequence of late moves, while I am null-moving all the time, there is a reduction of 2 or 3 for each of my moves, and a reduction of 1 (or 2) for each of his moves, and you need excessive nominal depth before you start to see the trouble coming.
The deminishing returns of combining null-move pruning and LMR might not only be from that they partly do the same, but from that together they actually overdo it.
So my suggestion is: do not apply the LMR reduction to the null-move search of the daughter. E.g. if you use null move with R=2, when a node is reached through a late move, you would normally reduce the null move by R=3, and when it fails low, reduce the other moves by 1, and only if all these fail low too, you would search them unreduced (because the late move below you now fails high, and you take the reduction away.)
What I propose is to keep the reduction of the null move at R=2, but when it fails low, reduce all the normal moves still by 1.
This should make you much less blind. And my suspicion is that it would be comparatively cheap, because I already did try the opposite: only reduce the null move one extra after a late move, and switch to normal depth immediately when it fails low. This hardly produced any reduction of the tree size for the same nominal depth. Apparently the branches with null moves are already so much reduced, that they hrdly contribute to the node count of the tree, and reducing them further has no measurable effect on tree size, but a very detrimental effect on playing strength! So you might as well extend them, in the hope that the opposite will hold.
Using different windows each time is very complicated and expensive for the search. The overhead is too much.
-
bob
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR revisited.
I'm not seeing any overhead, other than as the window is offset downward, you naturally get more fail-highs and have to re-search the reduced move, but to normal depth. Whether this will help or not is a guess. My hope is to find a reasonable offset so that potentially good moves that would normally fail low on the reduced search now fail high, causing a normal-depth search. More after a few million games are done.diep wrote:I tried this extensively in 2004/2005 for like 6 months in all kind of ways and different ideas. Whatever i tried there, never could get it to work.bob wrote:I am also toying with an LMR search using an offset window. Lower the window and reduce the depth. The lowered window has the opportunity to find that a reduced move still wants to fail high, then the normal re-search with normal depth will see if it is really better. Seems interesting, has some plusses, has to pass the "match test" first...bob wrote:I'll try to "digest" that and run a test. Right now I am running some long games just to confirm that the last batch of LMR changes are no good regardless of the time control.hgm wrote:OK, I have a suggestion:
The main disadvantage of LMR seems to be that it tends to make the engine blind against threats in side branches. This is particularly bad in combination with null moves: if the opponent can mount a dangerous attack with a sequence of late moves, while I am null-moving all the time, there is a reduction of 2 or 3 for each of my moves, and a reduction of 1 (or 2) for each of his moves, and you need excessive nominal depth before you start to see the trouble coming.
The deminishing returns of combining null-move pruning and LMR might not only be from that they partly do the same, but from that together they actually overdo it.
So my suggestion is: do not apply the LMR reduction to the null-move search of the daughter. E.g. if you use null move with R=2, when a node is reached through a late move, you would normally reduce the null move by R=3, and when it fails low, reduce the other moves by 1, and only if all these fail low too, you would search them unreduced (because the late move below you now fails high, and you take the reduction away.)
What I propose is to keep the reduction of the null move at R=2, but when it fails low, reduce all the normal moves still by 1.
This should make you much less blind. And my suspicion is that it would be comparatively cheap, because I already did try the opposite: only reduce the null move one extra after a late move, and switch to normal depth immediately when it fails low. This hardly produced any reduction of the tree size for the same nominal depth. Apparently the branches with null moves are already so much reduced, that they hrdly contribute to the node count of the tree, and reducing them further has no measurable effect on tree size, but a very detrimental effect on playing strength! So you might as well extend them, in the hope that the opposite will hold.
Using different windows each time is very complicated and expensive for the search. The overhead is too much.
I'm seeing some promise here however, in that this offset can be adjusted to significantly speed up tactical positions. Real game testing is next on the list, after the current longish-game test is done.
-
jarkkop
- Posts: 198
- Joined: Thu Mar 09, 2006 2:44 am
- Location: Helsinki, Finland
Re: LMR revisited.
Try and test the code below inspired by strelka . Quick test gave about 30 ELO. All pure Crafty code.
and
Code: Select all
if (first_move) {
if (depth - 1 + extensions > 0)
if(Check(wtm))
value = -SearchCheck(tree, -beta, -alpha, Flip(wtm), depth - 1 + extensions, 2, DO_NULL);
else
value = -Search(tree, -beta, -alpha, Flip(wtm), depth - 1 + extensions, 2, DO_NULL);
else
value = -QuiesceChecks(tree, -beta, -alpha, Flip(wtm), 2);
first_move = 0;
} else {
if (depth - 1 + extensions > 0) {
if(Check(wtm))
value = -SearchCheck(tree, -alpha - 1, -alpha, Flip(wtm), depth - 1 + extensions, 2, DO_NULL);
else
value = -Search(tree, -alpha - 1, -alpha, Flip(wtm), depth - 1 + extensions, 2, DO_NULL);
if (value > alpha && extensions < 0)
value = -Search(tree, -alpha - 1, -alpha, Flip(wtm), depth - 1, 2, DO_NULL);
} else
value = -QuiesceChecks(tree, -alpha - 1, -alpha, Flip(wtm), 2);
if (abort_search)
break;
if ((value > alpha) && (value < beta)) {
extensions = Max(extensions, 0);
if (depth - 1 + extensions > 0)
value = -Search(tree, -beta, -alpha, Flip(wtm), depth - 1 + extensions, 2, DO_NULL);
else
value = -QuiesceChecks(tree, -beta, -alpha, Flip(wtm), 2);
}
}
and
Code: Select all
int SearchCheck(TREE * RESTRICT tree, int alpha, int beta, int wtm, int depth, int ply, int do_null) {
register BITBOARD start_nodes = tree->nodes_searched;
register int moves_searched = 0;
register int o_alpha, value = 0, t_beta = beta;
register int extensions, extended, pieces;
register int fprune;
/*
************************************************************
* *
* Check to see if we have searched enough nodes that it *
* is time to peek at how much time has been used, or if *
* is time to check for operator keyboard input. This is *
* usually enough nodes to force a time/input check about *
* once per second, except when the target time per move *
* is very small, in which case we try to check the time *
* at least 10 times during the search. *
* *
* Note that we check for timeout in all active threads, *
* but we only do I/O in thread 0 to avoid read race *
* conditions that are problematic. *
* *
************************************************************
*/
tree->nodes_searched++;
#if defined(NODES)
temp_search_nodes--;
if (temp_search_nodes <= 0) {
time_abort++;
abort_search = 1;
return (0);
}
#endif
if (--next_time_check <= 0) {
next_time_check = nodes_between_time_checks;
if (TimeCheck(tree, 0)) {
time_abort++;
abort_search = 1;
return (0);
}
if (tree->thread_id == 0) {
if (CheckInput())
Interrupt(ply);
}
}
if (ply >= MAXPLY - 1)
return (beta);
/*
************************************************************
* *
* Check for draw by repetition. *
* *
************************************************************
*/
if (RepetitionCheck(tree, ply, wtm)) {
value = DrawScore(wtm);
if (value < beta)
SavePV(tree, ply, 0);
#if defined(TRACE)
if (ply <= trace_level)
printf("draw by repetition detected, ply=%d.\n", ply);
#endif
return (value);
}
/*
************************************************************
* *
* Now call HashProbe() to see if this position has been *
* searched before. If so, we may get a real score, *
* produce a cutoff, or get nothing more than a good move *
* to try first. There are four cases to handle: *
* *
* 1. HashProbe() returns "EXACT" if this score is *
* greater than beta, return beta. Otherwise, return the *
* score. In either case, no further searching is needed *
* from this position. Note that lookup verified that *
* the table position has sufficient "draft" to meet the *
* requirements of the current search depth remaining. *
* *
* 2. HashProbe() returns "UPPER" which means that when *
* this position was searched previously, every move was *
* "refuted" by one of its descendents. As a result, *
* when the search was completed, we returned alpha at *
* that point. We simply return alpha here as well. *
* *
* 3. HashProbe() returns "LOWER" which means that when *
* we encountered this position before, we searched one *
* branch (probably) which promptly refuted the move at *
* the previous ply. *
* *
* 4. HashProbe() returns "AVOID_NULL_MOVE" which means *
* the hashed score/bound was no good, but it indicated *
* that trying a null-move in this position would be a *
* waste of time since it will likely fail low, not high. *
* *
************************************************************
*/
switch (HashProbe(tree, ply, depth, wtm, &alpha, beta)) {
case EXACT:
if (alpha < beta)
SavePV(tree, ply, 1);
return (alpha);
case EXACTEGTB:
if (alpha < beta)
SavePV(tree, ply, 2);
return (alpha);
case LOWER:
return (beta);
case UPPER:
return (alpha);
case AVOID_NULL_MOVE:
do_null = 0;
}
/*
************************************************************
* *
* Now it's time to try a probe into the endgame table- *
* base files. This is done if we notice that there are *
* 6 or fewer pieces left on the board. EGTB_use tells *
* us how many pieces to probe on. Note that this can be *
* zero when trying to swindle the opponent, so that no *
* probes are done since we know it is a draw. *
* *
************************************************************
*/
#if !defined(NOEGTB)
if (ply <= iteration_depth && TotalAllPieces <= EGTB_use &&
Castle(ply, white) + Castle(ply, black) == 0 &&
(CaptureOrPromote(tree->curmv[ply - 1]) || ply < 3)) {
int egtb_value;
tree->egtb_probes++;
if (EGTBProbe(tree, ply, wtm, &egtb_value)) {
tree->egtb_probes_successful++;
alpha = egtb_value;
if (abs(alpha) > MATE - 300)
alpha += (alpha > 0) ? -ply + 1 : ply;
else if (alpha == 0) {
alpha = DrawScore(wtm);
if (Material > 0)
alpha += (wtm) ? 1 : -1;
else if (Material < 0)
alpha -= (wtm) ? 1 : -1;
}
if (alpha < beta)
SavePV(tree, ply, 2);
tree->pv[ply].pathl = 0;
HashStore(tree, ply, MAX_DRAFT, wtm, EXACT, alpha,
tree->pv[ply].path[ply]);
return (alpha);
}
}
#endif
/*
************************************************************
* *
* Now iterate through the move list and search the *
* resulting positions. Note that Search() culls any *
* move that is not legal by using Check(). The special *
* case is that we must find one legal move to search to *
* confirm that it's not a mate or draw. *
* *
* First step is to see if we need to extend this move *
* for some tactical reason. If not, we check to see if *
* we can reduce the depth (LMR) to save time. A final *
* case is to determine if we can use AEL pruning *
* (Heinz 2000) near the search frontier. Note for those *
* that have read Heinz's paper. Frontier nodes in *
* crafty have a depth = 2. Pre-frontier nodes have a *
* depth = 3. And finally, pre-pre-frontier nodes have a *
* depth = 4. *
* *
************************************************************
*/
tree->next_status[ply].phase = HASH_MOVE;
// if(tree->inchk[ply])
// tree->phase[ply] = NextEvasion(tree, ply, wtm)
while (tree->phase[ply] = NextEvasion(tree, ply, wtm)) {
#if defined(TRACE)
if (ply <= trace_level)
Trace(tree, ply, depth, wtm, alpha, beta, "Search2", tree->phase[ply]);
#endif
MakeMove(tree, ply, tree->curmv[ply], wtm);
if (tree->inchk[ply] || !Check(wtm))
do {
extended = SearchExtensions(tree, wtm, ply, depth);
extensions = extended - 1;
fprune = 0;
if (depth + extensions > 0){
if (Check(wtm))
value = -SearchCheck(tree, -beta, -alpha, Flip(wtm), depth + extensions, ply + 1, DO_NULL);
else
value = -Search(tree, -beta, -alpha, Flip(wtm), depth + extensions, ply + 1, DO_NULL);
}else
value = -QuiesceChecks(tree, -beta, -alpha, Flip(wtm), ply + 1);
if (abort_search || tree->stop)
break;
if (value > alpha) {
if (value >= beta) {
Killer(tree, ply, tree->curmv[ply]);
UnmakeMove(tree, ply, tree->curmv[ply], wtm);
HashStore(tree, ply, depth, wtm, LOWER, value, tree->curmv[ply]);
tree->fail_high++;
if (!moves_searched)
tree->fail_high_first++;
return (value);
}
alpha = value;
}
t_beta = alpha + 1;
moves_searched++;
} while (0);
else
tree->nodes_searched++;
UnmakeMove(tree, ply, tree->curmv[ply], wtm);
if (abort_search || tree->stop)
return (0);
/*
************************************************************
* *
* If this is an SMP search, and we have idle processors, *
* now is the time to get them involved. We have now *
* satisfied the "young brothers wait" condition since we *
* have searched one move. All that is left is to check *
* the size of the tree we have searched so far, so that *
* we do not split too near the tips and drive up the *
* overhead unacceptably. This has the additional effect *
* that we might split after 2-3 moves have been searched *
* which might sound like an issue, but the overhead is *
* not so critical if we are more certain that we need to *
* actually search every move. The more moves we have *
* searched, the greater the probability that we are *
* going to search them all. *
* *
************************************************************
*/
#if (CPUS > 1)
if (smp_idle && moves_searched &&
tree->nodes_searched - start_nodes > smp_split_nodes) {
tree->alpha = alpha;
tree->beta = beta;
tree->value = alpha;
tree->wtm = wtm;
tree->ply = ply;
tree->depth = depth;
if (Thread(tree)) {
if (abort_search || tree->stop)
return (0);
if (tree->thread_id == 0 && CheckInput())
Interrupt(ply);
value = tree->search_value;
if (value > alpha) {
if (value >= beta) {
Killer(tree, ply, tree->cutmove);
HashStore(tree, ply, depth, wtm, LOWER, value, tree->cutmove);
tree->fail_high++;
return (value);
}
alpha = value;
break;
}
}
}
#endif
}
/*
************************************************************
* *
* All moves have been searched. If none were legal, *
* return either MATE or DRAW depending on whether the *
* side to move is in check or not. *
* *
************************************************************
*/
if (moves_searched == 0) {
value = (Check(wtm)) ? -(MATE - ply) : DrawScore(wtm);
if (value >= alpha && value < beta) {
SavePV(tree, ply, 0);
#if defined(TRACE)
if (ply <= trace_level)
printf("Search() no moves! ply=%d\n", ply);
#endif
}
return (value);
} else {
int bestmove = (alpha == o_alpha) ? 0 : tree->pv[ply].path[ply];
int type = (alpha == o_alpha) ? UPPER : EXACT;
if (alpha != o_alpha) {
memcpy(&tree->pv[ply - 1].path[ply], &tree->pv[ply].path[ply],
(tree->pv[ply].pathl - ply + 1) * sizeof(int));
memcpy(&tree->pv[ply - 1].pathh, &tree->pv[ply].pathh, 3);
tree->pv[ply - 1].path[ply - 1] = tree->curmv[ply - 1];
Killer(tree, ply, tree->pv[ply].path[ply]);
}
HashStore(tree, ply, depth, wtm, type, alpha, bestmove);
return (alpha);
}
}