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.
Answer
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.
No comments:
Post a Comment