Enhancements of proof number search in connect6

Abstract

Based on PN search which is a best first search, a new search algorithm named PN# is proposed in this paper. Being easiest to (dis)prove, the node with least pn or dn is always expanded first in the naive implementation of PN search. However, the frontier nodes can not be sorted by the initialized value of their pn and dn. Especially, the brother nodes is always expanded at the same degree though some of them are superior than others. For above reasons, the domain knowledge is introduced, which makes the key factors to select the nodes to be expanded next is combined with the weight of the moves, besides the threshold pn and dn. Our experiments show that compared with the naive PN, PN# enhances the speed of program, reduces the size of search tree, and strengthens the ability to solve a position.