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

doi:10.1007/978-3-642-17928-0_2

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

Department of Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

39 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 language	English
Title of host publication	Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers
Pages	11-22
Number of pages	12
DOIs	https://doi.org/10.1007/978-3-642-17928-0_2
State	Published - 15 Apr 2011
Event	7th Computer and Games Conference, CG 2010 - Kanazawa, Japan Duration: 24 Sep 2010 → 26 Sep 2010

Publication series

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

Conference

Conference	7th Computer and Games Conference, CG 2010
Country/Territory	Japan
City	Kanazawa
Period	24/09/10 → 26/09/10

Access to Document

10.1007/978-3-642-17928-0_2

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

@inproceedings{aa5369cd545a45aba86c900ea7f1ecdd,

title = "Job-level proof-number search for connect6",

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.",

author = "I-Chen Wu and Lin, {Hung Hsuan} and Lin, {Ping Hung} and Sun, {Der Johng} and Chan, {Yi Chih} and Chen, {Bo Ting}",

year = "2011",

month = apr,

day = "15",

doi = "10.1007/978-3-642-17928-0_2",

language = "English",

isbn = "3642179274",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "11--22",

booktitle = "Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers",

note = "7th Computer and Games Conference, CG 2010 ; Conference date: 24-09-2010 Through 26-09-2010",

}

Wu, I-C, Lin, HH, Lin, PH, Sun, DJ, Chan, YC & Chen, BT 2011, Job-level proof-number search for connect6. in Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6515 LNCS, pp. 11-22, 7th Computer and Games Conference, CG 2010, Kanazawa, Japan, 24/09/10. https://doi.org/10.1007/978-3-642-17928-0_2

Job-level proof-number search for connect6. / Wu, I-Chen; Lin, Hung Hsuan; Lin, Ping Hung et al.
Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers. 2011. p. 11-22 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6515 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Job-level proof-number search for connect6

AU - Wu, I-Chen

AU - Lin, Hung Hsuan

AU - Lin, Ping Hung

AU - Sun, Der Johng

AU - Chan, Yi Chih

AU - Chen, Bo Ting

PY - 2011/4/15

Y1 - 2011/4/15

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

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

UR - http://www.scopus.com/inward/record.url?scp=79953839378&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-17928-0_2

DO - 10.1007/978-3-642-17928-0_2

M3 - Conference contribution

AN - SCOPUS:79953839378

SN - 3642179274

SN - 9783642179273

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 11

EP - 22

BT - Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers

T2 - 7th Computer and Games Conference, CG 2010

Y2 - 24 September 2010 through 26 September 2010

ER -

Job-level proof-number search for connect6

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this