Alexiyies
asked on
Making a game of Tic Tac Toe, with a computer player....
First, I know I can use a 2 dimensional array to set the 9 "sectors" of the board. For two players, this wouldn't be neccessarily extremely difficult, I have obtained source for a two player game of Tic Tac Toe.
However, I want to make a game which has a computer opponenet. Obviously, in Tic Tac Toe, if both players know the strategy to it, it will always be a tie. I want to make some sort of logic for the computer to follow, so it can do the same.
My initial idea was to assign each square a number from 1 to 9. Thus, 1+2+3 is a winner, 1+5+9 is a winner, and so on. However, this conflicts because there are four different ways to get 15 as a solution.
I am looking for some help for this. If anyone either has source, or can offer help for the type of logic the Computer could use, it will be accepted as an answer if it works.
However, I want to make a game which has a computer opponenet. Obviously, in Tic Tac Toe, if both players know the strategy to it, it will always be a tie. I want to make some sort of logic for the computer to follow, so it can do the same.
My initial idea was to assign each square a number from 1 to 9. Thus, 1+2+3 is a winner, 1+5+9 is a winner, and so on. However, this conflicts because there are four different ways to get 15 as a solution.
I am looking for some help for this. If anyone either has source, or can offer help for the type of logic the Computer could use, it will be accepted as an answer if it works.
Well, Tic Tac Toe is a very poor example, because a computer can too easily allways win.
If you had in mind doing a game like Othello, you'd conceive your code in a different way.
The global method is often called 'games strategy method' and is a kind of AI.
You have to build during execution a tree, where each node is a status of the game.
The tree is calculated by the program each time it plays (if it is a computer opponent). You don't have to build the tree if the opponent is a human one.
The first level of the tree is the choice of the first player.
The second level of the tree contains all the choices the second player can make (in correspondance with the choice of the first player).
The third level contains the choices of the first player, after the last 2 rounds.
And so on.
Now, for a simple game like Tic Tac Toe, a current PC can easily calculate the entire gaming tree.
So he knows what choices are best for him and worse for the opponent. And so he plays by allways choosing the worse path (through the tree) for the opponent.
Beware: a good program never chooses the best choice for him at one moment, but the worse for the opponent.
If you had in mind doing a game like Othello, you'd conceive your code in a different way.
The global method is often called 'games strategy method' and is a kind of AI.
You have to build during execution a tree, where each node is a status of the game.
The tree is calculated by the program each time it plays (if it is a computer opponent). You don't have to build the tree if the opponent is a human one.
The first level of the tree is the choice of the first player.
The second level of the tree contains all the choices the second player can make (in correspondance with the choice of the first player).
The third level contains the choices of the first player, after the last 2 rounds.
And so on.
Now, for a simple game like Tic Tac Toe, a current PC can easily calculate the entire gaming tree.
So he knows what choices are best for him and worse for the opponent. And so he plays by allways choosing the worse path (through the tree) for the opponent.
Beware: a good program never chooses the best choice for him at one moment, but the worse for the opponent.
Well, I'd like to add a few things to my answer:
- it is better to use the strategy as I described than the one you or ozo proposed, because the method I explained works for all kind of games (where 2 players play and where luck is not a factor to win or loose.
The strategy you proposed only works for a simple game like Tic Tac Toe and the code cannot be reused for a more complex game.
- With other games than Tic Tac Toe, it is often the case that the computer cannot calculate the entire gaming tree (or it would take too much time).
So it has to stop the calculation at a given tree depth.
Then, there are a few methods (like A star, written A*) that can optimize the treatment.
But first, try with a simple gaming tree.
- it is better to use the strategy as I described than the one you or ozo proposed, because the method I explained works for all kind of games (where 2 players play and where luck is not a factor to win or loose.
The strategy you proposed only works for a simple game like Tic Tac Toe and the code cannot be reused for a more complex game.
- With other games than Tic Tac Toe, it is often the case that the computer cannot calculate the entire gaming tree (or it would take too much time).
So it has to stop the calculation at a given tree depth.
Then, there are a few methods (like A star, written A*) that can optimize the treatment.
But first, try with a simple gaming tree.
Take a look at :
http://www.xs4all.nl/~verhelst/chess/search.html#minimax
where tree search methods are explained.
The example is a chess game, but as I said above, the advantages of using tree search are that they are reusable for different games.
Sure, you have to change things, like all the heuristics, but the principle is mainly the same.
http://www.xs4all.nl/~verhelst/chess/search.html#minimax
where tree search methods are explained.
The example is a chess game, but as I said above, the advantages of using tree search are that they are reusable for different games.
Sure, you have to change things, like all the heuristics, but the principle is mainly the same.
here is a website that has tic tac toe, with the source code. That should give you all the logic you need.
http://www.jaked.org/ttt.html
thanks!
http://www.jaked.org/ttt.html
thanks!
here is a website that has tic tac toe, with the source code. That should give you all the logic you need.
http://www.jaked.org/ttt.html
thanks!
http://www.jaked.org/ttt.html
thanks!
ASKER
Tic Tac Toe is rather absurd, because the strategy is to take the center, and if you're '0', and X took the center, you take a corner. The computer opponent above isn't 'hard' or 'easy'. On easy, it just purposely makes dumb moves. On hard, you will always tie it.
What I meant with 15, was that my initial idea was to have every winning combination (8 in all) add up to a different number, then I could have the computer find what number it needs to complete it's sequence. However, it won't work.
What I DON'T want to do is to program every possible playing position. I'm trying to make some kind of thought process.
mCon, do you have any idea what the logic of the source you posted is? I'm having some trouble understanding how it works.
What I meant with 15, was that my initial idea was to have every winning combination (8 in all) add up to a different number, then I could have the computer find what number it needs to complete it's sequence. However, it won't work.
What I DON'T want to do is to program every possible playing position. I'm trying to make some kind of thought process.
mCon, do you have any idea what the logic of the source you posted is? I'm having some trouble understanding how it works.
The code at jaked.org uses the treesearch strategy that Deckmeister described. And it really is the best known strategy for attacking problems of this kind. Given enough horsepower it has accomplished remarkable things. A program of this type is the undisputed wordchampion in checkers, and in chess, such a program has occasionally beaten a grandmaster.
I would also contend that the gametree type of progress is a big part of how I think when playing chess, or even tic tac toe. (If I do this, then he can these things for which I would have the following replies etc. etc.).
However, this is an excersize, and there are other ways of approaching the problem (inferior though they may be for gameplaying perse).
In the tic tac toe game, you could label your squares with coordinates:
0,0 | 1,0 | 2,0
--------------------------
0,1 | 1,1 | 2,1
--------------------------
0,2 | 1,2 | 2,2
Now if you consider any two placed "pieces" you can create a "vector" by subtracting their coordinates:
Suppose there is a piece on 0,0 and 1,1; then the vector would be 1,1.
Now add this vector to the position of the second piece and you get 2,2, which is where you want the third piece to go.
If the two pieces were on 0,1 and 1,1 the vector would be 1,0, and the winning position (1,1)+(1,0)=(2,1).
Note that you either have to order the pieces somehow, or try adding and subtracting and checking if you are still on the grid. (What if the two pieces are 1,0 and 2,0 for instance?)
Note also, that you have to worry about whether there is already a piece there or not, about all other possible two piece combinations, and, if you can't play a winning move, whether your opponent might be able to, so that you can foil it.
I have to say again that all of that complexity can be taken care of with a centralized board evaluator and a game tree.
I would also contend that the gametree type of progress is a big part of how I think when playing chess, or even tic tac toe. (If I do this, then he can these things for which I would have the following replies etc. etc.).
However, this is an excersize, and there are other ways of approaching the problem (inferior though they may be for gameplaying perse).
In the tic tac toe game, you could label your squares with coordinates:
0,0 | 1,0 | 2,0
--------------------------
0,1 | 1,1 | 2,1
--------------------------
0,2 | 1,2 | 2,2
Now if you consider any two placed "pieces" you can create a "vector" by subtracting their coordinates:
Suppose there is a piece on 0,0 and 1,1; then the vector would be 1,1.
Now add this vector to the position of the second piece and you get 2,2, which is where you want the third piece to go.
If the two pieces were on 0,1 and 1,1 the vector would be 1,0, and the winning position (1,1)+(1,0)=(2,1).
Note that you either have to order the pieces somehow, or try adding and subtracting and checking if you are still on the grid. (What if the two pieces are 1,0 and 2,0 for instance?)
Note also, that you have to worry about whether there is already a piece there or not, about all other possible two piece combinations, and, if you can't play a winning move, whether your opponent might be able to, so that you can foil it.
I have to say again that all of that complexity can be taken care of with a centralized board evaluator and a game tree.
If you want all wins to have different sums, you might arrange the numbers as
1 2 3
8 9 4
7 6 5
Although some non-winning combinations may still "conflict"
If you want all possible sums to be diferent, you could number them as
1 2 4
8 16 32
64 128 256
but I'm not sure why you want to use sums in the first place.
But however you represent the squares, Tic Tac Toe should be quite easy for the computer to play, since it's small enough that you can easily store all possible positions.
Since it's so easy to construct the entire game tree, it may be more interesting to try to use some simple heuristics, rather than to try for a perfect player.
General principles might be to try to form as many opportunities as possible among the 8 rows, while blocking your opponents opportunities.
1 2 3
8 9 4
7 6 5
Although some non-winning combinations may still "conflict"
If you want all possible sums to be diferent, you could number them as
1 2 4
8 16 32
64 128 256
but I'm not sure why you want to use sums in the first place.
But however you represent the squares, Tic Tac Toe should be quite easy for the computer to play, since it's small enough that you can easily store all possible positions.
Since it's so easy to construct the entire game tree, it may be more interesting to try to use some simple heuristics, rather than to try for a perfect player.
General principles might be to try to form as many opportunities as possible among the 8 rows, while blocking your opponents opportunities.
here are some other sites with source code.
http://prairiedog.cs.indiana.edu:7777/a348/prj/
http://objectsfusion.com/applets/tictactoe.html
http://www.tictactoe.com/
http://stud1.tuwien.ac.at/~e9125168/javas/jticgame.html
if you look at each one you can find out which way you like best. If you want more specific info let me know. (what are you trying to use for your output? a console, a web page, or a form?)
http://prairiedog.cs.indiana.edu:7777/a348/prj/
http://objectsfusion.com/applets/tictactoe.html
http://www.tictactoe.com/
http://stud1.tuwien.ac.at/~e9125168/javas/jticgame.html
if you look at each one you can find out which way you like best. If you want more specific info let me know. (what are you trying to use for your output? a console, a web page, or a form?)
ASKER
Well, this is in the c++ forum so.... :)
Problem is, if you were to make a game of Othello, how can you possibly program every single possible position? There would be millions, if not billions (depends on size of board).
Like Chess too... Chess is totally different I'm sure.
Problem is, if you were to make a game of Othello, how can you possibly program every single possible position? There would be millions, if not billions (depends on size of board).
Like Chess too... Chess is totally different I'm sure.
ASKER
I'm looking for a c++ version (Console).....
Mainly because I do not understand the logic used in the above applets. If anyone can explain them, it'll work as well.
Mainly because I do not understand the logic used in the above applets. If anyone can explain them, it'll work as well.
this one has been so overdone for so many years, why are we not all bored to death with it? Do any humans play anymore?
How about at least adding a column, go like 3D, now what was that called -- Qubic? Then it might get more interesting again: 4x4x4, get four in a row, now not so trivial
30 yrs ago or so it was called AI to have cpu 'remember' prior moves to 'learn' to win -- but hey, there are not so many moves here, too trivial ?
How about at least adding a column, go like 3D, now what was that called -- Qubic? Then it might get more interesting again: 4x4x4, get four in a row, now not so trivial
30 yrs ago or so it was called AI to have cpu 'remember' prior moves to 'learn' to win -- but hey, there are not so many moves here, too trivial ?
ASKER
I just want to know what kind of logic the above programs use to find wins.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Comment accepted as answer
ASKER
Why does minimax() just repeatedly put in X and 0? How can it possibly find a solution?
I'm sorry to ask you, but I'm really confused about how the logic works, mainly on how minimax/find_move work.
I'm sorry to ask you, but I'm really confused about how the logic works, mainly on how minimax/find_move work.
ASKER
Thanks ozo, I appreciate it.
If you want all wins to sum to 15, you might arrange the numbers as
8 1 6
3 5 7
4 9 2