Late Move Pruning（LMP）は、手の順序のかなり後ろにある quiet move を、 そもそも探索せずに打ち切る前方枝刈りである。 Late Move Reductionsと近い考え方だが、 LMR が「浅く読む」のに対し、LMP は「読まない」点が異なる。
LMP は、
という前提を使う。
そこで、たとえば
といった条件を満たした quiet move を省く。
実装上は Futility Pruning の近縁として扱われることも多い。
Late Move Reductionsは、 後ろの手をまず浅く読んで、危険そうなら再探索する。 一方 LMP は、浅い深さでは「その手はまず読まなくてよい」と判断して飛ばす。
このため LMP は LMR より強い選択性を持ち、 誤ると tactical miss に直結しやすい。
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;
}
}将棋は分岐数が大きいので、浅いノードで late move を省く効果が出やすい。 ただし、
のように、後ろに並んでいても重要な手がある。
そのため将棋AIでは、 history heuristicや Countermove Heuristicを併用し、 本当に読まなくてよい手だけを対象に絞ることが多い。