LMR Research

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

LMR Research

Post by ZirconiumX » Mon Jul 02, 2012 6:15 pm

There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

bob
Posts: 20392
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: LMR Research

Post by bob » Mon Jul 02, 2012 6:31 pm

ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Almost all nodes are actually searched with alpha == beta-1, which means there is very little difference. In such nodes, if value >= beta, then it must be > alpha. If the value were <= alpha, the reduced-search fail low is accepted automatically...

You are talking hundreds of nodes not millions...

User avatar
marcelk
Posts: 348
Joined: Fri Feb 26, 2010 11:21 pm
Contact:

Re: LMR Research

Post by marcelk » Mon Jul 02, 2012 10:18 pm

ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Mind that PVS will eventually do a research anyway.
The only question is if you want smaller intermediate researches to occur before that happens, and for different programs the optimal conditions vary a bit. It can help to defer the researches to a place a bit deeper down the tree. It can also hurt depending on the program.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: LMR Research

Post by Don » Tue Jul 03, 2012 5:03 pm

ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
The right value is alpha. For PV nodes we research if the reduced search is > alpha, for non-PV nodes we do the same but beta is always the same as alpha+1 in this case.

The whole concept is that if a reduced search comes back better than alpha, it could be a new best move and deserves to be properly searched. So beta makes no sense if that is the concept.

It's possible to control your risk by manipulating the actual window you do the reduced depth search for, but we have never found it to be helpful although we have done a few experiments. For example if you want LMR to be a little safer, you could search alpha - margin so that you research even if the reduced search is a little less than alpha, by any margin you choose. Or if you want to be faster (but miss more) you can search with alpha + margin which will cause you to miss moves you perhaps should have researched under the speculative theory that it will probably fail anyway.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

User avatar
lucasart
Posts: 3035
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: LMR Research

Post by lucasart » Tue Jul 03, 2012 11:07 pm

ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Thanks Matt. You're right!!

I replaced >= beta by > alpha and DiscoCheck scored over 54% after 2000 games against itself (easily significant).

Bob: yes there are much fewer PV nodes, but triggering a full window research in those realatively fewer nodes is much costlier, so overall the difference in node count is actually quite significant (ie. >alpha is slower in time to depth, but more accurate, in the end tha accuracy wins for me).

One case where >= beta makes sense is if your engine doesnt reduce at PV nodes, of course (in which case >alpha and >= beta will produce the same result).

jdart
Posts: 3785
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: LMR Research

Post by jdart » Wed Jul 04, 2012 2:45 am

I tried an intermediate research approach a while back and it was not a winner for my program.

--Jon

bob
Posts: 20392
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: LMR Research

Post by bob » Wed Jul 04, 2012 3:38 pm

lucasart wrote:
ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Thanks Matt. You're right!!

I replaced >= beta by > alpha and DiscoCheck scored over 54% after 2000 games against itself (easily significant).

Bob: yes there are much fewer PV nodes, but triggering a full window research in those realatively fewer nodes is much costlier, so overall the difference in node count is actually quite significant (ie. >alpha is slower in time to depth, but more accurate, in the end tha accuracy wins for me).

One case where >= beta makes sense is if your engine doesnt reduce at PV nodes, of course (in which case >alpha and >= beta will produce the same result).
You should not draw conclusions on a few test positions, rather over complete games, where the difference is not so big. >alpha is still the right answer, because any score > alpha when you are expecting all moves to fail low indicates that something is not right. And most likely it will still fail low on the re-search when the depth returns to normal, and that is a LOT cheaper than accepting that fail-high (or actual score from a search that is too shallow) and then triggering a window-widening search, only to discover it really doesn't fail high like you thought...

IE it is better to just verify that the fail-high move is really going to fail high, rather than having to search ALL moves at this ply to see if that single move will fail high normally...

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: LMR Research

Post by diep » Wed Jul 04, 2012 4:50 pm

Don wrote:
ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
The right value is alpha. For PV nodes we research if the reduced search is > alpha, for non-PV nodes we do the same but beta is always the same as alpha+1 in this case.

The whole concept is that if a reduced search comes back better than alpha, it could be a new best move and deserves to be properly searched. So beta makes no sense if that is the concept.

It's possible to control your risk by manipulating the actual window you do the reduced depth search for, but we have never found it to be helpful although we have done a few experiments. For example if you want LMR to be a little safer, you could search alpha - margin so that you research even if the reduced search is a little less than alpha, by any margin you choose. Or if you want to be faster (but miss more) you can search with alpha + margin which will cause you to miss moves you perhaps should have researched under the speculative theory that it will probably fail anyway.
I did do extensive experiments stretching over nearly a full year from after world champs 2004 to start 2005, manipulating windows trying to reduce more. Though it's always promising, the price you pay to do so is rather huge.

Not seldom factor 6 overhead for a tad more reduction. That would mean it should improve your branching factor significantly to break even.

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: LMR Research

Post by diep » Wed Jul 04, 2012 4:53 pm

bob wrote:
lucasart wrote:
ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Thanks Matt. You're right!!

I replaced >= beta by > alpha and DiscoCheck scored over 54% after 2000 games against itself (easily significant).

Bob: yes there are much fewer PV nodes, but triggering a full window research in those realatively fewer nodes is much costlier, so overall the difference in node count is actually quite significant (ie. >alpha is slower in time to depth, but more accurate, in the end tha accuracy wins for me).

One case where >= beta makes sense is if your engine doesnt reduce at PV nodes, of course (in which case >alpha and >= beta will produce the same result).
You should not draw conclusions on a few test positions, rather over complete games, where the difference is not so big. >alpha is still the right answer, because any score > alpha when you are expecting all moves to fail low indicates that something is not right. And most likely it will still fail low on the re-search when the depth returns to normal, and that is a LOT cheaper than accepting that fail-high (or actual score from a search that is too shallow) and then triggering a window-widening search, only to discover it really doesn't fail high like you thought...

IE it is better to just verify that the fail-high move is really going to fail high, rather than having to search ALL moves at this ply to see if that single move will fail high normally...
Bob, education is only useful for those who have the capacity to learn...

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: LMR Research

Post by ZirconiumX » Wed Jul 04, 2012 5:15 pm

bob wrote:
lucasart wrote:
ZirconiumX wrote:There are some programs which research after LMR if value >= beta, some if value > alpha, and some don't research at all.

FF currently uses value >= beta, but I haven't tested this. This is why I ask if anyone else *has*.

Something tells me that value > alpha is best, because it allows Cut-Nodes AND PV-Nodes, rather than either only Cut-Nodes (value >= beta), or nothing (no research).

Matthew:out
Thanks Matt. You're right!!

I replaced >= beta by > alpha and DiscoCheck scored over 54% after 2000 games against itself (easily significant).

Bob: yes there are much fewer PV nodes, but triggering a full window research in those realatively fewer nodes is much costlier, so overall the difference in node count is actually quite significant (ie. >alpha is slower in time to depth, but more accurate, in the end tha accuracy wins for me).

One case where >= beta makes sense is if your engine doesnt reduce at PV nodes, of course (in which case >alpha and >= beta will produce the same result).
You should not draw conclusions on a few test positions, rather over complete games, where the difference is not so big. >alpha is still the right answer, because any score > alpha when you are expecting all moves to fail low indicates that something is not right. And most likely it will still fail low on the re-search when the depth returns to normal, and that is a LOT cheaper than accepting that fail-high (or actual score from a search that is too shallow) and then triggering a window-widening search, only to discover it really doesn't fail high like you thought...

IE it is better to just verify that the fail-high move is really going to fail high, rather than having to search ALL moves at this ply to see if that single move will fail high normally...
Bob,
Yes, I know that you prefer a gauntlet of engines over games against itself, but please, where did Lucas mention test positions?!?!

Lucas,
Glad to help, that's 2 improvements I've made to DiscoCheck. According to Sigma Chess, that means you've got about +30 ELO because of that.

Don,
That is an interesting idea. Maybe you could have a variable margin over depth, the idea being that at a higher depth, you may miss more. But then you pay the price of speed. Maybe that is something for you to try, Lucas? (*hint*)

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Post Reply