GAMES TWO: LESSON Ten: Tic Tac Toe: Intelligent Moves
It is possible to create a computer_move method which plays a perfect game
of tic tac toe. A perfect game of tic tac toe from the computer's
perspective is that it always wins when there is an opportunity to win and
it never loses (NEVER LOSES). Rewriting the computer_move method so that a
perfect game of tic tac toe is always played by the computer is beyond the
scope of this lesson, but we can play a pretty good game.
The only modifications to the applet to implement improved intelligence (in
terms of move selection) need to be made in the computer_move method. We
will not implement a perfect move algorithm here. If you are interested in a
perfect move algorithm you can do a little research into the minimax
algorithm and alpha-beta pruning.
Here is the altered computer_move method:
<![CDATA[
public void computer_move(){
Random r = new Random();
int index = 0;
boolean selected = false;
//look for win
for(int i=0; i<moves.length; i++){
if(!selected){
if(grid[moves[i][0]].equals("X") &&
grid[moves[i][1]].equals("X") &&
grid[moves[i][2]].equals("") ) {
index=moves[i][2];
selected=true;
}
}
}
//look for block
for(int i=0; i<moves.length; i++){
if(!selected){
if(grid[moves[i][0]].equals("O") &&
grid[moves[i][1]].equals("O") &&
grid[moves[i][2]].equals("") ) {
index=moves[i][2];
selected=true;
}
}
}
//make random move, if no move already selected.
if(!selected){
do{
index=Math.abs(r.nextInt()%9);
}while(!grid[index].equals("") );
}
grid[index]="X";
turn++;
if(winner(0) || turn==9 ) gameOver=true;
}
]]>
The computer_move method relies on the following array for a list of
locations to check when deciding upon a move.
<![CDATA[
int[][] moves = { {0,1,2}, {1,2,0}, {0,2,1},
{3,4,5}, {4,5,3}, {3,5,4},
{6,7,8}, {7,8,6}, {6,8,7},
{0,3,6}, {3,6,0}, {0,6,3},
{1,4,7}, {4,7,1}, {1,7,4},
{2,5,8}, {5,8,2}, {2,8,5},
{2,4,6}, {4,6,2}, {2,6,4},
{0,4,8}, {4,8,0}, {0,8,4} };
]]>
It is correct to say that the computer will now play a pretty intelligent
game of tic-tac-toe, but it does not play a perfect game using this
algoritm.
ASSIGNMENT:
Use the moves array to shorten the code for the winner method.