On drawn K-in-a-row games

Sheng Hao Chiang*, I-Chen Wu, Ping Hung Lin

*Corresponding author for this work

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

1 Scopus citations

Abstract

In 2005, Wu and Huang [9] presented a generalized family of k-in-a-row games. The current paper simplifies the family to Connect(k, p). Two players alternately place p stones on empty squares of an infinite board in each turn. The player who first obtains k consecutive stones of his own horizontally, vertically, diagonally wins. A Connect(k, p)game is drawn if both have no winning strategy. Given p, this paper derives the value k draw(p), such that Connect(k draw(p), p) is drawn, as follows. (1) k draw(2) = 11. (2) For all p ≥ 3, k draw(p) = 3p+3d+8, where d is a logarithmic function of p. So, the ratio k draw(p)/p is approximate to 3 for sufficiently large p. To our knowledge, our k draw(p) are currently the smallest for all 2 ≤ p < 1000, except for p = 3.

Original languageEnglish
Title of host publicationAdvances in Computer Games - 12th International Conference, ACG 2009, Revised Papers
Pages158-169
Number of pages12
DOIs
StatePublished - 25 Jun 2010
Event12th International Conference on Advances in Computer Games, ACG 2009 - Pamplona, Spain
Duration: 11 May 200913 May 2009

Publication series

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

Conference

Conference12th International Conference on Advances in Computer Games, ACG 2009
CountrySpain
CityPamplona
Period11/05/0913/05/09

Fingerprint Dive into the research topics of 'On drawn K-in-a-row games'. Together they form a unique fingerprint.

Cite this