証明数を用いたλ 探索の効率的な実装

df-pn 駆動λ 探索およびdf-pn 駆動dualλ 探索の性能をシンペイの局面を対象として評価した．df-pn 駆動λ 探索は脅威度を用いた探索アルゴリズムであるλ 探索と証明数を用いた探索アルゴリズムであるdf-pn を組み合わたアルゴリズムであり，将棋の必至問題で及び囲碁の捕獲問題での有効性を示されている．ただし，λ 探索とdf-pn を組み合わせる方法である拡幅戦略の比較と，双方のプレイヤの脅威度を利用する探索アルゴリズムであるdf-pn 駆動dualλ 探索の有効性は将棋の必至問題のみを対象に評価した．しかし，将棋の必至問題には強い脅威度が存在する局面のみが存在するため，弱い脅威度の存在する局面での拡幅戦略による違いやdf-pn 駆動λ 探索とdf-pn 駆動dualλ 探索の比較はおこなわれていない．そこで，弱い脅威度の存在する局面で拡幅戦略の比較およびdf-pn駆動λ 探索とdf-pn 駆動dualλ 探索をおこなうため，シンペイを対象として実験をおこなった．シンペイは全ての局面が解かれているゲームで，弱い脅威度の存在する局面があることやλ 探索が正解できない局面があることも知られており，実験の対象として興味深い．シンペイの全局面のうち勝ちとなる局面の1000 分の1 をランダムで取り出し，各アルゴリズム・拡幅戦略の性能を比較した．その結果，拡幅戦略の違いにより，大きな性能の変化は見られなかった．一方で，df-pn 駆動λ 探索と比べてdf-pn 駆動dualλ 探索は，多くの問題で性能が改善されることがわかった．

AND/OR tree search algorithms called the df-pn driven λ-search and the df-pn driven dualλ-search were tested on the game of Simpei. Df-pn driven λ-search is the combination of a threat based search algorithm called the λ-search algorithm and a proof number based search algorithm called the df-pn search algorithm. Df-pn driven λ-search was tested on brinkmate problems of Shogi and capture problems of Go. Several other methods to combine the λ-search algorithm and the df-pn search algorithm were also proposed as an expansion to df-pn driven λ-search called widening schemes. The df-pn driven dual λ-search algorithm was also proposed, which takes into account of threats by both players. Widening schemes and df-pn driven dual λ-search were tested for Shogi brinkmate problems. However, as Shogi brinkmate problems contain positions with strong threats only, there were no experiments of comparing these methods in positions involving weak threats. In this paper, the comparison of widening schemes and the comparison of df-pn driven λ-search and df-pn driven dual λ-search are made for positions with weak threats. The game of Simpei is a strongly solved game. It is known to have positions with weak threats, and it has some positions that λ-search can never solve, which make it an interesting target. 1 out of 1000 positions were randomly sampled from all the positions in Simpei, and positions where the winner is to play were extracted as the target, and the resource needed to solve the target was measured for each algorithms. As the result, no significant difference were seen between the widening schemes, while df-pn driven dual λ-search performed better than df-pn driven λ-search in most positions.