Possible LMR improvement using AB_FOOL

[Rebel]

You mean not doing Alpha-Beta at all, or doing Alpha-Beta with an infinite window for all moves? I guess the second, so you (if I understand correctly) are not doing PVS (first move with open window, rest of moves with null window).

So you search the first n iterations with open window for all moves (and same depth for all), then sort the root moves according to the real eval at that iteration, and search the next iteration (n+1) doing LMR, right? So what happens at iteration n+2? Do you keep the same sorting and LMR schema?

The idea sounds interesting, but I don't quite understand how it works.

Thanks for sharing.

It does not matter which type of search and windowing you are doing. Just add that one instruction to your AB-check in the main-search leaving everything else the same.

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

And store the values in an extra table. So if "ab_depth=2" it will do iteration 1 and 2 without AB.

At iteration 3 and on (AB is active again) you allow LMR on root moves using the real_scores you gathered during the first 2 iterations in that extra score table that never changes after the first 2 iterations.

I think José is right, what you mean is not "don't do AB" as in "do a full minimax search", but "use full AB window [-INF .. +INF] for all root moves to get true scores instead of bounds". I see no other possible meaning of your pseudocode statement "don't do AB".

I don't see how [-INF .. +INF] would matter as the regular FH and FL wil take care of that. Tried your [-INF .. +INF] approach anyway and as expected got about the same (good) ordering and (good) scores. I don't like the [-INF .. +INF] approach because the system still allows AB in QS.

[Sven]

You mean not doing Alpha-Beta at all, or doing Alpha-Beta with an infinite window for all moves? I guess the second, so you (if I understand correctly) are not doing PVS (first move with open window, rest of moves with null window).

So you search the first n iterations with open window for all moves (and same depth for all), then sort the root moves according to the real eval at that iteration, and search the next iteration (n+1) doing LMR, right? So what happens at iteration n+2? Do you keep the same sorting and LMR schema?

The idea sounds interesting, but I don't quite understand how it works.

Thanks for sharing.

It does not matter which type of search and windowing you are doing. Just add that one instruction to your AB-check in the main-search leaving everything else the same.

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

And store the values in an extra table. So if "ab_depth=2" it will do iteration 1 and 2 without AB.

At iteration 3 and on (AB is active again) you allow LMR on root moves using the real_scores you gathered during the first 2 iterations in that extra score table that never changes after the first 2 iterations.

I think José is right, what you mean is not "don't do AB" as in "do a full minimax search", but "use full AB window [-INF .. +INF] for all root moves to get true scores instead of bounds". I see no other possible meaning of your pseudocode statement "don't do AB".

I don't see how [-INF .. +INF] would matter as the regular FH and FL wil take care of that. Tried your [-INF .. +INF] approach anyway and as expected got about the same (good) ordering and (good) scores. I don't like the [-INF .. +INF] approach because the system still allows AB in QS.

I disagree. You want exact scores of all root moves, right? You get them by using [-INF .. +INF] for each single root move in conjunction with standard AB used the way down its subtree, QS included. By doing it that way you just guarantee not to get any FH or FL of a root move. Note that an AB cutoff cuts those subtrees which are proven not to have any influence on the score of the root node, and if the latter is always a PV node then you have what you need.

On the other hand, of course you get the same result by completely disabling AB throughout the whole search, just with a lot more nodes to search ... Not very significant for depth=2 but maybe for depth=4.

Calling AB for a node can return a bound instead of an exact score only if you use a non-infinite window for that node.

Sven

[hgm]

I tried schemes like this, but applied in all tree nodes, rather than just in the root, for deciding which moves are so poor that they deserve a larger reduction. I noticed that one of the things that offset the gain is hashing. By opening the search window, (which I typically did by shifting alpha down 100cP), and searching at extra-reduced depth, everything is fine when the move fails low. But some of the moves will not fail low, and you then want to re-search them with less or no reduction, with the normal PVS null-window, against which they are expected to fail low.

The problem then is that the reduced-depth, enlarged-window pilot search destroyed your hash entries. In the pilot search nodes from a previous unreduced search did not supply bounds you could use, so they were thus searched, and replaced by entries of lower draft. This then makes the re-search more expensive, because you destroyed all the entries that were useful for that.

So it is really important to re-design your hashing scheme so that it avoids a reduced pilot search erasing information needed in a less reduced search.

[Dan Honeycutt]

I don't see how [-INF .. +INF] would matter as the regular FH and FL wil take care of that. Tried your [-INF .. +INF] approach anyway and as expected got about the same (good) ordering and (good) scores. I don't like the [-INF .. +INF] approach because the system still allows AB in QS.

I disagree. You want exact scores of all root moves, right? You get them by using [-INF .. +INF] for each single root move in conjunction with standard AB used the way down its subtree, QS included. By doing it that way you just guarantee not to get any FH or FL of a root move. Note that an AB cutoff cuts those subtrees which are proven not to have any influence on the score of the root node, and if the latter is always a PV node then you have what you need.

On the other hand, of course you get the same result by completely disabling AB throughout the whole search, just with a lot more nodes to search ... Not very significant for depth=2 but maybe for depth=4.

Calling AB for a node can return a bound instead of an exact score only if you use a non-infinite window for that node.

Sven

Ed, Sven is correct unless there is something we don't understand about what you're doing. Turning "off" AB (no AB pruning) and searching the root with a +/- infinity window will give exactly the same score for every root move if depth is the same. The only reason for turning off AB is if you want exact scores for every move at plys 2 and up - which it doesn't sound like you need those.

However, along those lines, I've become interested in ways to make an engine play well weak; ie not play a strong game but still make moves that look plausible and logical. One idea I had was to do a no AB search looking for a set of scores at ply 2 where one move that is not an obvious capture or recapture is substantially better than all the rest. Playing into that position gives the opponent (presumably a human - this would be suicide against another computer) a chance to make a gain but only if they select THE move.

Best
Dan H.

[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

[hgm]

Another danger of doing a pilot search with open window is that you will prime later, deeper searches to go for the best move, rather than the simplest refutation. This might not always give you the smallest tree. Default move ordering has a very high probability to find the simplest refutation, immediately trading a high piece or capturing a hanging one, due to captures-first, MVV ordering. Normally this would then become hash move, and picked as first choice in subsequent iterations. But if you search with open window, what otherwise would have been a satisfactory refutation will not cause a cutoff, and alternative moves will be search to see if they secure additional small benefits over what is needed for plain and simple refutation. And if it finds one, it will become hash move. And if you later always search hash move first, you will never get rid of it, no matter how much the depth increases.

So in any case it is very important that null move is searched before hash move. Otherwise things that were refutable by null move will be refuted by the much more expensive hash move in stead. As the open-window search won't be able to get the null-move score above beta if beta = +INF, so you always will get a hash move.

[RoadWarrior]

Another danger of doing a pilot search with open window is that you will prime later, deeper searches to go for the best move, rather than the simplest refutation. This might not always give you the smallest tree.

Thanks, this is a nice insight that explains an experiment result that's been bothering me for the last week.

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

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

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