Tic Tac Toe

[rego]

Hi all!
just wanted to know what i could represent as the training data for the computer to learn to play a game of tic-tac-toe against a human.
cheers!

[anubis]

maybe you could explain a little more how your AI system works ?

[NomadRock]

If you wanted AI to play tic-tac-toe you would just have it check all possible solutions, there aren't many. You can use magic square techniques to speed this up, but on modern computers slow algorithms for this will go faster than the user can click.

[anubis]

better yet... precompute the whole game and save it to disk. the game tree for tic tac toe is very small so you won't have a problem with space

[ShadowHawk]

Well precomputing is not really much of an AI is it. It is more a lookup table. From the formulation of the question i guess that the AI used is some sort of learning AI ( NN or genetic ) for that just make a programm that creates all the game possible states and then trian it with that. It is faster to create a programm for the testdata then to make the testdata yourself.

[rego]

thank you shadowhawk that is what i meant! i will be using the back propagtion algorithm for NNs and ID3 for decision tree learning! :) i would be interested in using genetic learning but im not sure if it can be used for learning to play games!

many thanks!

[ShadowHawk]

Be sure to post your game ( with code ) when it is done so other people can learn from it if they want. At least if u dont object to that. I for 1 would like to know how u solved the issue that a square in the game can be either black-white-open i only made a NN ( as a simple test ) to determine if a player had won or not.

[anubis]

for tic tac toe you would usually use some sort of minimax/negamax algorithm and running that beforehand is as much AI as it is to use it while the game is running. of course it might be far more fun to write a programm that actually learns how to play the game... i guess i just wasn't sure what the intention of the OP was so i suggested the obvious :)

[SnprBoB86]

Anyone ever seen http://www.zillions-of-games.com/ ? very cool stuff

[anubis]

i've heard of it... they have an AI that only knows about the formally stated rules of a game and tries to play by them

[rego]

no problem shadowhawk i will post my game as soon as it is completed! it's gonna be completely made in Prolog!
many thanks!

[rego]

does anyone know which of the following learning algorithms i can use to learn to play tic-tac-toe against a human?

candidate-elimination algorithm
Find-S algorithm
ID3 algorithm
Back-Propagation algorithm
Naive Bayes Classifier
K-Nearest neighbor algorithm
Q-Learning algorithm

I need to use 3 of them for my project!

I was thinking candidate-elimination algorithm, Back-Propagation and Q-Learning but i don't know if these wil work!

Many Thanks

[SnprBoB86]

Tic-Tac-Toe is far too simple to really get a good trial out of any more complex AI techniques. Why don't you pick something a little bit more complicated while stile simplistic in rules such as Reversi or Checkers or some other boardgame? With perfect play, Tic-Tac-Toe is always a draw... it is really quite uninteresting...

[rego]

yeah i know but im already half way into the course and i cant change now - would be too much work!

[NomadRock]

You need to sit down and learn what those algorithms are. Worrying about changing games is the least of your problems. If you understood the techniques you could apply them to any simple game in minutes. Try reading your textbook, and talking with your proffessor.

[rego]

ok thanks