Tic-Tac-Toe
Author
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?
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.
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.
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
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
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!
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!
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.
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.
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
But like i said at the start OVERKILL
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.
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?
Also for a game like tic tac toe, how many hidden layers would be adviseable and how many neurons per hidden layer?
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
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
