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.