Tic Tac Toe

• 11-11-2005, 10:08 PM
Tic Tac Toe
I created a tic tac toe game where you plsy against the computer, however its too easy for the human player to win. how can i make it so that the computer wins all the time or ties the human player?

public int[] chooseMove(char symbol){
int[] move = new int[2];
int blockRow = 0;
int blockCol = 0;
int progressRow = 0;
int progressCol = 0;

for (int i=0; i < ticTacToe.length; i++){
for (int j=0; j < ticTacToe[i].length; j++){
if (ticTacToe[i][j] == '_'){
progressRow = i;
progressCol = j;
} else if (ticTacToe[i][j] != symbol){

} else {

}
}
}

if(blockRow != 0 || blockCol != 0){
move[0] = blockRow;
move[1] = blockCol;
} else {
move[0] = progressRow;
move[1] = progressCol;
}
return move;
}
• 11-13-2005, 05:27 PM
evlich
I wrote a generalized version of this game for one of my courses in college. Basically what I did was had a set which contained all possible solutions as referenced cells. When a square was played in by either player, the cell was filled in. When a solution had at least one square for both players, that solution was considered invalid and was discarded. It turns out to be very efficient to incrementally update and search the board for your best move, as long as you aren't going to be looking too deep. The algorithm would go something like this:

A | B | C
----+---+----
D | E | F
----+---+----
G | H | I

There are 8 possible solutions:
ABC, DEF, GHI, ADG, BEH, CFI, AEI, GEC
They are valued by the number of moves remaining for the player to win (positive numbers if you will win and negative numbers if the opponent will win). Then you can just check the groups that have value 1, and if there are any, then make your move into the last remaining cell. Then do the same thing for the groups with -1. You can then do intersections of the groups of values 2 to see if there is a single square such that moving there would make 2 2 valued groups into 1 valued groups, if you can do that then you move there. Same thing for the opponent and -2 valued groups.

This may be a bit of overkill, and it probably wouldn't take too long to write a program to solve the best move simply using a depth-first traversal of all possible sequences of moves from a given point.

Hope this helps.
• 11-14-2005, 09:52 PM