LMR Research

[ZirconiumX]

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

[bob]

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

[marcelk]

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.

[Don]

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.

[lucasart]

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]

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

--Jon

[bob]

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]

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]

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]

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