Tic-Tac-Toe V. Click on the board buttons to play...
package ttt;
import java.awt.*;
import java.awt.event.*;
/**
* Encapsulates a trivial message box.
*/
public class MessageBox extends Frame implements ActionListener
{
private static final int W = 200;
private static final int H = 150;
Button b = new Button("OK");
tttFrame tf = null;
public MessageBox(String title, String message, tttFrame tf)
{
super(title);
this.tf = tf;
int w = Toolkit.getDefaultToolkit().getScreenSize().width;
int h = Toolkit.getDefaultToolkit().getScreenSize().height;
int x = (w - W) / 2;
int y = (h - H) / 2;
setBounds(x, y, W, H);
setResizable(false);
setLayout(new BorderLayout());
Panel p = new Panel(new FlowLayout(FlowLayout.CENTER));
p.add(new Label(message), BorderLayout.CENTER);
Panel bWrap = new Panel(new FlowLayout(FlowLayout.CENTER));
bWrap.add(b);
b.addActionListener(this);
add(p, BorderLayout.CENTER);
add(bWrap, BorderLayout.SOUTH);
// closing of the frame
this.addWindowListener(
new WindowAdapter()
{
public void windowClosing(WindowEvent we)
{
MessageBox.this.dispose();
}
}
);
show();
}
public void actionPerformed(ActionEvent ae)
{
dispose();
tf.restart();
}
}
/**
*
*
*
*
*
*
*
*
*/
package ttt;
import java.applet.*;
import java.awt.*;
/**
* Tic-Tac-Toe Applet
*
* @since 01/11/2003
* @version 1.0
*
*/
public class tttApplet extends Applet
{
public static final String VERSION = "1.0";
/**
* This class can be used as a main clas of the application
*/
public static void main(String[] a)
{
new tttFrame();
}
/**
* Also, this class can be used as the entry point to an applet
*/
public void init()
{
new tttFrame();
}
}
package ttt;
public class tttBoard
{
public int[][] board = new int[3][3]; // the board
public int rowPlayed = -1;
public int colPlayed = -1;
/**
* Default constructor
*/
public tttBoard() { ; }
/**
* Constructor that takes a board
*/
public tttBoard(tttBoard currBoard)
{
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
{
board[i][j] = currBoard.board[i][j];
}
}
/**
* Exact evaluation function.
* @return 1 for win, -1 for loss and 0 for draw
*/
public int getBoardEval(int player)
{
if(player == tttEngine.X)
{
if(vertical3(tttEngine.X) || horizontal3(tttEngine.X) || diagonal3(tttEngine.X)) return 1;
else if(vertical3(tttEngine.O) || horizontal3(tttEngine.O) || diagonal3(tttEngine.O)) return -1;
else return 0;
}
else if(player == tttEngine.O)
{
if(vertical3(tttEngine.O) || horizontal3(tttEngine.O) || diagonal3(tttEngine.O)) return 1;
else if(vertical3(tttEngine.X) || horizontal3(tttEngine.X) || diagonal3(tttEngine.X)) return -1;
else return 0;
}
else throw new IllegalArgumentException("what?");
}
/**
* Checks the vertical 3 in a row
*/
public boolean vertical3(int i)
{
if(board[0][0] == i && board[0][1] == i && board[0][2] == i ||
board[1][0] == i && board[1][1] == i && board[1][2] == i ||
board[2][0] == i && board[2][1] == i && board[2][2] == i) return true;
else return false;
}
/**
* Checks the horizontal 3 in a row
*/
public boolean horizontal3(int i)
{
if(board[0][0] == i && board[1][0] == i && board[2][0] == i ||
board[0][1] == i && board[1][1] == i && board[2][1] == i ||
board[0][2] == i && board[1][2] == i && board[2][2] == i) return true;
else return false;
}
/**
* Checks the diagonals for 3 in a row
*/
public boolean diagonal3(int i)
{
if(board[0][0] == i && board[1][1] == i && board[2][2] == i ||
board[0][2] == i && board[1][1] == i && board[2][0] == i) return true;
else return false;
}
/**
* Dumps board to log (used for debug)
*/
public void dumpBoardToLog(tttFrame f)
{
for(int i=0; i<3; i++) f.log("" + board[i][0] + "" + board[i][1] + "" + board[i][2]);
}
}
package ttt;
import java.awt.*;
import java.util.*;
public class tttEngine
{
// internal statics
private static final int EMPTY = 0; // empty field
public static final int X = 1; // "X" piece
public static final int O = 2; // "O" piece
private static final int DEPTH = 8; // depth of search tree
private tttFrame f;
// game states
public static final int COMPUTER_WON = 0;
public static final int USER_WON = 1;
public static final int DRAW = 2;
public static final int KEEP_PLAYING = 3;
// other internal variables
public tttBoard board = null; // the board
public boolean computerFirst = false; // whether computer played first or not
public int moveCounter = 1; // the current move
public int gameState = -1; // the state of the game
int pruned = 0; // how many branches did we prune in a move
/**
* The constructor
*/
public tttEngine(tttFrame f)
{
board = new tttBoard();
this.f = f;
}
/**
* Resets the board
*/
public void resetBoard()
{
board = new tttBoard();
moveCounter = 1;
}
/**
* User's move implementation
* Updates the game state
* @return true if the move was valid
*/
public boolean play(int field)
{
int i = field / 3;
int j = field - 3 * i;
if(board.board[i][j] == EMPTY)
{
board.board[i][j] = getUserPiece();
moveCounter++;
updateGameState();
return true;
}
else return false;
}
/**
* Computer's move implementation
* Updates the game state
*/
public void play()
{
// the very first move is a special one
if(moveCounter == 1 ||
moveCounter == 2 && board.board[1][1] == EMPTY)
{
board.board[1][1] = getComputerPiece();
moveCounter++;
updateGameState();
return;
}
pruned = 0;
// find all successors to the current position
Vector v = getAllSuccessors(board, getComputerPiece());
if(v.size() != 0)
{
// find which one of them has the minimum value (these values will be computed by alpha-beta)
int min = alphaBeta((tttBoard)v.elementAt(0), -1, 1, getUserPiece());
tttBoard nextBestMinBoard = (tttBoard)v.elementAt(0);
for(int i=1; i<v.size(); i++)
{
int temp = alphaBeta((tttBoard)v.elementAt(i), -1, 1, getUserPiece());
if(min > temp)
{
min = temp;
nextBestMinBoard = (tttBoard)v.elementAt(i);
}
}
// play there
board.board[nextBestMinBoard.rowPlayed][nextBestMinBoard.colPlayed] = getComputerPiece();
moveCounter++;
if(f.alphaBetaCB.getState()) f.log("Alpha-Beta pruned " + pruned + " game tree branch(es)");
}
updateGameState();
}
/**
* Return all immediate successors from a given position
*/
private Vector getAllSuccessors(tttBoard b, int player)
{
if(b.horizontal3(player) || b.vertical3(player) || b.diagonal3(player)) return new Vector();
int invert = player == O ? X : O;
if(b.horizontal3(invert) || b.vertical3(invert) || b.diagonal3(invert)) return new Vector();
Vector v = new Vector();
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
if(b.board[i][j] == EMPTY)
{
tttBoard newBoard = new tttBoard(b);
newBoard.rowPlayed = i;
newBoard.colPlayed = j;
newBoard.board[i][j] = player;
v.addElement(newBoard);
}
}
}
return v;
}
private int alphaBeta(tttBoard b, int alpha, int beta, int player)
{
int maxValue, value;
// determine all successors of the current position
Vector successors = getAllSuccessors(b, player);
// if there are no successors, the alpha-beta value is trivial
if(successors.size() == 0) return b.getBoardEval(player);
// trivial max value
maxValue = alpha;
// for all successors, call the alphaBeta recursively
for(int i=0; i<successors.size(); i++)
{
// call recursively with inverted values (MAX becomes MIN and MIN becomes MAX)
value = -alphaBeta((tttBoard)successors.elementAt(i), -beta, -maxValue, player == X ? O : X);
// if the value found is greater than the current value, use it
if(value > maxValue) maxValue = value;
// pruning happens here! (if maxValues is greater than upper bound, no need to search further!)
if(maxValue >= beta && f.alphaBetaCB.getState())
{
pruned++;
break;
}
}
return maxValue;
}
/**
* Returns the internal representation of computer's piece
*/
public int getComputerPiece()
{
return computerFirst ? X : O;
}
/**
* Returns the internal representation of user's piece
*/
public int getUserPiece()
{
return computerFirst ? O : X;
}
/**
* Returns the representaion of the piece on the board
*/
public String getPieceGUI(int i)
{
switch(i)
{
case X : return "X";
case O : return "O";
default : return "";
}
}
/**
* Getter for the gameState
*/
public int getGameState()
{
return gameState;
}
/**
* Updates the game state
*/
private void updateGameState()
{
if(moveCounter < 5)
{
gameState = KEEP_PLAYING;
return;
}
if(board.vertical3(getComputerPiece()) ||
board.horizontal3(getComputerPiece()) ||
board.diagonal3(getComputerPiece()))
{
gameState = COMPUTER_WON;
return;
}
if(board.vertical3(getUserPiece()) ||
board.horizontal3(getUserPiece()) ||
board.diagonal3(getUserPiece()))
{
gameState = USER_WON;
return;
}
if(moveCounter < 10) gameState = KEEP_PLAYING;
else gameState = DRAW;
}
}
package ttt;
import java.awt.*;
import java.awt.event.*;
/**
* Frame to encapsulate the GUI for the game
*/
public class tttFrame extends Frame implements ActionListener, ItemListener
{
// GUI appearance
private static final int FRAME_W = 520;
private static final int FRAME_H = 560;
private static final String BOARD_FONT = "monospaced";
private static final int BOARD_FONT_SIZE = 60;
// GUI variables
private TextArea status = null;
private Button restartButton = new Button("Restart Game");
public Checkbox alphaBetaCB = new Checkbox("Alpha-Beta", true);
private Checkbox playsFirstCB = new Checkbox("Computer Plays First");
private Checkbox logCB = new Checkbox("Logging", true);
private Panel statusPanelWrap = null;
private Button buttons[][] = null;
// internal variables
public boolean minimax = false;
public boolean alphaBeta = false;
private tttEngine engine = null;
/**
* The constructor
*/
public tttFrame()
{
super();
engine = new tttEngine(this);
initGUI();
pack();
show();
log("Program started");
restart();
}
/**
* Inits the GUI
*/
private void initGUI()
{
int w = Toolkit.getDefaultToolkit().getScreenSize().width;
int h = Toolkit.getDefaultToolkit().getScreenSize().height;
int x = (w - FRAME_W) / 2;
int y = (h - FRAME_H) / 2;
setBounds(x, y, FRAME_W, FRAME_H);
setTitle("Tic-Tac-Toe by Mihailo Despotovic");
setLayout(new BorderLayout());
Panel controlPanel = new Panel();
controlPanel.setLayout(new GridLayout(0, 1));
controlPanel.add(new Panel());
controlPanel.add(alphaBetaCB);
controlPanel.add(new Panel());
controlPanel.add(playsFirstCB);
controlPanel.add(new Panel());
controlPanel.add(new Panel());
controlPanel.add(new Panel());
controlPanel.add(logCB);
controlPanel.add(new Panel());
Panel temp = new Panel();
temp.add(restartButton);
controlPanel.add(temp);
controlPanel.add(new Panel());
Panel controlPanelWrap = new Panel(new BorderLayout());
controlPanelWrap.add(new Panel(), BorderLayout.WEST);
controlPanelWrap.add(controlPanel, BorderLayout.CENTER);
controlPanelWrap.add(new Panel(), BorderLayout.EAST);
Panel boardPanel = new Panel(new GridLayout(3, 3))
{
public Dimension getPreferredSize()
{
return new Dimension(350, 350);
}
};
buttons = new Button[3][3];
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
Button b = new Button();
int buttonId = i * 3 + j;
b.addActionListener(this);
b.setActionCommand("" + buttonId);
b.setBackground(Color.white);
b.setFont(new Font(BOARD_FONT, Font.BOLD, BOARD_FONT_SIZE));
boardPanel.add(b);
buttons[i][j] = b;
}
}
Panel boardPanelWrap = new Panel(new BorderLayout());
boardPanelWrap.add(boardPanel, BorderLayout.CENTER);
boardPanelWrap.add(new Panel(), BorderLayout.SOUTH);
boardPanelWrap.add(new Panel(), BorderLayout.WEST);
boardPanelWrap.add(new Panel(), BorderLayout.NORTH);
boardPanelWrap.add(new Panel(), BorderLayout.EAST);
Panel statusPanel = new Panel();
statusPanel.setLayout(new BorderLayout());
status = new TextArea(8, 60);
statusPanel.add(status, BorderLayout.CENTER);
statusPanelWrap = new Panel(new BorderLayout());
statusPanelWrap.add(statusPanel, BorderLayout.CENTER);
statusPanelWrap.add(new Panel(), BorderLayout.NORTH);
statusPanelWrap.add(new Panel(), BorderLayout.SOUTH);
statusPanelWrap.add(new Panel(), BorderLayout.WEST);
statusPanelWrap.add(new Panel(), BorderLayout.EAST);
Panel infoPanel = new Panel(new FlowLayout(FlowLayout.CENTER));
infoPanel.add(new Label("Tic-Tac-Toe V" + tttApplet.VERSION + ". Click on the board buttons to play..."));
add(infoPanel, BorderLayout.NORTH);
add(controlPanelWrap, BorderLayout.EAST);
add(boardPanelWrap, BorderLayout.CENTER);
add(statusPanelWrap, BorderLayout.SOUTH);
refreshLogging();
// closing of the frame
this.addWindowListener(
new WindowAdapter()
{
public void windowClosing(WindowEvent we)
{
tttFrame.this.dispose();
}
}
);
// add listeners
restartButton.addActionListener(this);
alphaBetaCB.addItemListener(this);
playsFirstCB.addItemListener(this);
logCB.addItemListener(this);
}
/**
* Deals with the buttons
*/
public void actionPerformed(ActionEvent ae)
{
Object src = ae.getSource();
String cmd = ae.getActionCommand();
if(src.equals(restartButton))
{
restart();
}
else // board fields
{
if(engine.play(Integer.parseInt(cmd)))
{
updateBoard();
if(gameFinished()) return;
log("Computer is playing move " + engine.moveCounter);
engine.play(); // computer
updateBoard();
if(gameFinished()) return;
if(engine.moveCounter < 10) log("Waiting for user to play move " + engine.moveCounter);
if(engine.moveCounter > 9)
{
log("Board is full");
restart();
}
}
}
}
/**
* Deals with the checkboxes
*/
public void itemStateChanged(ItemEvent ie)
{
Object src = ie.getSource();
if(src.equals(playsFirstCB))
{
engine.computerFirst = playsFirstCB.getState();
log("Computer plays first: " + (engine.computerFirst ? "yes" : "no"));
if(engine.moveCounter == 1) restart();
}
else if(src.equals(alphaBetaCB))
{
alphaBeta = alphaBetaCB.getState();
log("Alpha-Beta is now " + (alphaBeta ? "on" : "off"));
}
else if(src.equals(logCB))
{
refreshLogging();
}
}
private void refreshLogging()
{
statusPanelWrap.setVisible(logCB.getState());
pack();
}
/**
* Restarts the game
*/
protected void restart()
{
boolean backupFirst = engine.computerFirst;
engine = new tttEngine(this);
engine.computerFirst = backupFirst;
updateBoard();
if(engine.computerFirst)
{
log("Computer is playing move " + engine.moveCounter);
engine.play();
updateBoard();
log("Waiting for user to play move " + engine.moveCounter);
}
else log("Waiting for user to play move " + engine.moveCounter);
}
/**
* Updates the board
*/
private void updateBoard()
{
for(int i=0; i<3; i++)
{
for(int j=0; j<3; j++)
{
String piece = engine.getPieceGUI(engine.board.board[i][j]);
buttons[i][j].setForeground(piece.equals("X") ? Color.blue : Color.red);
buttons[i][j].setLabel(piece);
buttons[i][j].invalidate();
}
}
repaint();
}
/**
* Check if the game is finished.
* Might restart the game as a side effect.
*/
private boolean gameFinished()
{
switch(engine.getGameState())
{
case tttEngine.COMPUTER_WON :
{
displayWin("COMP");
return true;
}
case tttEngine.USER_WON :
{
displayWin("USER");
return true;
}
case tttEngine.DRAW :
{
displayDraw();
return true;
}
case tttEngine.KEEP_PLAYING :
{
return false;
}
default :
{
// should never happen...
log("What?");
return false;
}
}
}
/**
* Displays won message
*/
private void displayWin(String who)
{
String msg = who.equals("USER") ? "You" : "Computer";
msg += " won the game";
log(msg);
new MessageBox("The End", msg, this);
}
/**
* Displaus draw message
*/
private void displayDraw()
{
String msg = "No winner";
log(msg);
new MessageBox("The End", msg, this);
}
/**
* Appends a string to the status
* Works only if the logging is ON
*/
public void log(String s)
{
if(logCB.getState())
{
status.append(s + ".\n");
status.setCaretPosition(status.getText().length());
//System.out.println(s);
}
}
}