<p>See <a href="http://xkcd.com/832/" rel="nofollow noreferrer">Tic-Tac-Toe</a>  by Randall Munroe. 
<img src="https://i.sstatic.net/myes0.png" alt="enter image description here"></p>

CC BY-SA 3.0
2013-01-12T20:40:13.777Z
2013-01-12T20:40:13.777Z
Vijay D
<p>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:</p>

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

<p>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".</p>

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

<p>Thanks.</p>

CC BY-SA 3.0
2013-01-12T14:18:11.793Z
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.
John K.
CC BY-SA 3.0
2013-01-12T21:20:52.410Z
@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.
Martin Berger
CC BY-SA 3.0
2013-01-13T13:22:50.510Z
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](https://plus.google.com/u/0/101584889282878921052/posts/gt37jDDS8CN).
siuman
CC BY-SA 3.0
2013-01-14T19:51:36.027Z
@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.
deepend0
CC BY-SA 3.0
2013-01-15T19:08:01.597Z
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 [cs.se] which has a broader scope or for [SO].
Kaveh
CC BY-SA 3.0
2013-01-16T09:20:11.523Z
@user6994 Though the question is closed, I wonder if you could at least clean up the question to add what you meant by block and fork. Mainly because I'm curious.
Vijay D
CC BY-SA 3.0
2013-01-17T21:29:28.737Z
@VijayD "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. If you're interested, I may give more details about further positions that I propose.
deepend0
<co.combinatorics><ai.artificial-intel><gt.game-theory><board-games>
Developing A Perfect Tic-Tac-Toe Player - AI
deepend0
# Developing A Perfect Tic-Tac-Toe Player - AI

(Asked by: username_0 on 2013-01-12)

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.

Thanks.

**Tags:** co.combinatorics, ai.artificial-intel, gt.game-theory, board-games
> **Comments:**
> **username_1**: 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.  
> **username_2**: @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.  
> **username_3**: 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](https://plus.google.com/u/0/101584889282878921052/posts/gt37jDDS8CN).  
> **username_0**: @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.  
> **username_4**: 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 [cs.se] which has a broader scope or for [SO].  
> **username_5**: @user6994 Though the question is closed, I wonder if you could at least clean up the question to add what you meant by block and fork. Mainly because I'm curious.  
> **username_0**: @VijayD "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. If you're interested, I may give more details about further positions that I propose.  

---

## 1 answers

### Answer by username_5 on 2013-01-12. Score: 9

See [Tic-Tac-Toe](http://xkcd.com/832/) by Randall Munroe.
![enter image description here](https://i.sstatic.net/myes0.png)


---

