I'm interested in AI as an area to study on in MSc. I don't have much prior knowledge. So, I decided to develop an AI that plays Tic-Tac-Toe perfectly, as an introduction. I've made some progress that AI can make or block "win" and "fork" positions. "Fork" is a position that a mark ( X or O ) creates two one-move-to-win position at once. If opponent can't make another one-move-to-win position himself, forking player has a certain win. "Fork" position requires to calculate two moves after. And I suggest a "Double Fork" position which requires to calculate three moves after. I've done this by analyzing game combinatorics, generating "win" and "fork" patterns, and applying algorithm below:

1 - Win
2 - If can't win, block opponent's win
3 - Fork
4 - If can't fork, block opponents fork
5 - Play random

Obviously that is not a perfect-playing method. I've noticed there exists more complex positions by further analyzing game combinatorics. These positions are, as I name them, "win and fork" and "double fork".

It seemed to me that it is inefficiently complex to handle these further positions. I want you to inform me whether I haven't analyzed game combinatorics completely or I should use other methods like using game state space tree.


  • 4
    $\begingroup$ This is not a research level question and thus does not belong here. If you want a hint, pick a different problem for your MSc than this. This problem is trivial as you could even manually write down every possible game play in a tree. This game is decided and there is no winning strategy. $\endgroup$
    – Pål GD
    Jan 12 '13 at 14:18
  • 3
    $\begingroup$ @PålGD This is only true of the standard Tic-Tac-Toe game. It's generalisations, e.g. 3-dimensional 5x5x5 suffer from massive combinatorial explosions ruling out brute force approaches. In fact of all $n^d$ Tic-Tac-Toe games only two have been solved: $3^3$ and $4^3$. So if the original poster is willing to look at generalisations of Tic-Tac-Toe, there is lot's of interesting work to be done. $\endgroup$ Jan 12 '13 at 21:20
  • 2
    $\begingroup$ Second what @MartinBerger said. There are interesting generalizations of Tic-Tac-Toe, like misère X-only tic-tac-toe and its disjunctive variant (a.k.a. Notakto), whose combinatorics is research level (not to mention its AI would be far from trivial). See this excellent summary. $\endgroup$
    – siuman
    Jan 13 '13 at 13:22
  • $\begingroup$ @PålGD I frankly respond that my question is about standard Tic-Tac-Toe. And I can agree that this is not a research-level question because of the game is completely resolved. But I want to mention that there exists 255,168 possible Tic-Tac-Toe games. Generating all these variations exhaustively would be useless for such an easy game. Actually, I wanted to ask, whether it is possible to make the game played perfectly without by generating game state space tree but by analyzing positions such as "double fork" and "fork and win" . And I'm figuring things out by myself. $\endgroup$
    – oak
    Jan 14 '13 at 19:51
  • 1
    $\begingroup$ Welcome to cstheory, a Q&A site for research-level questions in theoretical computer science (TCS). Your question does not appear to be a research-level question in TCS. Please see the FAQ for more information on what is meant by this. Your question might be suitable for Computer Science which has a broader scope or for Stack Overflow. $\endgroup$
    – Kaveh
    Jan 15 '13 at 19:08

See Tic-Tac-Toe by Randall Munroe. enter image description here


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