Dependency-based search for Connect6

I-Chen Wu; Hao Hua Kang; Hung Hsuan Lin; Ping Hung Lin; Ting Han Wei; Chieh Min Chang

doi:10.1007/978-3-319-09165-5_1

Dependency-based search for Connect6

I-Chen Wu^*, Hao Hua Kang, Hung Hsuan Lin, Ping Hung Lin, Ting Han Wei, Chieh Min Chang

^*Corresponding author for this work

Department of Computer Science

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

1 Scopus citations

Abstract

Allis proposed dependency-based search (DBS) to solve Go-Moku, a kind of five-in-a-row game. DBS is critical for threat space search (TSS) when there are many independent or nearly independent TSS areas. Similarly, DBS is also important for the game Connect6, a kind of six-in-a-row game with two pieces per move. Unfortunately, the rule that two pieces are played per move in Connect6 makes DBS extremely difficult to apply to Connect6 programs. This paper is the first attempt to apply DBS to Connect6 programs. The targeted program is NCTU6, which won Connect6 tournaments in the Computer Olympiad twice and defeated many professional players in Man-Machine Connect6 championships. The experimental results show that DBS yields a speedup factor of 4.12 on average, and up to 50 for some hard positions.

Original language	English
Title of host publication	Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers
Publisher	Springer Verlag
Pages	1-13
Number of pages	13
ISBN (Print)	9783319091648
DOIs	https://doi.org/10.1007/978-3-319-09165-5_1
State	Published - 1 Jan 2014
Event	8th International Conference on Computers and Games, CG 2013 - Yokohama, Japan Duration: 13 Aug 2013 → 15 Aug 2013

Publication series

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

Conference

Conference	8th International Conference on Computers and Games, CG 2013
Country	Japan
City	Yokohama
Period	13/08/13 → 15/08/13

Keywords

Connect6
Dependency-based search
NCTU6
Threat-space search

Access to Document

10.1007/978-3-319-09165-5_1

Fingerprint Dive into the research topics of 'Dependency-based search for Connect6'. Together they form a unique fingerprint.

Cite this

Wu, I-C., Kang, H. H., Lin, H. H., Lin, P. H., Wei, T. H., & Chang, C. M. (2014). Dependency-based search for Connect6. In Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers (pp. 1-13). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8427 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-09165-5_1

Wu, I-Chen ; Kang, Hao Hua ; Lin, Hung Hsuan ; Lin, Ping Hung ; Wei, Ting Han ; Chang, Chieh Min. / Dependency-based search for Connect6. Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers. Springer Verlag, 2014. pp. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{db4d67024c5b4250b205d1cb6b7c2fae,

title = "Dependency-based search for Connect6",

abstract = "Allis proposed dependency-based search (DBS) to solve Go-Moku, a kind of five-in-a-row game. DBS is critical for threat space search (TSS) when there are many independent or nearly independent TSS areas. Similarly, DBS is also important for the game Connect6, a kind of six-in-a-row game with two pieces per move. Unfortunately, the rule that two pieces are played per move in Connect6 makes DBS extremely difficult to apply to Connect6 programs. This paper is the first attempt to apply DBS to Connect6 programs. The targeted program is NCTU6, which won Connect6 tournaments in the Computer Olympiad twice and defeated many professional players in Man-Machine Connect6 championships. The experimental results show that DBS yields a speedup factor of 4.12 on average, and up to 50 for some hard positions.",

keywords = "Connect6, Dependency-based search, NCTU6, Threat-space search",

author = "I-Chen Wu and Kang, {Hao Hua} and Lin, {Hung Hsuan} and Lin, {Ping Hung} and Wei, {Ting Han} and Chang, {Chieh Min}",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-319-09165-5_1",

language = "English",

isbn = "9783319091648",

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

publisher = "Springer Verlag",

pages = "1--13",

booktitle = "Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers",

address = "Germany",

note = "null ; Conference date: 13-08-2013 Through 15-08-2013",

}

Wu, I-C, Kang, HH, Lin, HH, Lin, PH, Wei, TH & Chang, CM 2014, Dependency-based search for Connect6. in Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8427 LNCS, Springer Verlag, pp. 1-13, 8th International Conference on Computers and Games, CG 2013, Yokohama, Japan, 13/08/13. https://doi.org/10.1007/978-3-319-09165-5_1

Dependency-based search for Connect6. / Wu, I-Chen; Kang, Hao Hua; Lin, Hung Hsuan; Lin, Ping Hung; Wei, Ting Han; Chang, Chieh Min.

Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers. Springer Verlag, 2014. p. 1-13 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8427 LNCS).

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

TY - GEN

T1 - Dependency-based search for Connect6

AU - Wu, I-Chen

AU - Kang, Hao Hua

AU - Lin, Hung Hsuan

AU - Lin, Ping Hung

AU - Wei, Ting Han

AU - Chang, Chieh Min

PY - 2014/1/1

Y1 - 2014/1/1

N2 - Allis proposed dependency-based search (DBS) to solve Go-Moku, a kind of five-in-a-row game. DBS is critical for threat space search (TSS) when there are many independent or nearly independent TSS areas. Similarly, DBS is also important for the game Connect6, a kind of six-in-a-row game with two pieces per move. Unfortunately, the rule that two pieces are played per move in Connect6 makes DBS extremely difficult to apply to Connect6 programs. This paper is the first attempt to apply DBS to Connect6 programs. The targeted program is NCTU6, which won Connect6 tournaments in the Computer Olympiad twice and defeated many professional players in Man-Machine Connect6 championships. The experimental results show that DBS yields a speedup factor of 4.12 on average, and up to 50 for some hard positions.

AB - Allis proposed dependency-based search (DBS) to solve Go-Moku, a kind of five-in-a-row game. DBS is critical for threat space search (TSS) when there are many independent or nearly independent TSS areas. Similarly, DBS is also important for the game Connect6, a kind of six-in-a-row game with two pieces per move. Unfortunately, the rule that two pieces are played per move in Connect6 makes DBS extremely difficult to apply to Connect6 programs. This paper is the first attempt to apply DBS to Connect6 programs. The targeted program is NCTU6, which won Connect6 tournaments in the Computer Olympiad twice and defeated many professional players in Man-Machine Connect6 championships. The experimental results show that DBS yields a speedup factor of 4.12 on average, and up to 50 for some hard positions.

KW - Connect6

KW - Dependency-based search

KW - NCTU6

KW - Threat-space search

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

U2 - 10.1007/978-3-319-09165-5_1

DO - 10.1007/978-3-319-09165-5_1

M3 - Conference contribution

AN - SCOPUS:84958525843

SN - 9783319091648

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

SP - 1

EP - 13

BT - Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers

PB - Springer Verlag

Y2 - 13 August 2013 through 15 August 2013

ER -

Wu I-C, Kang HH, Lin HH, Lin PH, Wei TH, Chang CM. Dependency-based search for Connect6. In Computers and Games - 8th International Conference, CG 2013, Revised Selected Papers. Springer Verlag. 2014. p. 1-13. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-319-09165-5_1

Dependency-based search for Connect6

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Cite this