Drawn k-in-a-row games

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

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

Wu and Huang (2005) [12] and Wu et al. (2006) [13] presented a generalized family of k-in-a-row games, called Connect(m, n, k, p, q). Two players, Black and White, alternately place p stones on an m×n board in each turn. Black plays first, and places q stones initially. The player who first gets k consecutive stones of his/her own horizontally, vertically, or diagonally wins. Both tie the game when the board is filled up with neither player winning. A Connect(m, n, k, p, q) game is drawn if neither has any winning strategy. Given p, this paper derives the value kdraw(p), such that Connect(m, n, k, p, q) games are drawn for all k≥kdraw(p), m≥1, n≥1, 0≤q≤p, as follows. (1) kdraw(p)=11. (2) For all p≥3, k draw(p)=3p+3d-1, where d is a logarithmic function of p. So, the ratio kdraw(p)/p is approximately 3 for sufficiently large p. The first result was derived with the help of a program. To our knowledge, our kdraw(p) values are currently the smallest for all 2≤p≥1000.

Original languageEnglish
Pages (from-to)4558-4569
Number of pages12
JournalTheoretical Computer Science
Volume412
Issue number35
DOIs
StatePublished - 12 Aug 2011

Keywords

  • Connect6
  • Hypergraphs
  • k-in-a-row games

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

Cite this