18
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\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
    Commented Mar 14, 2021 at 15:13
  • 3
    $\begingroup$ @LSpice $c$ is also a parameter of the game, and may be less than $\max(a,b)$. $\endgroup$
    – pi66
    Commented Mar 14, 2021 at 16:05
  • 6
    $\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
    Commented Mar 14, 2021 at 16:22
  • $\begingroup$ @WillSawin You're right, it's not clear. $\endgroup$
    – pi66
    Commented Mar 15, 2021 at 0:24
  • 1
    $\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
    Commented Mar 15, 2021 at 1:44

3 Answers 3

Reset to default
13
$\begingroup$

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.

Improve this answer
$\endgroup$
0
4
$\begingroup$

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$ .

Improve this answer
$\endgroup$
0
$\begingroup$

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).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .