What Kind of AI does Tic Tac Toe use? Thanks.

a very simple kind :-)

Tic Tac Toe can be done with several types of AI:

The Dumb AI: Random Selection
The Smart AI: Some kind of game branching mechinism

For the dumb AI it''s real simple, just randomly select an unoccupied square.

For the smart AI you need to create a tree of every possible move. This can be done easily with a recursive function and wouldn''t be much of a memory problem because a Tic-Tac-Toe tree is rather small.

All in all the smart AI for Tic-Tac-Toe isn''t much more than a greatly simplified chess AI, which a quick google search should turn up a ton of resources on.

-SniperBoB-

You really need to go to the Articles & Resources link at the top of this page. Then click on the AI section on the right. You will find links to tons of articles. Read away, son!

Dave Mark
President and Lead Designer
Intrinsic Algorithm Development
"Reducing the world to mathematical equations!"

the smart AI that is decribed below sounds sort of like mini max which is a good way of playing tic tac toe. Just one word of warning due to the nature of the game a AI using mini max will genrally draw rather than win, this is because it is impossable to win if ur oponent makes the correct move, which mini max assumes when it works out its next move.

The best AI will cheat by making loud scary noises coming from the speakers attempting to distract the opponent''s attention momentarily, thus giving the AI the chance to erase one or more of the opponent''s marks, decreasing the odds of a tie.

I wrote a AI for a TTT, but for 10*10 squares and 4 in a row wins.


The AI is based on prioritys;
That means: Every square gets analysed and then gets points.
Then the AI chooses the one with the highest priority(means: with the most points).

Do you use search at all to prioritise your squares? or do you just run your evaluation function on a single move''s distance (ie. minimax with a depth 2 (including root) limit)?

Building a tree of anything is probably not worth the effort.

1. Check if you can win in one shot
2. Check if your opponent can win in one shot and block

After that, there really aren''t many combinations left and you can check them manually.

Cédric

With 10*10 squares i''d say there are a lot of combinations left. Also not being able to look into the future is going to end up with a very easy to beat AI.

Rule 3. Take the middle square if it is vacant.
After this there are a small number of exceptional cases.

In my physics project group we played with four players on a large grid. It gets terribly funny once everyone works out the best strategy.