df-pnアルゴリズム学習記(1)
詰め将棋ならdf-pnアルゴリズムとどこかで聞いた。
今日から３日かけてこのアルゴリズムを理解して実装してみる。
理解するために飛び回るのは
CiNii 論文 - df-pnアルゴリズムの詰将棋を解くプログラムへの応用
CiNii 論文 - 詰将棋を解くための探索技術について(<レクチャーシリーズ>コンピュータ将棋の技術〔第2回〕)
の２つの中だ。
これらの参考文献のうち、前者はdf-pnの考案者による論文だが前提知識を多々必要とする様子だった。
よって（将棋の駒の動かし方以外の）前提知識を必要としない後者を中心に今日は読む。
ポイントだと感じたところ。まだ実装していないので、間違って理解している可能性が高い：
- 「合法手」の意味が指し将棋と詰め将棋で違う。前者では「将棋のルールに違反しない手」を指すが、後者ではプレイヤによって意味が違う。
攻め方の「合法手」： 王手をかける手
玉方の「合法手」： 王手から逃げる手
これを理解していないとなぜ終端OR節点、終端AND節点の２つでそれぞれdn(n) = 0 とpn(n) =0となるのか理解できない。
終端OR節点でdn(n) = 0 となる理由： 「王手をかける手」がないから。
終端AND節点でpn(n)=0となる理由： 「王手から逃げる手」がないから。
理解せずともとりあえず実装はできる…と夢を見たいが恐らく実装もできないと思う。すなわち合法手生成の関数をプレイヤごとに別々に用意しなければいけないと気付かないといけない。たとえば
genmove_semeru()
genmove_mamoru()
のように実装する。genmove(semeruOrMamoru)でもいいけど。指し将棋とは決定的にここが違う。 - よって、
終端OR節点でpn(n) = 無限
終端AND節点でdn(n) = 無限
となっているのは、便宜である。実際にはpn(終端OR節点) = 3やdn(終端AND節点) = 1程度かもしれない。この「無限」は「整数値として考える意味がなくなった」ことを表す記号であり、おそらくは計算上でつじつまが合うからというだけの理由でこう書かれている（実装のときに、条件分岐などで便利なのだろう）。 - 先端節点と終端節点は違う。先端節点とはまだ子節点(子ノード)があるかもしれない節点のこと。先端節点についてgenmove(semeruOrMamoru)したときに0が表示されたときに、その先端節点が終端節点になる。
ここまでが一まとまりに理解したい事柄で、以下は個々別々に覚えておきたい事柄。
- 子節点に向かう合法手が少ない節点ほど、探索を優先させるべきとみなされる。
- 各節点が、{証明数、反証数、値}の３つ組をそれぞれ持つということを強く意識しておきたい。AND/OR木におけるこの値(true,false,不明)１つだけをminimax木における評価値と考えておくと、あれじゃあ証明数と反証数ってなんで必要なの？という痛い目に合う。実際には証明数と反証数という（２つの）評価値がminimax木における（Ⅰつの）評価値に対応しており、trueやfalseや不明という値というのは証明数と反証数のどちらかが0になったときをそう総称しているだけに過ぎない。
と理解しているのだがちょっとこの理解は信用できない。というのは上記の参考文献の前者において、GenerateLegalMoves()を呼び出す前に既に末端ノードを判定しているからだ。ということはgenmove()された合法手の数以外に末端を見分ける識別基準が存在するのかも。ここがまだ怪しい。
