第IV部並列化とプロトコル

第13章定跡

将棋エンジンが序盤の数手を毎回ゼロから探索するのは非効率です。人間の棋士が定跡を暗記するように、エンジンもあらかじめ用意された「定跡データベース」を参照して、序盤の指し手を高速かつ高精度に決定できます。本章では、Hayanagi が採用する定跡機能の仕組みを詳しく見ていきます。

13.1 定跡（Opening Book）とは何か

定跡とは、序盤のある局面に対して「この手を指すべき」という情報をまとめたデータベースです。プロ棋士の棋譜や強力なエンジンの自己対局結果から構築されます。定跡を利用することで、探索を省略して即座に最善手を返すことができ、序盤の時間消費を大幅に削減できます。

Hayanagi では、やねうら王が採用する YANEURAOU-DB2016 フォーマットの定跡ファイルを読み込みます。これは広く普及しているフォーマットで、多くの定跡ファイルがこの形式で配布されています。

13.2 やねうら王 DB2016 フォーマットの構造

定跡ファイルはテキスト形式で、以下のような構造を持ちます。

#YANEURAOU-DB2016 1.00
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1
7g7f 3c3d 50 16 12345
2g2f 8c8d 30 14 9876
sfen lnsgkgsnl/1r5b1/ppppppppp/9/9/2P6/PP1PPPPPP/1B5R1/LNSGKGSNL w - 2
3c3d 8h2b+ 40 12 5432

構成要素は次の通りです。

ヘッダ行 — #YANEURAOU-DB2016 1.00 のようにバージョン情報を示します。# で始まる行はコメントとして読み飛ばされます。
SFEN 行 — sfen ... で始まり、局面を SFEN 文字列で記述します。以降の手エントリがこの局面に紐付きます。
手のエントリ — スペース区切りで 5 つのフィールドを持ちます。
- best_move — その局面での最善手（USI 形式）
- ponder_move — 相手の予測応手（none の場合もある）
- score — 評価値（cp 単位）
- depth — 探索深さ
- count — 出現回数や学習回数

1 つの SFEN に対して複数の手エントリが存在できます。 Hayanagi は現在、先頭のエントリ（最も優先度の高い手）を採用します。

13.3 BookEntry 構造体

定跡の 1 エントリは BookEntry 構造体で表現されます（book.h）。

struct BookEntry {
    std::string best_move;
    std::string ponder_move;
    int score = 0;
    int depth = 0;
    int count = 0;
};

フォーマットの 5 フィールドがそのままメンバに対応しています。手は USI 文字列のまま保持し、エンジンに渡す際にそのまま出力できるようにしています。

13.4 Book クラス

定跡全体を管理するのが Book クラスです（book.h）。

class Book {
public:
    bool load(const std::string& path);
    bool is_loaded() const { return loaded_; }
    const std::vector<BookEntry>* lookup(const std::string& sfen) const;

private:
    std::unordered_map<std::string, std::vector<BookEntry>> entries_;
    bool loaded_ = false;
};

内部データ構造は std::unordered_map で、SFEN 文字列をキーとして BookEntry のベクタを値として保持します。ハッシュマップなので、局面の検索は平均 O(1) で完了します。

13.4.1 load() — ファイル読み込みとパース処理

load() メソッドがファイルの読み込みとパースを行います（book.cpp）。

bool Book::load(const std::string& path) {
    entries_.clear();
    loaded_ = false;

    std::ifstream file(path);
    if (!file.is_open()) {
        return false;
    }

    std::string line;
    std::string current_sfen;

    while (std::getline(file, line)) {
        if (!line.empty() && line.back() == '\r') {
            line.pop_back();
        }
        if (line.empty() || line[0] == '#') {
            continue;
        }

        if (line.rfind("sfen ", 0) == 0) {
            current_sfen = line.substr(5);
            continue;
        }

        if (current_sfen.empty()) {
            continue;
        }

        std::istringstream iss(line);
        BookEntry entry;
        if (!(iss >> entry.best_move >> entry.ponder_move
                  >> entry.score >> entry.depth
                  >> entry.count)) {
            continue;
        }

        entries_[current_sfen].push_back(entry);
    }

    loaded_ = true;
    return true;
}

処理の流れは以下の通りです。

既存データをクリアしてファイルを開く。
1 行ずつ読み込みながら、CRLF 対応として末尾の \r を除去する。Windows 環境で作成されたファイルでも正しくパースできるようにするためです。
空行やコメント行（# 始まり）はスキップする。
sfen で始まる行は局面キーとして current_sfen に保存する。
それ以外の行は手エントリとしてパースし、current_sfen に紐付けて格納する。

13.4.2 lookup() — SFEN キーによる検索

const std::vector<BookEntry>* Book::lookup(const std::string& sfen) const {
    const auto it = entries_.find(sfen);
    if (it == entries_.end()) {
        return nullptr;
    }
    return &it->second;
}

SFEN 文字列を受け取り、対応するエントリのベクタへのポインタを返します。該当する局面がなければ nullptr を返します。ポインタを返すことで、不要なコピーを避けつつ「見つからなかった」ことも表現できます。

13.5 エンジンとの統合

定跡機能は UsiEngine クラスを通じてエンジンに統合されています。

13.5.1 関連オプション

usi_engine.h には以下のメンバが定義されています。

Book book_;
bool usi_own_book_ = true;
std::string book_dir_ = "book";
std::string book_file_ = "standard_book.db";
bool book_loaded_ = false;

USI の setoption コマンドで以下のオプションを設定できます。

USI_OwnBook — 定跡を使用するかどうか（デフォルト: true）
BookDir — 定跡ファイルのディレクトリ（デフォルト: book）
BookFile — 定跡ファイル名（デフォルト: standard_book.db、no_book で無効化）

13.5.2 isready 時の読み込み

定跡ファイルの読み込みは isready コマンド受信時に行われます。

if (line == "isready") {
    if (!book_loaded_ && usi_own_book_ && book_file_ != "no_book") {
        namespace fs = std::filesystem;
        fs::path book_path;
        fs::path dir(book_dir_);
        if (dir.is_absolute()) {
            book_path = dir / book_file_;
        } else {
            auto exe_dir = fs::path("/proc/self/exe");
            std::error_code ec;
            auto resolved = fs::read_symlink(exe_dir, ec);
            if (!ec) {
                book_path = resolved.parent_path() / dir / book_file_;
            } else {
                book_path = dir / book_file_;
            }
        }
        if (book_.load(book_path.string())) {
            std::cout << "info string book loaded " << book_path.string() << std::endl;
        } else {
            std::cout << "info string book not found " << book_path.string() << std::endl;
        }
        book_loaded_ = true;
    }
    std::cout << "readyok" << std::endl;
}

パスの解決では、BookDir が相対パスの場合は実行ファイルの場所を基準にします。 Linux 環境では /proc/self/exe のシンボリックリンクを辿って実行ファイルのディレクトリを取得しています。読み込み結果は info string で GUI に通知されます。

13.5.3 go 時の定跡参照フロー

start_search() の冒頭で定跡を参照します。

if (usi_own_book_ && book_.is_loaded() && !options.ponder) {
    const std::string sfen = snapshot.to_sfen();
    const auto* entries = book_.lookup(sfen);
    if (entries && !entries->empty()) {
        const BookEntry& entry = (*entries)[0];
        std::cout << "info string book hit " << entry.best_move
                  << " score " << entry.score
                  << " depth " << entry.depth
                  << " count " << entry.count << std::endl;
        std::cout << "bestmove " << entry.best_move;
        if (usi_ponder_.load() && entry.ponder_move != "none") {
            std::cout << " ponder " << entry.ponder_move;
        }
        std::cout << std::endl;
        return;
    }
}

フローを整理すると以下のようになります。

usi_own_book_ が有効かつ定跡がロード済みで、ponder 探索でないことを確認する。
現在の局面を to_sfen() で SFEN 文字列に変換し、定跡を検索する。
ヒットした場合、先頭エントリの best_move を即座に bestmove として返す。
USI_Ponder が有効で ponder_move が none でなければ、ponder 指定も付与する。
定跡にヒットしなかった場合は、通常の探索に進む。

このように、定跡参照は探索の前段階で行われ、ヒットすれば探索を完全にスキップします。序盤の時間節約と安定した指し手の選択を両立する仕組みです。