Version Eight:
1. Uses the Alpha-Beta algorithm to find best move.

Faster Than MiniMax!!!

Complete Listings:

def.java:

t8.java

/* t8.java: Uses AlphaBeta Algorithm
*  This is an applet class which displays a game of tic tac toe.
*  The actual game is implemented in the TicTacToe.java file.
*/

import java.awt.*;
import java.applet.*;
import java.awt.event.*;
import java.util.*;

public class t8 extends Applet implements def{

TicTacToe t;
  TextArea ta;
  static final int height=210;
  static final int width=210;

public void init() {
/******************************************************************
*  Initializes variables and references used by applet.
*  Precondition: Browser calls applet
*  Postcondition: variables and references initialized. 
*******************************************************************/
    setLayout(null);
    t=new TicTacToe(this);
    ta=new TextArea(30, 60);
    t.init_game();
    setBackground(Color.black);
    ta.setLocation(10,210);
    ta.setSize(300,120);
    ta.setBackground(Color.white);
    add(ta);
    addMouseListener(new ML());
  }

class ML extends MouseAdapter {
/*****************************************************************
*  Inner class which deals with mouse clicks.
*****************************************************************/
    public void mouseReleased(MouseEvent e) {
/***************************************************************
*  Called whenever mouse released in applet area.
*  Precondition: Click of mouse.
*  Postcondition: plotMove(MouseEvent) called
*******************************************************************/
      plotMove(e);
    }
  }

public void plotMove(MouseEvent e) {
/*****************************************************************
*  Determines game condition and where mouse clicked and calls various 
*  methods.
*  Precondition: Call from mouseReleased.
*  Postcondition: t.computer_move() or t.human_move() called and then
*  applet repainted.
**********************************************************************/
    if(t.GAMEOVER==YES) {
      t.init_game();
      if(t.TURN==COMPUTER) 
        t.computer_move();
      repaint();
    }
    else {
      if(t.TURN==HUMAN) {
        int x=e.getX();
        int y=e.getY();
        if(x>(2*width/3)) x=2;
        else if(x>width/3) x=1;
        else x=0;
        if(y>(2*height/3)) y=2;
        else if(y>height/3) y=1;
        else y=0;
        t.human_move(y,x);
        repaint();
      }
    }
    if(t.TURN==COMPUTER && t.GAMEOVER==NO) {
      t.computer_move();
      repaint();
    }
  }
  
  public void drawBoard(Graphics g) {
/*****************************************************************
* Draws grid and players in their positions.
* Precondition: Call from paint(Graphics g)
* Postcondition: Current state of game displayed
*******************************************************************/
    g.setColor(Color.yellow);
    int x = width/3;
    int y = height/3;
    g.drawLine(x, 0, x, height);
    g.drawLine(2*x, 0, 2*x, height);
    g.drawLine(0, y, width, y);
    g.drawLine(0, 2*y, width, 2*y);
    for(int i=0; i<3; i++)
      for(int j=0; j<3; j++) {
        if(t.position[i][j]==COMPUTER) {
          g.setColor(Color.red);
          g.drawOval(j*x+1, i*y+1, x-2, y-2);
        }
        else if(t.position[i][j]==HUMAN) {
          g.setColor(Color.cyan);
          g.drawLine(j*x+1, i*y+1, j*x+x-2, i*y+y-2);
          g.drawLine(j*x+1, i*y+y-2, j*x+x-2, i*y+1);
        }
    }
  }

public void plotWin(Graphics g) {
/**************************************************************
* Draws a line highlighting path of win.
* Precondition: Called by paint(Graphics g). Only actually does 
* anything if a winning pattern exists.
* Postcondition: A winning pattern is highlighted if one exists.
***************************************************************/
    g.setColor(Color.magenta);
    if(t.DIRWIN==0) g.drawLine(0, height/6,width,height/6);
    if(t.DIRWIN==1) g.drawLine(0, height/2, width,height/2);
    if(t.DIRWIN==2) g.drawLine(0, 5*height/6, width, 5*height/6);
    if(t.DIRWIN==3) g.drawLine(width/6, 0, width/6, height);
    if(t.DIRWIN==4) g.drawLine(width/2, 0, width/2, height);
    if(t.DIRWIN==5) g.drawLine(5*width/6, 0, 5*width/6, height);
    if(t.DIRWIN==6) g.drawLine(0,0,width,height);
    if(t.DIRWIN==7) g.drawLine(0, height, width, 0);
  }
         
  public void paint(Graphics g) {
/******************************************************************
* Calls drawBoard and plotWin to display current game state.
* Precondition: Called after init method and by plotMove() method
* through use of repaint() method.
* Postcondition: Display of game state updated.
******************************************************************/
    drawBoard(g);
    plotWin(g);
  }
}

TicTacToe.java

/*****************************************************************
* TicTacToe.java  This class is used to keep track of a game of
*  tictactoe. It generates computer moves using the AlphaBeta
*  pruning algorithm.
*******************************************************************/
import java.util.*;

class TicTacToe implements def{
  public int DIRWIN;
  public int GAMEOVER;
  int bestr[]=new int[1];
  int bestc[]=new int[1];
  public static final int UNCLEAR=0;
  public static final int HUMAN_WIN=1;
  public static final int DRAW=2;
  public static final int COMPUTER_WIN=3;
  Random r;
  int TURN;
  int MOVES;
  int [][] position;
  t8 display;
  int m;

TicTacToe(t8 t) {
/****************************************************************
* Initializes instance of class and enables updating of textarea in t8.
* Precondition: Call from t8 applet.
* Postcondition: Class initialized and ready for a game.
*****************************************************************/
    display=t;
  }

public void init_game() {
//*********************************************************
* Initializes main variables used in game.
* Precondition: Call from init() or plotMove() of t8.
* Postcondition: Empty board and other variables set for start
*  of game.
**********************************************************/
    MOVES=0;
    GAMEOVER=NO;
    DIRWIN=8;  //winning directions 0-7, 8 is not a winning direction
    r=new Random();
    TURN=(Math.abs(r.nextInt())%2 == 1) ? HUMAN : COMPUTER;
    position = new int[3][3];
    for(int i=0; i<3; i++)
      for(int j=0; j<3; j++)
        position[i][j]=EMPTY;
  }

public void win() {
/*******************************************************************
* Detects if a win exists and identifies its direction
* Precondition: Call from computer_move() or human_move().
* Postcondition: Identifies direction of win, if one exists.
********************************************************************/
    for(int player=COMPUTER; player<=HUMAN; player++) {
      if(position[0][0]==player && position[0][1]==player && position[0][2]==player)
        DIRWIN=0;
      if(position[1][0]==player && position[1][1]==player && position[1][2]==player)
        DIRWIN=1;
      if(position[2][0]==player && position[2][1]==player && position[2][2]==player)
        DIRWIN=2;
      if(position[0][0]==player && position[1][0]==player && position[2][0]==player)
        DIRWIN=3;
      if(position[0][1]==player && position[1][1]==player && position[2][1]==player)
        DIRWIN=4;
      if(position[0][2]==player && position[1][2]==player && position[2][2]==player)
        DIRWIN=5;
      if(position[0][0]==player && position[1][1]==player && position[2][2]==player)
        DIRWIN=6;
      if(position[0][2]==player && position[1][1]==player && position[2][0]==player)
        DIRWIN=7;
    } //end for-loop
    if(DIRWIN!=8) GAMEOVER=YES;
    //check for cat's game
    MOVES++;
    if(MOVES==9) GAMEOVER=YES;
  }

public void computer_move() {
/************************************************************************
* Calls miniMax to decide on best move and then stores move in 
*  position array. Also displays information regarding algorithm
*  efficiency and calls function to check for winning state.
* Precondition: Call from plotMove in applet.
* Postcondition: Computer's move made and flag set for human to make 
*  move. 
************************************************************************/
    GameState gs=new GameState(position);
    m=0;
    miniMax(gs,COMPUTER, HUMAN_WIN, COMPUTER_WIN, bestc, bestr);
    display.ta.setText("M: "+m);
    position[bestr[0]][bestc[0]]=COMPUTER;
    win();
    TURN=HUMAN;
  }

public void human_move(int x, int y) {
/*******************************************************************
* Stores human move in array.
* Precondition: Call from plotMove in applet.
* Postcondition: Human move stored and flag set for computer to make
* move.
*********************************************************************/
    if(position[x][y]==EMPTY) {
      position[x][y]=HUMAN;
      win();
      TURN=COMPUTER;
    }
  }

public int evaluate(GameState gs) {
/********************************************************************
* Returns value of possible moves.
* Precondition: Call from miniMax method.
* Postcondition: Returns a value which indicates affect of possible
* move: human win, computer win, cat's game, or game not finished.
********************************************************************/
    int i, j;
    for(i=0; i<3; i++) {
      if((gs.position[i][0]==gs.position[i][1])&&
         (gs.position[i][1]==gs.position[i][2])&&
         (gs.position[i][0] != EMPTY)) {//vertical win
           if(gs.position[i][0]==COMPUTER) return COMPUTER_WIN;
           else if(gs.position[i][0]==HUMAN) return HUMAN_WIN;
      }
      if((gs.position[0][i]==gs.position[1][i])&&
         (gs.position[1][i]==gs.position[2][i])&&
         (gs.position[0][i] != EMPTY)) {//horizontal win
           if(gs.position[0][i]==COMPUTER) return COMPUTER_WIN;
           else if(gs.position[0][i]==HUMAN) return HUMAN_WIN;
      }
    }
    if((gs.position[0][0]==gs.position[1][1])&&
       (gs.position[1][1]==gs.position[2][2])&&
       (gs.position[1][1] != EMPTY)) {//diagonal win
         if(gs.position[1][1]==COMPUTER) return COMPUTER_WIN;
         else if(gs.position[1][1]==HUMAN) return HUMAN_WIN;
    }
    if((gs.position[0][2]==gs.position[1][1])&&
       (gs.position[1][1]==gs.position[2][0])&&
       (gs.position[1][1] != EMPTY)) {//diagonal win
         if(gs.position[1][1]==COMPUTER) return COMPUTER_WIN;
         else if(gs.position[1][1]==HUMAN) return HUMAN_WIN;
    }
    for(i=0;i<3;i++) {
      for(j=0;j<3;j++) {
        if(gs.position[i][j] == EMPTY) return UNCLEAR; //no win, more moves
      }
    }
    return DRAW;  //no win, no moves
  }

public int miniMax(GameState gs, int side, int alpha, int beta, int bestc[], int bestr[]) {
/**********************************************************************
* Searches for best move for computer.
* Precondition: Call from computer_move method.
* Postcondition: Stores best move in bestc and bestr.
***********************************************************************/ 
    int opp=0;
    int reply=0;
    int value=0;
    int[] dc = new int[1];

if(evaluate(gs)!=UNCLEAR) return evaluate(gs); //base case

if(side==COMPUTER) {
      opp=HUMAN;
      value=alpha;
    }
    else {
      opp=COMPUTER;
      value=beta;
    }

for(int row=0; row<3; row++) {
      for(int col=0; col<3; col++) {
        if(gs.position[row][col]==EMPTY) {
          gs.position[row][col]=side;  //try out experimental move
          reply=miniMax(gs,opp, alpha, beta, dc, dc); //recursive call
          gs.position[row][col]=EMPTY; //undo experimental move
          if(((side==COMPUTER)&&(reply>value)) ||   //MAX
             ((side==HUMAN) && (reply<value)) ) {     //MIN
               if(side==COMPUTER) {  //store new best computer move
                 alpha=reply;
                 value=reply;
               }
               else {                //store new best human move
                 beta=reply;
                 value=reply;
               }
             m++;
             bestr[0]=row;
             bestc[0]=col;
             if(alpha>=beta) return value;
          } //if         
        } //if
      } //for
    } //for
    return value;
  }
}