Qhapaq Lab

Triangular PV-Table

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

概要

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

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

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

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

これは、

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

どのように格納するか

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

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

という流れになる。

実装例

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 バッファを使う
  • 置換表から PV を復元する

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

将棋AIでの位置づけ

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

現代的なエンジンでは、 置換表から PV を復元する方式も多いが、 Triangular PV-Table は仕組みが明快で、

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

という利点がある。

注意点

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

関連項目

参考にしたホームページ