高速な詰め将棋アルゴリズム完全に理解したい（その１）
Qhapaq アドベント将棋記事６日目
※：執筆時間不足の関係で複数回続きます。申し訳ないです ※：現在の記事の最新版はこちらです（連作ではなく、全ての解説を最新版に記載しています）
昨今のコンピュータ将棋は超高速で詰め将棋を解くことが出来る。という文言は多くの将棋プレイヤーが聞いたことがあるとは思います。
今の詰将棋のルーチンの屋台骨となっているのはdf-pnアルゴリズムです。df-pnアルゴリズムは凄く雑に言えば「攻める時は逃げる側の逃げる手が少なそうな手を、逃げる時は攻める側の次の手が少なそうな手を優先して選ぶ」というものです。例えば以下の記事などに詳細が記されています。
さてしかし、実際の将棋ソフトでは本当に深さ優先探索をしているわけではありません。というのも、純粋なdf-pnアルゴリズムには並列処理がしにくい、局面の無限ループを回避し難いという問題があるからです。
そこで本稿からしばらくの間、今のtanuki-詰め将棋エンジンに実装されているdf-pnアルゴリズムの概要を説明していきたいと思います。今回はアルゴリズムの原著論文（英語）の疑似コードに逐一日本語の解説を付けていきます。
func DFPNwithTCA(n, thpn, thdn, inc_flag) {
// この関数が再帰的に呼ばれる。n=局面
// thpn = n のproof number(pn)がこれ以上なら探索を打ち切る
// thdn = nのdisproof number(dn)がこれ以上なら探索を打ち切る
// inc_flag thpn, thdnを増やすことで探索を強制的に打ち切らないようにする
// nが詰み、または、王手をかける手がない（不詰確定）の場合、探索を打ち切る
if (n is a terminal node) {
handle n
return;
}
first time = true; // ループに入って最初の処理かを判別
// 以下無限ループ
while (1) {
// n が探索されるのはこれが初めてならthpn, thdnの拡張は不要
if (n is a leaf) {
inc flag = false;
}
// nの子局面の中にnよりも元局面からの深さが浅い局面がある = ループしている、かつ、子局面の詰み、不詰みが確定していない
if (n has an unproven old child) {
inc flag = true; // inc_flagをon
}
// 局面nから合法手を生成、子局面のpn, dnからnのpn,dnを計算する
expand_and_compute_pn_dn(n);
if (first time && inc flag) {
thpn = max(thpn, pn(n) + 1);
thdn = max(thdn, dn(n) + 1);
}
// 局面nのpn, dnが thpn, thdnより多い
// ≒局面nの兄弟局面の中にnよりpn, dnが小さい局面がある可能性がある
if (pn(n) ≥ thpn || dn(n) ≥ thdn) break;
first time= false;
// 局面nの子局面のなかでpn, dnが最も小さいもの、２番めに小さいものを探す
n1, n2 = find_best_and_second_best_child(n);
if (n is an OR node) {
// 攻め側の場合のpn, dnの更新
thpn child = min(thpn, pn(n2) + 1);
thdn child = thdn - dn(n) + dn(n1);
else {
// 受け側の場合の更新
thpn child = thpn - pn(n) + pn(n1);
thdn child = min(thdn, dn(n2) + 1);
}
// 一番いい子ノードに対して再帰的に探索
DFPNwithTCA(n1, thpn child, thdn child, inc flag);
}
