Reduction reductions reductions

  # Reduction

Reduction は、特定の手やノードに対して探索深さを減らす手法の総称である。
[Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)が代表例であり、
現代的な alpha-beta 探索では重要な高速化技術になっている。

## 概要

発想は extension の逆で、

- この手は重要そうだから深く読む

ではなく、

- この手は重要でない可能性が高いから浅く読む

という判断を使う。

典型的には、

- 後ろに並んだ quiet move
- hash move でも capture でも check でもない手

に対して reduction をかける。

## 実装例

```cpp
int reduction = 0;

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

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

浅く読んだ結果が良ければ、通常深さで再探索するのが一般的である。

## 代表例

- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- Internal Iterative Reductions

また、[Improving](/shogi/shogiwiki/search/improving/)やノードタイプによって reduction 量を変えることも多い。

## Extension との関係

- [Extension](/shogi/shogiwiki/search/extensions/)
  重要な手を深く読む
- Reduction
  重要でなさそうな手を浅く読む

という対称的な関係にある。

現代的な探索では、全体としては reduction の方が大きな役割を持つことが多い。

## 将棋AIでの位置づけ

将棋は分岐数が大きいので、reduction の恩恵が大きい。
ただし、

- 王手
- 受け
- 成り
- 打つ手

のような tactical な手を浅く読みすぎると危険である。

## 注意点

- reduction しすぎると tactical miss が増える
- [手の並べ替え](/shogi/shogiwiki/search/move-ordering/)が悪いと有望手まで浅く読んでしまう
- extension や pruning との全体バランスが重要

## 関連項目

- [Late Move Reductions](/shogi/shogiwiki/search/late-move-reductions/)
- [Improving](/shogi/shogiwiki/search/improving/)
- [ノードタイプ](/shogi/shogiwiki/search/node-types/)
- [Extension](/shogi/shogiwiki/search/extensions/)

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

- [Chessprogramming Wiki: Reductions](https://www.chessprogramming.org/Reductions)
- [Chessprogramming Wiki: LATE MOVE Reductions](https://www.chessprogramming.org/Late_Move_Reductions)
- [Chessprogramming Wiki: Internal Iterative Reductions](https://www.chessprogramming.org/Internal_Iterative_Reductions)