Job-Level Proof Number Search

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 independen...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computational intelligence and AI in games. 2013-03, Vol.5 (1), p.44-56
Main Authors: I-Chen Wu, Hung-Hsuan Lin, Der-Johng Sun, Kuo-Yuan Kao, Ping-Hung Lin, Yi-Chih Chan, Po-Ting Chen
Format: Article
Language:English
Subjects:
Computer games
Connect6
desktop grids
Distributed processing
job-level proof number search (JL-PNS)
Program processors
proof number search
Search problems
threat-space search
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:1943-068X
1943-0698
DOI:10.1109/TCIAIG.2012.2224659