# TicTacToe AI

• 05-27-2007
Loic
TicTacToe AI
I’m making my first little game and I have gotten up to the part where I am trying to work out how I am going to do the AI, as I am new to this im not to sure how to go about it… the best way that I can think of would be to use quite a few if statements to determine where the “cpu” will go next…

Eg:
Code:

`if (pos[0][0] && pos[0][1] == 'X') {pos[0][2] = 'O';}`
Where pos[0][0] is row “0” column “0”

Is that the best way to create “AI” for a tictactoe game? Or is there a better more effect method?
• 05-27-2007
Desolation
• 05-27-2007
Junior89
You gotta minimax it, and it's tricky for a new programmer, i've been at this for years and (well this just goes to show i suck =P) still havent gotten it completely down.
• 05-28-2007
Loic
Quote:

Originally Posted by Junior89
You gotta minimax it, and it's tricky for a new programmer, i've been at this for years and (well this just goes to show i suck =P) still havent gotten it completely down.

Yeah, i am just going through that wikipedia page on it... just a little bit lost.. hahaha

But hopefully i can find something broken down a little more / more in depth...
• 05-28-2007
Junior89
It's tricky, it consists of creating a tree (minimax tree) of Every possible move one can make with every possible move leading from there, etc. etc.

If you have experience with Linked Lists, and Binary Trees specifically, what you're going to do is learn that first, and learn it very well. Then you basically take a binary tree but instead of each leaf having 2 nodes, each has however many possible moves exist. Obviously writing the tree itself by hand would be tricky, so you need an algorithm to create the tree in the program, than a form of a minimax algorithm to judge and sort the tree as the game is played, determining the best move as you go along.

One would assume such a simple game would be easy, ha, it isn't such a piece of cake however.

Good luck!
• 05-28-2007
cakey
• 05-28-2007
tomcant
I posted in a thread here not so long ago. I basically explain how to get a variation of the minimax algorithm up and running. This variation is called AlphaBeta and produces exactly the same output as minimax, but in a much faster time. If you have any particular problems with the code, just ask. Good luck! :)
• 05-28-2007
Perspective
Tic tac toe is a solved game, you don't actually need a minimax tree, you can precompute everything and just look up your next move in a table.
• 05-28-2007
tomcant
Quote:

Originally Posted by Perspective
Tic tac toe is a solved game, you don't actually need a minimax tree, you can precompute everything and just look up your next move in a table.

And how are you going to compute that information? A minimax tree perhaps? :)
• 05-28-2007
Perspective
so long as you don't do any pruning you could use a tree method, otherwise I could make your AI vomit by making a non-optimal move. The alternative is just exhaustive enumeration of board states, TTT is relatively small. You can also exploit symetries to make it even smaller.