Browsing by Author "Chiang, Sheng-Hao"

Now showing 1 - 2 of 2

Drawn k-in-a-row games
(2011-08-12)
Chiang, Sheng-Hao
;
Wu, I-Chen
;
Lin, Ping-Hung
;
資訊工程學系
;
Department of Computer Science
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 x 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 k(draw)(p), such that Connect(m, n, k, p, q) games are drawn for all k >= k(draw)(p), m >= 1, n >= 1, 0 <= q <= p, as follows. (1) k(draw)(p) = 11. (2) For all p >= 3, k(draw)(p) = 3p + 3d - 1, where d is a logarithmic function of p. So, the ratio k(draw)(P)/P is approximately 3 for sufficiently large p. The first result was derived with the help of a program. To our knowledge, our k(draw)(p) values are currently the smallest for all 2 <= p <= 1000. (C) 2011 Elsevier B.V. All rights reserved.
On Drawn K-In-A-Row Games
(2010)
Chiang, Sheng-Hao
;
Wu, I-Chen
;
Lin, Ping-Hung
;
資訊工程學系
;
Department of Computer Science
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.