Journal of Northeastern University(Natural Science)

Journal of Northeastern University Natural Science ›› 2016, Vol. 37 ›› Issue (8): 1070-1075.DOI: 10.12068/j.issn.1005-3026.2016.08.002

• Information & Control • Previous Articles     Next Articles

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)

994

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

CLC Number: