Enhancements of proof number search in connect6
Authors:
- 1 June 2009
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 19489439,p. 4525-4529
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.Keywords
This publication has 5 references indexed in Scilit:
- GAME OVER: BLACK TO PLAY AND DRAW IN CHECKERSICGA Journal: The Journal of the Computer Games Community, 2007
- A solution to the GHI problem for depth-first proof-number searchInformation Sciences, 2005
- An effective two-level proof-number search algorithmTheoretical Computer Science, 2004
- The -search algorithm: Application to tsume-shogiArtificial Intelligence, 2001
- Proof-number searchArtificial Intelligence, 1994