Tic Tac Toe

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 20, 2004 at 12:08

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!

15 Replies

Please log in or register to post a reply.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Nov 20, 2004 at 12:40

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

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 20, 2004 at 14:55

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Nov 20, 2004 at 17:41

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

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 23, 2004 at 07:45

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.

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 23, 2004 at 10:37

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!

51db081cc72925fda1695ce254187b20
0
ShadowHawk 101 Nov 23, 2004 at 11:17

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.

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Nov 23, 2004 at 21:19

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 :)

6e0b32504d31ae07efc17f3322cdb147
0
SnprBoB86 101 Nov 23, 2004 at 21:43

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

F7a4a748ecf664f189bb704a660b3573
0
anubis 101 Nov 24, 2004 at 10:23

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

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 24, 2004 at 11:57

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

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 27, 2004 at 16:24

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

6e0b32504d31ae07efc17f3322cdb147
0
SnprBoB86 101 Nov 27, 2004 at 16:48

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…

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 28, 2004 at 11:53

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

7543b5c50738e23b200e69fe697ea85a
0
NomadRock 101 Nov 28, 2004 at 19:34

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.

Df0edc8d0f85d69e84fcab7c5fabfcb7
0
rego 101 Nov 30, 2004 at 10:50

ok thanks