Puzzling Stack Exchange is a question and answer site for those who create, solve, and study puzzles. It only takes a minute to sign up.
Sign up to join this community
A perfect tic-tac-toe AI/algorithm would ideally never lose, but only win or draw, 100% of the time.
Imagine that you play against once such algorithm, and it calculates the next move to make.
Is there an optimal algorithm that can calculate this as fast as is theoretically possible, i.e with the lowest asymptotic complexity?
"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, the game of gomoku (which is a generalization of tic-tac-toe and can be played on boards of different sizes) is what's called PSPACE-complete. That's for the "decision problem" where you ask whether a given position is a win for the first player, for the second player, or neither; if you can solve this then you can find optimal moves about as easily by asking "who wins?" for the position resulting from each of your possible moves, and if you can find optimal moves then you can solve the decision problem about as easily (for games that can't run very long) by playing optimal moves until the game ends and seeing who won. So the optimal-play problem asked about here is also PSPACE-complete (speaking a little fuzzily; strictly speaking this is a term that applies only to decision problems).
This implies in particular that if P=PSPACE (a stronger claim than P=NP, which itself is widely thought unlikely, but no one has proved it impossible) you can find optimal gomoku moves in polynomial time, but if P!=PSPACE (widely thought true, and certainly not proved impossible) then you cannot.
If you had a program that demonstrably found optimal gomoku moves as fast as possible, then either you would have resolved the big scary open problem of whether P=PSPACE, or else you wouldn't be able to figure out the worst-case running time of your program (in which case it wouldn't tell you much about the complexity of the problem).
I personally would guess that finding optimal gomoku moves requires exponential running time as a function of board size, but that is only a guess and for the reasons given above I don't expect anything better than guesswork to be available in the near future. It certainly can't be worse than (singly) exponential.
Link to solution:
Side note
Meaningless characters to bring this post above 30 characters.
