Qhapaq Lab 
  # Move Count Based Pruning

Move Count Based Pruning（MCBP）は、
あるノードで一定数の手を読んだ後、それ以降の late quiet moves を省く枝刈りである。
実務上は [Late Move Pruning](/shogi/shogiwiki/search/late-move-pruning/) とほぼ重なることが多く、
LMP を move count しきい値で定式化した説明として扱われることもある。

## 概要

基本的な考え方は単純で、

- 先頭の数手は読む
- moveCount が深さに応じたしきい値を超えたら
- 後続の quiet move を打ち切る

というものである。

この判定は主に、

- 非 PV-node
- 深さが浅い
- 王手中ではない
- tactical な手ではない

といった条件の下で使われる。

## なぜ有効か

[反復深化](/shogi/shogiwiki/search/iterative-deepening/)と
[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が十分に機能していれば、
有望な手は上位に並ぶ可能性が高い。

そのため、後ろの quiet move をまとめて省くことで、
探索量を大きく減らせる。

特に shallow node では、
1 手 1 手を浅く読むより、怪しい手を最初から読まない方が効率がよいことがある。

## 実装例

```cpp
int pruneAfter = 3 + depth * depth;

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

    if (!pvNode
        && depth <= 5
        && moveCount > pruneAfter
        && 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;
    }
}
```

しきい値は固定値ではなく、

- depth
- [history heuristic](/shogi/shogiwiki/search/history-heuristic/)
- [improving](/shogi/shogiwiki/search/improving/)
- ノードタイプ

で調整されることが多い。

## 将棋AIでの位置づけ

将棋AIでも、浅い探索で分岐を抑える補助として有効である。
ただし将棋では、

- 打ちによる詰めろ
- 成りで急変する手
- 受けの急所

が後ろから出てくることがあるため、静的条件だけで強く刈りすぎると危険である。

実際には、[Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)、
[Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)、
[Static Exchange Evaluation](/shogi/shogiwiki/search/static-exchange-evaluation/)などと組み合わせて使われる。

## 注意点

- move count のしきい値が小さすぎると tactical miss が増える
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が前提なので ordering が弱いと危険
- [PV-node](/shogi/shogiwiki/search/node-types/)では通常使わない

## 関連項目

- [Late Move Pruning](/shogi/shogiwiki/search/late-move-pruning/)
- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Futility Pruning](/shogi/shogiwiki/search/futility-pruning/)
- [Improving](/shogi/shogiwiki/search/improving/)

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

- [Chessprogramming Wiki: MOVE Count Based Pruning](https://www.chessprogramming.org/Move_Count_Based_Pruning)
- [Chessprogramming Wiki: Pruning](https://www.chessprogramming.org/Pruning)
- [www.arasanchess.org: Programr.Shtml](https://www.arasanchess.org/programr.shtml)
- [GitHub: matthiaslang/jackychess](https://github.com/matthiaslang/jackychess)