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
LMR Research
Moderators: hgm, Rebel, chrisw
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
LMR Research
Some believe in the almighty dollar.
I believe in the almighty printf statement.
I believe in the almighty printf statement.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR Research
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...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
You are talking hundreds of nodes not millions...
-
- Posts: 348
- Joined: Sat Feb 27, 2010 12:21 am
Re: LMR Research
Mind that PVS will eventually do a research anyway.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 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.
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: LMR Research
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.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 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.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: LMR Research
Thanks Matt. You're right!!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
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).
-
- Posts: 4366
- Joined: Fri Mar 10, 2006 5:23 am
- Location: http://www.arasanchess.org
Re: LMR Research
I tried an intermediate research approach a while back and it was not a winner for my program.
--Jon
--Jon
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR Research
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...lucasart wrote:Thanks Matt. You're right!!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
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).
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...
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: LMR Research
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.Don wrote: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.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 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.
Not seldom factor 6 overhead for a tad more reduction. That would mean it should improve your branching factor significantly to break even.
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: LMR Research
Bob, education is only useful for those who have the capacity to learn...bob wrote: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...lucasart wrote:Thanks Matt. You're right!!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
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).
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...
-
- Posts: 1334
- Joined: Sun Jul 17, 2011 11:14 am
Re: LMR Research
Bob,bob wrote: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...lucasart wrote:Thanks Matt. You're right!!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
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).
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...
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.
I believe in the almighty printf statement.