Qhapaq Lab 
  # Late Move Pruning

Late Move Pruning（LMP）は、手の順序のかなり後ろにある quiet move を、
そもそも探索せずに打ち切る前方枝刈りである。
[Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)と近い考え方だが、
LMR が「浅く読む」のに対し、LMP は「読まない」点が異なる。

## 概要

LMP は、

- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)がよく効いている
- 後ろの quiet move は有望でないことが多い

という前提を使う。

そこで、たとえば

- 非 PV-node
- 深さが浅い
- 王手でない
- moveCount がしきい値を超えた

といった条件を満たした quiet move を省く。

実装上は [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/) の近縁として扱われることも多い。

## LMR との関係

[Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)は、
後ろの手をまず浅く読んで、危険そうなら再探索する。
一方 LMP は、浅い深さでは「その手はまず読まなくてよい」と判断して飛ばす。

このため LMP は LMR より強い選択性を持ち、
誤ると tactical miss に直結しやすい。

## 実装例

```cpp
for (Move move : generateMoves(pos)) {
    ++moveCount;

    if (!pvNode
        && depth <= 4
        && moveCount > lateMovePruningLimit(depth)
        && isQuiet(move)
        && !inCheck(pos)
        && !givesCheck(move)) {
        continue;
    }

    Position next = doMove(pos, move);
    int score = -search(next, depth - 1, -beta, -alpha);

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

## 将棋AIでの位置づけ

将棋は分岐数が大きいので、浅いノードで late move を省く効果が出やすい。
ただし、

- 王手
- 受け
- 成り
- 打ちによる急所手

のように、後ろに並んでいても重要な手がある。

そのため将棋AIでは、
[history heuristic](/shogi/shogiwiki/search/history-heuristic/)や
[Countermove Heuristic](/shogi/shogiwiki/search/countermove-heuristic/)を併用し、
本当に読まなくてよい手だけを対象に絞ることが多い。

## 注意点

- 手の並べ替えが悪いと有望手を丸ごと捨ててしまう
- [静止探索](/shogi/shogiwiki/search/quiescence-search/)直前では条件を慎重に置く必要がある
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)が強い局面では aggressive にしすぎない方がよい

## 関連項目

- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Move Count Based Pruning](/shogi/shogiwiki/search/move-count-based-pruning/)
- [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)

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

- [Chessprogramming Wiki: LATE MOVE Pruning](https://www.chessprogramming.org/Late_Move_Pruning)
- [Chessprogramming Wiki: Pruning](https://www.chessprogramming.org/Pruning)
- [www.arasanchess.org: Programr.Shtml](https://www.arasanchess.org/programr.shtml)
- [www.linuxlinks.com: Laser UCI Compliant Chess Engine](https://www.linuxlinks.com/laser-uci-compliant-chess-engine/)