Rebel wrote:Got an idea yesterday based on an old idea I never got to work. It's about doing LMR at root moves. LMR at root moves hurts my engine but not that much. Now that I have added special code to it I get a nice improvement by fooling Alpha-Beta (AB) till a given iteration depth.
The idea is to do the first x iterations without AB. What's the effect? You get a fully sorted root move list based on the real scores. I use these real values for LMR at root moves with a 0.12 margin and reduce one ply after all.
That's it. I call the technique AB_FOOL for the moment.
int root_score [max_moves]; // where the normal root scores are
int ab_fool_score [max_moves]; // shadow table for the ab_fool scores
int ab_margin = 12; // educuated guess for the moment.
When the AB_FOOL phase is over then for each root move do the following: get the real score of the root move from ab_fool_score and compare it with the highest real score of ab_fool_score with a margin of ab_margin and reduce one ply. Of course do the normal exclusion checks first (checks, captures etc.)
int ab_margin_1 = 12; // reduce one ply
int ab_margin_2 = 100; // reduce one more
2. Since we are doing the x first iterations without AB we can count the nodes of each variation and store them. This can be used to improve move ordering. When 1-2-3...7 nodes all would give a "real" AB cut-off why not take the one with the lowest nodes as move for the hash table?
I've always done LMR at the root. Can't see any reason to treat the root any differently than any other node. The moves at the bottom of the list are still often completely losing moves, and ought to be reduced. In my case, my root move scores are pretty good because I do an actual quiesce() search for each one to analyze any hung pieces or moves that hang pieces...
I do not do the full-width at the root for the first N iterations trick however, I don't see why the scores need to be that exact since they are not at ply=2 and beyond, and they are just as important...
Well, since I am retired I never tried it and only know that Ed does. Never discussed it with him either but would guess that it provides search guidance for time consuming needed cases such as a move failing alpha at the root and subsequently having to research with wider bounds. The stored best line from a four ply previous search will at least suggest a best pathway to get started from. It is very frustrating watching a program, stuck in a failed alpha search, taking way too long to comeback with a new move because the search guidance isn't there. And then the extended time controller kicking in. Perhaps Ed can use it to even suggest what the new bounds should be.
Also, it may provide useful search guidance in all higher iterations, for each move will be able to get started on a tested pathway specific to the move rather than just any old pathway which was found as "good enough" for refutation in AB. But, each to his own. Probably you know better.
The problem I see is ordering based on exact scores from a 2-3-4 ply alpha/beta-crippled search is not going to be very helpful when you get down to the 24+ ply searches we typically see even at CCT type time controls... And after you have done that 4-ply crippled search, the 5 ply search will also search and overwrite that 4-ply information. By the time you get to 8-10, which is instant nowadays, there is probably nothing remaining.
But in any case, LMR is about treating "later moves" differently since they are searched "later" for some specific reasons. And searching them with reduced depth gets rid of 'em quicker, with the risk that you overlook something interesting tactically. The good thing about LMRing at the root is that you don't kill yourself by playing a bad move, at the very worse, you just miss playing a better move. The better your root score is, the more aggressive you can be, although that seems pointless as you are already winning anyway...
Well "crippled" is an emotive word which might give readers the wrong impression. In fact the full search employed will yield much more information than AB, including accurate scores, not bounds, and more sensible refutation moves.
You say "overwritten" by a subsequent five ply search, but this is surely unimaginative, isn't it? Why not save the full width full information four ply search information in an array, for later access, if needed?
Whether Rebel then makes use of the saved info at ten ply or twenty four ply is hardly relevant. The key is that his Near root first move refutation choices will be at least tested, rather than used on a good enough basis within a AB bound that, by definition, will have been broken. He will also have a pointer to a senseful new search window, testing would indicate if that helped - it ought to.
Ed's full search idea is not specifically connected to LMR, although there is no reason why the two ideas cannot coexist.
SImple question... would you really trust information from a simple 4-ply non-alpha/beta search over the results obtained from a 20 ply normal alpha/beta search, for anything at all??? I see moves with high scores at 4 plies that are losing at 20 and beyond. So keeping that stuff doesn't seem reasonable to me, the whole idea of doing another iteration is to learn more about the position, things you could not see with the 1-ply shallower search...
Methinks you are forgetting the difference between the quality of information from a search carried out within bounds and one that is just looking to be "good enough". Info from the latter can be and often is any old junk, quite unsuitable for search guidance or score prediction, whereas info from the non-beta search is as good as it can be across the whole search space.
Just to re-assert, info saved for non-best lines for your subsequent AB searches is sub-optimal, despite the depth. And depth does not make sub-optimal information any more optimal unless and until it searches that tree region with more realistic bounds.
Sorry, but how is it "sub-optimal" since alpha/beta and minimax are guaranteed to produce the same best move, the same best path, and the same best score??? Spending extra effort on irrelevant parts of the tree doesn't particularly give you "better information". The bounds are irrelevant so long as they bracket the true score.
It is suboptimal because you do not have the best reply to root moves
but only replies that are good enough to produce a cutoff.
If 1.a3 is bad because of 1...Qh3 and 2...Qg2 mate but you search again and again 1...Bc5 that is good enough to produce a cutoff but not good enough to get mate score then you clearly spend more nodes then you need at big depth to refute 1.a3
If you have some pruning or reduction based on evaluation then even if 1...Qh3 does not force mate but only force winning a queen then searching it can generate smaller tree relative to searching another move because you do more reductions or pruning after that move.
(a) why is it necessary or beneficial to have the "best reply"? (b) how certain are you that the search actually returns the "best reply" anyway???
a)I believe that having the best reply with some good pruning means that you have also a smaller tree.
b)I am not certain that I have the best reply based on search to small depth but I think that increasing the probability to get the best reply can be productive.
Rebel wrote:Got an idea yesterday based on an old idea I never got to work. It's about doing LMR at root moves. LMR at root moves hurts my engine but not that much. Now that I have added special code to it I get a nice improvement by fooling Alpha-Beta (AB) till a given iteration depth.
The idea is to do the first x iterations without AB. What's the effect? You get a fully sorted root move list based on the real scores. I use these real values for LMR at root moves with a 0.12 margin and reduce one ply after all.
That's it. I call the technique AB_FOOL for the moment.
int root_score [max_moves]; // where the normal root scores are
int ab_fool_score [max_moves]; // shadow table for the ab_fool scores
int ab_margin = 12; // educuated guess for the moment.
When the AB_FOOL phase is over then for each root move do the following: get the real score of the root move from ab_fool_score and compare it with the highest real score of ab_fool_score with a margin of ab_margin and reduce one ply. Of course do the normal exclusion checks first (checks, captures etc.)
int ab_margin_1 = 12; // reduce one ply
int ab_margin_2 = 100; // reduce one more
2. Since we are doing the x first iterations without AB we can count the nodes of each variation and store them. This can be used to improve move ordering. When 1-2-3...7 nodes all would give a "real" AB cut-off why not take the one with the lowest nodes as move for the hash table?
I've always done LMR at the root. Can't see any reason to treat the root any differently than any other node. The moves at the bottom of the list are still often completely losing moves, and ought to be reduced. In my case, my root move scores are pretty good because I do an actual quiesce() search for each one to analyze any hung pieces or moves that hang pieces...
I do not do the full-width at the root for the first N iterations trick however, I don't see why the scores need to be that exact since they are not at ply=2 and beyond, and they are just as important...
Well, since I am retired I never tried it and only know that Ed does. Never discussed it with him either but would guess that it provides search guidance for time consuming needed cases such as a move failing alpha at the root and subsequently having to research with wider bounds. The stored best line from a four ply previous search will at least suggest a best pathway to get started from. It is very frustrating watching a program, stuck in a failed alpha search, taking way too long to comeback with a new move because the search guidance isn't there. And then the extended time controller kicking in. Perhaps Ed can use it to even suggest what the new bounds should be.
Also, it may provide useful search guidance in all higher iterations, for each move will be able to get started on a tested pathway specific to the move rather than just any old pathway which was found as "good enough" for refutation in AB. But, each to his own. Probably you know better.
The problem I see is ordering based on exact scores from a 2-3-4 ply alpha/beta-crippled search is not going to be very helpful when you get down to the 24+ ply searches we typically see even at CCT type time controls... And after you have done that 4-ply crippled search, the 5 ply search will also search and overwrite that 4-ply information. By the time you get to 8-10, which is instant nowadays, there is probably nothing remaining.
But in any case, LMR is about treating "later moves" differently since they are searched "later" for some specific reasons. And searching them with reduced depth gets rid of 'em quicker, with the risk that you overlook something interesting tactically. The good thing about LMRing at the root is that you don't kill yourself by playing a bad move, at the very worse, you just miss playing a better move. The better your root score is, the more aggressive you can be, although that seems pointless as you are already winning anyway...
Well "crippled" is an emotive word which might give readers the wrong impression. In fact the full search employed will yield much more information than AB, including accurate scores, not bounds, and more sensible refutation moves.
You say "overwritten" by a subsequent five ply search, but this is surely unimaginative, isn't it? Why not save the full width full information four ply search information in an array, for later access, if needed?
Whether Rebel then makes use of the saved info at ten ply or twenty four ply is hardly relevant. The key is that his Near root first move refutation choices will be at least tested, rather than used on a good enough basis within a AB bound that, by definition, will have been broken. He will also have a pointer to a senseful new search window, testing would indicate if that helped - it ought to.
Ed's full search idea is not specifically connected to LMR, although there is no reason why the two ideas cannot coexist.
SImple question... would you really trust information from a simple 4-ply non-alpha/beta search over the results obtained from a 20 ply normal alpha/beta search, for anything at all??? I see moves with high scores at 4 plies that are losing at 20 and beyond. So keeping that stuff doesn't seem reasonable to me, the whole idea of doing another iteration is to learn more about the position, things you could not see with the 1-ply shallower search...
Methinks you are forgetting the difference between the quality of information from a search carried out within bounds and one that is just looking to be "good enough". Info from the latter can be and often is any old junk, quite unsuitable for search guidance or score prediction, whereas info from the non-beta search is as good as it can be across the whole search space.
Just to re-assert, info saved for non-best lines for your subsequent AB searches is sub-optimal, despite the depth. And depth does not make sub-optimal information any more optimal unless and until it searches that tree region with more realistic bounds.
Sorry, but how is it "sub-optimal" since alpha/beta and minimax are guaranteed to produce the same best move, the same best path, and the same best score??? Spending extra effort on irrelevant parts of the tree doesn't particularly give you "better information". The bounds are irrelevant so long as they bracket the true score.
It is suboptimal because you do not have the best reply to root moves
but only replies that are good enough to produce a cutoff.
If 1.a3 is bad because of 1...Qh3 and 2...Qg2 mate but you search again and again 1...Bc5 that is good enough to produce a cutoff but not good enough to get mate score then you clearly spend more nodes then you need at big depth to refute 1.a3
If you have some pruning or reduction based on evaluation then even if 1...Qh3 does not force mate but only force winning a queen then searching it can generate smaller tree relative to searching another move because you do more reductions or pruning after that move.
(a) why is it necessary or beneficial to have the "best reply"? (b) how certain are you that the search actually returns the "best reply" anyway???
a)I believe that having the best reply with some good pruning means that you have also a smaller tree.
This has been demonstrated to be false quote a few years ago. Simple example. "Good enough" move trades knights. "Best move" checks opponent king. The latter will almost certainly produce a bigger tree because two pieces are not exchanged, and we add a ply of search due to the check.
But remember we are talking about using info from a 4 ply search to influence decisions made during a 20+ ply search. Do you really think that 4 ply info is worth anything.
b)I am not certain that I have the best reply based on search to small depth but I think that increasing the probability to get the best reply can be productive.