Well this is my first attempt at actually trying to make a game. I have used C++ for the past 4 years so I'm pretty proficient in coding. So far I have created a text-based tic-tac-toe game that is two players. My next move is to add a single player mode with an AI, and after that make one with graphics. But first, since I have never programmed an AI before I thought I would ask some questions first. Observations about Tic-Tac-Toe: Since everyone has played this game as a kid I'm sure you all know the best way of winning. The first person should take one of the corner spots and the second player has to take the middle spot otherwise the first player will win. If the second player does take the middle spot it is automatically a "cat" game as long as they continue to block off player one. Anyway, my approach to this AI is a decision making binary tree. Basically it would be a series of yes and no questions and it would move right and left depending on the answer. For instance, it would start at whether or not it moved first then move left for yes and right for no. If it moved first it would take one of the corner spots; if the player moved first it would play off where he moved. From there it would continue to play off the player until someone won or it ended in a "cat" game. My question is two fold. One is this the best way to create an AI for this type of game? To me it seems like a lot of code to write a tree that would list all of the possibilities of where the computer should move. Second using the observations above you could create an AI that would either Win or force the “cat” game, but that wouldn't be very fun for the player so how would you create the AI so it too would make mistakes?

There are several ways you can go about this.

For a game as small as tic-tac-toe, programming a tree is fairly easy, especially when you realize there aren't that many combinations, when you account for rotations and flips (there are only three possible first moves, for example).

For a more AI approach, or if you were going to scale the program up to, say, a 4x4 tic tac toe, you could either go with the classic minimax algorithm, or you could go with a rule-based algorithm.

The minimax algorithm is very well studied, and there are dozens of tutorials on the web. It's the standard answer you will get when asking how to program an AI for a two player, rule-based, perfect information, zero sum, such as chess or tic-tac-toe.

A rule-based algorithm would try each position in term, and try to fill the following goals, in order of importance:
1. Complete three in a row.
2. Block their opponent from completing three in a row.
3. Threaten a win with two possible completions in two rows.
4. Avoid a configuration in which the opponent can force the win.
5. Threaten a win with a possible completion (two in a row).
6. Prevent the opponent from getting two in a row.

This will work perfectly in 3x3 tic-tac-toe, but may take too long for much larger boards.

For stupidity: give it a small probability of making an error. If a random generator decides it's time to make an error, don't pick the best move.

TicTacToe is tailor made for a rules based approach.
Since it is usually a programmer's second game (after Hangman/Guess the number)
using a binary tree seems a little like driving in a nail with a sledgehammer.

A complete TicTacToe application with a computer player was my final project in my first VB class years ago.
The basic rules are thus(assuming computer is X):
WinIfYouCan() // search for any combination of 2 X's and one space
else BlockIfYouMust() // search for any combination of 2 O's and one space
else ImplementCustomRule()

You only have to write a custom rule for the first 4 rounds(appoximately) and after that all moves become automatic as the computer is forced to block(just like human vs. human TicTacToe).

You can mix it up a little with some randomization. For example the first move should always go to a corner but if the computer player always goes to the same corner every game will look alike. When multiple moves are equally valid the computer should randomly pick from them.

Re: an intermediate TicTacToe AI
The route I chose was to have the intermediate computer player always make the correct first move on the first turn. Thereafter it would first look to win, then block the other player and if no block was necessary it would move to a random empty square. In other words same as the unbeatable player but only one "custom rule", the first turn. This intermediate player could only be beat by the "two ways to win" trap.

this is severe overkill but you could write a simple AI like Matt Apple said and when it wants to make a move it picks a random move then has the simple AI play itself on that result and if that move results in it winning it makes that move otherwise it picks a different move and repeats.
But like i said at the start OVERKILL

How would that work? I've tried to find an explanation online about using feedback in neuralnetworks but I haven't found ont yet.

Also for a game like tic tac toe, how many hidden layers would be adviseable and how many neurons per hidden layer?

Tic Tac Toe is known as a solved game, officially. That means, if each player moves perfectly, he can force a draw. Since this game is so small and simple, if you wanted to create a perfect AI opponent I would simply store a datalog of all possible board positions and the perfect move to make. If you google for it you can probably find it or you can work it out yourself. Then your AI will never lose, always draw at worst. Although this isn't very fun of course, and might be a bit tedious working for each possible board positions. (You can use symmetry rotations etc to reduce the number of board positions).

If you want to create AI for more complex board games in the future, such as Connect 4, Chess.... then I would highly recommand the minimax approach. Even though it is overkill in this situation, it will be very good practice for future projects. Just google minimax and you'll get tons of resources on it. Although the usual practice is to think a few moves ahead, evaluate the board, and pick the best move so far, this limitation is not really required for Tic Tac Toe. Simply have the computer think moves ahead till the end of the game, which by definition can be 9 turns maximum.

In summary, if you want a perfect AI, use the "hardcore" preprogram every position approach, or if you want to practice for future projects, use minimax. Or perhaps try both? (Well extra practice is good practice!)

Good luck.

Resources:
http://en.wikipedia.org/wiki/Solved_board_games
http://en.wikipedia.org/wiki/Minimax
http://edais.mvps.org/Tutorials/TTTAI/index.html

I know he didn't, but I was just pointing out the fact that it was possible, and that the game is mathmatically *solved*. Asbestos' suggestion of a random chance of error would be a good partner to the now not-so-perfect AI method. And I was pointing out that experiance with minimax will be *invaluable* for more complicated board game types, if that is what he is interested in for the future. If not, then ignore my suggestion :D

i understand the minimax theory but not the code itself. could someone give me the source code for a simple game (tic-tac-toe etc.) an known language will do (i can understand the idea of the code without knowing the language)

thanks

My guess would be that he's aware that the game is a simple draw. Czarkirk, I think your suggestion was already mentioned earlier in the thread.

In case my post was missed, I have a few questions of my own:

If applying a neural network to tic tac toe (to apply a learning approach and practice with neural networks)

how would the neural network look? 27 inputs, 9 outputs, how many hidden layers, and how many neurons per hidden layer?

i know this is a matter of choice, but i was looking for a simple solution that an expert would feel like using.

also, how is feedback applied? i cannot find anything online explaining using feedback. i understand the net is given feedback based on the outcome of the game.. how is this fed through and how does it alter the weights of the synapses.

one more question: is it necessary to tweak any kind of threshold values in this neural network? or should all neurons pass on their value up their synapse to the next layer and ignore the concept of threshold completely (for this application)

hmmm. minimax code....

would this help?