Tic-tac-toe with one mark type
Parameters $a,b,c$ are given such that $c\leq\max(a,b)$. In an $a\times b$ board, two players take turns putting a mark on an empty square. Whoever gets $c$ consecutive marks horizontally, vertically, or diagonally first wins. (Someone must win because we use only one mark type.) For each triple $(a,b,c)$, who has a winning strategy?
For $a=b=c=3$ (tic-tac-toe size), the first player can win by first going on the middle square and winning in the next turn.
In the one-dimensional case ($a=1$), this may well be a known game, but I also cannot find a reference. I asked the question on math.SE but it has not been solved.
co.combinatorics recreational-mathematics combinatorial-game-theory
pi66pi66
$\begingroup$ Don't you mean $c = \max(a, b)$ consecutive marks, not just $c \le \max(a, b)$ consecutive marks? If so, for $a = 1$ the game is won by the player who makes the $b$th move, regardless of what moves are made along the way. $\endgroup$
– LSpice
$\begingroup$ @LSpice $c$ is also a parameter of the game, and may be less than $\max(a,b)$. $\endgroup$
– pi66
$\begingroup$ I think your "all odd" strategy needs more detail, as the second player can win if $c$ is sufficiently large. I'll write x for a mark and . for an empty space. Let $c=7$. If after the first player's move, the middle row looks like x.x.x.x.x then the second player can move to x.xxx.x.x and there is no 6 of an 7-in-a-row marked so the first player makes the rotated move x.xxxxx.x but now there is 6 of a 7-in-a-row and the second player moves to xxxxxxx.x and wins. $\endgroup$
– Will Sawin
$\begingroup$ @WillSawin You're right, it's not clear. $\endgroup$
$\begingroup$ If I understand correctly, your game is very closely related to Neutral tic tac toe, which I asked about some time ago. $\endgroup$
– Timothy Chow
The case $a=1$ and $c=3$ is known as Treblecross. It is an octal game with code .007 and there is some computational data available on Achim Flammenkamp's webpage, but as far as I know, the game has not been analyzed completely. Given that this case is already difficult, more general values of $a$, $b$, and $c$ are probably going to be difficult as well, but maybe someone can find some parameter values that are tractable to analyze.
The case $a=b=c=3$ was the topic of Neutral tic tac toe, an MO question that I posed back in 2010, although the emphasis of that question was the misère version of the game (completing three-in-a-row loses) rather than the normal form that you are asking about (completing three-in-a-row wins). Thane Plambeck analyzed the misère version and, in a paper with Greg Whitehead, called it Notakto (pronounced "no-tac-toe"), a term that seems to have caught on—it gets a fair number of Google hits. The normal form is probably better referred to as "impartial tic tac toe" rather than "neutral tic tac toe," to conform to standard terminology in combinatorial game theory.
Timothy ChowTimothy Chow
All I have are three small observations.
For all $a,c\in \mathbb N^+$, $(2a,1,2c)$ is a second player win. Player two's winning strategy is to divide the board into adjacent pairs, and to respond with the square paired with player one's last move.
I tried to find a similar pairing strategy for a $(2a,2b,2c)$ board, but failed. In the game where only orthogonal rows count as a win, there is a sort of pairing strategy for the second player: divide the board into $2\times 2$ blocks, and make a winning move if it exists, otherwise respond diagonally opposite in the same block. Unfortunately, this fails when diagonals are wins.
The game $(a,1,3)$ is the octal game 0.11337, which is equivalent to 0.007 with an offset, as Timothy Chow said. That is, when $n\ge 2$, an empty $(n,1,3)$-board is equivalent to a 0.11337-heap of size $n$, which it turn equivalent to a 0.007-heap of size $n-2$ .
Mike EarnestMike Earnest
Game $\ (a\ b\ c)\ :=\ (a\ \ 1\ \ 2\!\cdot\!d)\ $ is won for the 2nd player even that 2nd player doesn't even know the value of $\ d,\ $ i.e. the winning strategy can be exactly the same for the arbitrarily fixed parameter $\ d=1\ 2\ \ldots\ $ (where $\ 2\cdot d\le a$).
(I'm leaving it as a mood-improving exercise; I'll provide a simple solution if it is requested from me).
Wlod AAWlod AA
Not the answer you're looking for? Browse other questions tagged co.combinatorics recreational-mathematics combinatorial-game-theory or ask your own question.
Neutral tic tac toe
Playing an (invertible) matrix game with two players
How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.
A Game of Knights and Queens
Generalized tic-tac-toe
Calculate the probability of winning for a selected tic-tac-toe player
Game on a string
The Sudoku game: Solver-Spoiler variation
Game on a square grid