Source of Aspiration Windows aspiration-windows

  # Aspiration Windows

Aspiration Windows は、[反復深化](/shogi/shogiwiki/search/iterative-deepening/)の前回反復で得た評価値の近くに探索窓を絞って、
[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)や[PVS](/shogi/shogiwiki/search/principal-variation-search/)を高速化する手法である。

## 概要

通常のルート探索では、最初は非常に広い探索窓を使う。
しかし前回反復の評価値がすでに分かっているなら、

- 今回の評価値もその近くにあるだろう

と期待できる。

そこで、たとえば

- 前回の評価値が `+80`
- 今回の初期窓を `[-20, +180]`

のように狭めて探索する。

窓が狭いほど枝刈りが増え、探索は速くなる。

## fail-high / fail-low

問題は、本当の評価値が窓の外に出る場合である。

- 真の値が `beta` 以上なら fail-high
- 真の値が `alpha` 以下なら fail-low

となり、探索をやり直す必要がある。

そのため実装では、失敗した側の境界だけを徐々に広げる
`gradual widening` がよく使われる。

## 実装例

```cpp
int aspirationSearch(Position pos, int depth, int guess) {
    int delta = 32;
    int alpha = guess - delta;
    int beta  = guess + delta;

    while (true) {
        int score = pvs(pos, depth, alpha, beta);

        if (score <= alpha) {
            alpha -= delta;
            delta *= 2;
            continue;
        }
        if (score >= beta) {
            beta += delta;
            delta *= 2;
            continue;
        }
        return score;
    }
}
```

このように、片側だけを広げて再探索することが多い。

## 反復深化との関係

Aspiration Windows は、前回反復の値を初期予測として使うため、
[反復深化](/shogi/shogiwiki/search/iterative-deepening/)とほぼセットで使われる。

また、[PVS](/shogi/shogiwiki/search/principal-variation-search/)とも相性が良い。

## 将棋AIでの位置づけ

将棋AIでは、

- 反復深化
- PVS
- Aspiration Windows

がまとめてルート探索の骨格になることが多い。

ただし局面が不安定なときや、詰み筋が見え始めたときは評価値が大きく跳ねるため、
再探索のコストが増えることがある。

## 注意点

- [探索不安定性](/shogi/shogiwiki/search/search-instability/)が強いと再探索が増えやすい
- 窓を狭くしすぎると、かえって遅くなることがある
- fail-high / fail-low 時にどちらの境界をどう広げるかは実装差が大きい

## 関連項目

- [アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)
- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)

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

- [Chessprogramming Wiki: Aspiration Windows](https://www.chessprogramming.org/Aspiration_Windows)
- [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search)
- [Chessprogramming Wiki: Search](https://www.chessprogramming.org/Search)
Aspiration Windows aspiration-windows aspiration-windows
