Floating Move Reduction

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.
Post Reply
D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Floating Move Reduction

Post by D Sceviour » Wed Sep 14, 2016 5:47 pm

Here is an experiment with a floating move reduction as an addition to late move reduction. It is similar to the tests that are commonly used for move sorting. The idea is to apply a similar test to move reductions near the horizon depth.

The calculation begins in a fail-low move list after the standard ordered moves have been tried, and a few ordinary moves have been tried to improve the position. The magic number is about move number 9 on the move list. An aggressive reduction can then be applied to all subsequent moves.

However, a very good move could appear anywhere in the move list. The classical approach to LMR can make the best move even harder to find by pushing the solution over the horizon. It is an interesting idea to resolve hanging positions with an extra ply, but not too much depth to explode the search. Quiescence often cuts off the search before the position is resolved. Tracing often shows a position score collapses on the horizon when the Queen is hanging. When a piece is attacked, can it escape?

For ordinary non-capturing moves in shallow depths where a reduction has already been made, in pseudo code:

Code: Select all

int Ordinary_SEE(move) {

if &#40;legal_moves_made<9&#41; return 0
if &#40;reduced = 0&#41; return 0
if &#40;depth>3&#41; return 0

if friendly pawn attacks enemy piece then return 1
if &#40;piece and not friendly queen&#41; attacks enemy queen then return 1
if piece attacks undefended pawn then return 1
if &#40;piece_gives_check&#41; return 1
if &#40;psqt&#40;moveto&#41; - psqt&#40;movefrom&#41; > 0&#41; return 1
return 0
&#125;
The return value indicates an extension (or less reduction) is appropriate. Program code can be modified efficiently to adapt to this. Very few moves in a list meet these conditions so a search explosion should not be noticed. Better score, good hash scores and improved saved best move should reduce the total number of nodes searched.

The main problem is taking the time to collect the information necessary for the evaluation. For example, a program might not have enough information to determine if a pawn is undefended. The test has to be very fast since it is performed on almost every move. However, it does have the advantage that the test can be delayed until the move is actually made, more SEE type calculations can made, and thus the demands on LMR move sorting are relaxed.

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Floating Move Reduction

Post by D Sceviour » Sun Sep 18, 2016 4:42 pm

Wonder why there were no comments? Maybe this is the most brilliant thing ever posted and leaves readers speechless.

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: Floating Move Reduction

Post by Desperado » Mon Sep 19, 2016 3:32 pm

D Sceviour wrote:Wonder why there were no comments? Maybe this is the most brilliant thing ever posted and leaves readers speechless.
Hi Dennis.

Well, i think it is not very clear what the general idea should be.

You provide an extension pattern that simply includes some rules. Some of the rules are pretty common like the check extension and the combination of the rules is certainly very sensitive to each engine.

The fact that you choose an arbitary ("magic") number of 9 moves does not make a general idea out of it.

The next thing is, that by the given description, it is unclear what you might mean with "extra ply". I am pretty sure you do not want to extend all moves with an index above 9 but you might want to limit the reduction for late moves.

So, different reduction levels based on move features would be the general idea, but it is not a new idea.

Finally, what is the context for "floating move" reduction ?!

:)

So, it looks like there is nothing new and the given conditions are used for extensions and reductions in many different ways already. The same for different extension and reduction weights.

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Floating Move Reduction

Post by D Sceviour » Mon Sep 19, 2016 5:42 pm

Thank you for the response.
Desperado wrote:Some of the rules are pretty common like the check extension and the combination of the rules is certainly very sensitive to each engine.

True. A check extension is standard practice and there is nothing new. In the mesh of thing things happening it was an idea to keep track of how much extension and reduction takes place for checks.
Desperado wrote:The fact that you choose an arbitrary ("magic") number of 9 moves does not make a general idea out of it.
No. It is a magic number found from a crystal ball. :)
Desperado wrote:The next thing is, that by the given description, it is unclear what you might mean with "extra ply".
An extra ply means instead of reducing 3, then reduce 2 for example.
Desperado wrote:Finally, what is the context for "floating move" reduction ?!
The amount of reduction is not based on move count number (except for magic 9). All moves receive the same initial amount of reduction. The amount of reduction "floats" down the move list. This is based on the theoretical observation that a move list is not binomially distributed, and that a good move could appear anywhere in the move list. This is new stuff.

Many posts concern move ordering based on captures and killers. That is important but the topic is exhausted. The theoretical and philosophical approach to a move list could be based on threats - not captures. Null move search exposes threats such as hanging pieces very quickly. By taking the extra time to identify threats in advance, overall node counts should be reduced (at least it does for me).

User avatar
cdani
Posts: 2095
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Floating Move Reduction

Post by cdani » Mon Sep 19, 2016 6:40 pm

From long time I had the general idea that move sorting can be improved a lot, specially at moves that will be seen at high depths so the engine should be able to spend more time sorting them.

I'm not sure if I understood your idea, but seems like an improved SEE. I had this global idea also and I already analyze on Andscacs some fast stuff inside quiet move sorting function, before starting to analyze each move, to save some time on clearly bad moves, but only if history of the move is 0.

All of this seems a clear field of improvement for the current engines, even the top ones.

D Sceviour
Posts: 389
Joined: Mon Jul 20, 2015 3:06 pm
Contact:

Re: Floating Move Reduction

Post by D Sceviour » Mon Sep 19, 2016 8:54 pm

Hello Daniel,
Perhaps it might less confusing to name the idea STE (Static Threat Evaluation) rather than SEE (Static Exchange Evaluation).

Post Reply