Hello. I'm trying to decide if I need to add conditions for reduce killer moves in LMR. If I set a condition on the LMR to have searched 5 or more moves do I still need the killer move condition? or will move ordering take care of it? Im thinking I need some kind of condition to not reduce the killer moves.
Im having some difficulty in figuring out how to write that condition (!killer_move). Could anyone please help with how to write a condition for not a killer move in this if I need one? Here is some simple code from the move ordering section:
if (searching_pv) {
searching_pv = FALSE;
for (i = 0; i < num_moves; i++) {
from = moves[i].from;
target = moves[i].target;
promoted = moves[i].promoted;
captured = moves[i].captured;
/* give captures precedence in move ordering, and order captures by
material gain */
if (captured != npiece)
move_ordering[i] = cap_values[captured]-cap_values[board[from]]+1000;
else
move_ordering[i] = 0;
/* make sure the suggested hash move gets ordered high: */
if (from == h_move->from && target == h_move->target
&& promoted == h_move->promoted) {
move_ordering[i] += INF-10000;
}
/* make the pv have highest move ordering: */
if (from == pv[1][ply].from && target == pv[1][ply].target
&& promoted == pv[1][ply].promoted) {
searching_pv = TRUE;
move_ordering[i] += INF;
}
/* heuristics other than pv (no need to use them on the pv move - it is
already ordered highest) */
else {
/* add the history heuristic bonus: */
move_ordering[i] += (history_h[from][target]>>i_depth);
/* add the killer move heuristic bonuses: */
if (from == killer1[ply].from && target == killer1[ply].target
&& promoted == killer1[ply].promoted)
move_ordering[i] += 1000;
else if (from == killer2[ply].from && target == killer2[ply].target
&& promoted == killer2[ply].promoted)
move_ordering[i] += 500;
else if (from == killer3[ply].from && target == killer3[ply].target
&& promoted == killer3[ply].promoted)
move_ordering[i] += 250;
}
}
}
I have tried adding (if moves.from == 0) in a test and the LMR got no hits at all. Same for others so I must be writing the condition wrong or something. I would really appreciate any help or advice you could give!
outAtime wrote:Hello. I'm trying to decide if I need to add conditions for reduce killer moves in LMR. If I set a condition on the LMR to have searched 5 or more moves do I still need the killer move condition? or will move ordering take care of it? Im thinking I need some kind of condition to not reduce the killer moves.
Im having some difficulty in figuring out how to write that condition (!killer_move). Could anyone please help with how to write a condition for not a killer move in this if I need one? Here is some simple code from the move ordering section:
if (searching_pv) {
searching_pv = FALSE;
for (i = 0; i < num_moves; i++) {
from = moves[i].from;
target = moves[i].target;
promoted = moves[i].promoted;
captured = moves[i].captured;
/* give captures precedence in move ordering, and order captures by
material gain */
if (captured != npiece)
move_ordering[i] = cap_values[captured]-cap_values[board[from]]+1000;
else
move_ordering[i] = 0;
/* make sure the suggested hash move gets ordered high: */
if (from == h_move->from && target == h_move->target
&& promoted == h_move->promoted) {
move_ordering[i] += INF-10000;
}
/* make the pv have highest move ordering: */
if (from == pv[1][ply].from && target == pv[1][ply].target
&& promoted == pv[1][ply].promoted) {
searching_pv = TRUE;
move_ordering[i] += INF;
}
/* heuristics other than pv (no need to use them on the pv move - it is
already ordered highest) */
else {
/* add the history heuristic bonus: */
move_ordering[i] += (history_h[from][target]>>i_depth);
/* add the killer move heuristic bonuses: */
if (from == killer1[ply].from && target == killer1[ply].target
&& promoted == killer1[ply].promoted)
move_ordering[i] += 1000;
else if (from == killer2[ply].from && target == killer2[ply].target
&& promoted == killer2[ply].promoted)
move_ordering[i] += 500;
else if (from == killer3[ply].from && target == killer3[ply].target
&& promoted == killer3[ply].promoted)
move_ordering[i] += 250;
}
}
}
I have tried adding (if moves.from == 0) in a test and the LMR got no hits at all. Same for others so I must be writing the condition wrong or something. I would really appreciate any help or advice you could give!
In crafty, I have several chained "selection states". It starts off with "hash_move", then "generate captures" followed by "search captures", then "killers" and then "rest_of_moves". I only reduce moves in "rest of moves" and apply restrictions there so that not all of those are reduced.
Sounds interesting! I don't know how I could implement this type of idea for myself though. Im only working with 2 main searches, root_search and search . Ive looked at stockfish, which has all kinds of searches: search_pv, search_root, search etc... Im somewhat confused by the vast number of different searches some, if not most engines do. I have trouble figuring out if the search_root Im working with is a mixture of search_pv and search_root (in stockfish) or what. All I know is in the search_root Im working on, searching PV = TRUE. So for now Im just doing a full width search there, but it actually calls search() e.g. (root_score = -search) so its almost like only one search or something. Most other programs have a different routine for each section. For now im doing all the LMR in search() although I dont know yet what difference it makes if I do it in search() or search_root(), or both for that matter, all approaches allow the engine to search. Im just trying to figure out if Im reducing the killer moves or not. If I am, then I need to write some kind of condition I figure. So far all the conditions I have tried shut down LMR completely.
outAtime wrote:Sounds interesting! I don't know how I could implement this type of idea for myself though. Im only working with 2 main searches, root_search and search . Ive looked at stockfish, which has all kinds of searches: search_pv, search_root, search etc... Im somewhat confused by the vast number of different searches some, if not most engines do. I have trouble figuring out if the search_root Im working with is a mixture of search_pv and search_root (in stockfish) or what. All I know is in the search_root Im working on, searching PV = TRUE. So for now Im just doing a full width search there, but it actually calls search() e.g. (root_score = -search) so its almost like only one search or something. Most other programs have a different routine for each section. For now im doing all the LMR in search() although I dont know yet what difference it makes if I do it in search() or search_root(), or both for that matter, all approaches allow the engine to search. Im just trying to figure out if Im reducing the killer moves or not. If I am, then I need to write some kind of condition I figure. So far all the conditions I have tried shut down LMR completely.
I have a SearchRoot() and a Search() myself. SearchRoot() is somewhat different in that there is no reason to probe the hash table, and move selection at the root is done differently since they are ordered by previous iterations, etc...
Finally got around to looking at how your search and search_root are organized, and I also saw your REMAINING_MOVES condition. I really like that condition, but Im not sure how to put it into my move ordering, since I assume thats where Id do it. I also noticed you have LMR in search and root_search, which was somthing I was thinking about. I noticed you are using (if (depth + extensions - 1 > 0)) to see if you are in the first move, where I have been using a counter (if msearch == 1) when I count msearch++ right after make and the legal check. I like your idea of depth+extensions -1 > 0 because if I could switch to that I could remove the msearch++ stuff which would be redundant because Im already using depth and extensions elsewhere. I was surprised at how similar this is to what Im working on, and it has answered some of my questions! Thanks! Now Im just trying to figure out if I should try the remaining moves thing, or rely on the condition that a certain number of moves must have been searched already with a full window (assumption is that the engine will search the highly ordered moves first) so in my case there is PV, hash, captures, and 3 Killers.. so Im thinking if LMR is only allowed if moves_searched is greater than 6 or so I shouldn't be worried about chopping any killers or anything good Ive stored? Thanks.
I think I've found most of the answers in another thread... it appears maybe we have been thinking about some similar ideas. Not sure what I'll end up deciding, but if I can avoid adding anything new I probably will
outAtime wrote:Finally got around to looking at how your search and search_root are organized, and I also saw your REMAINING_MOVES condition. I really like that condition, but Im not sure how to put it into my move ordering, since I assume thats where Id do it. I also noticed you have LMR in search and root_search, which was somthing I was thinking about. I noticed you are using (if (depth + extensions - 1 > 0)) to see if you are in the first move,
Not sure what you mean. That just determines whether I call Search() or Quiesce() (call Quiesce() if remaining depth == 0).
where I have been using a counter (if msearch == 1) when I count msearch++ right after make and the legal check. I like your idea of depth+extensions -1 > 0 because if I could switch to that I could remove the msearch++ stuff which would be redundant because Im already using depth and extensions elsewhere. I was surprised at how similar this is to what Im working on, and it has answered some of my questions! Thanks! Now Im just trying to figure out if I should try the remaining moves thing, or rely on the condition that a certain number of moves must have been searched already with a full window (assumption is that the engine will search the highly ordered moves first) so in my case there is PV, hash, captures, and 3 Killers.. so Im thinking if LMR is only allowed if moves_searched is greater than 6 or so I shouldn't be worried about chopping any killers or anything good Ive stored? Thanks.
I don't particularly like doing LMR after some random number of moves. In Crafty, "remaining_moves" at least lets me know I have tried all the usual suspects, including hash move, non-losing captures, and killers. And I have no good guess as to how many of those there might be, since positions can be wildly different. And even in "remaining moves" I exclude any moves that appear to be tactical in nature, such as checks.
I'd be interested to test a no_killer condition, but so far everything I've tried has been broken. Whenever I try out a new LMR condition I only count the nodes on the LMR search to kinda see how its working and every time I put a no_killer condition on there the nodes slip to ZERO. Unfortunately I spent some time trying to implement some sort of REST_OF_MOVES type of idea but the first try broke the search and I haven't tried again. I've (for now) gone back to no_checks and no_pv and no moves which have been extended and a depth condition to keep an eye on the horizon. I'm trying to search a minimum of 4 moves to full depth before LMR and hoping that move_ordering will make those first 4 moves the ones worth looking at before reductions. I've tried less than 4 moves and more than 4 moves but can't be sure yet what is best for me because I've changed the testing conditions (more fair now I think). I was using the Balanced14.abk and letting it run wild, the positions were interesting but not good I think for testing. So I'm trying Perfect10.abk with a 12 move limit for the games now.
Seems much more even out of the opening. Im surprised that with all the conditions you have on there that your LMR is ever used at all, if it is then I would guess its very rarely. I wonder if LMR dosen't perform better overall when it's allowed to run free over mostly everything except the PV in some programs (not necessarily yours). Im trying to figure out exactly how LMR differs from null move in terms of the risk of missing a better move, or playing an outright 'bad' move.
It seems reasonable and easy to implement to seek ALL otherwise uninteresting moves reduced and, after looking at the reduced search result, decide either skip move or research deeper. Sort of conditional internal iterative deepening.
