_ 詰将棋で必要になる工夫いろいろ

後輩がはまっていたのでついでにまとめ。And-or木の探索の研究において長井さんのdf-pn(+)アルゴリズムは画期的な進歩であり、現在のところ最も良いアルゴリズムと考えられているが、そのまま詰将棋に適用するといくつか落とし穴があることが指摘されている:

• ループによる証明数無限増殖の問題 (囲碁，将棋で発生，オセロでは起こらない)
• rootからの距離を数える方法(岸本さんの対策): Df-pn in Go: An Application to the One-Eye Problem, ACG10 (http://www.cs.ualberta.ca/~kishi/pdf_file/acg_kishimoto_mueller.pdf)
• 将棋独自のヒューリスティクスを使えば防げるかもしれない?
• GHI問題 (graph history interaction, 詰将棋では詰を不詰と判定してしまう問題)
• 長井さんの対策: rootの閾値を工夫する (この方法は不詰の発見に弱いことが岸本さんにより指摘されている)
• 岸本さんの対策: A General Solution to the Graph History Interaction Problem, AAAI'04 (http://www.cs.ualberta.ca/~kishi/pdf_file/AAAI04KishimotoA.pdf)
• 合流による証明(反証)数の二重カウント問題
• 長井さんの対策: 親のポインタをたどって分岐を発見し条件によっては\sumの代わりに\maxを使う
• 柿木さんの対策: 受ける手が少ない時に特別扱い「詰将棋プログラムにおける証明数の２重カウント対策の一手法」CSA例会2005年１月(http://www02.so-net.ne.jp/~kakinoki/book.htm)

長井さんの研究はいずれも「コンピュータ将棋の進歩4」または情報処理学会論文誌に掲載された文献を参照。

_ その他の有用なenhancement

• 証明駒，反証駒: 脊尾さんのGPW99の論文(詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について)が出典，df-pnでも有効
• 岸本さんの研究で閾値の動的な制御 (to appear かな)
• 三輪さんの研究でh の初期化や，詰将棋をいつ呼ぶか (http://www.logos.ic.i.u-tokyo.ac.jp/~miwa/papers.html)
• 局面表のGCについて: 大変そうなのでおいかけてなかったり
• その他、金子も詰将棋関連の研究にちょっと関わっていたり

(他に関連研究がありましたらコメントお願いします)