Possible LMR improvement using AB_FOOL

[chrisw]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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.

[marcelk]

But in any case, LMR is about treating "later moves" differently since they are searched "later" for some specific reasons.

But what are those specific reasons? A 4-ply exact value seems to be a better reason than an ordering based on losing/non-losing captures and maybe some killer info left from a previous search (if you use that at all)?

From a TV documentary a long time ago (1994'ish) I remember that 4-ply exact searches is what DT used to do to order its root moves. I remember I cringed at the time at the realization that my own program only reached 4 ply at tournament level.

[bob]

The most common "specific reason" is the behavior of each of those moves in the previous iteration, as relayed through the history counters...

And it seems to me that 4-ply exacty values for a particular position lead on average to a better ordering for that particular position than one based on history counters. Btw, I don't really see how history counters from the previous iteration are used for ordering of root moves.

History counters are typically used in LMR decisions, I didn't intend to imply they were ever used to order root moves although I suppose they could be.

If you re-read what I wrote, I said "results from previous iterations are used to improve information for the next iteration." For root moves, I use the node counts from iteration N-1 to order the root moves for iteration n. I would claim that a 20-ply node count is far more accurate than a score from a 4 ply search...

(I might very well be mistaken, but I think I read somewhere that you removed history counters from crafty?)

Correct. History counters as used in the original Fruit were not effective either in Fruit or in Crafty. History counters used to order moves does help a bit, but it also costs a bit. For me, it was a wash and I removed them. But if you do the real "L" in LMR, then history counters are apparently more useful, because now moves that appear late in a move list can be reasonably reduced...

As far as your last statement goes, I don't follow at all. The root is no different from any other node, except it is the position you have to pick a move for.

If you make a mistake at the root node, that clearly has a far bigger impact on the quality of the search than a mistake at a single node 10 ply from the root.

Every ply is less consequential. But a mistake at ply 2 is devastating, just as it is at the root, only slightly less so.

The point is: there is only one root node. You can do something extra for just that node without any measurable impact on performance. Obviously that is not the case for all nodes at 10 ply from the root, since there are too many of those.

Anyway, you can hardly disagree that ordering of root moves deserves special attention:

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...

You are doing something extra when ordering moves at the root as compared to any other node. Ed's proposal is to replace the quiesce() search for each move by a 4-ply search with window (-inf,inf) (or maybe just a 3-ply for each move, so in total a 4-ply, I would have to reread the initial post).

My point was that after you do that, and get to depth=10 and beyond in the REAL searches, that 4-ply search information is gone, as it should be, because the 10 ply information is far more useful. Nothing wrong with "getting a good start" on ordering. But a 4 ply true-valued search is "just a good start" and has outlived its usefulness once you start to do real searches...

[bob]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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.

[syzygy]

For root moves, I use the node counts from iteration N-1 to order the root moves for iteration n. I would claim that a 20-ply node count is far more accurate than a score from a 4 ply search...

Ok, using the node counts to reorder after each iteration makes sense (I don't think you mentioned that in your previous post).

I'm not sure that it helps to avoid bad reductions, since a reduced root move in the previous iteration should normally have a reduced node count for the reason that it was reduced (possibly some heuristics could help here though), but it is reasonable to prefer this over an essentially fixed ordering based on a 4-ply search.

My point was that after you do that, and get to depth=10 and beyond in the REAL searches, that 4-ply search information is gone, as it should be, because the 10 ply information is far more useful. Nothing wrong with "getting a good start" on ordering. But a 4 ply true-valued search is "just a good start" and has outlived its usefulness once you start to do real searches...

If the information gathered from node counts is more useful (which I find easy to believe), then yes.

[Uri Blass]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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.

[jwes]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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.

An example could be a move has an exact value of -8 at depth 4 and an upper bound 0.2 at depth 20. Which information would be more useful for move ordering or LMR?

[bob]

For root moves, I use the node counts from iteration N-1 to order the root moves for iteration n. I would claim that a 20-ply node count is far more accurate than a score from a 4 ply search...

Ok, using the node counts to reorder after each iteration makes sense (I don't think you mentioned that in your previous post).[/quote[]


Quite a few do this today. I believe the idea originated in Cray Blitz in the 80's, suggested by Harry Nelson as a way to get a move that appears to be close to failing high, and moving it to the top of the list so it is searched before time runs out.

I'm not sure that it helps to avoid bad reductions, since a reduced root move in the previous iteration should normally have a reduced node count for the reason that it was reduced (possibly some heuristics could help here though), but it is reasonable to prefer this over an essentially fixed ordering based on a 4-ply search.

My point was that after you do that, and get to depth=10 and beyond in the REAL searches, that 4-ply search information is gone, as it should be, because the 10 ply information is far more useful. Nothing wrong with "getting a good start" on ordering. But a 4 ply true-valued search is "just a good start" and has outlived its usefulness once you start to do real searches...

If the information gathered from node counts is more useful (which I find easy to believe), then yes.

[bob]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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???

[bob]

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.

Some code snippets to clarify.

Code: Select all

char ab_depth=2;	// 3 or 4

A value of 4 can be done in 0.1 sec most of the time.

if (ab_depth <= iteration_depth) { don't do AB; }

Only needed in the main-search, keep AB in QS.

Code: Select all

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.)

Possible improvements are:

1. Create 2 margins.

Code: Select all

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.

An example could be a move has an exact value of -8 at depth 4 and an upper bound 0.2 at depth 20. Which information would be more useful for move ordering or LMR?

I certainly don't think the depth 4 score is worth anything when starting a 20+ ply search and trying to make LMR decisions at the root based on that hopelessly outdated information...