df-pnアルゴリズムをRustで実装して公開しました
やねうら王さんの記事が話題になっていたので、便乗して以前 Rust で実装した df-pn アルゴリズムの実装を整理して公開しました。
試しに 15 手詰めを解かせたところ 3 秒程度で解けているのでそこそこ優秀なんじゃないでしょうか。（もちろん問題によるでしょうが）
リポジトリはこちらです。
正直、個人的に C++や Python のコードはとても追いづらくて辛いので Rust で書いた df-pn の実装が誰かの理解に役立てば幸いです。
使い方
READMEにも書いた通りですが、将棋の盤面を AA で書いたファイルを引数に渡すと詰み盤面を探索します。
詰みの全パターンを網羅して出力し、一番最後にお互いに最善手を打ったパターンを出力しています。
cargo run --release -- ./examples/nine.txt
df-pn のシンプルな理解
df-pn アルゴリズムは一見難しそうですが、コアの概念は全然難しくありません。
重要なのは以下の一点のみです。
これを実装に落とし込もうとすると df-pn アルゴリズムになる、というだけの話です。
実装で工夫したところ
dn と pn の計算方法
ありがちな df-pn アルゴリズムの実装として「攻方は pn が小さくなるように、玉方は dn が小さくなるようにする」というのがありますが、これがとても混乱しやすいです。
計算式も逆にせねばならず、実装も複雑になります。
わかりやすい実装としては、お互いに相手方の dn から pn を計算し、pn から dn を計算します。そうすることで、双方ともに pn を小さくすることを目標にすることができるので、実装もシンプルになります。
攻方の pn が 0 になったらその盤面は詰みが証明され、玉方の pn が 0 になったら、その盤面は不詰みが証明されます。
pub(crate) fn update_reversed(&mut self, other: &PnDn) {
if other.dn < self.pn {
self.pn = other.dn;
}
self.dn = self.dn.saturating_add(other.pn);
}
千日手の対処
千日手に特に何も対処をしないと、無限ループが発生して解けなくなります。
これをどうするかは特徴の出るところですが、今回はシンプルに不詰みとして処理してみました。
探索系路上に同じ盤面が発生した時点でその先の探索は詰み探索には不要なわけで、それを不詰みとしてしまうことで実装がシンプルになったと思います。
if history.contains(&next_board) {
self.children
.push_back(Node::ForceNotCheckmate(ForceNotCheckmateNode::new(
next_position,
)));
continue;
}
飛車と角の王手判定
飛車と角が盤面に存在するとき、その駒が王手しているかの判定は、ナイーブな実装ではループでの探索になると思いますが、シンプルな条件分岐で計算量を減らすことができます。
以下の実装の戻り値が None だった場合は王手でないことが証明されます。
ただし、None でないからと言って直ちに王手ではないので注意が必要です。
fn get_hisha_vec(p1: &Piece, p2: &Piece) -> Option<Coord> {
if p1.coord.x == p2.coord.x {
Some(Coord::new(0, if p1.coord.y < p2.coord.y { 1 } else { -1 }))
} else if p1.coord.y == p2.coord.y {
Some(Coord::new(if p1.coord.x < p2.coord.x { 1 } else { -1 }, 0))
} else {
None
}
}
fn get_kaku_vec(p1: &Piece, p2: &Piece) -> Option<Coord> {
if i8::abs(p1.coord.x - p2.coord.x) == i8::abs(p1.coord.y - p2.coord.y) {
Some(Coord::new(
if p1.coord.x < p2.coord.x { 1 } else { -1 },
if p1.coord.y < p2.coord.y { 1 } else { -1 },
))
} else {
None
}
}
実装でやれていないこと
不成
歩・2 行目の香車・飛車・角は強制的に成ります。不成によって詰ませられることがあるようですが、探索効率が下がることの方が圧倒的に多いためやっていません。
合駒の枝刈り
現在の実装では、玉方が合駒できる場合、全種類の合駒を検証します。
これは大変効率が悪いので、本質的に同じ合駒の場合は同一盤面として枝刈りすべきですが、ドメイン知識がなく断念しています。
ヒューリスティックな駒の選定
特に持ち駒による王手が可能な場合、状況に応じてヒューリスティックな駒の選定が可能だと想像できますが、これもドメイン知識がなく断念しました。
最小詰み手順の探索
詰み手順を発見したタイミングで探索を完了し、その一手目に対する最善手を表示する実装になっています。
全ての一手目を探索すれば最小の詰み手順を探すことは可能ですが、面倒なのでやっていません。
n 手以下の手順を探索するオプションは用意しているため、想定詰み手順よりも少ない手順を探すことは簡単にできるようになっています。
将棋エンジンへの対応
クラスタ外の人間であるため将棋エンジンに関する知識が全くなく、対応できていません。
やれることは AA のテキストをパースして AA で出力するだけです。
並列処理
df-pn アルゴリズムはわりかし並列処理がしやすい部類だとは思うんですが、並列処理の実装はあんまり楽しくないのでやってません。
余談
df って何？
df-pn の df ってなにか知ってる人いたら教えてください。
pn-dn アルゴリズムの方がわかりやすくない？
Discussion