Deep df-pn and Its Application to Connect6

Depth-first proof-number search (df-pn) is a powerful variant of proof-number search algorithms, widely used for AND/OR tree search or solving games. However, it suffers from the seesaw effect, which can be concluded as frequently going back to the ancestor nodes for selecting the most proving node. It works strongly against the efficiency in some situations. This paper proposes a new proof number algorithm called Deep depth-first proof-number search (Deep df-pn) to reduce the seesaw effect in df-pn. The only difference between Deep df-pn and df-pn is the proof number or disproof number of unsolved nodes. The proof number or disproof number of unsolved nodes is 1 in df-pn, while it is a function of depth with two parameters in Deep df-pn. By adjusting the value of parameters, Deep df-pn changes its behavior from searching broadly to searching deeply. Moreover, this paper proves that Deep df-pn enables to reduce the seesaw effect. Experiments performed in the domain of Connect6 show its effectiveness in searching efficiency.The 21st Game Programming Workshop (GPW2016