Job-level proof-number search for connect6

I-Chen Wu*, Hung Hsuan Lin, Ping Hung Lin, Der Johng Sun, Yi Chih Chan, Bo Ting Chen

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

29 Scopus citations

Abstract

This paper proposes a new approach for proof number (PN) search, named job-level PN (JL-PN) search, where each search tree node is evaluated or expanded by a heavy-weight job, which takes normally over tens of seconds. Such JL-PN search is well suited for parallel processing, since these jobs are allowed to be performed by remote processors independently. This paper applies JL-PN search to solving automatically several Connect6 positions including openings on desktop grids. For some of these openings, so far no human expert had been able to find a winning strategy. Our experiments also show that the speedups for solving the test positions are roughly linear, fluctuating from sublinear to superlinear. Hence, JL-PN search appears to be a quite promising approach to solving games.

Original languageEnglish
Title of host publicationComputers and Games - 7th International Conference, CG 2010, Revised Selected Papers
Pages11-22
Number of pages12
DOIs
StatePublished - 15 Apr 2011
Event7th Computer and Games Conference, CG 2010 - Kanazawa, Japan
Duration: 24 Sep 201026 Sep 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6515 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference7th Computer and Games Conference, CG 2010
CountryJapan
CityKanazawa
Period24/09/1026/09/10

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

Cite this