Possible Duplicate:
What Algorithm for a Tic-Tac-Toe Game Can I Use To Determine the “Best Move” for the AI?
I have already created a tic tac toe game for 2 players i.e. playing against each other. Now i have planned to implement the same game but for playing against computer. So can anyone suggest some nice algorithm or idea to implement that?
Since the game is so simple, you can do a search tree. This is a tree which alternatives between "your move" and "enemy move". The enemy is always picking what is best for them, and you are always picking what is best for you. For each board position, rate it as "WINS"/"LOSE"/"TIE" if optimal play results in a win/lose/tie, respectively. Perform a depth-first search (or any search) and pick the branch. This is basically how the complicated chess programs which beat grandmasters work (albeit they are highly optimized and are running on excellent hardware in parallel). This is known as the minimax algorithm.
Alternatively, you can code all the optimal moves by-hand (with a routine which compares it against known moves by rotating and flipping the board). There are only 500-ish possibilities.
However since tic-tac-toe is a solved game, it would be fairly boring. The computer will always tie you, if the computer plays optimally. Since tic-tac-toe is only challenging to 5-year-olds, you might consider the audience of your game: it may be reasonable to have the computer make a random non-losing move. Then the human player at least has a chance.
A search tree, like ninjagecko has already suggested, would be straightforward and optimal to code up.
But just as making a search tree is more interesting than coding all of the optimal moves by hand, I think it would be even more interesting to try a machine learning approach.
It would be cool to make a program that used reinforcement learning, for example.
