Source of Principal Variation - Computer Shogi Wiki

  # Principal Variation

Principal Variation（PV、従来「主変化」とも呼ばれる）は、その時点で探索器が最善とみなしている読み筋である。
解析時にエンジンが表示する「候補手列」の本体であり、
[反復深化](/shogi/shogiwiki/search/iterative-deepening/)や[手の並べ替え](/shogi/shogiwiki/search/move-ordering/)でも重要な役割を持つ。

## 概要

[ミニマックス法](/shogi/shogiwiki/search/minimax/)や[アルファベータ法](/shogi/shogiwiki/search/alpha-beta/)では、
ルートから葉までさまざまな候補手順を調べる。
その中で、現在もっとも良いと評価されている手順列が Principal Variation である。

たとえば、

- ルートで `7六歩`
- 相手が `3四歩`
- こちらが `2六歩`

という順が最善と見えているなら、この列が PV になる。

## 何に使うか

Principal Variation は表示用だけでなく、探索の効率化にも使われる。

- 前回反復の PV 手を次の反復で最初に読む
- ルートで最善手候補として表示する
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)の前提になる

つまり PV は、「読み筋の説明」と「次の探索の手掛かり」の両方を兼ねている。

## PV-node

Principal Variation 上にあるノードは `PV-node` と呼ばれる。
PV-node では正確な値が必要なので、

- 探索窓を広めに取る
- 一部の枝刈りを弱める

といった実装上の違いが入ることが多い。

## 実装例

単純な方法では、子ノードから最善手列を受け取り、親で先頭に自分の手を付ける。

```cpp
struct SearchResult {
    int score;
    std::vector<Move> pv;
};

SearchResult search(Position pos, int depth) {
    SearchResult best{ -INF, {} };

    for (Move move : generateMoves(pos)) {
        Position next = doMove(pos, move);
        SearchResult child = search(next, depth - 1);
        int score = -child.score;

        if (score > best.score) {
            best.score = score;
            best.pv.clear();
            best.pv.push_back(move);
            best.pv.insert(best.pv.end(), child.pv.begin(), child.pv.end());
        }
    }

    return best;
}
```

実戦的には、

- [Triangular PV-Table](/shogi/shogiwiki/search/triangular-pv-table/)
- stack 上の PV バッファ
- [置換表](/shogi/shogiwiki/search/transposition-table/)からの復元

などの方法が使われる。

## 将棋AIでの位置づけ

将棋AIでは、USI の `info pv ...` に出る読み筋がこれにあたる。
対局時の最善手選択だけでなく、解析やデバッグにも重要である。

特に、

- PV が頻繁に揺れる
- 深くなると急に別の筋へ飛ぶ

といった現象は、[探索不安定性](/shogi/shogiwiki/search/search-instability/)や
[Aspiration Windows](/shogi/shogiwiki/search/aspiration-windows/)の再探索と関係することがある。

## 注意点

- [置換表](/shogi/shogiwiki/search/transposition-table/)から PV を復元すると、不完全な列になることがある
- fail-high だけでは正確な PV が得られないことがある
- 表示用の PV と内部で保持する PV の実装を混同しない方がよい

## 関連項目

- [反復深化](/shogi/shogiwiki/search/iterative-deepening/)
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)

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

- [Chessprogramming Wiki: Principal Variation](https://www.chessprogramming.org/Principal_Variation)
- [Chessprogramming Wiki: Triangular PV Table](https://www.chessprogramming.org/Triangular_PV-Table)
- [Chessprogramming Wiki: Principal Variation Search](https://www.chessprogramming.org/Principal_Variation_Search)
Principal Variation principal-variation
