• Advertisement
Sign in to follow this  

Tic-Tac-Toe

This topic is 4149 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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?

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
that would work but an altermative to the tree is to use the min-max algorithm (search on google for it), also search these forums for tic-tac-toe because this type of question has been asked alot recently.

As for making it make mistakes there are a number of ways for example in min-max you could add a small random number to the fitness so the AI doesnt always chose the best solution

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
damn u beat me lol

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
The Tree for TicTacTo is so Small though, why bother wasting time recalculating it every turn via minimax?



If you want a AI that can make mistakes how about this:

for each given position, there is a row,col, and sometimes diagonal that it affects. These are called 'neighborhoods'.
some examples:
(*,O,X)
(O,_,*) *star is the proposed move location...
etc...
You can make a table of all possible neightborhoods, (its not that bad) keep in mind that they are symmetrical back and forwards, and rows and cols are the same thing.
When the player moves, record what neighborhoods his move has created, and add points tho those locations in your table.
When it's your turn to move, for each open square on the board, look at the neighborhoods each one would create, then assign a point value to that square based on the values of its neighborhoods from your table.
To choose your move, don't just take the highest value sqauare, but Randomly choose, using probability weighted by value.

Since your table starts out empty, the first game the AI will be very dumb and play randomly. But each game, its table will bet bigger, and it will get 'smarter'...
It's basically learning by imitation...

P.S. when adding neighborhoods to the table, remember, its not the symbols X and O that matter, but instead it is which player had what symbol -varies between games, so be careful with how to represent it!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Whilst we're on the subject of complete overkill on Tic Tac Toe, you could also write a Neural Network to 'learn' to play... Give it nine inputs for the board squares (perhaps a +1 and -1 for 'your piece' and 'their piece'), nine outputs, and take the highest which is valid as the move. Assign feedback based on whether the game is won or lost, and how quickly it ended.

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
No,
He's already said that he doesn't want a perfect AI that wins all the time
hence the roundabout suggestions that are neither dictionary lists nor minimax

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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)

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova

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


Why 27 inputs? I think you could do the same or better with just 9, with the states -1, 0 and 1. If that doesn't work, I'd go for 18, though, as having 9 neurons for "empty" is redundant, and will probably slow down your learning.

With almost all problems of this sort, where you're not trying to, say, create a cognitive model, or have some plan for what the different hidden layers ought to represent, you can do with just one hidden layer. Actually, all functions can be mapped by a three-layer ANN, although sometimes it's not worth it.

The number of hidden neurons is your own preference. I'd go for an hourglass-shaped network, to encourage generalization, so would have four or five hiddens.

Also, I'd help the network out a little bit by doing all the rotations for it. If someone started in the corner, I rotate the board so the network always saw a corner opening as the same opening. This is something we do in our heads, and a ANN could probably get, eventually, but it's nice to help it out. This changes 9x8x7... possible states into 3x5x... state tree.

Quote:

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.

Personally, I'd go for a GA here. Looking online, it seems quite a few other people have come up with the same conclusion. Alternatively, you could create a table of the best move in every situation, and apply backprop. However, this requires you to work out the best move each time, which rather defeats the purpose.

Quote:
Original post by Moon 111
id like a full source please...

The link above you wasn't enough? I think the source code there was pretty good. Work through that and try to understand it.

Share this post


Link to post
Share on other sites
The thing is I don't want to use a GA. I have another project which is applying GA quite nicely. I just want to learn how to apply back propogation. I've looked online and most sources give a vague explanation of how to do it but I'm trying to find specifics.

Let me give you an example and if you would be so kind as to tell me step by step how to apply back propogation, it would solve my dilemna completely.

I'll make this small so it won't be a pain in the butt:

3 layers
2 inputs(I1, I2), 3 hiddens(H1, H2, H3), 2 outputs(O1, O2)

so we have 12 weighted synapses given arbitrary values:

I1->H1 = .2
I1->H2 = .3
I1->H3 = .4
I2->H1 = .5
I2->H2 = .6
I2->H3 = .1
H1->O1 = .7
H1->O2 = .3
H2->O1 = .4
H2->O2 = .25
H3->O1 = .45
H3->O2 = .05

now let's say our inputs were .5 and .25

H1 = .225
H2 = .3
H3 = .225

O1 = .37875
O2 = .15375

let's say my desired outputs were..
O1 = .45
O2 = .05


how would I apply back propogation to evolve this network?

Share this post


Link to post
Share on other sites
heres some source code for back-propagation hope it helps

http://cortex.snowseed.com/neural_networks.htm

also i have a pdf on nueralnets and backpropagation wich covers alot of the math if u want me to email it to you.

Share this post


Link to post
Share on other sites
Quote:
Original post by sharpnova
I just want to learn how to apply back propogation. I've looked online and most sources give a vague explanation of how to do it but I'm trying to find specifics.


The simplest tutorial by far that I've found on backprop is at www.cs.ucc.ie/~dgb/courses/ai/notes/notes9.pdf. The first two pages are sufficient to code the algorithm, but he also has source-code and an example.

Note something that's confusing for beginers learning backprop: the backprop algorithm uses a function, g'(x), that depends on the activation function you have chosen. This function will be different for different activation functions. The function he gives in this tutorial is only if your activation function is the sigmoid function (which is handy, as sigmoid is probably the only function you'll need for a long time).

I still don't think tic-tac-toe is a good scenario for learning backprop, however. It should work fine for your mini-problem, though.

Share this post


Link to post
Share on other sites
To use backpropagation without having to determine the "right" move each time, you need to play the games to the end, then "credit" the moves which contributed to a win. This is the technique that was used very successfully for backgammon (search for TD-Gammon). I suspect the details of how to implement Temporal Difference learning are tricky, but it should be possible to learn with Tic-tac-toe.

This book is an academic treatment of the whole area:
http://www.cs.ualberta.ca/%7Esutton/book/ebook/the-book.html

Share this post


Link to post
Share on other sites
An actor/critic machine-learning approach would satisfy everything you want in such simple games.

Even without rotations, there are only 3^9 possible game positions (some of which arent legal) and at most 9 possible choices. Simply put, you dont have to do any generalization of any kind and can self-play to perfection in a few milliseconds at most.

Imperfect play is built right into most actor/critic models in the form of occasionally choosing a random move (used to explore alternatives to what is currently considered best)

Share this post


Link to post
Share on other sites
I used this AI struct for my tictac toe, its intelligent, is difficult to beat, but can be beaten.

1. If the computer can win on this move, make that move.
2. if the human can win on his next move, block it.
3. Otherwise, take the best remaining open square. The best square is the center. The next best squares are the corners, and then the rest of the squares.

If you want you can spice up 3 a bit and have it try to do opposite corner's, or even better add in a small (about 30%) chance the computer will not take the "next best" move but the "secondbest" place.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement