Although it is impossible to win every game of tic-tac-toe, is it possible to never lose? Is there a specific placement or strategy for the game?
[Math] Is it possible to never lose in tic-tac-toe
game theorytic tac toe
Related Solutions
The first question, if there is a non-losing strategy, I have an answer for: Yes.
Since this is a finite two-person perfect information game without chance, at least one player must have a non-losing strategy, guaranteed by Zermelo's theorem (of game theory).
For Tic-Tac-Toe related games, it can be proven that the first player has this non-losing strategy. (If it is a winning strategy depends on whether or not the second player has a non-losing strategy).
The argument goes something like this (Player 1 = $P_1$, Player 2 = $P_2$): Suppose there is a non-losing strategy $S$ for $P_2$. Then $P_1$ will start the game with a random move $X$, and for whatever $P_2$ will do, follow strategy $S$ (thus $P_1$ takes on the role of being the second player). Since $S$ is a non-losing strategy, $P_1$ will not lose, which means $S$ is a non-losing strategy for $P_1$.
Note that, if strategy $S$ ever calls for making the move $X$ (which was the original random move), $P_1$ may simply do another random move $X_2$ and then keep following $S$ as if $X_2$ had been the original random move. This is further explained in page 12-13 here.
(EDIT: Since the first move $P_1$ affects what move $P_2$ can do (by rule 2) the latter argument may not apply to this game. Anyone?)
Let us re-interpret the tic-tac-toe game in terms of edge coloring for two associated graphs.
Note that there are $12$ total ways to win on the torus. There are $3$ horizontal lines and $3$ vertical lines. Analogously, there are $3$ diagonal lines and $3$ anti-diagonal lines. Each horizontal/vertical line pair uniquely determines a cell through their intersection. Conversely each cell belongs to precisely one such pair. The same holds for the diagonal/anti-diagonal pairs.
Let there be $6$ vertices on our first graph, one for each vertical/horizontal line. Join each vertical vertex to each horizontal vertex. The result is the complete bipartite graph $K_{3,3}$ where each edge corresponds to a cell on the playing grid. Construct the second graph through the same procedure for diagonal/anti-diagonal lines.
Now the game can be interpreted as $2$-coloring the edges of the graphs (where each move colors an edge on both graphs). Winning the game corresponds to saturating a vertex on one of the two graphs with edges of the same color. The key is now to note the following two facts:
If there exists a perfect matching with edges of the same color on one graph, then this necessarily implies the existence of a vertex saturated with the same color on the other graph.
If every vertex of $K_{3,3}$ is adjacent to edges of both color then there necessarily exists a perfect matching with edges of the same color.
It's not very difficult to prove the above two facts and I will not do so here (although the proof I have still requires a bit of case-checking, if anyone has an elegant proof of the two facts above, please share it with me). The overall interpretation here is that the game on the torus brings in a duality between vertical/horizontal wins and diagonal/anti-diagonal wins. Not winning one way forces a win the other way.
Best Answer
Yes. Here is a link explaining the whole thing: https://blog.ostermiller.org/tic-tac-toe-strategy.