证据计数法在落子类机器博弈中的应用  

Application of Proof-Number Search to Computer Lazi Games

作　　者：高强[1,2] 徐心和[1] 

机构地区：[1]东北大学信息科学与工程学院,辽宁沈阳110819 [2]沈阳大学辽宁省装备制造综合自动化重点实验室,辽宁沈阳110044

出　　处：《东北大学学报（自然科学版）》2016年第8期1070-1074,1103,共6页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(61370153)

摘　　要：详细阐述了基于"与或树"的证据计数法原理,综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷.基于PN2算法,提出了一种两级的PN算法,即PN-DFPN,其中第一级采用标准的PN算法,第二级采用一种深度优先的PN算法代替PN2算法中的第二级PN算法,弥补了PN2算法存在的不足.将PN2和PN-DFPN算法应用于求解7×7和9×9棋盘的六子棋开局局面上,实验证明,PN-DFPN在搜索效率和求解能力上都明显优于PN2.The principles of proof-number based on the AND/OR tree are expounded,the application of proof-number search to computer Lazi games is summarized and the flaws of proof-number and PN2 search are discussed.Moreover,a newtwo-level algorithm,i.e.,PN-DFPN search,is introduced,which performs at the first-level a standard proof-number search and at the second-level a depth-first PN search that replaces the second-level of PN2.This algorithm covers the shortage of PN2 search.PN2 and PN-DFPN are applied to solve some openings of Connect 6on 7 × 7 and 9 × 9 boards.The experimental result shows that PN-DFPN is more efficient than PN2.

关 键 词：计算机博弈 证据计数法 两级PN算法 与或树 博弈问题理论解 六子棋 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]