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

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

1 Scopus citations


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 languageEnglish
Title of host publicationComputers and Games - 8th International Conference, CG 2013, Revised Selected Papers
PublisherSpringer Verlag
Number of pages13
ISBN (Print)9783319091648
StatePublished - 1 Jan 2014
Event8th International Conference on Computers and Games, CG 2013 - Yokohama, Japan
Duration: 13 Aug 201315 Aug 2013

Publication series

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


Conference8th International Conference on Computers and Games, CG 2013


  • Connect6
  • Dependency-based search
  • NCTU6
  • Threat-space search

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

Cite this