Late Move Reductions
Encyclopedia
Late Move Reductions is a non-game specific enhancement to the alpha-beta algorithm
and its variants which attempts to examine a game search tree
more efficiently. It uses the assumption that good game-specific move ordering causes a program to search the most likely moves early. If a cut-off is going to happen in a search, the first few moves are the ones most likely to cause them. In games like chess
, most programs
search winning captures and "killers
" first. LMR will reduce the search depth for moves searched later at a given node. This allows the program to search deeper along the critical lines, and play better.
Most chess programs will search the first several moves at a node to full depth. Often, they do not reduce moves considered to be very tactical, such as captures or promotions.
This search reduction can lead to a different search space than the pure alpha-beta method which can give different results. Care must be taken to select the reduction criteria or the search will miss some deep threats.
Alpha-beta pruning
Alpha-beta pruning is a search algorithm which seeks to decrease the number of nodes that are evaluated by the minimax algorithm in its search tree. It is an adversarial search algorithm used commonly for machine playing of two-player games...
and its variants which attempts to examine a game search tree
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
more efficiently. It uses the assumption that good game-specific move ordering causes a program to search the most likely moves early. If a cut-off is going to happen in a search, the first few moves are the ones most likely to cause them. In games like chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
, most programs
Computer chess
Computer chess is computer architecture encompassing hardware and software capable of playing chess autonomously without human guidance. Computer chess acts as solo entertainment , as aids to chess analysis, for computer chess competitions, and as research to provide insights into human...
search winning captures and "killers
Killer heuristic
In competitive two-player games, the killer heuristic is a technique for improving the efficiency of alpha-beta pruning, which in turn improves the efficiency of the minimax algorithm. This algorithm has an exponential search time to find the optimal next move, so general methods for speeding it...
" first. LMR will reduce the search depth for moves searched later at a given node. This allows the program to search deeper along the critical lines, and play better.
Most chess programs will search the first several moves at a node to full depth. Often, they do not reduce moves considered to be very tactical, such as captures or promotions.
This search reduction can lead to a different search space than the pure alpha-beta method which can give different results. Care must be taken to select the reduction criteria or the search will miss some deep threats.