TY - JOUR

T1 - On the fairness and complexity of generalized k-in-a-row games

AU - Hsieh, Ming Yu

AU - Tsai, Shi-Chun

PY - 2007/10/15

Y1 - 2007/10/15

N2 - Recently, Wu and Huang [I.-C. Wu, D.-Y. Huang, A new family of k-in-a-row games, in: The 11th Advances in Computer Games Conference, ACG'11, Taipei, Taiwan, September 2005] introduced a new game called Connect6, where two players, Black and White, alternately place two stones of their own color, black and white respectively, on an empty Go-like board, except for that Black (the first player) places one stone only for the first move. The one who gets six consecutive (horizontally, vertically or diagonally) stones of his color first wins the game. Unlike Go-Moku, Connect6 appears to be fairer and has been adopted as an official competition event in Computer Olympiad 2006. Connect (m, n, k, p, q) is a generalized family of k-in-a-row games, where two players place p stones on an m × n board alternatively, except Black places q stones in the first move. The one who first gets his stones k-consecutive in a line (horizontally, vertically or diagonally) wins. Connect6 is simply the game of Connect (m, n, 6, 2, 1). In this paper, we study two interesting issues of Connect (m, n, k, p, q): fairness and complexity. First, we prove that no one has a winning strategy in Connect (m, n, k, p, q) starting from an empty board when k ≥ 4 p + 7 and p ≥ q. Second, we prove that, for any fixed constants k, p such that k - p ≥ max {3, p} and a given Connect (m, n, k, p, q) position, it is PSPACE-complete to determine whether the first player has a winning strategy. Consequently, this implies that Connect6 played on an m × n board (i.e., Connect (m, n, 6, 2, 1)) is PSPACE-complete.

AB - Recently, Wu and Huang [I.-C. Wu, D.-Y. Huang, A new family of k-in-a-row games, in: The 11th Advances in Computer Games Conference, ACG'11, Taipei, Taiwan, September 2005] introduced a new game called Connect6, where two players, Black and White, alternately place two stones of their own color, black and white respectively, on an empty Go-like board, except for that Black (the first player) places one stone only for the first move. The one who gets six consecutive (horizontally, vertically or diagonally) stones of his color first wins the game. Unlike Go-Moku, Connect6 appears to be fairer and has been adopted as an official competition event in Computer Olympiad 2006. Connect (m, n, k, p, q) is a generalized family of k-in-a-row games, where two players place p stones on an m × n board alternatively, except Black places q stones in the first move. The one who first gets his stones k-consecutive in a line (horizontally, vertically or diagonally) wins. Connect6 is simply the game of Connect (m, n, 6, 2, 1). In this paper, we study two interesting issues of Connect (m, n, k, p, q): fairness and complexity. First, we prove that no one has a winning strategy in Connect (m, n, k, p, q) starting from an empty board when k ≥ 4 p + 7 and p ≥ q. Second, we prove that, for any fixed constants k, p such that k - p ≥ max {3, p} and a given Connect (m, n, k, p, q) position, it is PSPACE-complete to determine whether the first player has a winning strategy. Consequently, this implies that Connect6 played on an m × n board (i.e., Connect (m, n, 6, 2, 1)) is PSPACE-complete.

KW - Computational complexity

KW - k-in-a-row games

KW - Mathematical games

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

U2 - 10.1016/j.tcs.2007.05.031

DO - 10.1016/j.tcs.2007.05.031

M3 - Article

AN - SCOPUS:34548792316

VL - 385

SP - 88

EP - 100

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-3

ER -