Possible LMR improvement using AB_FOOL

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Rebel
Posts: 5349
Joined: Thu Aug 18, 2011 10:04 am

Possible LMR improvement using AB_FOOL

Post by Rebel » Tue Apr 24, 2012 9:13 am

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 &#91;max_moves&#93;;        // where the normal root scores are
int ab_fool_score &#91;max_moves&#93;;     // 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
Posts: 151
Joined: Wed Mar 08, 2006 9:09 pm
Location: Murcia (Spain)

Re: Possible LMR improvement using AB_FOOL

Post by Jose Carlos » Tue Apr 24, 2012 9:44 am

Rebel wrote:Got an idea yesterday based on an old idea I never got to work. It's about doing LMR at root moves. LMR at root moves hurts my engine but not that much. Now that I have added special code to it I get a nice improvement by fooling Alpha-Beta (AB) till a given iteration depth.

The idea is to do the first x iterations without AB. What's the effect? You get a fully sorted root move list based on the real scores. I use these real values for LMR at root moves with a 0.12 margin and reduce one ply after all.

That's it. I call the technique AB_FOOL for the moment.

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 &#91;max_moves&#93;;        // where the normal root scores are
int ab_fool_score &#91;max_moves&#93;;     // 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.
__________________________
José Carlos Martínez Galán

User avatar
Rebel
Posts: 5349
Joined: Thu Aug 18, 2011 10:04 am

Re: Possible LMR improvement using AB_FOOL

Post by Rebel » Tue Apr 24, 2012 10:34 am

José Carlos wrote: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
Posts: 171
Joined: Wed Dec 28, 2011 7:44 pm
Location: United States

Re: Possible LMR improvement using AB_FOOL

Post by dchoman » Tue Apr 24, 2012 11:01 am

Rebel wrote:Got an idea yesterday based on an old idea I never got to work. It's about doing LMR at root moves. LMR at root moves hurts my engine but not that much. Now that I have added special code to it I get a nice improvement by fooling Alpha-Beta (AB) till a given iteration depth.

The idea is to do the first x iterations without AB. What's the effect? You get a fully sorted root move list based on the real scores. I use these real values for LMR at root moves with a 0.12 margin and reduce one ply after all.

That's it. I call the technique AB_FOOL for the moment.

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 &#91;max_moves&#93;;        // where the normal root scores are
int ab_fool_score &#91;max_moves&#93;;     // 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

User avatar
Steve Maughan
Posts: 1074
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Possible LMR improvement using AB_FOOL

Post by Steve Maughan » Tue Apr 24, 2012 12:52 pm

Hi Ed,
Rebel wrote:<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
Posts: 3858
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Possible LMR improvement using AB_FOOL

Post by Sven » Tue Apr 24, 2012 1:20 pm

Rebel wrote:
José Carlos wrote: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
Posts: 8771
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Possible LMR improvement using AB_FOOL

Post by Uri Blass » Tue Apr 24, 2012 1:21 pm

Steve Maughan wrote:Hi Ed,
Rebel wrote:<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
Posts: 3951
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: Possible LMR improvement using AB_FOOL

Post by jdart » Tue Apr 24, 2012 2:16 pm

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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Possible LMR improvement using AB_FOOL

Post by diep » Tue Apr 24, 2012 4:11 pm

Rebel wrote:
José Carlos wrote: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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Possible LMR improvement using AB_FOOL

Post by diep » Tue Apr 24, 2012 4:27 pm

jdart wrote: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...

Post Reply