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

^*此作品的通信作者

資訊工程學系

研究成果: Conference contribution › 同行評審

41 引文斯高帕斯（Scopus）

摘要

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.

原文	English
主出版物標題	Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers
頁面	11-22
頁數	12
DOIs	https://doi.org/10.1007/978-3-642-17928-0_2
出版狀態	Published - 15 4月 2011
事件	7th Computer and Games Conference, CG 2010 - Kanazawa, 日本持續時間: 24 9月 2010 → 26 9月 2010

出版系列

名字	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
卷	6515 LNCS
ISSN（列印）	0302-9743
ISSN（電子）	1611-3349

Conference

Conference	7th Computer and Games Conference, CG 2010
國家/地區	日本
城市	Kanazawa
期間	24/09/10 → 26/09/10

存取文件

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

其它文件與鏈接

Link to publication in Scopus

引用此

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. 於 Computers and Games - 7th International Conference, CG 2010, Revised Selected Papers (頁 11-22). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); 卷 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. 於 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), 卷 6515 LNCS, 頁 11-22, 7th Computer and Games Conference, CG 2010, Kanazawa, 日本, 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 等.
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); 卷 6515 LNCS).

研究成果: Conference contribution › 同行評審

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 - https://www.scopus.com/pages/publications/79953839378

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

摘要

出版系列

Conference

存取文件

其它文件與鏈接

指紋

引用此