第II部局面管理と合法手生成

第6章合法手生成

将棋エンジンの核心部分ともいえる合法手生成について解説します。局面に対して指せる手をすべて正確に列挙する処理は、探索の土台であり、そのパフォーマンスがエンジン全体の速度を大きく左右します。

6.1 設計思想: 疑似合法手生成 vs 直接合法手生成

合法手生成には大きく分けて2つのアプローチがあります。

疑似合法手生成 + フィルタ方式は、王手を考慮せず全ての「疑似合法手」を生成してから自玉への王手をチェックする方式です。実装はシンプルですが無駄な計算が発生します。

Hayanagi は直接合法手生成方式を採用しています。ピン（動かすと自玉に王手がかかる駒）と王手の状態を事前に計算し、最初から合法な手だけを生成します。具体的には、(1) compute_pins_and_checks() でピンと王手を同時検出、 (2) 王手の数に応じて分岐（両王手なら玉移動のみ）、 (3) ピンされた駒は移動ライン上にのみ移動可能、 (4) 各駒種の手を直接生成、という流れです。

6.2 generate_legal_moves() のエントリポイント

Position クラスには、合法手生成のための複数のオーバーロードが用意されています。

// position.h より
std::vector<Move> generate_legal_moves() const;
std::vector<Move> generate_legal_moves(bool include_drops,
                                        bool enforce_pawn_drop_mate) const;
std::vector<Move> generate_search_legal_moves() const;
std::vector<Move> generate_quiescence_moves() const;
std::vector<Move> generate_checking_moves() const;

これらはすべて、最終的に以下のプライベートメソッドに委譲されます。

// position.cpp 1228行目
std::vector<Move> Position::generate_legal_moves(bool include_drops,
                                                 bool enforce_pawn_drop_mate,
                                                 MoveSelection selection) const {
    std::vector<Move> moves;
    moves.reserve(256);
    const Color color = side_to_move_;
    const auto& t = tables();
    const Bitboard own_occ = color_bb_[static_cast<int>(color)];

    Bitboard checkers;
    Bitboard pinned;
    std::array<Bitboard, kSquareCount> pin_lines{};
    compute_pins_and_checks(color, checkers, pinned, pin_lines);

    const int check_count = checkers.count();
    const bool in_check = check_count > 0;
    generate_king_moves(color, selection, in_check, moves);
    if (check_count >= 2) {
        return moves;
    }
    // ... 以下、個別の駒種の手生成が続く
}

各公開メソッドは MoveSelection を変えてこのプライベートメソッドに委譲しています。 moves.reserve(256) は典型的な局面の手数をカバーする初期確保で、再アロケーションの回数を減らします。

6.3 MoveSelection 列挙型

MoveSelection は、生成する手の種類を制御するための列挙型です。

// position.h 70行目
enum class MoveSelection : int {
    All = 0,
    Tactical,
    Checking,
};

値	用途	生成される手
`All`	通常探索	全ての合法手
`Tactical`	静止探索	駒取り・成り・王手回避手
`Checking`	王手生成	相手玉に王手をかける手のみ

フィルタリングは should_keep_generated_move() で行われます（後述）。全ての手を一度生成してからフィルタするのではなく、各手の生成時点で即座にフィルタが適用される設計です。

6.4 compute_pins_and_checks() — ピンと王手の同時検出

合法手生成の前処理として、ピンされている駒と王手をかけている駒を同時に検出します。この処理は盤面の8方向（縦横斜め）の X 線（X-ray）検出に基づいています。

// position.cpp 1036行目
void Position::compute_pins_and_checks(Color color,
                                       Bitboard& checkers,
                                       Bitboard& pinned,
                                       std::array<Bitboard, kSquareCount>& pin_lines) const {
    const auto& t = tables();
    const Color enemy = opposite(color);
    const int king_square = find_king(color);

    checkers = attackers_to(king_square, enemy);
    pinned = Bitboard{};
    for (auto& line : pin_lines) {
        line = t.all_squares;
    }

    for (int dir = 0; dir < 8; ++dir) {
        int candidate = -1;
        for (int index = 0; index < t.ray_lengths[king_square][dir]; ++index) {
            const int sq = t.ray_squares[king_square][dir][index];
            const int piece = board_[sq];
            if (is_empty(piece)) {
                continue;
            }
            if (piece_color(piece) == color) {
                if (candidate != -1) {
                    break;
                }
                candidate = sq;
                continue;
            }
            if (!is_slider_for_direction(piece_type(piece), enemy, dir)) {
                break;
            }
            if (candidate != -1) {
                pinned.set(candidate);
                pin_lines[candidate] = t.between[king_square][sq] | t.square_bb[sq];
            }
            break;
        }
    }
}

アルゴリズムの詳細

処理は2段階で構成されています。

第1段階として、attackers_to(king_square, enemy) で王手駒のビットボード (checkers) を取得します。第2段階として、自玉から8方向にレイ（ray）を飛ばし、以下のロジックでピンを検出します。

レイ上の各マスを自玉から順に走査する
空きマスはスキップする
自分の駒を見つけたら、ピン候補 (candidate) として記録する。ただし既に候補がある場合（自分の駒が2つ並んでいる場合）は、その方向のピンはありえないので打ち切る
敵の駒を見つけた場合:
- その駒がその方向のスライダーでなければ (is_slider_for_direction が false)、打ち切る
- スライダーであり、かつ候補があれば、候補の駒はピンされている

ピンされた駒の移動可能範囲は pin_lines[candidate] に設定されます。これは玉と敵スライダーの間のマス (t.between[king_square][sq]) と敵スライダー自身のマス (t.square_bb[sq]) の和集合です。つまり、ピンされた駒はピンラインの上でのみ移動（合駒位置への移動、または敵スライダーの駒取り）が許されます。

ピンされていない駒の pin_lines は t.all_squares（全マス）に初期化されているため、移動制限がかからない仕組みです。

6.5 両王手時の処理（玉移動のみ）

両王手（double check）の場合、2つの駒から同時に王手がかかっているため、合駒や駒取りでは王手を解消できません。唯一の選択肢は玉を動かすことです。

    const int check_count = checkers.count();
    const bool in_check = check_count > 0;
    generate_king_moves(color, selection, in_check, moves);
    if (check_count >= 2) {
        return moves;  // 両王手: 玉移動のみで即座にリターン
    }

このように、check_count >= 2 の場合は generate_king_moves() の結果だけを返します。王手している駒の数を数えるだけで、大幅な枝刈りが実現できています。

6.6 単王手時の move_mask（合駒・駒取りの制限）

王手をかけている駒が1つだけの場合（単王手）、玉以外の駒による王手回避方法は以下の2つです。

駒取り: 王手している駒を取る
合駒: 王手している駒と玉の間に駒を挟む（スライダーによる王手の場合のみ）

    Bitboard move_mask = t.all_squares;
    if (check_count == 1) {
        Bitboard single = checkers;
        const int checker_square = single.pop_lsb();
        move_mask = t.square_bb[checker_square];
        const PieceType checker_type = piece_type(board_[checker_square]);
        if (checker_type == PieceType::Lance || checker_type == PieceType::Bishop ||
            checker_type == PieceType::Rook || checker_type == PieceType::Horse ||
            checker_type == PieceType::Dragon) {
            move_mask |= t.between[find_king(color)][checker_square];
        }
    }

move_mask は「玉以外の駒が移動できるマスの集合」です。王手がない場合は全マス、単王手の場合は王手駒のマス（駒取り）とスライダーの場合は間のマス（合駒）の和集合になります。桂馬や歩による王手の場合はその駒を取る以外に回避方法がありません（玉移動を除く）。

6.7 generate_king_moves() — 玉の移動生成

玉の移動は他の駒と異なり、移動先が敵に攻撃されていないことを確認する必要があります。

// position.cpp 1077行目
void Position::generate_king_moves(Color color,
                                   MoveSelection selection,
                                   bool in_check,
                                   std::vector<Move>& moves) const {
    const int from = find_king(color);
    Bitboard targets = attacks_from(from, PieceType::King, color, occupied_);
    targets &= ~color_bb_[static_cast<int>(color)];
    const Color enemy = opposite(color);

    while (targets.any()) {
        const int to = targets.pop_lsb();
        const Move move{from, to, PieceType::King, false, false};
        if (!is_square_attacked_after_king_move(to, enemy, from) &&
            should_keep_generated_move(move, selection, in_check)) {
            moves.push_back(move);
        }
    }
}

ポイントは is_square_attacked_after_king_move(to, enemy, from) です。「玉が from からいなくなった状態で to が攻撃されているか」を判定し、玉自身が遮蔽物となっているケース（背後のスライダーから逃げる方向に動く場合）を正しく処理します。 targets &= ~color_bb_[...] で自分の駒がいるマスへの移動を除外しています。

6.8 generate_piece_moves() — 各駒種の移動生成

玉以外の全駒種は generate_piece_moves() で統一的に処理されます。

// position.cpp 1096行目
void Position::generate_piece_moves(Color color,
                                    PieceType type,
                                    Bitboard pieces,
                                    const Bitboard& own_occ,
                                    const Bitboard& move_mask,
                                    const Bitboard& pinned,
                                    const std::array<Bitboard, kSquareCount>& pin_lines,
                                    MoveSelection selection,
                                    bool in_check,
                                    std::vector<Move>& moves) const {
    while (pieces.any()) {
        const int from = pieces.pop_lsb();
        Bitboard targets = attacks_from(from, type, color, occupied_);
        targets &= ~own_occ;
        targets &= move_mask;
        if (pinned.test(from)) {
            targets &= pin_lines[from];
        }

        while (targets.any()) {
            const int to = targets.pop_lsb();
            add_move_variants(from, to, type, selection, in_check, moves);
        }
    }
}

ピンされた駒の移動ライン制限

pinned.test(from) が true の場合、その駒はピンラインの上でしか動けません。 targets &= pin_lines[from] により、ピンライン外への移動が除外されます。ピンされていない駒は pin_lines[from] が all_squares のため、この AND 演算は実質的に無効です。

move_mask による王手回避の制限

targets &= move_mask により、王手がかかっている場合は合駒・駒取り可能なマスのみに制限されます。王手がかかっていない場合は move_mask が全マスなので、この AND 演算は無影響です。

成り生成（add_move_variants）

移動先が確定した後、add_move_variants() が成りと不成の手を適切に生成します。

// position.cpp 1122行目
void Position::add_move_variants(int from,
                                 int to,
                                 PieceType piece,
                                 MoveSelection selection,
                                 bool in_check,
                                 std::vector<Move>& moves) const {
    const int target = board_[to];
    if (!is_empty(target) && piece_type(target) == PieceType::King) {
        return;
    }

    const Color color = side_to_move_;
    const int from_row = square_row(from);
    const int to_row = square_row(to);
    const bool promotion_available =
        can_promote(piece) &&
        (is_in_promotion_zone(color, from_row) || is_in_promotion_zone(color, to_row));
    const bool promotion_required = must_promote(piece, color, to_row);

    if (!promotion_required) {
        const Move move{from, to, piece, false, false};
        if (should_keep_generated_move(move, selection, in_check)) {
            moves.push_back(move);
        }
    }
    if (promotion_available) {
        const Move move{from, to, piece, true, false};
        if (should_keep_generated_move(move, selection, in_check)) {
            moves.push_back(move);
        }
    }
}

promotion_available は成り可能な駒種で移動元か移動先が敵陣にある場合、 promotion_required は歩・香が最奥段、桂馬が最奥2段に到達した場合に true になります。成り必須でなければ不成の手を、成れるなら成りの手も生成します。敵玉を取る手は生成しません（piece_type(target) == PieceType::King のチェック）。

6.9 add_drop_moves() — 駒打ち生成

持ち駒を盤上に打つ手の生成です。将棋特有の複雑なルールが反映されています。

// position.cpp 1155行目
void Position::add_drop_moves(Color color,
                              const Bitboard& move_mask,
                              bool enforce_pawn_drop_mate,
                              MoveSelection selection,
                              bool in_check,
                              std::vector<Move>& moves) const {
    if (selection == MoveSelection::Tactical && !in_check) {
        return;
    }

    const auto& t = tables();
    Bitboard empty = t.all_squares & ~occupied_;
    empty &= move_mask;

    for (int index = 1; index <= static_cast<int>(PieceType::Rook); ++index) {
        const PieceType piece = static_cast<PieceType>(index);
        if (piece == PieceType::King || hand_count(color, piece) == 0) {
            continue;
        }

        Bitboard targets = empty;
        for (int file = 0; file < kBoardSize; ++file) {
            if (piece == PieceType::Pawn &&
                (piece_bb_[static_cast<int>(color)][static_cast<int>(PieceType::Pawn)] &
                 t.file_bb[file])
                    .any()) {
                targets &= ~t.file_bb[file];
            }
        }

        while (targets.any()) {
            const int to = targets.pop_lsb();
            const int row = square_row(to);
            if ((piece == PieceType::Pawn || piece == PieceType::Lance) &&
                is_last_rank(color, row)) {
                continue;
            }
            if (piece == PieceType::Knight && is_last_two_ranks(color, row)) {
                continue;
            }

            const Move move{-1, to, piece, false, true};
            if (piece == PieceType::Pawn && enforce_pawn_drop_mate &&
                is_pawn_drop_mate(move)) {
                continue;
            }
            if (should_keep_generated_move(move, selection, in_check)) {
                moves.push_back(move);
            }
        }
    }
}

二歩判定

歩を打つ場合、同じ筋（file）に自分の歩が既にあるかをチェックします。 piece_bb_（駒種別ビットボード）と file_bb（筋ビットボード）の AND をとることで、その筋に歩があるかをビットボード演算で高速に判定しています。二歩の筋は targets &= ~t.file_bb[file] で打てるマスから一括除外されます。

行き所のない駒の禁止

移動できなくなるマスへの駒打ちは禁止されています。

歩・香: 最奥段（is_last_rank）への打ちは禁止
桂馬: 最奥2段（is_last_two_ranks）への打ちは禁止

打ち歩詰め判定（is_pawn_drop_mate）

歩を打って相手玉を即座に詰ます手（打ち歩詰め）は将棋のルールで禁止されています。 enforce_pawn_drop_mate フラグが true の場合、この判定が行われます。

// position.cpp 1437行目
bool Position::is_pawn_drop_mate(const Move& move) const {
    Position next = *this;
    next.do_move_unchecked(move);
    const Color attacker = side_to_move_;
    const Color defender = next.side_to_move_;
    const int king_square = next.find_king(defender);
    if (king_square == -1 || !next.is_square_attacked(king_square, attacker)) {
        return false;
    }
    return next.generate_legal_moves(false, false).empty();
}

歩を打った局面を作成し、王手になっていれば相手の合法手が0かどうかを調べます。合法手が0なら打ち歩詰めであり、この手は禁止されます。 generate_legal_moves(false, false) の第1引数は「駒打ちを含めない」、第2引数は「打ち歩詰め判定を行わない」（再帰防止）を意味します。

なお、selection == MoveSelection::Tactical && !in_check の場合は駒打ちが全てスキップされます。静止探索では駒取り・成りのみを探索するため、王手回避中でない限り駒打ちは不要です。

6.10 should_keep_generated_move() — 戦術手/王手手のフィルタ

生成された手を MoveSelection に応じてフィルタリングする関数です。

// position.cpp 1409行目
bool Position::should_keep_generated_move(const Move& move,
                                          MoveSelection selection,
                                          bool in_check) const {
    switch (selection) {
        case MoveSelection::All:
            return true;
        case MoveSelection::Tactical:
            return in_check || board_[move.to] != 0 || move.promote;
        case MoveSelection::Checking:
            return gives_check(move);
        default:
            return true;
    }
}

MoveSelection	保持条件
`All`	常に `true`（全手生成）
`Tactical`	王手中 / 駒取り / 成りのいずれか
`Checking`	`gives_check(move)` が `true` の手のみ

Tactical で in_check が含まれているのは、王手回避時は全手を探索する必要があるためです。

6.11 generate_quiescence_moves() と generate_checking_moves() の違い

この2つの関数は、目的の異なる手の部分集合を生成します。

generate_quiescence_moves()（静止探索用）

std::vector<Move> Position::generate_quiescence_moves() const {
    return generate_legal_moves(true, true, MoveSelection::Tactical);
}

MoveSelection::Tactical を使用し、駒取り・成り・王手回避の手だけを生成します。静止探索（quiescence search）は、評価値が大きく変動する手（captures/promotions）のみを探索して水平線効果を軽減する手法です。駒打ちは王手回避中を除きスキップされます。

generate_checking_moves()（王手生成用）

std::vector<Move> Position::generate_checking_moves() const {
    return generate_legal_moves(true, true, MoveSelection::Checking);
}

MoveSelection::Checking を使用し、相手玉に王手をかける手だけを生成します。 gives_check(move) は移動後の局面で相手玉が攻撃されているかを判定する関数で、コストが高いため、詰み探索など特定の状況でのみ使用されます。

6.12 全体の処理フロー

合法手生成の全体フローを整理すると、以下のようになります。

generate_legal_moves(include_drops, enforce_pawn_drop_mate, selection)
  +-- compute_pins_and_checks()    // ピン・王手の検出
  +-- generate_king_moves()        // 玉の移動生成
  +-- [両王手なら即リターン]
  +-- move_mask の計算              // 単王手なら合駒・取りの制限
  +-- generate_piece_moves() x 13  // 各駒種の移動生成
  +-- add_drop_moves()             // 駒打ち生成

全13種の駒種（歩・香・桂・銀・金・角・飛・と・成香・成桂・成銀・馬・龍）に対して generate_piece_moves() を順に呼び出し、該当する駒種のビットボード piece_bb_[color][type] を渡すことで一括生成します。全ての合法性チェックが事前のビットボード計算に集約され、生成される手はすべて合法であることが保証されます。