GPS将棋のdf-pnを1つのソースファイルに移植したことで、LLMにコード全体をコンテキストとして与え、解説させられるようになった。
GPS将棋のdf-pnは、詰将棋探索アルゴリズムの知見が数多く詰め込まれた非常に価値の高いコードである。しかし、前々回の記事で述べたように、その複雑さゆえに、現在では将棋AI開発者からもあまり読まれなくなっている。
そこで、その価値を少しでも伝えるために、GPT-5.5 Proに移植版のコードを読ませ、詳細な解説を作成してもらった。
解説対象のソース(osl_dfpn.cpp):
github.com
このコードは何をするものか
このコードは、将棋の局面 Position に対して、
攻方が相手玉を詰ませられるか？
を調べるための 詰将棋用 df-pn 探索エンジンである。
中心になるのは osl_dfpn.cpp のこの2つである。
ProofDisproof OslDfPn::Impl::attack(...);
ProofDisproof OslDfPn::Impl::defense(...);
attack() は攻方ノード、defense() は受方ノードである。
低レベルの手生成は generateMoves.cpp が担当する。そこには generateMoves<CheckAllOslmate>、generateMoves<CheckAllOslmateFixedRaw>、generateMoves<Evasion> などがあり、osl_dfpn.cpp から王手生成・逃げ手生成として使われる。
全体を一言でいうと、
df-pn の理論をベースに、
将棋の詰み探索向けに、
手生成・置換表・持ち駒優越・ループ検出・DAG対策・証明流用・PV取得を組み込んだ実装
である。
まず理解すべき理論：AND/OR木
ゲーム木探索では、局面を ORノード と ANDノード に分けて考えることがある。
詰将棋に当てはめると、こうなる。
ORノード
攻方の手番。
どれか1つの王手で詰みに向かえればよい。
ANDノード
受方の手番。
受方のすべての逃げ手を潰さなければならない。
ORノードでは、少なくとも1つの子が真なら親も真である。ANDノードでは、すべての子が真でなければ親は真にならない。ORノードは「少なくとも一つの子ノードが真なら真」、ANDノードは「すべての子ノードが真なら真」と定義できる。
将棋の詰み探索では、これを次のように読むと自然である。
攻方:
王手A、王手B、王手Cのうち、
どれか1つで詰みが続けばよい。
受方:
逃げ手A、逃げ手B、逃げ手Cのすべてに対して、
攻方が詰ませられなければならない。
この対応が、attack() と defense() の根本である。
証明数・反証数とは何か
ノードを証明するために展開する必要がある先端ノード数の最小値を 証明数、反証するために必要な先端ノード数の最小値を 反証数 と呼ぶ。証明数が小さいほど証明しやすく、反証数が小さいほど反証しやすい、という意味である。
このコードでは、その組を ProofDisproof が持つ。
proof
詰みを証明する難しさ。
disproof
不詰を証明する難しさ。
特別な意味はこうである。
proof == 0
詰みが証明された。
disproof == 0
不詰が証明された。
proof > 0 かつ disproof > 0
まだ未解決。
そして、ORノードとANDノードで集約方法が違う。
ORノード:
proof = 子 proof の最小値
disproof = 子 disproof の合計
ANDノード:
proof = 子 proof の合計
disproof = 子 disproof の最小値
この式が、attack() と defense() のコードにそのまま出ている。
attack() と defense() の対応
この表が、ソース全体の地図である。
| 観点 |
attack() |
defense() |
| 理論上のノード |
ORノード |
ANDノード |
| 手番 |
攻方 |
受方 |
| 生成する手 |
王手 |
王手回避 |
| 主な手生成 |
generate_check_moves() |
generate_escape_moves() |
| 子で呼ぶ関数 |
defense() |
attack() |
| 成功条件 |
どれか1つの王手が詰みに進む |
すべての逃げ手を詰ませる |
| 失敗条件 |
すべての王手が失敗 |
どれか1つ逃げられる |
| proof集約 |
最小値 |
合計 |
| disproof集約 |
合計 |
最小値 |
| 次に読む子 |
proof が小さい王手 |
disproof が小さい逃げ手 |
つまり、合言葉はこれである。
attack は OR。
どれか1手でよい。
proof は min、disproof は sum。
defense は AND。
全部潰す必要がある。
proof は sum、disproof は min。
df-pnとは何か
df-pn は、証明数探索を深さ優先探索に変換した手法である。証明数と反証数の両方にしきい値を持ち、そのしきい値を超えるまで深さ優先で最有力ノードを追う。
このコードでは、しきい値は次の構造体で表される。
struct Threshold {
uint32_t proof;
uint32_t disproof;
};
理論上の φ / δ や th_pnum / th_dnum に相当するものである。
attack() と defense() は、子を再帰探索するときに、その子専用のしきい値を作る。
oslmate_attack_child_proof_threshold(...)
oslmate_attack_child_disproof_threshold(...)
oslmate_defense_child_proof_threshold(...)
これらは、
この子をどこまで読めば、親の評価が変わるか？
を計算している。
df-pn の重要な特徴は、
常に最有力ノードへ向かって深く読む
ただし証明数・反証数のしきい値で読みすぎを防ぐ
ことである。
このコードでは、attack() なら proof が最小の子、defense() なら disproof が最小の子を next_index として選ぶ。
公開APIから全体を見る
まず読むべき入口は、ファイル下部にある公開関数である。
bool OslDfPn::dfpn(Position& pos);
bool OslDfPn::dfpn_andnode(Position& pos);
Move OslDfPn::dfpn_move(Position& pos);
ProofDisproof OslDfPn::dfpn_probe(Position& pos, Move* best_move);
void OslDfPn::get_pv(Position& pos, std::vector<u32>& pv);
通常の入口は dfpn() である。
流れはこうである。
OslDfPn::dfpn(pos)
↓
root_attack_color = pos.turn()
↓
探索表をクリア
↓
小さいノード上限から探索開始
↓
Impl::attack(pos, root threshold)
↓
未解決ならノード上限を増やして再探索
↓
詰み成功なら true
dfpn_andnode() は、root を受方ノードとして始めたい場合の入口である。
dfpn()
root は attack()
dfpn_andnode()
root は defense()
この2つの違いを最初に押さえると、下の実装が読みやすくなる。
ProofDisproof の読み方
このコードでは、探索結果は ProofDisproof で表す。
代表的な状態は次のように読むとよい。
Unknown
まだ分からない。
Checkmate
攻方が詰ませられる。
NoCheckmate
攻方が詰ませられない。
NoEscape
受方に逃げ手がない。
攻方から見れば詰み成功。
PawnCheckmate
打ち歩詰め絡みの特殊扱い。
LoopDetection
ループ検出。
注意すべきなのは、NoEscape である。
NoEscape = 受方に逃げがない
= 攻方の詰み成功
名前だけ見ると「逃げなし」だが、詰み探索の結果としては攻方成功側である。
attack() の読み方
attack() は攻方ノードである。
大まかな流れはこうである。
1. 深さ・ノード制限を確認する。
2. 現在局面を経路表に登録する。
3. 置換表から過去の探索結果を読む。
4. すでに詰み・不詰が分かっていれば返す。
5. 浅い詰みショートカットを試す。
6. 王手を生成する。
7. 王手がなければ NoCheckmate。
8. 各王手の子局面を調べる。
9. proof/disproof を集計する。
10. proof が最小の王手を選んで defense() を再帰する。
11. 結果を置換表に保存する。
擬似コードにするとこうである。
ProofDisproof attack(pos, threshold) {
record = table.probe(pos);
if (record is final)
return record;
if (fixed_attack shortcut succeeds)
return Checkmate;
moves = generate_check_moves(pos);
if (moves.empty())
return NoCheckmate;
for move in moves:
child = table.probe(pos after move);
if unknown:
child = estimate_child(...);
while (not solved) {
min_proof = min(child.proof);
sum_disproof = sum(child.disproof);
if threshold reached:
save and return;
next = child with smallest proof;
do move;
defense(child_pos, child_threshold);
undo move;
update child;
}
}
attack() の中で最重要なのは、
min_proof
second_proof
sum_disproof
next_index
である。
この next_index が、次に深く読む王手である。
defense() の読み方
defense() は受方ノードである。
大まかな流れはこうである。
1. 深さ・ノード制限を確認する。
2. 現在局面を経路表に登録する。
3. 王手がかかっていなければ NoCheckmate。
4. 置換表から過去の探索結果を読む。
5. 逃げ手を生成する。
6. 逃げ手がなければ NoEscape。
7. 各逃げ手の子局面を調べる。
8. proof/disproof を集計する。
9. disproof が最小の逃げ手を選んで attack() を再帰する。
10. 結果を置換表に保存する。
擬似コードにするとこうである。
ProofDisproof defense(pos, threshold) {
if (!pos.inCheck())
return NoCheckmate;
record = table.probe(pos);
if (record is final)
return record;
moves = generate_escape_moves(pos);
if (moves.empty())
return NoEscape;
for move in moves:
child = table.probe(pos after move);
if unknown:
child = quick_estimate(...);
while (not solved) {
sum_proof = sum(child.proof);
min_disproof = min(child.disproof);
if threshold reached:
save and return;
next = child with smallest disproof;
do move;
attack(child_pos, child_threshold);
undo move;
update child;
}
}
defense() で重要なのは、
sum_proof
min_disproof
second_disproof
next_index
である。
この next_index が、受方にとって一番逃げやすそうな手である。
先端ノードの初期値と評価
理論上、未展開の先端ノードは普通 (1,1) とする。
proof = 1
disproof = 1
しかし実際のゲームでは局面によって証明しやすさが違うため、ゲーム固有の評価関数で初期 proof/disproof を変える改良がある。
このコードでそれに対応するのが、次の関数群である。
attack_estimation_zero(...)
fixed_attack_estimation_zero(...)
estimate_attack_pdp(...)
estimate_attack_pdp_with_support(...)
attack_proof_cost(...)
これらは、未探索の子を単純な (1,1) とせず、
相手玉の逃げ道はいくつあるか
王手した駒が取られやすいか
攻方の利きが多いか
受方の利きが多いか
駒打ちで逃げ道を塞げそうか
を見て、初期値を調整する。
King8RuntimeInfo は相手玉8近傍の評価器
詰将棋では、相手玉の周囲8マスが非常に重要である。
このコードでは、
struct King8RuntimeInfo {
uint8_t drop_candidate;
uint8_t liberty;
uint8_t liberty_candidate;
uint8_t move_candidate2;
uint8_t spaces;
uint8_t moves;
uint8_t liberty_count;
};
が使われる。
意味はこうである。
liberty
本当の逃げ道になりそうなマス。
drop_candidate
駒を打つと詰みに絡みそうなマス。
move_candidate2
駒移動で詰みに絡みそうなマス。
spaces
空きマス。
moves
玉移動や応手に関係するマス。
liberty_count
逃げ道の数。
make_king8_runtime_info() は、相手玉の周囲8マスについて、空きマスか、自駒か、相手駒か、攻方の利きがあるか、受方の十分な利きがあるかを見て、この情報を作る。
これが、1手詰め検出や proof/disproof の見積もりに使われる。
1手詰め検出
本格的な df-pn に入る前に、簡単な詰みは先に見つける。
中心はこれである。
Move immediate_mate_move_in_1_osl(Position& pos, ...);
流れはこうである。
1. 自玉が王手中なら試さない。
2. 攻方色と相手玉を取得する。
3. King8RuntimeInfo で相手玉周辺を評価する。
4. 駒移動候補を見る。
5. 桂候補を見る。
6. 駒打ち候補を見る。
immediate_mate_move_in_1_osl() は、まず移動による詰み候補を探し、次に桂、最後に駒打ち候補を探す。fixed_attack_depth2_osl() などの浅い探索でも、最初にこの1手詰め検出を試す。
固定深さショートカット
本格探索の前に浅い探索を行う仕組みもある。
代表的なのは、
fixed_attack_osl_shortcut(...)
fixed_attack_depth2_osl(...)
fixed_escape_by_move_zero(...)
fixed_has_escape_by_move_zero(...)
fixed_attack_may_unsafe_depth1(...)
である。
役割は、
1手詰め
3手詰めに近い浅い詰み
逃げ手が明らかにない局面
玉周りから見た簡易評価
を本格 df-pn より先に処理することである。
fixed_attack_osl_shortcut() は fixed_attack_depth2_osl() を呼ぶ形になっており、固定深さ用の王手生成では generate_fixed_depth_check_moves_into() が使われる。ここでは通常の generate_check_moves() とは違い、OSL の raw な生成順を保つようになっている。
generateMoves.cpp は手生成工場
osl_dfpn.cpp は探索本体であるが、低レベルな手生成は generateMoves.cpp にある。
中心はこのテンプレートである。
template <MoveType MT, Color US, bool ALL = false>
struct GenerateMoves;
MoveType によって生成する手が変わる。
Check
王手を生成する。
CheckAll
通常省略される不成も含めた王手を生成する。
CheckAllOslmate
詰み探索用の王手生成。
CheckAllOslmateFixedRaw
固定深さ探索用の raw 王手生成。
Evasion
王手回避手を生成する。
Legal
合法手を生成する。
PseudoLegal
疑似合法手を生成する。
generateMoves<MT>(moveList, pos) は、手番が先手なら GenerateMoves<MT, Black>、後手なら GenerateMoves<MT, White> を呼ぶ。
王手生成の中身
王手生成では、大きく次の2種類を考える。
直接王手
動いた駒そのものが相手玉に利く。
開き王手
pin されている駒が動き、後ろの飛車・角・香などの利きが通る。
generateMoves.cpp の GenerateMoves<Check, US, ALL> では、王手を次のように整理している。
1. 成らない移動による直接王手
2. 成る移動による直接王手
3. pinされている駒の移動による間接王手
コード中では、直接王手候補を x、開き王手候補を y として分けて扱っている。ほとんどの局面では開き王手候補が空なので、その前提で最適化されている。
また、歩打ちでは二歩と打ち歩詰めを避ける処理がある。
王手回避生成の中身
GenerateMoves<Evasion, US, ALL> は、王手回避手を生成する。
流れはこうである。
1. 王手している駒を列挙する。
2. その駒の利きで玉が逃げられないマスを bannedKingToBB に入れる。
3. 玉の逃げ手を生成する。
4. 両王手なら玉移動しかないので終了する。
5. 単王手なら、王手駒を取る手や合駒を生成する。
makeBannedKingTo() は、王手している駒の種類に応じて、玉が移動できないマスを作る。GenerateMoves<Evasion> は、玉の移動先に敵の利きがある場合や pin された駒を動かす場合など、非合法手を含む疑似合法手を生成し、あとで合法性を確認する設計である。
generate_check_moves() の役割
osl_dfpn.cpp の generate_check_moves() は、攻方ノード用の王手生成である。
分岐はこうである。
pos.inCheck() == true
王手を受けながら、さらに王手になる手だけを拾う。
pos.inCheck() == false
generateMoves<CheckAllOslmate> で王手を生成する。
その後、
append_ignored_unpromote_checks
reorder_osl_numbered_check_moves
sort_moves
を行う。
つまり、
王手を作る
↓
必要な不成手を追加する
↓
OSL風の順序に整える
↓
探索用にソートする
という流れである。generate_check_moves() は generateMoves<CheckAllOslmate> を使ったあと、OSL の phase / target / piece-number order に寄せてから sort_moves() をかけている。
generate_escape_moves() の役割
generate_escape_moves() は、受方ノード用の逃げ手生成である。
流れはこうである。
1. delay_node かどうかを見る。
2. delay_node なら特定マスへの cheap king escape を生成する。
3. 通常は cheap escape を生成する。
4. OSL駒番号順に補正する。
5. sort_moves する。
6. need_full_width なら全逃げ手を追加する。
7. 必要な不成逃げ手を追加する。
need_full_width が false のときは、まず軽い逃げ手だけを見る。危険な場合や詰み確認が必要な場合に need_full_width を立て、全幅の逃げ手を追加する。
need_full_width の意味
need_full_width は、受方の逃げ手生成をどこまで広げるかを表す。
need_full_width == 0
cheap escape だけで探索する。
need_full_width != 0
全幅の逃げ手を生成する。
詰み探索では、毎回すべての逃げ手を生成すると重い。
そこで最初は、
重要そうな逃げ手だけ見る
という軽量探索をする。
ただし、それだけで詰みと断定すると危険である。そこで必要になったら全逃げ手を追加する。defense() では、詰み成功に見えても need_full_width == 0 の場合、全幅確認へ戻す処理がある。
OSL互換の手順序
このコードには、手順序を整える関数が多くある。
reorder_osl_numbered_check_moves(...)
reorder_osl_numbered_escape_target_moves(...)
reorder_osl_numbered_long_moves_impl(...)
sort_moves(...)
dfpn_check_move_phase(...)
dfpn_check_move_subphase(...)
これは単なるソートではない。
cshogi の汎用王手生成順は OSL の raw order と違うため、OSL の phase / target / piece-number order に近づけてから sort_moves() を行う。
つまり、このコードは、
普通の df-pn 実装
ではなく、
OSL の探索順序に近づけた df-pn 実装
として読む必要がある。
探索アルゴリズムでは、同じ手を最終的に読むとしても、読む順番が速度や保存結果に大きく影響する。詰将棋探索では特に重要である。
OslPieceNumberState は駒番号の再現装置
OSL では、駒に番号があり、その番号順に手を生成する場面がある。
このコードでは、
class OslPieceNumberState
がそれを再現する。
主な中身は、
std::array<PieceInfo, 40> pieces_;
std::array<int, SquareNum> board_number_;
である。
将棋の駒は全部で40枚なので、40個の PieceInfo を持つ。
このクラスは、
この駒は何番か
今どこにあるか
持ち駒か
手を指したらどう更新するか
undo でどう戻すか
を管理する。
OslPieceNumberState には from_position()、from_history()、apply_move()、undo_move()、number_of_move_piece()、number_of_square() がある。探索中に手順履歴へ追従し、OSL風の駒番号順ソートに使われる。
不成手の扱い
将棋では、成れる駒を成らずに指す手がある。
普通は成った方が強いので省略したくなるが、詰将棋では不成が意味を持つ場合がある。
このコードでは、
has_ignored_unpromote_check(...)
has_ignored_unpromote_escape(...)
is_ignored_unpromote_check_variant(...)
append_ignored_unpromote_checks(...)
unpromote_counterpart(...)
がそのためにある。
generate_check_moves() では、生成後に append_ignored_unpromote_checks() を呼ぶ。generate_escape_moves() でも、full-width 時に必要な不成逃げ手を追加する。
打ち歩詰めと PawnCheckmate
将棋固有のルールとして、打ち歩詰めがある。
generateMoves.cpp の歩打ち生成では、
一段目には打てない
二歩を避ける
打ち歩詰めを避ける
という処理がある。
osl_dfpn.cpp 側にも、
has_pawn_drop_checkmate(...)
ProofDisproof::PawnCheckmate()
normalize_pawn_drop_no_escape(...)
is_pawn_drop_no_escape(...)
がある。
読み方としては、
歩打ちで詰んでいるように見える
↓
しかし打ち歩詰めなら通常の詰みとは違う
↓
PawnCheckmate として特別扱いする
である。
局面キーとハッシュ
置換表に保存するため、局面にはキーが必要である。
主な関数はこれである。
osl_board64_key(pos)
osl_board32_key(pos)
board_index_key(pos)
secondary_board_key(pos)
board_index_key_after_move(...)
secondary_board_key_after_move(...)
board_keys_after_move(...)
このコードでは、盤面キーを2つに分けている。
board_index
主キー。手番情報も含む。
board_secondary
補助キー。
そして、
struct OslmateBoardKey {
Key board_key;
uint64_t board_secondary;
};
として扱う。
ただし将棋では、盤面が同じでも持ち駒が違えば別局面である。そのため、DfpnRecord は stands[Black] と stands[White] を持ち、同じ盤面キーの bucket に持ち駒違いのレコードを複数保存する。
DfpnRecord は局面のカルテ
DfpnRecord は、1局面分の探索結果を保存する構造体である。
主なフィールドは次の通りである。
ProofDisproof proof_disproof;
Move best_move;
Hand stands[ColorNum];
uint64_t board_secondary;
Hand proof_pieces;
Hand proof_pieces_candidate;
uint64_t solved;
uint64_t dag_moves;
uint32_t node_count;
uint32_t tried_oracle;
uint32_t min_pdp;
uint16_t remaining_depth;
Move last_move;
Square last_to;
ProofPiecesType proof_pieces_set;
uint8_t need_full_width;
bool false_branch;
bool dag_terminal;
bool exact;
意味はこうである。
proof_disproof
この局面の現在の評価。
best_move
有力手、または証明に使った手。
stands
この記録が前提にしている持ち駒。
proof_pieces
詰み証明または不詰証明に必要な持ち駒情報。
solved
解決済みの子を bit で保持。
dag_moves
DAG的にまとめられる子を bit で保持。
node_count
この局面以下の探索量。
tried_oracle
証明流用をどこまで試したか。
last_move
DAG探索や証明流用で手順をたどるための手。
last_to
逃げ手生成の限定に使うマス。
need_full_width
全幅逃げ手生成が必要か。
exact
厳密な探索結果かどうか。
つまり、
DfpnRecord = 局面の探索結果・再利用情報・証明情報のカルテ
である。
DfpnTable は置換表
df-pn では、探索済みノードの証明数・反証数を保存する置換表が不可欠である。置換表を使うことで、同じ局面を何度も探索する手間を減らせる。
このコードでは、それが DfpnTable である。
std::unordered_map<
OslmateBoardKey,
std::forward_list<DfpnRecord>,
OslmateBoardKeyHash
> table_;
普通の置換表なら、
局面キー → レコード
しかし、このコードでは、
盤面キー → 複数の DfpnRecord
である。
持ち駒違いの局面を同じ bucket に入れるためである。
DfpnTable::probe() の読み方
DfpnTable::probe() は非常に重要である。
流れはこうである。
1. board key で bucket を探す。
2. bucket がなければ Unknown 相当の DfpnRecord を返す。
3. 同じ持ち駒の record があればそれを使う。
4. 詰み成功 record なら、攻方持ち駒が proofPieces を満たすか見る。
5. 不詰 record なら、受方持ち駒が disproofPieces を満たすか見る。
6. final でない record から proof_hint / disproof_hint を作る。
7. 未知なら初期 proof/disproof を hint で調整する。
この「持ち駒優越」を使うところが、普通の置換表より強力である。probe() は完全一致だけでなく、詰み成功なら攻方持ち駒が証明に必要な駒を満たすか、不詰なら受方持ち駒が反証に必要な駒を満たすかを確認する。
持ち駒優越とは何か
たとえば、
攻方が金1枚を持っていれば詰む
と証明できたとする。
その場合、
攻方が金1枚と銀1枚を持っている
局面でも、その詰み証明を再利用できる可能性が高い。
これが 持ち駒優越である。
コードでは、
osl_stand_is_superior_or_equal(...)
setProofPieces(...)
setDisproofPieces(...)
proofPieces()
disproofPieces()
が関係する。
詰み成功の証明では攻方の持ち駒、詰み失敗の証明では受方の持ち駒を見て、過去の探索結果を再利用する。
SearchContext は探索中の作業机
SearchContext は、探索中に必要な状態をまとめた構造体である。
主なフィールドはこうである。
std::vector<PathEncoding> path_encodings;
std::vector<Move> move_history;
std::vector<Threshold> threshold_history;
std::vector<PathRecord*> path_records;
std::unique_ptr<Position> root_position;
Optional<OslPieceNumberState> piece_numbers;
std::vector<Key> board_index_history;
std::vector<uint64_t> board_secondary_history;
std::vector<std::array<Hand, ColorNum>> stand_history;
std::vector<ActiveNode> active_nodes;
std::vector<std::vector<Move>> move_scratch;
std::vector<std::vector<ChildState>> child_scratch;
役割はこうである。
move_history
ここまでの手順。
threshold_history
各深さの proof/disproof しきい値。
path_encodings
経路ハッシュ。
path_records
ループ検出用の現在経路。
piece_numbers
OSL駒番号順を再現する状態。
board_index_history / board_secondary_history
局面キー履歴。
stand_history
持ち駒履歴。
active_nodes
現在展開中の祖先ノード群。
move_scratch / child_scratch
深さごとの手・子状態の作業領域。
Position::doMove() だけでは、探索履歴や駒番号状態は更新されない。そのため探索中は、pos.doMove() とあわせて ctx.push_move()、戻すときに ctx.pop_move() を使う。
ループ検出と経路情報
サイクルを含むゲームでは、同じ局面に戻ることがある。
サイクルを含む探索空間では局面の真偽が経路に依存することがあり、単純な置換表利用で誤る可能性がある。
このコードでは、
PathEncoding
PathRecord
DfpnPathTable
VisitLock
child_loop_reason(...)
child_is_loop(...)
がそれに対応する。
PathRecord は、
int distance;
bool visiting;
uint32_t node_count;
std::forward_list<PathEncoding> twin_paths;
を持つ。
意味はこうである。
visiting
現在の探索経路上にいるか。
twin_paths
経路依存として記録された path。
distance
探索経路上での距離情報。
node_count
その path record の探索量。
VisitLock は RAII で、関数に入ったら visiting = true、出るときに false に戻す。
初心者向けにはこうである。
DfpnTable
過去に調べた局面の表。
DfpnPathTable
今たどっている道の表。
PathEncoding
道筋を小さな値にしたもの。
DAG二重カウント対策
探索空間が木ではなくDAGの場合、別手順で同じ局面に到達することがある。
このとき、証明数・反証数を二重に数えてしまう問題が起こる。
このコードで対応するのが、
dag_moves
dag_terminal
find_dag_source(...)
add_dag(...)
である。
find_dag_source() は、終端レコードの last_move を使って親方向へたどり、現在の active_nodes の祖先と照合する。該当する祖先が見つかると、祖先レコードの dag_moves に bit を立てる。
意味はこうである。
同じ局面に合流する枝を見つける
↓
同じ proof/disproof を何度も数えないようにする
attack() と defense() の中でも、proof/disproof が一定以上大きい未解決子に対して find_dag_source() を試す。
証明流用とシミュレーション
すでに証明されたノードの証明木を使って、似た別ノードも証明できるかを高速に調べる手法がある。ORノードでは証明木から取り出した指し手だけを使い、ANDノードではすべての応手を確認する。
このコードでは、対応するのが次の関数群である。
try_proof(...)
proof_oracle_attack(...)
proof_oracle_defense(...)
blocking_simulation(...)
grand_parent_simulation(...)
proof_oracle_attack() は、
既存の詰み証明レコードを探す
↓
best_move を取り出す
↓
現在局面でも使えるように補正する
↓
その1手だけを試す
↓
proof_oracle_defense() で受方応手を確認する
という流れである。
proof_oracle_attack() では、find_proof_oracle() で証明済みレコードを探し、adjust_oracle_attack_move() で現在局面でも使える手に補正する。
blocking_simulation
blocking_simulation() は、受方の合駒・遮断手のような「似た応手」に証明を流用できるか試す。
流れはこうである。
1. ある子が既に詰み成功している。
2. 同じ target に向かう別の未解決手を探す。
3. その手に対して proof_oracle_attack() を試す。
4. 成功すれば、その子の結果を更新する。
同じマスに合駒する手などは、証明構造が似ている可能性がある。そこで、すでに証明済みの子を利用して別の子も確認する。
grand_parent_simulation
grand_parent_simulation() は、祖父ノードの証明情報を使って現在の子にも証明を流用できるか試す処理である。
条件を満たすと、
祖父ノードの証明済み情報を oracle とする
↓
現在の子局面で proof_oracle_attack() を試す
↓
結果を child にコピーする
という流れになる。
grand_parent_simulation_suitable() は、直近3手の形を見て、証明流用に向いた形かを判定する。
メモリ管理とGC
df-pn は置換表を大量に使う。
ハッシュ表のメモリが限られるため、小さい部分木の情報を優先的に消す考え方がある。
このコードでは、
DfpnTable::run_gc()
DfpnPathTable::run_gc()
Impl::run_gc_if_needed(...)
が対応する。
DfpnTable::run_gc() は、
final でない
node_count が小さい
レコードを削除対象にする。
つまり、
探索量が小さく、再構築しやすそうな記録を消す
という考え方である。DfpnPathTable::run_gc() も、visiting 中のものや node_count が大きいもの、twin_paths を持つ重要そうなものを残す。
EffectSetCache は利き計算のキャッシュ
詰み探索では、
このマスに攻方の利きがあるか
受方の利きが何枚あるか
複数利きか
を大量に調べる。
このコードでは、
effect_set_at(...)
effect_has_at(...)
effect_count(...)
has_multiple_effect_at(...)
がよく出る。
内部では EffectSetCache が pos.attackersTo(...) の結果をキャッシュする。
これにより、
王手候補の評価
玉の逃げ道評価
攻方・受方の利き比較
手のソート
1手詰め判定
固定深さショートカット
が速くなる。
oslmate との速度差の主因
osl_dfpn.cpp は、探索結果の PV や nodes が oslmate と一致するように、探索順序や置換表の扱いを OSL に寄せている。
ただし、速度まで完全に同じにはならない。主因は、
同じ node を読むときの、1 node あたりの局面評価コスト
の違いである。
oslmate は NumEffectState という局面表現を使う。これは、局面を進めたり戻したりするときに、利き情報も一緒に増分更新する仕組みである。
そのため oslmate では、次のような情報を比較的安く取り出せる。
このマスに利きがあるか
利きが何枚あるか
玉が王手されているか
pin / open 情報
玉周辺の利き情報
一方、この移植版は cshogi/Apery 系の Position と Bitboard を使っている。EffectSetCache は利き計算をキャッシュするが、OSL の NumEffectState のように、局面の進行に合わせて全体の利き状態を常に増分更新しているわけではない。
そのため、探索中に次のような処理が多く発生する。
pos.attackersTo(...) を使った利きの再計算
effect_has_at(...) や effect_count(...) の問い合わせ
pin / open 判定の再構築
王手生成・王手回避生成の補助判定
玉周辺8マスの安全性評価
nodes が oslmate と一致している場合、探索木の形はおおむね一致している。それでも実行時間に差が出るなら、原因は「余分な node を読んでいること」ではなく、
同じ node を処理するために必要な利き計算や補助判定が重いこと
と考えるのが自然である。
つまり、EffectSetCache はこの実装における速度差を縮めるための重要な部品であるが、NumEffectState そのものの代替ではない。oslmate との残る速度差は、この局面表現の違いに由来する部分が大きい。
sort_moves() の意味
sort_moves() は、生成した王手や逃げ手を探索しやすい順に並べる。
主に見ているのは、
攻方の利きが受方の利きより多いか
移動先の位置
駒種
成りかどうか
である。
ただし、このソートは単なる良さそうな手順序ではない。OSL の生成順序に近づけた上で、その segment 内を並べ替える、という設計である。
generate_check_moves() と generate_escape_moves() のコメントにも、OSL の raw order や piece-number order を再現する意図が書かれている。
PV取得：詰み手順を取り出す
探索で詰みが分かったあと、実際の手順を取り出す必要がある。
そのための関数が、
get_pv(...)
retrieve_pv(...)
pv_attack(...)
pv_defense(...)
linked_pv_attack_move(...)
linked_pv_defense_move(...)
である。
流れはこうである。
retrieve_pv()
↓
攻方番なら pv_attack()
受方番なら pv_defense()
↓
best_move を探す
↓
局面を進める
↓
次のノードへ
pv_attack() は、1手詰め、固定深さショートカット、置換表の best_move、証明流用などを順に見て、詰み手順を構成する。
理論と実装の対応表
| 理論上の概念 |
このコードの対応 |
| ORノード |
attack() |
| ANDノード |
defense() |
| 真 |
攻方の詰み成功 |
| 偽 |
攻方の詰み失敗 |
| 証明数 |
ProofDisproof::proof |
| 反証数 |
ProofDisproof::disproof |
| 先端ノード初期値 |
ProofDisproof(1, 1)、Unknown |
| 先端ノード評価 |
attack_estimation_zero()、estimate_attack_pdp() |
| df-pn のしきい値 |
Threshold{proof, disproof} |
| SelectChild |
next_index 選択 |
| トランスポジションテーブル |
DfpnTable |
| TTLookup |
DfpnTable::probe() |
| TTSave |
store_exact_oslmate() / store_nonexact_oslmate() |
| 経路情報 |
PathEncoding |
| 経路依存記録 |
PathRecord::twin_paths |
| ループ検出 |
DfpnPathTable、child_loop_reason() |
| DAG二重カウント対策 |
find_dag_source()、dag_moves |
| シミュレーション |
proof_oracle_*、blocking_simulation()、grand_parent_simulation() |
| GC |
DfpnTable::run_gc()、DfpnPathTable::run_gc() |
| 証明木の指し手 |
best_move、last_move |
| PV取得 |
get_pv()、retrieve_pv()、pv_attack()、pv_defense() |
主要関数の一言辞書
公開API
OslDfPn::dfpn
現在手番を攻方として詰みを探索する。
OslDfPn::dfpn_andnode
現在局面を受方ノードとして探索する。
OslDfPn::dfpn_move
探索結果の best_move を返す。
OslDfPn::dfpn_probe
現在局面の ProofDisproof を置換表から読む。
OslDfPn::get_pv
詰み手順を取り出す。
探索本体
Impl::attack
攻方ノード。王手を選ぶ。
Impl::defense
受方ノード。逃げ手を選ぶ。
try_proof
証明流用を試す入口。
proof_oracle_attack
過去の詰み証明を攻方側から流用する。
proof_oracle_defense
流用した証明が受方応手すべてに耐えるか確認する。
手生成
generate_check_moves
df-pn 用の王手生成。
generate_escape_moves
df-pn 用の逃げ手生成。
generate_fixed_depth_check_moves
固定深さショートカット用の王手生成。
generateMoves<CheckAllOslmate>
詰み探索用の王手生成。
generateMoves<Evasion>
王手回避生成。
保存・再利用
DfpnRecord
1局面分の探索結果。
DfpnTable
探索結果の置換表。
DfpnPathTable
探索経路上の局面表。ループ検出用。
PathEncoding
手順を hash 的に表す。
OslPieceNumberState
OSL と同じ駒番号順を再現するための状態。
高速化
immediate_mate_move_in_1_osl
1手詰め候補の高速判定。
fixed_attack_osl_shortcut
浅い固定深さ探索。
King8RuntimeInfo
相手玉の8近傍評価。
EffectSetCache
利き情報のキャッシュ。
sort_moves
OSL互換と探索効率のための手順序付け。
読む順番のおすすめ
1周目：入口と主再帰だけ読む
OslDfPn::dfpn()
↓
Impl::attack()
↓
Impl::defense()
ここでは、細かい補正・証明流用・DAG対策は読まなくて大丈夫である。
見るべきことは、
attack は王手を生成して defense を呼ぶ。
defense は逃げ手を生成して attack を呼ぶ。
だけである。
2周目：proof/disproof の集約を見る
attack() では、
min_proof
second_proof
sum_disproof
next_index
を探す。
defense() では、
sum_proof
min_disproof
second_disproof
next_index
を探す。
ここが理論と実装の一致点である。
3周目：置換表を見る
DfpnRecord
DfpnTable::probe()
DfpnTable::store_exact_oslmate()
DfpnTable::run_gc()
ここで、
探索結果をどう保存するか
同じ局面をどう再利用するか
持ち駒優越をどう使うか
を理解する。
4周目：手生成を見る
generate_check_moves()
generate_escape_moves()
generateMoves<CheckAllOslmate>
GenerateMoves<Check>
GenerateMoves<Evasion>
ここで、探索本体と手生成がつながる。
5周目：高度な再利用を見る
PathEncoding
DfpnPathTable
find_dag_source
proof_oracle_attack
proof_oracle_defense
blocking_simulation
grand_parent_simulation
ここは最後でよい。
全体を4層に分ける
このソースは大きいが、4層に分けると見通しがよくなる。
第1層: 公開API
OslDfPn::dfpn
OslDfPn::dfpn_andnode
OslDfPn::dfpn_probe
OslDfPn::get_pv
第2層: df-pn探索本体
Impl::attack
Impl::defense
Threshold
ProofDisproof
ChildState
SearchContext
第3層: 保存・再利用・ループ対策
DfpnRecord
DfpnTable
DfpnPathTable
PathEncoding
find_dag_source
proof_oracle_attack
proof_oracle_defense
blocking_simulation
grand_parent_simulation
第4層: 将棋固有の手生成・評価
generate_check_moves
generate_escape_moves
generateMoves<CheckAllOslmate>
generateMoves<Evasion>
King8RuntimeInfo
EffectSetCache
OslPieceNumberState
fixed_attack_osl_shortcut
最初から第4層を全部読もうとすると、かなり大変である。
まず第1層と第2層で、
attack / defense の相互再帰
proof/disproof の min/sum
を押さえるのが安全である。
このコードの設計思想
このコードは、単純な df-pn ではない。
設計思想は、おそらく次のようなものである。
1. df-pn の攻方/受方ノード構造を使う。
2. OSL の詰将棋探索に近い手順序を再現する。
3. cshogi/Apery系の Position / Move / Bitboard を使う。
4. 置換表で proof/disproof と best_move を保存する。
5. 将棋の持ち駒優越を使って、完全一致でない局面も再利用する。
6. 経路情報を使ってループや経路依存問題を抑える。
7. DAG合流を検出して二重カウントを減らす。
8. 証明流用で似た局面の探索を省く。
9. 1手詰め・浅い詰みは本格探索前に拾う。
10. メモリが増えすぎたらGCする。
11. 探索後にPVとして詰み手順を取り出す。
このため、attack() と defense() だけならもっと短く書けるはずであるが、実戦的な詰将棋探索として多くの補助機構が追加されている。
混乱しやすいポイント
attack_color と pos.turn()
attack_color は、この探索全体で詰ませたい側である。
pos.turn() は現在手番である。
多くの場合、
attack() 中:
pos.turn() == attack_color
defense() 中:
pos.turn() == oppositeColor(attack_color)
である。
ただし、証明流用や履歴処理では混乱しやすいので注意である。
NoEscape は詰み成功
NoEscape は受方に逃げがない状態である。
攻方から見ると詰み成功である。
same_stands() が Black の持ち駒だけを見る
DfpnTable::same_stands() は、record.stands[Black] == pos.hand(Black) を見る。
これは OSL 互換の HashKey 的な扱いに由来する。普通の「両者の持ち駒を全部比較するはず」という感覚で読むと戸惑う。
証明流用は通常探索ではない
proof_oracle_* は通常の attack() / defense() とは違い、既存の証明手を利用して似た局面を高速確認する。
失敗しても「不詰」ではない。
証明流用に失敗した
↓
まだ分からない
↓
通常の df-pn 探索が必要
である。
最短理解用のミニ課題
課題1: dfpn() から attack() へ線を引く
見る場所は、
OslDfPn::dfpn
Impl::SearchContext ctx
ctx.set_root(pos)
impl_->attack(...)
確認することは、
root_attack_color が pos.turn() になる
node_limit を段階的に増やす
探索状態を最初にクリアする
である。
課題2: attack() の王手生成を見る
探す行は、
generate_check_moves(pos, moves, ...)
その前後に、
置換表 probe
固定深さショートカット
GC
王手がなければ NoCheckmate
がある。
課題3: defense() の逃げ手生成を見る
探す行は、
generate_escape_moves(pos, moves, ...)
その後に、
moves.empty() なら NoEscape
になることを確認する。
課題4: 手生成側へ飛ぶ
generate_check_moves() から、
generateMoves<CheckAllOslmate>
へ飛ぶ。
そこで、
GenerateMoves<Check>
直接王手
開き王手
駒打ち王手
の生成を見ると、探索本体と手生成の接続が分かる。
課題5: DfpnTable::probe() を読む
見るポイントは、
同じ持ち駒なら record を返す
詰み成功 record は proofPieces で再利用する
不詰 record は disproofPieces で再利用する
未知なら proof_hint / disproof_hint を使う
である。
最後のまとめ
このコードは、理論的には、
AND/OR木
↓
証明数・反証数
↓
df-pn
↓
置換表
↓
経路情報・DAG対策・証明流用
という流れの上にある。
実装としては、
attack()
攻方ノード。
王手を生成し、proof 最小の子を defense() で読む。
defense()
受方ノード。
逃げ手を生成し、disproof 最小の子を attack() で読む。
DfpnTable
探索結果を保存・再利用する。
DfpnPathTable
現在経路を管理してループを検出する。
generateMoves.cpp
王手・逃げ手・駒打ち・合法手生成の工場。
King8RuntimeInfo
相手玉の8近傍から詰みやすさを見積もる。
proof_oracle_* / simulation
過去の証明を似た局面へ流用する。
である。
いちばん大切なのは、やはりこれである。
attack は OR。
どれか1つ詰めばよい。
proof = min、disproof = sum。
defense は AND。
全部の逃げを潰す必要がある。
proof = sum、disproof = min。
この対応を見失わなければ、置換表、持ち駒優越、経路情報、DAG、証明流用、手生成順序などの複雑な仕組みも、すべて「df-pn を将棋の詰み探索として実用化するための部品」として整理して読める。
