Job-level proof number search

I-Chen Wu, Hung Hsuan Lin, Der Johng Sun, Kuo Yuan Kao, Ping Hung Lin, Yi Chih Chan, Po Ting Chen

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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.

Original languageEnglish
Article number6329938
Pages (from-to)44-56
Number of pages13
JournalIEEE Transactions on Computational Intelligence and AI in Games
Issue number1
StatePublished - 1 Jan 2013


  • Connect6
  • Desktop grids
  • Job-level proof number search (JL-PNS)
  • Proof number search
  • Threat-space search

Fingerprint Dive into the research topics of 'Job-level proof number search'. Together they form a unique fingerprint.

Cite this