// TicTacToe.java, version 1.04, file created, January 30, 2001.
//
// Applet for tic tac toe game.
//
// Ported from a C program written by Rick Wagner as an example for CS 101, Introduction
// to Programming, at the University of Southern California.
//
// This file last updated February 5, 2001, by Rick Wagner.
// Copyright 2001 by Rick Wagner, all rights reserved.
//
// Use of this source code is authorized for educational purposes only. No use without
// proper attribution to Rick Wagner (http://iris.usc.edu/home/iris/rwagner/
// e-mail: wagner@pollux.usc.edu).
//
// The prefix naming convention used here is a modified Hungarian notation.
// "s" is string, "sf" is single precision floating point, "i" is integer, "b" is boolean,
// "d" is dimension, and "c" is color.

import java.applet.*;
import java.awt.*;

public class TicTacToe extends Applet implements Runnable
{
  // Applet instance variables:
  private String sVerNum = "1.04";                       // Only constructors can run here ("" is a constructor).
  private Dimension dApplet = null;                      // The applet panel size (set in calling html).
  private Image imOffScreen = null;                      // Offscreen image for double buffering.
  private Graphics grOffScreen = null;                   // Offscreen graphics for double buffering.

  private int iLeftRegionB = 0;                          // Region boundaries for dividing the game grid.
  private int iCenterXRegionB = 0;                       //
  private int iTopRegionB = 0;                           //
  private int iCenterYRegionB = 0;                       //

  private Thread tCompute = null;                        // Do the thinking in a thread.

  private char cBoardConfig[] = new char[9];             // The board game configuration.
  private GameNode gnGameRoot = new GameNode();          // Root game node for computing the game tree.

  private boolean bThinking = false;                     // Don't take user inputs while thinking.
  private boolean bNewGame = true;                       // Is it a new game or a continuing one?
  private boolean bPlay = true;                          // Play as long as this flag is true.
  private int iStatus = 0;                               // Who won the game.

  // To allow browsers to get information about the applet (not yet implemented in Netscape nor in MSIE):
  public String getAppletInfo()
  {
    return "Tic tac toe applet, version " + sVerNum +
           ", by Rick Wagner, copyright 2001,\nall rights reserved.\n\n" +
           "Compiled February 2, 2001. Source code use authorized for\n" +
           "educational purposes only. No use without attribution.\n";
  }

  // Initialize the applet
  public void init()
  {
    int i = 0;
    this.setBackground(Color.lightGray);
    dApplet = this.size();

    // Set the region boundaries:
    iLeftRegionB = dApplet.width / 3;
    iCenterXRegionB = dApplet.width * 2 / 3;
    iTopRegionB = dApplet.height / 3;
    iCenterYRegionB = dApplet.height * 2 / 3;

    // Set the game root GameNode and board initial configuration:
    for (i = 0; i < 9; i++)
    {
      gnGameRoot.cConfig[i] = '-';                           // Hyphen represents empty square.
      cBoardConfig[i] = '-';
    }
  } // End of init()

  // Execute this code after initialization
  public void start()
  {
    System.out.println("\n" + this.getAppletInfo());         // Identify self to the Java console-aware user
  } // End of start()

  public void run()                                          // Thread computation.
  {
    int i = 0;
    int iNumAvailable = 0;
    int iAvailable[] = new int[9];                           // Array of available squares.

    bThinking = true;                                        // No user input while thinking.

    // Copy the board configuration to the root GameNode:
    for (i = 0; i < 9; i++)
    {
      gnGameRoot.cConfig[i] = cBoardConfig[i];
    }
    iNumAvailable = getAvailableMoves(gnGameRoot.cConfig, iAvailable);
    gnGameRoot.iBestMove = iAvailable[0];                    // Initialize the best move.
    gnGameRoot.iMetric = 0;
    gnGameRoot.bComputerMove = true;                         // It's the computer's turn to move.

    // Start the recursive search:
    computerMove(gnGameRoot);

    cBoardConfig[gnGameRoot.iBestMove] = 'O';                // Mark an O for the computer's move.
    repaint();                                               // Show the new move by repainting.

    iStatus = evaluation(cBoardConfig);                      // Check for three in a row.
    if (iStatus != 0) bPlay = false;                         // Somebody has won.
    bThinking = false;                                       // Enable the user to input his move.
  }

  // Implements double buffering 
  public void update(Graphics g)
  {
    if (imOffScreen == null)
    {
      // Make sure the offscreen and graphics exist:
      imOffScreen = this.createImage(dApplet.width, dApplet.height);
      grOffScreen = imOffScreen.getGraphics();
      grOffScreen.clearRect(0, 0, dApplet.width, dApplet.height);
    }
    this.paint(grOffScreen);
    g.drawImage(imOffScreen, 0, 0, null);
  }

  // The applet frame painting function
  public void paint(Graphics g)
  {
    // Code for displaying images or drawing in the applet frame (called by the OS).
    g.clearRect(0, 0, dApplet.width, dApplet.height);        // Needed for double buffering.
    this.setBackground(Color.lightGray);                     // Ditto.

    drawBoard(g);                                            // Draw the board.
    drawFrame(g);                                            // Draw the frame abound the applet.
  } // End of paint()

  public boolean mouseDown(Event e, int x, int y)
  {
    int i = 0;
    int iHumanMove = 0;
    int iNumAvailable = 0;
    int iAvailable[] = new int[9];

    if (!bThinking)
    {
      if (bPlay)
      {
        if (bNewGame)
        {
          bNewGame = false;                                     // Was a new game.
          bPlay = true;                                         // Play as long as this flag is true.
          iStatus = 0;                                          // Neither side has won.
        }
        iHumanMove = getHumanMove(x, y, cBoardConfig);
        if (iHumanMove >= 0)
        {
          cBoardConfig[iHumanMove] = 'X';
          repaint();
          iNumAvailable = getAvailableMoves(cBoardConfig, iAvailable);
          if (iNumAvailable == 0)
          {
            bPlay = false;
          }
          else
          {
            tCompute = new Thread(this);
            tCompute.start();
          }
        }
      }
      else
      {
        bPlay = true;
        bNewGame = true;
        // Set the game root GameNode and board initial configuration:
        for (i = 0; i < 9; i++)
        {
          gnGameRoot.cConfig[i] = '-';                          // Hyphen represents empty square.
          cBoardConfig[i] = '-';
        }
        repaint();
      }
    }
    return true;                                                // Absorb the event.
  }

  private void drawBoard(Graphics g)
  {
    int i = 0;

    // Draw the tic-tac-toe grid:
    g.setColor(Color.black);
    g.drawLine(10, iTopRegionB, dApplet.width - 10, iTopRegionB);                  // Horizontal line.
    g.drawLine(10, iTopRegionB + 1, dApplet.width - 10, iTopRegionB + 1);          // Horizontal line.
    g.drawLine(10, iCenterYRegionB, dApplet.width - 10, iCenterYRegionB);          // Horizontal line.
    g.drawLine(10, iCenterYRegionB + 1, dApplet.width - 10, iCenterYRegionB + 1);  // Horizontal line.

    g.drawLine(iLeftRegionB, 10, iLeftRegionB, dApplet.height - 10);               // Vertictal line.
    g.drawLine(iLeftRegionB + 1, 10, iLeftRegionB + 1, dApplet.height - 10);       // Vertictal line.
    g.drawLine(iCenterXRegionB, 10, iCenterXRegionB, dApplet.height - 10);         // Vertictal line.
    g.drawLine(iCenterXRegionB + 1, 10, iCenterXRegionB + 1, dApplet.height - 10); // Vertictal line.
    // Draw the Xs and Os:
    for (i = 0; i < 9; i++)
    {
      if (cBoardConfig[i] != '-')                                 // Draw the symbol.
      {
        drawSymbol(i, g);
      }
    }
  }

  private void drawSymbol(int n, Graphics g)                      // Draw an X or an O.
  {
    int iRow = n / 3;
    int iColumn = n % 3;

    int iWidth = (iLeftRegionB * 2) / 3;
    int iHeight = (iTopRegionB * 2) / 3;

    int iCenterX = iLeftRegionB / 2 + iColumn * iLeftRegionB;
    int iCenterY = iTopRegionB / 2 + iRow * iTopRegionB;
    int iTopLeftX = iCenterX - (iWidth / 2);
    int iTopLeftY = iCenterY - (iHeight / 2);
    int iTopRightX = iCenterX + (iWidth / 2);
    int iTopRightY = iCenterY - (iHeight / 2);
    int iBottomLeftX = iCenterX - (iWidth / 2);
    int iBottomLeftY = iCenterY + (iHeight / 2);
    int iBottomRightX = iCenterX + (iWidth / 2);
    int iBottomRightY = iCenterY + (iHeight / 2);

    iWidth = 0;                                                     // Weird bug workaround. Don't ask.
    iHeight = 0;

    g.setColor(Color.black);

    if (cBoardConfig[n] == 'X')                                     // Draw an X
    {
      g.drawLine(iTopLeftX, iTopLeftY, iBottomRightX, iBottomRightY);
      g.drawLine(iBottomLeftX, iBottomLeftY, iTopRightX, iTopRightY);
    }
    else                                                            // Draw an O
    {
      g.drawOval(iTopLeftX, iTopLeftY, iBottomRightX - iTopLeftX, iBottomRightY - iTopLeftY);
    }
  }

  private void drawFrame(Graphics g)
  {
    // Draw a recessed frame around the applet border. Designed for gray-on-gray browser background.
    g.setColor(Color.black);
    g.drawLine(0, 0, dApplet.width - 1, 0);
    g.drawLine(0, 0, 0, dApplet.height - 1);
    g.setColor(Color.white);
    g.drawLine(0, dApplet.height - 1, dApplet.width - 1, dApplet.height - 1);
    g.drawLine(dApplet.width - 1, 1, dApplet.width - 1, dApplet.height - 1);
  }

  private int getHumanMove(int x, int y, char[] board)               // Turn mouse coordinates into
  {                                                                  // a board location.
    int iHumanMove = 0;
    int i = 0;
    int iNumAvailableMoves = 0;
    int iAvailable[] = new int[9];
    boolean bNotCorrect = true;
    
    if (x <= iLeftRegionB)
    {
      // Left region
      if (y <= iTopRegionB)
      {
        // Left top
        iHumanMove = 0;
      }
      else
      {
        if (y > iCenterYRegionB)
        {
          // Left bottom
          iHumanMove = 6;
        }
        else
        {
          // Left center
          iHumanMove = 3;
        }
      }
    }
    else
    {
      if (x > iCenterXRegionB)
      {
        if (y <= iTopRegionB)
        {
          // Right top
          iHumanMove = 2;
        }
        else
        {
          if (y > iCenterYRegionB)
          {
            // Right bottom
            iHumanMove = 8;
          }
          else
          {
            // Right center
            iHumanMove = 5;
          }
        }
      }
      else
      {
        // Center region
        if (y <= iTopRegionB)
        {
          // Center top
          iHumanMove = 1;
        }
        else
        {
          if (y > iCenterYRegionB)
          {
            // Center bottom
            iHumanMove = 7;
          }
          else
          {
            // Center center
            iHumanMove = 4;
          }
        }
      }
    }

    iNumAvailableMoves = getAvailableMoves(board, iAvailable);

    for (i = 0; i < iNumAvailableMoves; i++)
    {
      if ((iHumanMove) == iAvailable[i])
      {
        bNotCorrect = false;
        break;
      }
    }

    if (bNotCorrect)                            // Don't let the human input an unavailable move.
    {
      iHumanMove = -1;
    }
    return iHumanMove;
  } // End of applet function getHumanMove();

  private int getAvailableMoves(char[] cConfig, int[] iAvailable)
  {
    // The hyphen indicates an empty position.
    int iNumAvailable = 0;
    int i = 0;

    for (i = 0; i < 9; i++)
    {
      if (cConfig[i] == '-')
      {
        iAvailable[iNumAvailable] = i;
        iNumAvailable++;
      }
    }
    return iNumAvailable;
  } // End of applet function getAvailableMoves()

  // The classic min-max algorithm.
  private void computerMove(GameNode gn)
  {
    int i = 0;
    int j = 0;
    int iStatus = 0;                       // Game metric semaphore: 1 is computer won, -1 is human won.
    int iNumAvailable = 0;                 // Number of available moves (= branching factor at this node).
    int iAvailable[] = new int[9];         // Available move indices.
    int iMin = 0;
    int iMax = 0;

    iNumAvailable = getAvailableMoves(gn.cConfig, iAvailable);

    // See if the game is over
    iStatus = evaluation(gn.cConfig);

    if (iStatus != 0 || iNumAvailable == 0)           
    {
      // Game is over, bottom of tree (at a leaf). Carry the outcome back up.
      gn.iMetric = iStatus;
    }
    else 
    {
      // Game is not over, keep recursion going...
      // Construct my children:
      for (i = 0; i < iNumAvailable; i++)
      {
        gn.gnChild[i] = new GameNode();
      }

      // Spawn by recursion:
      for (i = 0; i < iNumAvailable; i++)
      {
        // Toggle the computer move flag:
        gn.gnChild[i].bComputerMove = !(gn.bComputerMove);
        gn.gnChild[i].iMetric = 0;

        // Copy the child initial board configuration from the parent:
        for (j = 0; j < 9; j++)
        {
          gn.gnChild[i].cConfig[j] = gn.cConfig[j];
        }
        // Each child makes a different available move:
        if (gn.bComputerMove)
        {
          gn.gnChild[i].cConfig[iAvailable[i]] = 'O';
        }
        else
        {
          gn.gnChild[i].cConfig[iAvailable[i]] = 'X';
        }
        // Recursion
        computerMove(gn.gnChild[i]);
      }
      // All recursion is complete now. Initialize the default best move
      gn.iBestMove = iAvailable[0];
      iMax = gn.gnChild[0].iMetric;
      iMin = gn.gnChild[0].iMetric;

      // Maximize on the computer's move, minimize on the human's move.
      if (gn.bComputerMove)
      {
        // It's the computer's move, search the children for the best outcome (1).
        for (i = 1; i < iNumAvailable; i++)
        {
          if (gn.gnChild[i].iMetric > iMax)
          {
            iMax = gn.gnChild[i].iMetric;
            gn.iBestMove = iAvailable[i];
            if (iMax == 1) break;
          }
        }
        gn.iMetric = iMax;
      }
      else
      {
        // It's the human's move, search the children for the worst outcome (-1).
        for (i = 1; i < iNumAvailable; i++)
        {
          if (gn.gnChild[i].iMetric < iMin)
          {
            iMin = gn.gnChild[i].iMetric;
            gn.iBestMove = iAvailable[i];
            if (iMin == -1) break;
          }
        }
        gn.iMetric = iMin;
      }

      // Recursion is complete and we've gathered the information: destroy the children.
      for (i = 0; i < iNumAvailable; i++)
      {
        gn.gnChild[i] = null;           // This activates the JRE garbage collector.
      }
    }
  } // End of applet function computerMove()

  // Return 1 for computer victory, -1 for human victory, 0 for neither.
  private int evaluation(char[] board)
  {
    // The game is over if there are three in a row:
    int i = 0;

    for (i = 0; i < 3; i++)
    {
      // Check for rows:
      if (board[i * 3 + 0] == 'X' && board[i * 3 + 1] == 'X'  && board[i * 3 + 2] == 'X')
      {
        // We have a row of Xs and the human wins. */
        return -1;
      }
      if (board[i * 3 + 0] == 'O' && board[i * 3 + 1] == 'O'  && board[i * 3 + 2] == 'O')
      {
        // We have a row of Os and the computer wins.
        return 1;
      }

      // Check for columns:
      if (board[0 + i] == 'X' && board[3 + i] == 'X'  && board[6 + i] == 'X')
      {
        // We have a column of Xs and the human wins.
        return -1;
      }
      if (board[0 + i] == 'O' && board[3 + i] == 'O'  && board[6 + i] == 'O')
      {
        // We have a column of Os and the computer wins.
        return 1;
      }
    }

    // Check for diagonals:
    if (board[0] == 'X' && board[4] == 'X'  && board[8] == 'X')
    {
      // We have a diagonal of Xs and the human wins.
      return -1;
    }
    if (board[2] == 'X' && board[4] == 'X'  && board[6] == 'X')
    {
      // We have a diagonal of Xs and the human wins.
      return -1;
    }
    if (board[0] == 'O' && board[4] == 'O'  && board[8] == 'O')
    {
      // We have a diagonal of Os and the computer wins.
      return 1;
    }
    if (board[2] == 'O' && board[4] == 'O'  && board[6] == 'O')
    {
      // We have a diagonal of Os and the computer wins.
      return 1;
    }

    return 0;                                          // If we're still here, nobody has won.
  } // End of function evaluation()

} // End of Applet class

class GameNode
{
  public int iMetric = 0;                              // Non-OOP for performance reasons.
  public boolean bComputerMove = false;                // Who's move is it, anyway?
  public int iBestMove = 0;                            // The best move.
  public GameNode gnChild[];                           // Game tree children array.
  public char cConfig[];                               // Board configuration for the node.

  GameNode()                                           // Constructor.
  {
    gnChild = new GameNode[9];
    cConfig = new char[9];
  }
} // End of class GameNode