@article {IOPORT.05201836,
    author       = {Hsieh, Ming Yu and Tsai, Shi-Chun},
    title        = {On the fairness and complexity of generalized $k$-in-a-row games.},
    year         = {2007},
    journal      = {Theoretical Computer Science},
    volume       = {385},
    number       = {1-3},
    issn         = {0304-3975},
    pages        = {88-100},
    publisher    = {Elsevier Science Publishers, Amsterdam},
    doi          = {10.1016/j.tcs.2007.05.031},
    abstract     = {Summary: Recently, I.-C. Wu and 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 $\bold{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 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, $\bold{Connect6}$ appears to be fair and has been adopted as an official competition event in Computer Olympiad 2006. $\text{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\times 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. $\bold{Connect6}$ is simply the game of $\text{Connect}(m,n,6,2,1)$. In this paper, we study two interesting issues of $\text{Connect}(m,n,k,p,q)$: fairness and complexity. First, we prove that no one has a winning strategy in $\text{Connect}(m,n,k,p,q)$ starting from an empty board when $k\geq 4p+7$ and $p\geq q$. Second, we prove that, for any fixed constants $k,p$ such that $k-p\geq max{3,p}$ and for a given $\text{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 $\bold{Connect6}$ played on an $m\times n$ board (i.e., $\text{Connect}(m,n,6,2,1)$) is PSPACE-complete.},
    identifier   = {05201836},
}