Counting Reachable Positions in a Simplified Model of Connect Four

Abstract

By eliminating the win condition in the game of Connect Four and extending the board to infinite height, a rich state space of positions is obtained. We investigate the number of positions reachable on an $n$-column board after $k$ color-alternating moves. For fixed $k$ we demonstrate polynomiality, derive a partial formula for the polynomial coefficients, and precisely characterize the asymptotic behavior as $n\to \infty$. We then turn our attention to the fixed-$n$ case and show that, under a natural addition operation, positions reachable in an even number of moves form a monoid with a highly symmetric finite generating set; by examining certain free submonoids, we bound the exponential growth rate as $k\to \infty$.