| 证据计数法在落子类机器博弈中的应用 |
| |
| 引用本文： | 高强,徐心和.证据计数法在落子类机器博弈中的应用[J].东北大学学报(自然科学版),2016,37(8):1070-1075. |
| |
| 作者姓名： | 高强 徐心和 |
| |
| 作者单位： | (1. 东北大学 信息科学与工程学院， 辽宁 沈阳110819; 2.沈阳大学 辽宁省装备制造综合自动化重点实验室，辽宁 沈阳110044) |
| |
| 基金项目： | 国家自然科学基金资助项目(61370153). |
| |
| 摘 要： | 详细阐述了基于"与或树"的证据计数法原理,综述了证据计数法在一些落子类博弈系统中的应用;论述了证据计数法和PN2算法的缺陷.基于PN2算法,提出了一种两级的PN算法,即PN-DFPN,其中第一级采用标准的PN算法,第二级采用一种深度优先的PN算法代替PN2算法中的第二级PN算法,弥补了PN2算法存在的不足.将PN2和PN-DFPN算法应用于求解7×7和9×9棋盘的六子棋开局局面上,实验证明,PN-DFPN在搜索效率和求解能力上都明显优于PN2.
|
| 关 键 词： | 计算机博弈 证据计数法 两级PN算法 与或树 博弈问题理论解 六子棋 |
Application of Proof-Number Search to Computer Lazi Games |
| |
| GAO Qiang,XU Xin-he.Application of Proof-Number Search to Computer Lazi Games[J].Journal of Northeastern University(Natural Science),2016,37(8):1070-1075. |
| |
| Authors: | GAO Qiang XU Xin-he |
| |
| Institution: | 1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 2. Key Laboratory of Manufacturing Industrial Integrated Automation， Shenyang University， Shenyang 110044， China. |
| |
| Abstract: | 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 new two-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 6 on 7×7 and 9×9 boards. The experimental result shows that PN-DFPN is more efficient than PN2. |
| |
| Keywords: | computer game proof-number search PN2 AND/OR tree game-theoretical value Connect 6 |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《东北大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《东北大学学报(自然科学版)》下载免费的PDF全文 |
