Tic Tac Toe Algorithm Trouble
Pages: 12
Hi everybody. I just made a topic here and it took posting that to figure out what was wrong with my last problem, but now I have an entirely different problem.
I'm making a game of Tic Tac Toe in which you are pitted against an AI opponent. All seems to work properly except for one very crucial part;
The AI seems to give up after 2 or 3 turns.
I've stepped through my code, and it appears to be running through the move algorithms, but it doesn't make a move. If anyone could shed some light onto this, it would be very much appreciated
Here is the code:
I apologize for the long read, there is probably a simpler way to handle the algorithm but I couldn't figure one out.
Thanks again for any help
I'm making a game of Tic Tac Toe in which you are pitted against an AI opponent. All seems to work properly except for one very crucial part;
The AI seems to give up after 2 or 3 turns.
I've stepped through my code, and it appears to be running through the move algorithms, but it doesn't make a move. If anyone could shed some light onto this, it would be very much appreciated
Here is the code:
|
|
|
|
I apologize for the long read, there is probably a simpler way to handle the algorithm but I couldn't figure one out.
Thanks again for any help
All you assign is 1 (for the player) and never 2 (for the computer) in
WinBlock() and BestMove(). It needs a parameter that tells who does the move.
I'm not sure I follow. 1 is always X, which is always the computer's move. WinBlock and BestMove wouldn't need the option for a player because its only called for the computer
Have you thought about having a 2d array for your board - this might make it easier to do things with for loops.
To check for a win, check each row, each column, and both diagonals.
I am guessing your numbering system for the board is making the logic harder. Example - one of the diagonals is [0][0], [1][1], [2][2] rather than 0,4,8. Can you see how that makes it easier to do nested for loops?
Your code was a good effort, I think, but you are right in that it can be improved. The telling thing for me was all the repetitive else if's. If you find yourself writing code like this - then there is probably a much better way.
I hope you see this as constructive criticism, and learn from it. Don't worry there have been lot's of coders who have done something one way, only to find a much more elegant way.
The other thing is not to put code into header files. Headers are for declarations, not code. You could however have more than one cpp file - you just have to figure out how to compile & link it. Should be easy if you have an IDE. You will need to declare which functions you are using as extern, before main().
Hope all this has been useful to you,look forward to helping out more if needed.
To check for a win, check each row, each column, and both diagonals.
I am guessing your numbering system for the board is making the logic harder. Example - one of the diagonals is [0][0], [1][1], [2][2] rather than 0,4,8. Can you see how that makes it easier to do nested for loops?
Your code was a good effort, I think, but you are right in that it can be improved. The telling thing for me was all the repetitive else if's. If you find yourself writing code like this - then there is probably a much better way.
I hope you see this as constructive criticism, and learn from it. Don't worry there have been lot's of coders who have done something one way, only to find a much more elegant way.
The other thing is not to put code into header files. Headers are for declarations, not code. You could however have more than one cpp file - you just have to figure out how to compile & link it. Should be easy if you have an IDE. You will need to declare which functions you are using as extern, before main().
Hope all this has been useful to you,look forward to helping out more if needed.
Thanks, TheIdeasMan, I never thought of using two arrays to represent the rows and columns of the board. That was the elegant solution I was very much hoping someone would point out to me :)
However, I'm not going to mark this as solved just yet, I'm going to try to restructure my code in the way you have suggested and then see if it fixes it, or if it gives me an easier look at the problem / solution.
I was also thinking of making another .cpp for the definitions of the .h file, I just wanted to get the actual game working first before I clean it all up.
Thanks for the definitely constructive criticism :)
However, I'm not going to mark this as solved just yet, I'm going to try to restructure my code in the way you have suggested and then see if it fixes it, or if it gives me an easier look at the problem / solution.
I was also thinking of making another .cpp for the definitions of the .h file, I just wanted to get the actual game working first before I clean it all up.
Thanks for the definitely constructive criticism :)
OK, no worries.
Just one thing:
I meant one 2 dimensional array -
Just one thing:
| I never thought of using two arrays to represent the rows and columns of the board. |
I meant one 2 dimensional array -
|
|
Hi there again, I decided not to use a 2D array in the end as, while it seems simpler to do so, I figured out how to make it work pretty well with a normal array. However, now I have a new problem.
For some reason, the computer now chooses the squares 1 to 9 backwards, with no thought about the best place to move. It always starts with 9, and works its way back to 1, unless it is intercepted, in which case it skips the square that has been claimed by the player.
If you have 2 squares in a line, it makes no effort to try and block your move.
Here is the code now:
Again, sorry for the messy layout, I'll sort all that out once I'm done getting the computer to work properly.
Thanks for any help anyone can give
For some reason, the computer now chooses the squares 1 to 9 backwards, with no thought about the best place to move. It always starts with 9, and works its way back to 1, unless it is intercepted, in which case it skips the square that has been claimed by the player.
If you have 2 squares in a line, it makes no effort to try and block your move.
Here is the code now:
|
|
Again, sorry for the messy layout, I'll sort all that out once I'm done getting the computer to work properly.
Thanks for any help anyone can give
By not using a 2d array, makes you code long winded because the logic is much more involved.
You have 260 lines of code, some of the other examples of the same problem on this forum are only 100. I haven't looked at these other examples - it may be possible that these could be written with less as well.
One thing I do all the time is write my methodology as comments. This can be done iteratively, so start out with very general ideas first, then go back and put in more detail. Continue until you are ready to write code, leave the comments as they are documentation.
This will help you organise your thoughts logically, help identify what should be in functions etc.
The normal structure of a file looks like this:
That way we don't have to scroll all the way to the bottom to see what main does.
Now for some other observations:
You can make use of the toupper or tolower functions so you don't have a double test for y or Y.
The GameWon function could call the CheckRows, CheckCols, CheckDiags functions.
This code:
only checks up to i == 7. The normal idiom is this:
elsewhere you also had :
just stick to the normal idiom.
With this part startin line 55:
numXs & numOs are set to zero anyway, so why set them inside the if?
There are a lot of these repeated in your code:
This part:
can be shortened to:
The CheckBadMoves function will be a lot easier with the 2d array. You can check adjacent squares by adding / subtracting 1 from Row or Col.
This part :
can be shortened to :
In main(), if the FirstGo function returned a bool, the answer could be assigned to the compfirst variable, which could be declared in main, so now compfirst isn't a global variable.
The if and else if blocks are very similar, can you figure out how to write this more elegantly?
Hint: Play all the moves until the game is finished, then print out who won.
Hope this helps, but seriously consider rewriting with the 2d array
You have 260 lines of code, some of the other examples of the same problem on this forum are only 100. I haven't looked at these other examples - it may be possible that these could be written with less as well.
One thing I do all the time is write my methodology as comments. This can be done iteratively, so start out with very general ideas first, then go back and put in more detail. Continue until you are ready to write code, leave the comments as they are documentation.
This will help you organise your thoughts logically, help identify what should be in functions etc.
The normal structure of a file looks like this:
|
|
That way we don't have to scroll all the way to the bottom to see what main does.
Now for some other observations:
You can make use of the toupper or tolower functions so you don't have a double test for y or Y.
The GameWon function could call the CheckRows, CheckCols, CheckDiags functions.
This code:
for (i = 0; i < 8; i++)only checks up to i == 7. The normal idiom is this:
for (i = 0; i < 9; i++)elsewhere you also had :
for (i = 0; i <= 8; i++)just stick to the normal idiom.
With this part startin line 55:
|
|
numXs & numOs are set to zero anyway, so why set them inside the if?
There are a lot of these repeated in your code:
|
|
This part:
|
|
can be shortened to:
|
|
The CheckBadMoves function will be a lot easier with the 2d array. You can check adjacent squares by adding / subtracting 1 from Row or Col.
This part :
|
|
can be shortened to :
|
|
In main(), if the FirstGo function returned a bool, the answer could be assigned to the compfirst variable, which could be declared in main, so now compfirst isn't a global variable.
The if and else if blocks are very similar, can you figure out how to write this more elegantly?
Hint: Play all the moves until the game is finished, then print out who won.
Hope this helps, but seriously consider rewriting with the 2d array
I don't mean to sound like an ass here because I appreciate all the advice for cleaning up my code, but the problem I'm having is more to do with what the computer player is doing.
I don't see why it is starting with 9 every turn then working its way backwards towards 1. Can you see specifically what I'm doing wrong in the logic?
I don't see why it is starting with 9 every turn then working its way backwards towards 1. Can you see specifically what I'm doing wrong in the logic?
I found a 1d array much easier for tic-tac-toe.
The behavior comes from the loop in ComputerTurn() always resulting in "bestPosition" being the highest valid move. This means that EvalutePosition() isn't doing it's job correctly.
Looking at EvalutePosition(), the values are hard coded so it is going to return the same thing no matter what.
MarkValue() is hard to understand.
I also noticed that the computer is 'X' even though I went first.
The behavior comes from the loop in ComputerTurn() always resulting in "bestPosition" being the highest valid move. This means that EvalutePosition() isn't doing it's job correctly.
Looking at EvalutePosition(), the values are hard coded so it is going to return the same thing no matter what.
MarkValue() is hard to understand.
I also noticed that the computer is 'X' even though I went first.
Last edited on
Aha, that would make sense. Looking at EvaluatePosition(), though, I don't see a way in which I could make the values anything but hard coded. Is there an easy fix for the problem I'm having?
MarkValue() is something I picked up from googling my problem. What it basically does is it looks through the array and counts up the amount of Xs and Os there are in each line, then in each diagonal, and should return a value dependant on the outcome of each placement.
Also, I wasn't entirely sure about the rules of Tic Tac Toe, whenever I play it, we pick who goes first, then they either use an X or an O. This to say that I wasn't aware of any rule that suggests Xs go first or the like, so I just set the computer's value to X to avoid the hassle of changing it depending on who goes first.
MarkValue() is something I picked up from googling my problem. What it basically does is it looks through the array and counts up the amount of Xs and Os there are in each line, then in each diagonal, and should return a value dependant on the outcome of each placement.
Also, I wasn't entirely sure about the rules of Tic Tac Toe, whenever I play it, we pick who goes first, then they either use an X or an O. This to say that I wasn't aware of any rule that suggests Xs go first or the like, so I just set the computer's value to X to avoid the hassle of changing it depending on who goes first.
The first thing I did was split the AIs moves into two categories, things that have to happen, and choices. Choices are more complicated, but not too bad in tic-tac-toe.
The things that have to happen are: "did I loose", "can I win", "should I block". I dont want to go too far into things you don't know, but an enumerator might help you:
which lets you do things like:
With AI, I would start by getting it only to recognize when it lost, then try to get it to block your two-in-a-row, and then to see if it can win (winning takes precendence over blocking)
edit: Assume that pos1, pos2, and pos3 refer to an array, I didn't really code that in too well (ie, some parts don't make sense).
Hope that helps a little, I've got to go to work now though.
The things that have to happen are: "did I loose", "can I win", "should I block". I dont want to go too far into things you don't know, but an enumerator might help you:
enum STATE { FREE, LOST, CANWIN, BLOCK };which lets you do things like:
|
|
With AI, I would start by getting it only to recognize when it lost, then try to get it to block your two-in-a-row, and then to see if it can win (winning takes precendence over blocking)
edit: Assume that pos1, pos2, and pos3 refer to an array, I didn't really code that in too well (ie, some parts don't make sense).
|
|
Hope that helps a little, I've got to go to work now though.
Last edited on
So out of interest i coded the complete game. Inclusive a unbeatable ai.
Yes 1d array is the better choice (as mostly)
what i'm missing within your code is a function that collects positions of the free fields. If you had such a function you could easily rand() your next move out of those positions. And that would be a very basic but working game
Why is there no rand() in your code? I mean there're usually a range of possible moves from where you have to pick one.
Yes, it's a good idea to have a back up board to simulate the next move. But for both, the computer and the player -> if the simulation results in a win for either the computer (first) or the player (block) take that position.
From that you can make your computer more 'intelligent'. I can tell you how, if you're willing to follow my suggestions...
Yes 1d array is the better choice (as mostly)
what i'm missing within your code is a function that collects positions of the free fields. If you had such a function you could easily rand() your next move out of those positions. And that would be a very basic but working game
Why is there no rand() in your code? I mean there're usually a range of possible moves from where you have to pick one.
Yes, it's a good idea to have a back up board to simulate the next move. But for both, the computer and the player -> if the simulation results in a win for either the computer (first) or the player (block) take that position.
From that you can make your computer more 'intelligent'. I can tell you how, if you're willing to follow my suggestions...
Thanks for the insight into enum, LowestOne, but I don't actually know anything about that and don't really want to straight up copy code, I'd rather have some understanding of what I'm actually doing
Coder777, I first thought about doing the Rand() thing and having the computer throw in a random move, but upon doing that I realised that the game was too easy to win, since there was no logic being used by the computer player.
From there, I implemented a series of if statements that would lead the computer to cycle through the best tactical moves, starting from the middle and then working through the corners. However, this also proved to lead to easy wins, and then I started thinking about how I would make the computer play like a human. This is where I'm having trouble.
That's what I'm currently working with. I went back to the messy if/else method as it produced the best results, but now the computer seems to be grabbing at random numbers for a while, then going back to picking the highest to lowest open spots, without considering the tactical effect of each move
Coder777, I first thought about doing the Rand() thing and having the computer throw in a random move, but upon doing that I realised that the game was too easy to win, since there was no logic being used by the computer player.
From there, I implemented a series of if statements that would lead the computer to cycle through the best tactical moves, starting from the middle and then working through the corners. However, this also proved to lead to easy wins, and then I started thinking about how I would make the computer play like a human. This is where I'm having trouble.
|
|
That's what I'm currently working with. I went back to the messy if/else method as it produced the best results, but now the computer seems to be grabbing at random numbers for a while, then going back to picking the highest to lowest open spots, without considering the tactical effect of each move
Looks like line 116 needs to be:
I don't think you need the loop in ComputerTurn() at all. By the time you're in ComputerTurn you already know that there is a valid move left (!gameWon). WinBlock() is already returning the best move to do.
I don't think you really need to simulate next moves. Tic-Tac-Toe is pretty simple: If the center is free go there, otherwise take a corner, then take a side. You have to check whether or not you can win/block, but not much thinking.
Every game should end in a draw. I can still beat your AI, but maybe I let you find that :)
else return BestMove();I don't think you need the loop in ComputerTurn() at all. By the time you're in ComputerTurn you already know that there is a valid move left (!gameWon). WinBlock() is already returning the best move to do.
I don't think you really need to simulate next moves. Tic-Tac-Toe is pretty simple: If the center is free go there, otherwise take a corner, then take a side. You have to check whether or not you can win/block, but not much thinking.
Every game should end in a draw. I can still beat your AI, but maybe I let you find that :)
It seems to work a little better after making those changes, so thanks for that, but its still having its problems. Now, if I block the computer's winning move, it kind of just freezes up and doesn't make any more moves, then declares the game to be a draw.
Very peculiar.
Are you having this problem at all or is my computer just giving up?
Updated code.
Very peculiar.
Are you having this problem at all or is my computer just giving up?
|
|
Updated code.
| I don't think you really need to simulate next moves. |
ok, your approach seem different from mine. So i can post my code:
|
|
Managed to beat it ;P
But only starting first, found it impossible otherwise.
How are you getting it to block winning moves though? From the code it looks like the computer is just looking at the possible moves and making a random move from that list. Or do I have that completely wrong?
But only starting first, found it impossible otherwise.
How are you getting it to block winning moves though? From the code it looks like the computer is just looking at the possible moves and making a random move from that list. Or do I have that completely wrong?
I can win when the computer goes on an edge on the first move.
I'll have to get mine console ready, I wrote it as an exercise in GLUT.
I'll have to get mine console ready, I wrote it as an exercise in GLUT.
Pages: 12