TY - GEN

T1 - On drawn K-in-a-row games

AU - Chiang, Sheng Hao

AU - Wu, I-Chen

AU - Lin, Ping Hung

PY - 2010/6/25

Y1 - 2010/6/25

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77953773181&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-12993-3_15

DO - 10.1007/978-3-642-12993-3_15

M3 - Conference contribution

AN - SCOPUS:77953773181

SN - 3642129927

SN - 9783642129926

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 169

BT - Advances in Computer Games - 12th International Conference, ACG 2009, Revised Papers

Y2 - 11 May 2009 through 13 May 2009

ER -