5
$\begingroup$

There is not winning strategy for 9cell 3x3 board. There is a winning strategy for 16cell 4x4 board, or even for 10cell "3x3 + 1_cell_near_a_corner" board (see M.Gardner "Mathematical games"):

$$ \begin{array}{|c|c|} \hline & & & - \\ \hline & & & - \\ \hline \space\space & \space\space & X & \\ \hline \end{array} $$

here "$-$" states for unused cells. "$X$" - for the first winning move.

I wonder is there a board with 9 or less cells where a player has a winning strategy? So the question:

What is the smallest tic-tac-toe board to have a winning strategy for first or second player?

P.S. win means the usual thing: to put 3 signs ("x" or "o") consecutively in a row (horizontally, vertically or diagonally). So one obviously needs at least 5 cells to perform the moves until the winning one.

$\endgroup$
  • 5
    $\begingroup$ A 1 by 1 board? ;) $\endgroup$ – Doorknob Jun 20 '14 at 19:30
  • $\begingroup$ Are you looking for ones that result in 3 in a row? $\endgroup$ – kaine Jun 20 '14 at 19:44
  • $\begingroup$ @kaine, of course! $\endgroup$ – klm123 Jun 20 '14 at 19:46
6
$\begingroup$

6 or fewer cells will never make a board in which either player can force a win.

On a 6 cell board, each player moves exactly thrice. To win, $X$ must pick 3 cells which happen to lie adjacent to each other on a line, meaning that his only chance to win is on move 5. It's a standard strategy-stealing argument to show that $O$ can never force a win on any board (because making a move is always advantageous); either $X$ can force a win or the board is a draw with perfect play.

To be able to win move 5 on a board of any size, he must have at least two potential winning cells after move 3, since $O$ will be able to block one with move 4. But he only has selected two cells after his second move. These two cells determine a line, so both of his winning cells must also be on that line. Hence, he must have picked adjacent cells along the same line.

Now suppose there were only one line of 4 or more cells passing through $X$'s first move. $O$ knows $X$ can only force a win along this line with his second move (if at all). With move 2, she can pick either cell along this line adjacent to move 1. As we've already said, $X$'s only chance with move 3 is to play in the other square adjacent to move 1 along this line. But now $O$ already has one of the (at most) 2 cells $X$ could complete this line with blocked, and she can pick the other one with move 4. So with move 5, $X$ can't win since he's already committed to this line and $O$ has stopped him there.

So now we just have to show that a board with 6 cells or fewer can't possibly have two distinct lines of 4 or more. But this is actually obvious. If it did, by Pidgeonhole principle, those two lines must overlap on at least two cells. But if they overlap on two cells, they're each the line determined by those two cells; hence actually the same line. So 7 cells is required for a board to be a forced win for $X$. The proof also suggests the example given in this answer, which indeed is a forced win for $X$ on move 5. Interestingly, although the board has 7 cells, $X$ still only needs 3 moves to win.


You'll note that the fact that two points on a plane uniquely determine a line was used repeatedly here. This is necessary; it's what tells you that the board is on Euclidean space as opposed to something else. You might ask what happens if we loosen this and allow boards on other sorts of spaces. This isn't exactly a precise question, though there are several ways one can make it precise. If you look at tic-tac-toe on a cube (where the faces are cells), for example, in some sense the "diagonal" lines correspond to picking 3 vertices which meet at a corner. So in fact, any collection of 3 faces of a cube are adjacent along a "line" of some sort. Thus, for either the full cube or a subset of 5 faces, $X$ automatically wins turn 5 regardless of the moves chosen by either player.

$\endgroup$
6
$\begingroup$

What I found up to now is 7 cell board:

$$ \begin{array}{|c|c|} \hline - & & -& -\\ \hline & X & & \\ \hline - & & - & - \\ \hline - & & - & - \\ \hline \end{array} $$

But I do not have prove of minimality.

$\endgroup$
  • 1
    $\begingroup$ I don't understand the downvote. This is a useful answer to the question, even if it is not complete. $\endgroup$ – Ross Millikan Jun 21 '14 at 2:20
  • 1
    $\begingroup$ Proving minimality: Any subset of 3x3 won't work because 3x3 won't work. So your six cells must contain a row of four. Given that constraint, there are few enough ways to arrange them that you can just rule them each out by exhaustion. $\endgroup$ – greg m Jun 21 '14 at 2:47
  • $\begingroup$ That's not quite accurate: There are ways to arrange six cells without a row of four, but that won't fit inside a 3x3 grid. However, they are equivalent to something that will fit in a 3x3 if you look at them in terms of which cells comprise winning triples. $\endgroup$ – greg m Jun 21 '14 at 2:52
  • $\begingroup$ Better: with no row of four, in order to make three rows of three with six cells, three cells must be shared between two rows. You're guaranteed to get one of those on your first turn, and can block the third row on your second. $\endgroup$ – greg m Jun 21 '14 at 2:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.