Possible LMR improvement using AB_FOOL

[bob]

Sven, Dan, of course you are right. Each root-move needs [-inf ... +inf]. I get 35 elo doing it the OP way, maybe there is even more now

I hate to rain here, but I don't see how one can get +35 elo from just adding LMR at the root. That would suggest that you have speeded up your search by a full 1/2 ply overall, which seems very high. In the tests I ran and published here a year or two ago, LMR seems to be worth maybe 80-100 Elo max, overall. And when I ran that test I was already doing LMR at the root. I find it difficult to believe that I get 1/3 or more of my Elo from the root ply...

I can test easily enough, however...

[Rebel]

Sven, Dan, of course you are right. Each root-move needs [-inf ... +inf]. I get 35 elo doing it the OP way, maybe there is even more now

I hate to rain here, but I don't see how one can get +35 elo from just adding LMR at the root. That would suggest that you have speeded up your search by a full 1/2 ply overall, which seems very high. In the tests I ran and published here a year or two ago, LMR seems to be worth maybe 80-100 Elo max, overall. And when I ran that test I was already doing LMR at the root. I find it difficult to believe that I get 1/3 or more of my Elo from the root ply...

I can test easily enough, however...

The formula I am using is a good for an average reduction rate of 80-90% and another statistic shows an overall 0.5 depth increase. The 35 elo number was a mistake, it's 30 (54.5%). Doing a 2 ply reduction using a margin of a pawn did not pay off.

Like you I have been doing LMR at root moves from the start but took it out in the latest 1.74 version because it scored somewhat worse.

[Mincho Georgiev]

I remember some time ago we had a discussion about LMR at the root, shortly after I've applied it.
12 elo for me as far as I remember. Back then I've posted the results too. Still, that doesn't mean that for others it wouldn't work better, just nothing overhelming in my case.

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

[syzygy]

Ed's full search idea is not specifically connected to LMR, although there is no reason why the two ideas cannot coexist.

I think it is connected to LMR (at the root)?

The idea is to get exact 4-ply scores to order the moves at the root, then do LMR based on this ordering. With normal alpha-beta (and especially with PVS) you only get an exact score for the first move and for the rest you have basically no information except that they score lower than the first move.

It is certainly true that what might be the second-best move at 4 ply is the worst move at 22 ply, but on the whole it seems reasonable that there is a correlation between the ordering at 4 ply and at 22 ply. Certainly, an ordering based on 4-ply exact values will be far more accurate than any kind of static ordering.

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

It also seems reasonable that bad reductions at a depth of 0 ply have more impact than bad reductions at higher depth. So what is too expensive to do at all nodes, might pay off when done only at the root.

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

[bob]

Ed's full search idea is not specifically connected to LMR, although there is no reason why the two ideas cannot coexist.

I think it is connected to LMR (at the root)?

The idea is to get exact 4-ply scores to order the moves at the root, then do LMR based on this ordering. With normal alpha-beta (and especially with PVS) you only get an exact score for the first move and for the rest you have basically no information except that they score lower than the first move.

It is certainly true that what might be the second-best move at 4 ply is the worst move at 22 ply, but on the whole it seems reasonable that there is a correlation between the ordering at 4 ply and at 22 ply. Certainly, an ordering based on 4-ply exact values will be far more accurate than any kind of static ordering.

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

It also seems reasonable that bad reductions at a depth of 0 ply have more impact than bad reductions at higher depth. So what is too expensive to do at all nodes, might pay off when done only at the root.

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

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. But in the search, once you try a root move, you are again at a position where you have to pick a move. Only difference I see in the root is that a null-move makes no sense, nor does the in-check extension since that extends all moves and does nothing...

[Evert]

The idea is to get exact 4-ply scores to order the moves at the root, then do LMR based on this ordering. With normal alpha-beta (and especially with PVS) you only get an exact score for the first move and for the rest you have basically no information except that they score lower than the first move.

If that is really important you could do a multi-PV search to get accurate scores for more moves. From what I know that helps time-to-solution on (some) test positions, but doesn't help improve playing strength.
It might be worth doing in some difficult positions or specific situations, but that requires some careful testing.

It is certainly true that what might be the second-best move at 4 ply is the worst move at 22 ply, but on the whole it seems reasonable that there is a correlation between the ordering at 4 ply and at 22 ply. Certainly, an ordering based on 4-ply exact values will be far more accurate than any kind of static ordering.

You have the size of the search tree for each move, and you can order them based on that. I'll freely admit that I didn't do much testing with this myself when I implemented that, but it seemed a bit better than what I had before and it was reported as such as well, so I kept it.

[Rebel]

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

I have tried several methods for LMR root reductions. This one (fooling AB) happens to gimme the best results, so far. So I posted to share. And I am pretty sure there are better idea's to reduce root moves involving static considerations. It's a matter of time and energy you want to put in it. And for me counts that nowadays it's much more fun to talk about chess programming than actually doing it.

[syzygy]

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.

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

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.

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