Enhancements of Proof Number Search in Connect6
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 na飗e 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 na飗e PN, PN＃ enhances the speed of program, reduces the size of search tree, and strengthens the ability to solve a position.
Proof Number Search Connect6 Threat-Based Search Best First Search
Chang-ming Xu Z.M. Ma Jun-jie Tao Xin-he Xu
College of Information Science and Engineering, Shenyang 110004 Software College of Northeastern Univercity, Shenyang 110004
国际会议
2009年中国控制与决策会议(2009 Chinese Control and Decision Conference)
广西桂林
英文
4525-4529
2009-06-17（万方平台首次上网日期，不代表论文的发表时间）