Qhapaq Lab

Principal Variation

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

概要

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

たとえば、

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

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

何に使うか

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

  • 前回反復の PV 手を次の反復で最初に読む
  • ルートで最善手候補として表示する
  • Principal Variation Searchの前提になる

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

PV-node

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

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

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

実装例

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

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;
}

実戦的には、

などの方法が使われる。

将棋AIでの位置づけ

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

特に、

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

といった現象は、探索不安定性や Aspiration Windowsの再探索と関係することがある。

注意点

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

関連項目

参考にしたホームページ