How to improve the CPU turns in Tic-Tac-Toe
Hi there. I am too improve the strategy of the CPU in my tic-tac-toe game. So far I have got this algorithm for the CPU turns.
void TicTacToe::CPU_turns()
{
while (true) {
int Computer_choice = (rand() % 9) + 1;
int row = (Computer_choice - 1) / 3;
int col = (Computer_choice - 1) % 3;
char grid_pos = matrix[row][col];
if (grid_pos == 'X' || grid_pos == 'Y') {
continue;
}
else {
cout << "The computer has made a move" << Computer_choice<< endl;
matrix[row][col] = 'O';
break;
}
}
}
I am too make the computer detect a winning move and counter the opponent. Appreciate it if you could respond.
void TicTacToe::CPU_turns()
{
while (true) {
int Computer_choice = (rand() % 9) + 1;
int row = (Computer_choice - 1) / 3;
int col = (Computer_choice - 1) % 3;
char grid_pos = matrix[row][col];
if (grid_pos == 'X' || grid_pos == 'Y') {
continue;
}
else {
cout << "The computer has made a move" << Computer_choice<< endl;
matrix[row][col] = 'O';
break;
}
}
}
I am too make the computer detect a winning move and counter the opponent. Appreciate it if you could respond.
I guess you adopt a strategy rather than using rand().
https://en.wikipedia.org/wiki/Tic-tac-toe#Strategy
https://en.wikipedia.org/wiki/Tic-tac-toe#Strategy
Any well played game of tic-tac-toe should end in a draw. The game requires a player to make a mistake in order for there to be a winner.
You have two separate problems given, but there are 3. One is to detect a win. The second is to select a move. The third (which goes with 1), is to detect a draw. The draw detection is merely a check that there is no win, and then that all 9 moves have been played.
Win detection should occur at every turn, even the human player. If the computer player is properly written then there won't be a human winner, ever. That suggests checking for a human win is unnecessary, but the program would be incomplete without it, and while debugging if there ever is a human winner (or a winner if the computer plays against "itself"), then the play selection logic isn't correct.
You could mix in a computer move selection error, just to make it possible (perhaps at lower skill settings) for a human to win.
Win detection is an exhaustive search for connections. It is a simplified version of a ray cast algorithm (I suppose there are alternatives). For each square, project a "ray" along the various 8 possible directions a connection could be made, omitting those directions that run into a side. The central square is the only one that could actually make a "win" connection in all 8 directions, though obviously these mirror 4 of those directions, suggesting an optimization you can consider after you get it working. The speed of all modern computers is fast enough that such optimization would likely not be important. Obviously, you're checking for a line of 3 like squares for any direction. Several squares, like the center squares on each side, would "connect" in two directions. I'll leave you to figure out the details and ask as you proceed. It is tedious but otherwise fairly straight forward.
I'll offer this one suggestion. A square like the upper right corner, probably location 0, 2 where 0,0 is the upper left corner, has 5 directions that are off the edge of the board (and thus should not be considered). You'll know this happens when either coordinate is negative or > 2.
Now, to move selection. The computer should first check all empty squares for a possible "win" move. You'd use the win detection to test each open square move to see if that makes a win. If it does, take the move (unless you're adding that twist where the computer might allow the player to win).
If there are no "winning" moves, then the computer switches to logic which checks for a block. Here, again, if you're adding the twist that a human might be able to win, you might occasionally skip this check. The objective is to look for any potential move that the other player might make to win, and make sure to block it.
For each open square, suppose the other player (could be another computer player) makes a move there, and might win if they do. This checks for a potential win move by the other player, which if they're paying attention would be their next move.
If such a proposed "win" is found, then the computer must play to block on that square.
If that is not found, then a third mode begins. The computer should check every square for the potential to start a new connection with another existing piece owned by the computer. Favor the central square in this mode (probably by starting with that one first). Check every open square for an adjacent computer piece.
When a candidate is found, check to see if another open square exists in that line to make a connection (for example, if (0,0) is a computer piece, (0,1) is open (making a potential connection), check (0,2) to see if it is open. If it is, take the move. If it is not, store the option in a container, and continue searching. There's no need to take a square that wasn't a block (selected in the previous mode) if there's no chance of a win and somewhere else there is a chance to win.
If none of that has selected a move, then choose the central square if it is available. If not, any remaining open square will do, though a central square of any side is likely a better choice than the corners. Consult the list developed previously if required to drive this search.
That's an "off the cuff" plan, not fully tested or more seriously considered, but it's a start.
You have two separate problems given, but there are 3. One is to detect a win. The second is to select a move. The third (which goes with 1), is to detect a draw. The draw detection is merely a check that there is no win, and then that all 9 moves have been played.
Win detection should occur at every turn, even the human player. If the computer player is properly written then there won't be a human winner, ever. That suggests checking for a human win is unnecessary, but the program would be incomplete without it, and while debugging if there ever is a human winner (or a winner if the computer plays against "itself"), then the play selection logic isn't correct.
You could mix in a computer move selection error, just to make it possible (perhaps at lower skill settings) for a human to win.
Win detection is an exhaustive search for connections. It is a simplified version of a ray cast algorithm (I suppose there are alternatives). For each square, project a "ray" along the various 8 possible directions a connection could be made, omitting those directions that run into a side. The central square is the only one that could actually make a "win" connection in all 8 directions, though obviously these mirror 4 of those directions, suggesting an optimization you can consider after you get it working. The speed of all modern computers is fast enough that such optimization would likely not be important. Obviously, you're checking for a line of 3 like squares for any direction. Several squares, like the center squares on each side, would "connect" in two directions. I'll leave you to figure out the details and ask as you proceed. It is tedious but otherwise fairly straight forward.
I'll offer this one suggestion. A square like the upper right corner, probably location 0, 2 where 0,0 is the upper left corner, has 5 directions that are off the edge of the board (and thus should not be considered). You'll know this happens when either coordinate is negative or > 2.
Now, to move selection. The computer should first check all empty squares for a possible "win" move. You'd use the win detection to test each open square move to see if that makes a win. If it does, take the move (unless you're adding that twist where the computer might allow the player to win).
If there are no "winning" moves, then the computer switches to logic which checks for a block. Here, again, if you're adding the twist that a human might be able to win, you might occasionally skip this check. The objective is to look for any potential move that the other player might make to win, and make sure to block it.
For each open square, suppose the other player (could be another computer player) makes a move there, and might win if they do. This checks for a potential win move by the other player, which if they're paying attention would be their next move.
If such a proposed "win" is found, then the computer must play to block on that square.
If that is not found, then a third mode begins. The computer should check every square for the potential to start a new connection with another existing piece owned by the computer. Favor the central square in this mode (probably by starting with that one first). Check every open square for an adjacent computer piece.
When a candidate is found, check to see if another open square exists in that line to make a connection (for example, if (0,0) is a computer piece, (0,1) is open (making a potential connection), check (0,2) to see if it is open. If it is, take the move. If it is not, store the option in a container, and continue searching. There's no need to take a square that wasn't a block (selected in the previous mode) if there's no chance of a win and somewhere else there is a chance to win.
If none of that has selected a move, then choose the central square if it is available. If not, any remaining open square will do, though a central square of any side is likely a better choice than the corners. Consult the list developed previously if required to drive this search.
That's an "off the cuff" plan, not fully tested or more seriously considered, but it's a start.
TTT is known as a good starting point to learn about these things.
it turns out that if you rotate or mirror the board, and swap x an o (so an x in the upper left is the same position as an o in the upper left) you can get the number of possible boards down to a very small number, and then you can check which board you are currently on and pick the next best move from that. This idea is called transposition tables. Your AI can literally be just a lookup of (current board state, next move) and its still a small, manageable program.
it turns out that if you rotate or mirror the board, and swap x an o (so an x in the upper left is the same position as an o in the upper left) you can get the number of possible boards down to a very small number, and then you can check which board you are currently on and pick the next best move from that. This idea is called transposition tables. Your AI can literally be just a lookup of (current board state, next move) and its still a small, manageable program.
Topic archived. No new replies allowed.