詰将棋に対するdf-pnアルゴリズムの解説 | コウモリのちょーおんぱ

概要 #詰め将棋において、各局面の平均着手可能数は5.8手程度と言われている1。単純にこれを全探索することを考えると、\(n\) 手詰を解くためには \(5.8^n\) 局面を調べることになる。例えば、現時点で最長の詰将棋であるミクロコスモス（1525手詰）を解くためにはざっくり \(10^{1164}\) 局面を調べることになってしまう。このように、愚直な全探索では長手数の詰将棋を現実的な時間内で解くことはできないことが分かる。 しかし、ある局面が詰むことを示すだけならここまで膨大な探索は必要ない。例えば以下の局面を考える。 この局面の合法手は63金打、53金打など全部で9通りあるが、この局面が詰みであることを示すためには次の手順だけ探索できていればよい。 この探索結果より、玉方がどのように逃げても3手で詰むことが示せている。このような、ある局面が詰み（または不詰）だと証明するための局面