东北大学学报（自然科学版）

东北大学学报:自然科学版 ›› 2016, Vol. 37 ›› Issue (8): 1070-1075.DOI: 10.12068/j.issn.1005-3026.2016.08.002

• 信息与控制 • 上一篇    下一篇

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

高强1,2， 徐心和1   

  1. (1. 东北大学 信息科学与工程学院， 辽宁 沈阳110819; 2.沈阳大学 辽宁省装备制造综合自动化重点实验室，辽宁 沈阳110044)
  • 收稿日期:2015-05-01 修回日期:2015-05-01 出版日期:2016-08-15 发布日期:2016-08-12
  • 通讯作者: 高强
  • 作者简介:高强(1980-)，男，辽宁沈阳人，东北大学博士研究生； 徐心和(1940-)，男，黑龙江哈尔滨人，东北大学教授，博士生导师.
  • 基金资助:
    国家自然科学基金资助项目(61370153).

Application of Proof-Number Search to Computer Lazi Games

GAO Qiang1,2， XU Xin-he1   

  1. 1. School of Information Science & Engineering， Northeastern University， Shenyang 110819， China; 2. Key Laboratory of Manufacturing Industrial Integrated Automation， Shenyang University， Shenyang 110044， China.
  • Received:2015-05-01 Revised:2015-05-01 Online:2016-08-15 Published:2016-08-12
  • Contact: GAO Qiang
  • About author:-
  • Supported by:
    -

RichHTML

0

PDF (PC)

1048

摘要： 详细阐述了基于“与或树”的证据计数法原理，综述了证据计数法在一些落子类博弈系统中的应用；论述了证据计数法和PN2算法的缺陷.基于PN2算法，提出了一种两级的PN算法，即PN-DFPN，其中第一级采用标准的PN算法，第二级采用一种深度优先的PN算法代替PN2算法中的第二级PN算法，弥补了PN2算法存在的不足.将PN2和PN-DFPN算法应用于求解7×7和9×9棋盘的六子棋开局局面上，实验证明，PN-DFPN在搜索效率和求解能力上都明显优于PN2.

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

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.

Key words: computer game, proof-number search, PN2, AND/OR tree, game-theoretical value, Connect 6

中图分类号: