A new family of k-in-a-row games

I-Chen Wu*, Dei Yen Huang

*Corresponding author for this work

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

22 Scopus citations

Abstract

This paper contains three contributions. First, it introduces a new family of k-in-a-row games, Connect(m,n,k,p,q). In Connect(m,n,k, p,q), two players alternately place p stones on an m × n board in each turn, except for the start when the first player places q stones at her In this contribution we use 'she' and 'her' whenever 'she or he' and 'her or his' are meant. first move. The player who first obtains k consecutive stones of her own first wins. The traditional game five-in-a-row, also called Go-Moku, in the free style is Connect(15,15,5,1,1). For brevity, Connect(k,p,q) denotes the game Connect(∞,∞,k,p,q), played on infinite boards. Second, this paper analyzes the characteristics of these games, especially for the fairness. In the analysis of fairness, we first exclude the ones which are apparently unfair or solved. Then, for the rest of games, we argue that p=2q is a necessary condition for fairness in the sense that one player always has q more stones than the other after making a move. Among these games, Connect(6,2,1) is most interesting to this paper and is named Connect6. Third, this paper proposes a threat-based strategy to play Connect(k,p,q) games and implements a computer program for Connect6, based on the strategy. In addition, this paper also illustrates a new null-move search approach by solving Connect(6,2,3) where the first player wins. The result also hints that for Connect6 the second player usually should not place the initial two stones far away from the first stone played by the first player.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 11th International Conference, ACG 2005, Revised Papers
Pages180-194
Number of pages15
DOIs
StatePublished - 1 Dec 2006
Event11th International Conference on Advances in Computer Games, ACG 2005 - Taipei, Taiwan
Duration: 6 Sep 20059 Sep 2005

Publication series

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

Conference

Conference11th International Conference on Advances in Computer Games, ACG 2005
CountryTaiwan
CityTaipei
Period6/09/059/09/05

Fingerprint Dive into the research topics of 'A new family of k-in-a-row games'. Together they form a unique fingerprint.

Cite this