AIメモ2

[pdf]反復深化探索に基く協力詰将棋の解法


通常の詰将棋は先手後手共に最善手を打つのに対して、協力詰めの後手は最悪(先手にとっての最善)手を打つ詰将棋。通常の詰将棋はAND/OR木の探索問題として定式化できるのに対して、協力詰めはOR木の探索問題として定式化できる。


協力詰めの特性上、同じ局面で手数が異なる場合は手数が少ないほうが優秀であるため、反復深化深さ優先探索を行いながら置換表に局面を登録していく。こうすると置換表には手数の少ない局面から登録されることになり、ある局面が置換表に登録済みならそれを再利用すれば良い。


あるノードが確定局面とは、そのノードが葉であるか子ノード全てが確定局面であることである。また、確定局面を根とする部分木を考えると、その部分木は一度探索され置換表に記憶されている。しかし置換表を用いた枝刈りの特性上、確定局面を根とする部分木は根を除いて探索されることがない。他の探索で参照される可能性はあるが、ある程度雑に扱う(上書きを許す)ことでメモリの有効利用に繋がる。


反復深化と置換表は相性いいって聞くんだけど、どうも理解できない