Source of Triangular PV-Table - Computer Shogi Wiki

  # Triangular PV-Table

Triangular PV-Table は、
[Principal Variation](/shogi/shogiwiki/search/principal-variation/)を保持するための古典的なデータ構造である。
ply ごとに「その深さから先の最善手列」を格納するため、
全体として三角形状のメモリ配置になる。

## 概要

探索中に best move が更新されたら、
子ノードで得られた PV を親へコピーし、
先頭に自分の手を付ける。

深さ `d` のノードは最大で `d` 手ぶんの PV を持つので、

- 根は長い PV
- 深いノードほど短い PV

となり、配列の使用量が三角形状になる。

これは、

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

の実装で長く使われてきた。

## どのように格納するか

最も単純には、`pv[ply][remainingDepth]` のような 2 次元配列を用意する。
best move が見つかったら、

1. `pv[ply][0]` にその手を書く
2. `pv[ply + 1]` の内容を後ろへコピーする

という流れになる。

## 実装例

```cpp
Move pvTable[MAX_PLY][MAX_PLY];
int pvLength[MAX_PLY];

void updatePv(int ply, Move bestMove) {
    pvTable[ply][0] = bestMove;

    for (int i = 0; i < pvLength[ply + 1]; ++i) {
        pvTable[ply][i + 1] = pvTable[ply + 1][i];
    }

    pvLength[ply] = pvLength[ply + 1] + 1;
}
```

この方法は分かりやすい一方で、
毎回コピーが入る。
そのため実戦的には、

- 1 次元配列に三角形状で詰める
- stack 上の PV バッファを使う
- [置換表](/shogi/shogiwiki/search/transposition-table/)から PV を復元する

といった代替も用いられる。

## 将棋AIでの位置づけ

将棋AIでは USI の `info pv` 出力が重要なので、
Principal Variation を安定して組み立てる仕組みが必要になる。

現代的なエンジンでは、
[置換表](/shogi/shogiwiki/search/transposition-table/)から PV を復元する方式も多いが、
Triangular PV-Table は仕組みが明快で、

- デバッグしやすい
- 実装の学習に向く
- 短い PV や欠けた PV の原因を切り分けやすい

という利点がある。

## 注意点

- ノードごとにコピーが発生するため実装次第では重い
- [置換表](/shogi/shogiwiki/search/transposition-table/)併用時は、どちらを表示用の正本にするか決めた方がよい
- [探索不安定性](/shogi/shogiwiki/search/search-instability/)が強いと PV も揺れやすい

## 関連項目

- [Principal Variation](/shogi/shogiwiki/search/principal-variation/)
- [Principal Variation Search](/shogi/shogiwiki/search/principal-variation-search/)
- [置換表](/shogi/shogiwiki/search/transposition-table/)

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

- [Chessprogramming Wiki: Triangular PV Table](https://www.chessprogramming.org/Triangular_PV-Table)
- [Chessprogramming Wiki: Principal Variation](https://www.chessprogramming.org/Principal_Variation)
- [TalkChess スレッド](https://talkchess.com/viewtopic.php?t=13150)
- [Google Sites](https://sites.google.com/site/tscpchess/principal-variation)
Triangular PV-Table triangular-pv-table
