Qhapaq Lab 
  # Late Move Reductions

Late Move Reductions（LMR）は、手の順序の後ろに出てくる手を浅く読むことで探索量を減らす手法である。
[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が良いほど、
後ろの手は有望でない可能性が高いので、深さを減らしても強さを保ちやすい。

## 概要

典型的には、

- 最初の数手は通常深さで読む
- それ以降の手は深さを `R` だけ減らして読む
- 減らした探索で fail-high した手だけ通常深さで再探索する

という流れを取る。

この考え方は、

- [PVS](/shogi/shogiwiki/search/principal-variation-search/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)

と並んで、現代的探索の強力な高速化技術のひとつである。

## なぜ有効か

[反復深化](/shogi/shogiwiki/search/iterative-deepening/)と[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)がうまく働いていれば、
有望な手はだいたい先頭付近に来る。

そのため、後ろの手は

- たいてい悪い
- 少し浅く読んでも cut される

ことが多い。

## 実装例

```cpp
int searchMoves(Position pos, int depth, int alpha, int beta) {
    int moveCount = 0;

    for (Move move : generateMoves(pos)) {
        ++moveCount;
        Position next = doMove(pos, move);

        int reduction = 0;
        if (depth >= 3 && moveCount > 3 && isQuiet(move)) {
            reduction = 1;
        }

        int score = -search(next, depth - 1 - reduction, -alpha - 1, -alpha);

        if (reduction > 0 && score > alpha) {
            score = -search(next, depth - 1, -beta, -alpha);
        }

        if (score >= beta) {
            return score;
        }
        if (score > alpha) {
            alpha = score;
        }
    }

    return alpha;
}
```

現代エンジンでは、`depth` と `moveCount` の両方に応じて reduction 量を変えることが多い。

## reduction を変える材料

- 深いノードほど多く減らす
- 後ろの手ほど多く減らす
- 王手の手や捕獲手は減らしにくくする
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)が高い手は減らしにくくする
- cut-node 予想では多めに減らす

## 将棋AIでの位置づけ

将棋は分岐数が大きいため、LMR の効果が出やすい。
一方で、

- 王手
- 受け
- 成り
- 駒の取り合い

のような戦術的な手は、後ろに並んでいても重要な場合がある。
そのため、どの手を reduction の対象にするかは慎重な設計が必要である。

## 注意点

- 手の並べ替えが悪いと、有望手を浅く読んでしまう危険がある
- reduction しすぎると tactical miss が増える
- 再探索条件をどう置くかで強さが大きく変わる

## 関連項目

- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [Null Move Pruning](/shogi/shogiwiki/search/null-move-pruning/)
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)

## 参考にしたホームページ

- [Chessprogramming Wiki: LATE MOVE Reductions](https://www.chessprogramming.org/Late_Move_Reductions)
- [Chessprogramming Wiki: MOVE Ordering](https://www.chessprogramming.org/Move_Ordering)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)