Possible LMR improvement using AB_FOOL

[Rebel]

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?

[Jose Carlos]

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?

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.

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

[dchoman]

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 like the idea for having a better determined score for determining LMR reductions at the root. I do something a bit different in EXchess, but perhaps a related idea. I do a reduced depth search (usually depth/2-1) on each possible LMR move to decide if it is likely to fall below alpha. In this way the score LMR decision can change with depth of the search.

I have actually been thinking about testing this all again, as it seems like a lot of extra overhead for moves that are going to be searched again to depth-2 (if they are reduced by LMR). At the time I put it in, it was better than just using my rather poor move ordering to make LMR decisions. Your approach for improved move ordering might be a better compromise.

- Dan

[Steve Maughan]

Hi Ed,

<snip>

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

Sounds interesting.

My only comment is that 0.1 sec is a long time in the world of 3 second games (which seem to be the new testing norm).

Steve

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

Sven

[Uri Blass]

Hi Ed,

<snip>

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

Sounds interesting.

My only comment is that 0.1 sec is a long time in the world of 3 second games (which seem to be the new testing norm).

Steve

I see no reason to have constant number for ab_depth and ab_depth may be a function of the time control.

[jdart]

I already do something like this to detect "easy moves". An easy move has a real score significantly better than all other moves - but you need the real scores to determine this. I use a depth of 3 w/o AB for this. I also use the scores for initial move ordering but since the depth is small and will soon be exceeded that is probably not really useful.

For root LMR currently I am using cumulative node counts, with the usual move exclusions. I use counts to order the moves at later plies where I am using AB (other programs also do this - I think I first saw it in Crafty). The theory is that AB will spend more nodes at good moves than bad moves - certainly it will spend more at the PV and and also it will spend more when a re-search is required due to a cutoff. I start enabling LMR when a move has a node count < 0.75*the PV node count. This value has not been tuned though. This is a very recent addition to Arasan but in the latest released version.

--Jon

[diep]

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.

...back to the 90s...

You don't want to do AB first 2 ply? I assume you don't want to do AB-PRUNING, fist 2 plies from root?

First ply of course is a PV node anyway, so we speak about the 'refutation moves' of the opponent where diep most of the time nullmoves.

Are you still forward pruning last X plies though?

How can this eat 0.1 seconds in Rebel by the way?
You're testing at a 80286 or something?

Also you used to reset timer after ply1, so you only time iteration 2 and further (speeds up tactical testsets nicely), that's not counted in this 0.1 seconds i assume?

We can of course do that 'first ply' a nice conspiracy number search finding all tactics for us - that would kick butt (if we do not time it).

In 0.1 seconds i get a ply or 9, at a core or 16, you?

p.s. i remember The King searching first few plies fullwidth and only use nullmove later in search - that should work similar to this i guess - should pick up more tactics at bullet indeed.

[diep]

I already do something like this to detect "easy moves". An easy move has a real score significantly better than all other moves - but you need the real scores to determine this. I use a depth of 3 w/o AB for this. I also use the scores for initial move ordering but since the depth is small and will soon be exceeded that is probably not really useful.

For root LMR currently I am using cumulative node counts, with the usual move exclusions. I use counts to order the moves at later plies where I am using AB (other programs also do this - I think I first saw it in Crafty). The theory is that AB will spend more nodes at good moves than bad moves - certainly it will spend more at the PV and and also it will spend more when a re-search is required due to a cutoff. I start enabling LMR when a move has a node count < 0.75*the PV node count. This value has not been tuned though. This is a very recent addition to Arasan but in the latest released version.

--Jon

Nice to know there is still some who invent singular extensions themselves...