Floating Move Reduction
Posted: Wed Sep 14, 2016 7: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:
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.
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 (legal_moves_made<9) return 0
if (reduced = 0) return 0
if (depth>3) return 0
if friendly pawn attacks enemy piece then return 1
if (piece and not friendly queen) attacks enemy queen then return 1
if piece attacks undefended pawn then return 1
if (piece_gives_check) return 1
if (psqt(moveto) - psqt(movefrom) > 0) return 1
return 0
}
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.