Title: Job-Level Proof Number Search
Authors: Wu, I. -Chen
Lin, Hung-Hsuan
Sun, Der-Johng
Kao, Kuo-Yuan
Lin, Ping-Hung
Chan, Yi-Chih
Chen, Po-Ting
Department of Computer Science
Keywords: Connect6;desktop grids;job-level proof number search (JL-PNS);proof number search;threat-space search
Issue Date: 1-Mar-2013
Abstract: This paper introduces an approach, called generic job-level search, to leverage the game-playing programs which are already written and encapsulated as jobs. Such an approach is well suited to a distributed computing environment, since these jobs are allowed to be run by remote processors independently. In this paper, we present and focus on a job-level proof number search (JL-PNS), a kind of generic job-level search for solving computer game search problems, and apply JL-PNS to solving automatically several Connect6 positions, including some difficult openings. This paper also proposes a method of postponed sibling generation to generate nodes smoothly, and some policies, such as virtual win, virtual loss, virtual equivalence, flagging, or hybrids of the above, to expand the nodes. Our experiment compared these policies, and the results showed that the virtual-equivalence policy, together with flagging, performed the best against other policies. In addition, the results also showed that the speedups for solving these positions are 8.58 on average on 16 cores.
URI: http://dx.doi.org/10.1109/TCIAIG.2012.2224659
ISSN: 1943-068X
DOI: 10.1109/TCIAIG.2012.2224659
Volume: 5
Issue: 1
Begin Page: 44
End Page: 56
Appears in Collections:Articles

Files in This Item:

  1. 000316479500004.pdf