Relevance-Zone-Oriented Proof Search for Connect6

Abstract

Wu and Huang (Advances in Computer Games, pp. 180-194, 2006) presented a new family of k-in-a-row games, among which Connect6 (a kind of six-in-a-row) attracted much attention. For Connect6 as well as the family of k-in-a-row games, this paper proposes a new threat-based proof search method, named relevance-zone-oriented proof (RZOP) search, developed from the lambda search proposed by Thomsen (Int. Comput. Games Assoc. J., vol. 23, no. 4, pp. 203-217, 2000). The proposed RZOP search is a novel, general, and elegant method of constructing and promoting relevance zones. Using this method together with a proof number search, this paper solved effectively and successfully many new Connect6 game positions, including several Connect6 openings, especially the Mickey Mouse opening, which used to be one of the popular openings before we solved it.