47

Tic-tac-toe has been solved. The optimal first move is to go in the corner. As always, there is a relevant xkcd.


31

The first move can be made anywhere without sacrificing the game. If the opponent plays perfectly, any first move leads to a draw. However, if the opponent does not play perfectly, then the optimal place to go is the corner, since that leaves only one spot (the center) for the opponent to go to get a draw, increasing their chance of making a mistake.


29

The first player can always force a win. I wrote this Python script to analyze the tree of possible game states reachable from an empty starting board. No matter what the second player does, the first player can make a move that eventually leads to a win in ten moves or less. I took the tree and trimmed it down to only the optimal moves for the first ...


24

Yes, X can win. To simplify things I'm going to take advantage of your rules that O cannot win, so that X doesn't need to worry about O getting 1000 in a row. Just consider a 1 dimensional game, chose an origin, and label the locations with integers in order. Define the "bin $K$" as the set of spaces $x$ such that $1000\ K \le x < 1000 (K+1)$. A ...


14

Solution Step-by-step deduction If A plays first, then Proof: the crucial realisation is that B can always force A to play in a specific square. WLOG, say A's first move is an $X$. If A's first move is in a corner (WLOG, an $X$), B plays as follows: where the ? marks denote the positions of A's subsequent forced moves (each of which can be either an $X$ ...


13

The answer is no, no one can force a win. Suppose Niels goes first. Henrik can stop Niels from winning as follows: whenever Niels goes in a triangle, Henrik goes in the corresponding coloured triangle: Any 4 in a row must go over a pair of coloured triangles, so Niels cannot win. Now suppose Henrik can force a win. Then Niels steals Henrik's strategy and ...


12

X plays, O plays, X plays as follows: X O X We're now locked on this plane, albeit not uniquely (the O can be in the central or rightmost column). Either way, O is forced: X O O X And now X can uniquely define the board and force a double threat, and thus a win: X O O X X


11

Solution: Explanation: I noticed that there are only ${9\choose5 }= 126$ ways for the $X$ to play a game. I noticed that only $28$ of these would not represent a win for $X$ I then noticed that of the $28$ some may be a win for $O$. It turns out that after removing those which would be a win for $O$ there are $16$ left. i.e. $(\mbox{all games for X}) \...


8

If you're first: Go in a corner. If you're second, and the first person went in a corner: Go in the middle. From both of these positions, it is possible to guarantee no worse than a tie.


6

Alice wins. She starts by playing in the center square of the center board (which we'll call board C). Bob sends Alice over to another board, and she plays in the center of that one. Eventually, Bob fills up the rest of the middle board, and Alice then has the center of all but one of the outer boards. On that turn, Alice takes the "self-square" of the ...


6

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


6

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.


6

A wins if $n=2$: No matter what B plays on their first turn, there will be a flat plane passing through the first X, which contains at most one O. A can create a 2 by 2 square on that plane while forcing all of B's moves to block both ends of a 2-in-a-row, and then complete a row of 3. B draws if $n=3$: Divide the entire grid into 2x2x2 cubes. Every cell ...


5

Note: the contents of this answer are not actually correct; however, I've been asked to undelete this because it contains content that might be useful. I'm still trying to work through what I missed, but in essence, I think it comes down to the assumption that Red plays pieces that are adjacent to existing pieces, or do not otherwise interfere with them. I'...


5

Here's an easy "intuitive" explanation how X can win: If X can get a 998 in a row and it's her turn, she has won. So, if she can get TWO 998s in a row, and it's Os turn, she has won. {O will only be able to cover one - so it's over} So, if she can get FOUR 997s in a row, and it's O's turn, she has won. (O will only be able to cover ..two times.., so ...


3

The best move that player o can make each turn is to "cap" the currently longest line, i.e. placing an "o" at each endpoint of the current longest line. From there, the longest chain that player x can make is just the degrees of freedom in the lattice space, with degrees of freedom referring to the number of positive directions that a chain can be built in. ...


3

There is a nice article analyzing the Tic Tac Toe first move strategy at https://paperandpencilgames.com/2019/02/tic-tac-toe-strategy-tutorial.html To address the reviewers comments, here is the conclusion of the article. There is no way of winning against a "perfect player". Choosing a corner as the first move gives you the best chance of winning against a ...


3

"Asymptotic complexity" is a notion that only makes sense when you have some notion of "problem size" that can increase to infinity. The game of tic-tac-toe is always played on a 3x3 board and never takes longer than 9 moves. There is nothing to increase to infinity and no sense in asking about the asymptotic complexity of anything to do with it. However, ...


2

Yes, as long as I didn't interpret you wrong, I believe that player 1 has a forced win: Diagram: Diagram explantion and reasoning: 2. 3. 4.


2

Here is one possible move sequence with nine moves: BbFfGiJfHhGgFhGhIh The program seems to prioritize threats and then surround if none are available. By shooting one of your red blocks in the leg and leaving him in the corner, it lets you set up without hindrance. The strategy is to create a series of forced moves in spaces that needn't be occupied ...


2

Answer incomplete. This should probably be finished by a computer search, but I don't know how to do it efficiently enough. The ideas here may help some with efficiency. There are three possible tic-tac-toe draw configurations, up to rotation and reflection: A B C o x x x o x x o x x x o o o x x o x o o x x x o o ...


2

I don't know the answer exactly, but roughly speaking it should scale with $N$. Suppose the answer is a line of length $n$, and suppose that the O player is able to contain the X player in a hypercube with side of length $n$. Then the X player will have placed $n^N$ X's. The O player will have surrounded the hypercube on all sides, which requires $2Nn^{...


2

I don't know solution for any N, but may be investigation of more general problem can be helpful. Let's say we have N dimensional space and for each X turn O has M turns. Call the result (max length for X) - L(N,M). Here I call players - X and O, and their marks - x and o. Then: L(1,2+) = 1. Obvious. L(1,1) = 2. This one is more interesting. Let's prove ...


1

There can't be a draw because if the board is full, either you can move the board and get new places to play, or you can't because all positions you can go where already used, and you lose. So the game always ends with a win for first or second player. So, as it is a finite two players game with no draw, there is exactly one player that has a winning ...


Only top voted, non community-wiki answers of a minimum length are eligible