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 contribution

28 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

    Wu, I-C., Lin, H. H., Lin, P. H., Sun, D. J., Chan, Y. C., & Chen, B. T. (2011). Job-level proof-number search for connect6. In Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers (pp. 11-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6515 LNCS). https://doi.org/10.1007/978-3-642-17928-0_2