Skip to content

Instantly share code, notes, and snippets.

@juaxix

juaxix/TicTacToe.java

Created June 27, 2020 20:45
Show Gist options
  • Save juaxix/a29aeb2d4099b28b2c23ae7477881269 to your computer and use it in GitHub Desktop.
Save juaxix/a29aeb2d4099b28b2c23ae7477881269 to your computer and use it in GitHub Desktop.
Download ZIP
JAVA TicTacToe
Raw
TicTacToe.java
/// juaxix - TicTacToe
/// @see https://imgur.com/a/gBmaYD4
import javax.sound.sampled.AudioInputStream;
import javax.sound.sampled.AudioSystem;
import javax.sound.sampled.Clip;
import javax.swing.*;
import java.awt.*;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.Random;
public class Game extends JPanel
{
//State definition
public static class GameState
{
String[][] board = new String[4][4];
String nextPlayer;
int value;
int depth;
GameState parentState;
public GameState(String[][] board, GameState previousState, String nextPlayer, int heuristicValue, int depth)
{
this.board = board;
this.nextPlayer = nextPlayer;
this.value = heuristicValue;
this.depth = depth;
this.parentState = previousState;
}
public GameState(String[][] board)
{
this(board, null, null, 0, 0);
}
public GameState()
{
}
}
//difficulty definition
public enum DifficultyLevels {
EASY, MEDIUM, HARD
};
//constants
private static final String CHARACTER_PLAYER = "X";
private static final String CHARACTER_AI = "O";
private static final int MAX_ALPHA_LIMIT = 1000;
private static final int MIN_ALPHA_LIMIT = -1000;
private static final int DRAW = 0;
private final static int MAX_DEPTH = 6;
private final static Font BUTTON_FONT = new Font("Arial", Font.PLAIN, 40);
//static vars
private static boolean bIsCutoff = false;
private static int cuttingWithMaxValueCount = 0;
private static int cuttingWithMinValueCount = 0;
private static int totalNodesGenerated = 0;
private static int maxDepthReached = 0;
private static DifficultyLevels difficultyLevel = DifficultyLevels.MEDIUM;
private static boolean playerTurn = false;
private static JButton buttons[][] = new JButton[4][4];
private static GameState gameState = new GameState();
private static int playerDraws = 0;
private static int aiDraws = 0;
private ArrayList<GameState> possibleNextMoves = new ArrayList<>();
public Game()
{
setLayout(new GridLayout(4, 4));
initInterface();
}
//initialize buttons 2 d array
public void initInterface()
{
playSound("tic.wav");
for (int i = 0; i <= 3; i++) {
for (int j = 0; j <= 3; j++) {
buttons[i][j] = new JButton();
buttons[i][j].setText("");
buttons[i][j].addActionListener(new CellButtonListener());
buttons[i][j].setFont(BUTTON_FONT);
buttons[i][j].setOpaque(true);
buttons[i][j].setBackground(Color.black);
// hack to get the element associate to the 2D button array
buttons[i][j].putClientProperty("index_0", new Integer(i));
buttons[i][j].putClientProperty("index_1", new Integer(j));
add(buttons[i][j]);
}
}
}
public static synchronized void playSound(final String url)
{
new Thread(() ->
{
try {
Clip clip = AudioSystem.getClip();
InputStream resourceAsStream = Game.class.getResourceAsStream("sounds/" + url);
if (resourceAsStream != null) {
AudioInputStream inputStream = AudioSystem.getAudioInputStream(resourceAsStream);
clip.open(inputStream);
clip.start();
}
else
{
System.err.println("Sound could not be found: " + url);
}
} catch (Exception e) {
e.printStackTrace();
System.err.println("Sound could not be played: " + url + " : " + e.getMessage());
}
}).start();
}
private class CellButtonListener implements ActionListener
{
public void actionPerformed(ActionEvent e)
{
JButton buttonClicked = (JButton) e.getSource(); //get the touched button
if (buttonClicked.getText().length() > 0)
{
return; //it is already used!
}
if (playerTurn)
{ //only in the player turn the button can work!
int[] playerInput = new int[2];
playerInput[0] = (int) buttonClicked.getClientProperty("index_0");
playerInput[1] = (int) buttonClicked.getClientProperty("index_1");
buttons[playerInput[0]][playerInput[1]].setText(CHARACTER_PLAYER);
buttons[playerInput[0]][playerInput[1]].setForeground(Color.BLUE);
GameState newState;
// get next state
newState = getSuccessor(gameState, playerInput);
printUpdatedBoard(newState.board);
playSound("toc.wav");
playerDraws++;
if (checkForWin(newState) == true)
{
playSound("win.wav");
JOptionPane.showMessageDialog(null, "YOU WIN", "Tic Tac Toe : Game results", JOptionPane.INFORMATION_MESSAGE);
System.out.println("You win");
} else if (isTerminalNode(newState) == true)
{
playSound("draw.wav");
JOptionPane.showMessageDialog(null, "DRAW", "Tic Tac Toe : Game results", JOptionPane.INFORMATION_MESSAGE);
System.out.println("Draw");
}
else
{
if(playerDraws==2)
{
playerDraws = 0;
aiDraws = 0;
newState.nextPlayer = CHARACTER_AI;
AIMove(newState);
}
else
{
gameState = newState;
gameState.nextPlayer = CHARACTER_PLAYER;
}
}
}
}
}
public void startMatch()
{
GameState initialState = this.initState();
printUpdatedBoard(initialState.board);
playerTurn = true;
initialState.nextPlayer = CHARACTER_PLAYER;
gameState = initialState;
showSelectDifficulty();
}
// heuristic value computation
public int heuristicComputation(GameState currentState)
{
if (checkForWin(currentState) == true)
{
if (currentState.nextPlayer.equals(CHARACTER_AI))
{
return MIN_ALPHA_LIMIT;
}
else if (currentState.nextPlayer.equals(CHARACTER_PLAYER))
{
return MAX_ALPHA_LIMIT;
}
}
return DRAW;
}
public void showSelectDifficulty()
{
String[] possibleValues = {
"Easy", "Medium", "Hard"
};
Object selectedValue = JOptionPane.showInputDialog(
null, "Choose difficulty", "Input",
JOptionPane.INFORMATION_MESSAGE, null,
possibleValues, possibleValues[0]);
switch(selectedValue.toString()){
case "Easy":
difficultyLevel = DifficultyLevels.EASY;
break;
case "Medium":
difficultyLevel = DifficultyLevels.MEDIUM;
break;
case "Hard":
difficultyLevel = DifficultyLevels.HARD;
break;
}
/*
//uncomment to choose to be playing before AI
int reply=JOptionPane.showConfirmDialog(
null,"Play first?", "choose one", JOptionPane.YES_NO_OPTION
);
if(reply==JOptionPane.YES_OPTION)
{
playerTurn=true;
init.nextPlayer ="O";
humanMoveState=rootNode;
} else{
isHumanTurn=false;
rootNode.nextPlayer ="X";
this.computerMove(rootNode);
}*/
}
// get Successor of state
public GameState getSuccessor(GameState currentState, int[] playerInput)
{
if (this.isTerminalNode(currentState) == true)
{
return null;
}
else
{
if (currentState.nextPlayer == CHARACTER_AI)
{
return new GameState(this.updateBoard(currentState, playerInput), currentState, CHARACTER_PLAYER, heuristicComputation(currentState), currentState.depth + 1);
}
else
{
return new GameState(this.updateBoard(currentState, playerInput), currentState, CHARACTER_AI, heuristicComputation(currentState), currentState.depth + 1);
}
}
}
//check for Leaf node
public boolean isTerminalNode(GameState currentState)
{
return this.checkForWin(currentState) || !(this.isEmptySquareOnBoard(currentState.board));
}
// check for win on rows, columns and diagonals
public boolean checkForWin(GameState currentState)
{
boolean isWin = false;
isWin = (this.checkForWinOnRows(currentState) ||
this.checkForWinOnColumns(currentState) ||
this.checkForWinOnDiagonals(currentState));
return isWin;
}
public boolean checkForWinOnRows(GameState currentState)
{
for (int row = 0; row < currentState.board.length; row++)
{
int timesOfNodeRepeated = 0;
String scanForElement = currentState.board[row][0];
if (scanForElement == null)
{
continue;
}
for (int column = 1; column < currentState.board.length; column++)
{
String nextString = currentState.board[row][column];
if (nextString == null)
{
break;
}
else if (scanForElement.contentEquals(nextString) == false)
{
break;
}
else
{
timesOfNodeRepeated++;
}
}
if (timesOfNodeRepeated == 3)
{
return true;
}
}
return false;
}
public boolean checkForWinOnColumns(GameState currentState)
{
for (int column = 0; column < currentState.board.length; column++)
{
int timesOfNodeRepeated = 0;
String scanForElement = currentState.board[0][column];
if (scanForElement == null) continue;
for (int row = 1; row < currentState.board.length; row++)
{
String nextString = currentState.board[row][column];
if (nextString == null)
{
break;
}
else if (scanForElement.contentEquals(nextString) == false)
{
break;
}
else
{
timesOfNodeRepeated++;
}
}
if (timesOfNodeRepeated == 3)
{
return true;
}
}
return false;
}
public boolean checkForWinOnDiagonals(GameState currentState)
{
String[][] aBoard = currentState.board;
boolean isWinOnLeftDiagonal = false, isWinOnRightDiagonal = false;
if (aBoard[0][0] != null && aBoard[1][1] != null && aBoard[2][2] != null && aBoard[3][3] != null)
{
isWinOnLeftDiagonal = this.checkWinOnLeftDiagonal(currentState);
}
if (aBoard[3][0] != null && aBoard[0][3] != null && aBoard[2][1] != null && aBoard[1][2] != null)
{
isWinOnRightDiagonal = this.checkWinOnRightDiagonal(currentState);
}
return isWinOnLeftDiagonal || isWinOnRightDiagonal;
}
public boolean checkWinOnLeftDiagonal(GameState currentState)
{
String[][] aBoard = currentState.board;
return (aBoard[1][1].contentEquals(aBoard[0][0]) &&
aBoard[1][1].contentEquals(aBoard[2][2]) &&
aBoard[2][2].contentEquals(aBoard[3][3]));
}
public boolean checkWinOnRightDiagonal(GameState currentState)
{
String[][] aBoard = currentState.board;
return (aBoard[3][0].contentEquals(aBoard[2][1]) &&
aBoard[2][1].contentEquals(aBoard[1][2]) &&
aBoard[1][2].contentEquals(aBoard[0][3]));
}
// check for empty squares on board , return boolean
public boolean isEmptySquareOnBoard(String[][] board)
{
boolean isEmptySquareOnBoard = false;
int boardSize = board.length;
for (int row = 0; row < boardSize; row++)
{
if (isEmptySquareOnBoard)
{
break;
}
for (int column = 0; column < boardSize; column++)
{
if (board[row][column] == null)
{
isEmptySquareOnBoard = true;
break;
}
}
}
return isEmptySquareOnBoard;
}
// return all empty squares location on board
public ArrayList<int[]> scanAllEmptySquareOnBoard(GameState currentNode)
{
int boardSize = currentNode.board.length;
ArrayList<int[]> anArrayList = new ArrayList<int[]>();
for (int row = 0; row < boardSize; row++)
{
for (int column = 0; column < boardSize; column++)
{
if (currentNode.board[row][column] == null)
{
int[] arrayInput = new int[2];
arrayInput[0] = row;
arrayInput[1] = column;
anArrayList.add(arrayInput);
}
}
}
return anArrayList;
}
// update board according to given input
public String[][] updateBoard(GameState currentState, int[] emptySquareOnBoard)
{
String[][] newBoard = this.replicateBoard(currentState.board);
newBoard[emptySquareOnBoard[0]][emptySquareOnBoard[1]] = currentState.nextPlayer;
return newBoard;
}
// copy board
public String[][] replicateBoard(String[][] board)
{
int boardSize = board.length;
String[][] newBoard = new String[boardSize][boardSize];
for (int row = 0; row < boardSize; row++)
{
for (int column = 0; column < boardSize; column++)
newBoard[row][column] = board[row][column];
}
return newBoard;
}
// AI move - execute the search algo for the difficulty level chosen
public void AIMove(GameState currentState)
{
playerTurn = false;
GameState newState = this.initializeStateWithBoard(currentState.board);
newState = this.nextStateToMove(newState);
printStatistics();
aiDraws++;
this.printUpdatedBoard(newState.board);
if (this.checkForWin(newState) == true)
{
playSound("lost.wav");
JOptionPane.showMessageDialog(null, "AI Won", "Game results", JOptionPane.INFORMATION_MESSAGE);
System.out.println("AI won!");
} else if (this.isTerminalNode(newState) == true)
{
playSound("draw.wav");
JOptionPane.showMessageDialog(null, "The game is draw", "Game results", JOptionPane.INFORMATION_MESSAGE);
System.out.println("The game is draw");
} else {
if(aiDraws==2)
{
playerTurn = true;
gameState = newState;
playSound("tic.wav");
}
else
{
gameState = newState;
gameState.nextPlayer = CHARACTER_AI;
printUpdatedBoard(gameState.board);
AIMove(gameState);
}
}
}
// Determine next state for move
public GameState nextStateToMove(GameState currentState)
{
GameState newState = new GameState();
int numberOfEmptySquares = scanAllEmptySquareOnBoard(currentState).size();
ArrayList<GameState> successors = new ArrayList<GameState>();
// Only 1 square is left. No need of applying alpha beta
if (numberOfEmptySquares == 1)
{
successors = this.getAllSuccessors(currentState);
totalNodesGenerated += 1;
maxDepthReached += 1;
newState = successors.get(0);
}
// every square is empty or initial state. Assign random position for move
else if (numberOfEmptySquares == 16)
{
successors = this.getAllSuccessors(currentState);
Random r = new Random();
totalNodesGenerated += 16;
maxDepthReached += 1;
newState = successors.get(r.nextInt(16));
}
else
{
maxDepthReached = currentState.depth;
if (difficultyLevel == DifficultyLevels.EASY)
{
successors = this.getAllSuccessors(currentState);
Random r = new Random();
int numberOfSuccessors = successors.size();
totalNodesGenerated += numberOfSuccessors;
newState = successors.get(r.nextInt(numberOfSuccessors));
}
else
{
// apply alpha beta algorithm and store states. Then choose the Max Node in list
currentState.value = this.alphaBetaSearch(currentState, MIN_ALPHA_LIMIT, MAX_ALPHA_LIMIT);
newState = (this.possibleNextMoves.size() > 0) ? this.getMaxNodeInList(this.possibleNextMoves) : getAllSuccessors(currentState).get(0);
this.possibleNextMoves.clear();
}
}
return newState;
}
// From a set of states , choose node with maximum heuristic value
public GameState getMaxNodeInList(ArrayList<GameState> states)
{
GameState maxNode = states.get(0);
int listSize = states.size();
for (int index = 0; index < listSize; index++)
{
if (maxNode.value < states.get(index).value)
{
maxNode = states.get(index);
}
}
return maxNode;
}
// Evaluation function executed on cutoff
public int evaluationFunction(GameState state)
{
// Eval(s)= 6X3 + 3X2 + X1 - ( 6O3 + 3O2+ O1)
// X n is the number of rows, columns, or diagonals with exactly n X 's
// and no O’s. Similarly, On is the number of rows, columns, or diagonals with just n O’s
int[] xArray = {0, 0, 0, 0};
int[] oArray = {0, 0, 0, 0};
int xCounter = 0, oCounter = 0;
bIsCutoff = true;
String[][] board = state.board;
for (int row = 0; row < board.length; row++)
{
xCounter = 0;
oCounter = 0;
for (int column = 0; column < board.length; column++)
{
if (board[row][column] == CHARACTER_AI)
{
xCounter = xCounter + 1;
}
else if (board[row][column] == CHARACTER_PLAYER)
{
oCounter = oCounter + 1;
}
}
if (xCounter == 0 && oCounter != 0)
{
oArray[oCounter] += 1;
}
if (xCounter != 0 && oCounter == 0)
{
xArray[xCounter] += 1;
}
}
for (int column = 0; column < board.length; column++)
{
xCounter = 0;
oCounter = 0;
for (int row = 0; row < board.length; row++)
{
if (board[column][row] == CHARACTER_AI)
{
xCounter = xCounter + 1;
}
else if (board[column][row] == CHARACTER_PLAYER)
{
oCounter = oCounter + 1;
}
}
if (xCounter == 0 && oCounter != 0)
{
oArray[oCounter] += 1;
}
if (xCounter != 0 && oCounter == 0)
{
xArray[xCounter] += 1;
}
}
for (int row = 0; row < board.length; row++)
{
xCounter = 0;
oCounter = 0;
for (int column = 0; column < board.length; column++)
{
if (row == column)
{
if (board[row][column] == CHARACTER_AI)
{
xCounter = xCounter + 1;
}
else if (board[row][column] == CHARACTER_PLAYER)
{
oCounter = oCounter + 1;
}
}
}
if (xCounter == 0 && oCounter != 0)
{
oArray[oCounter] += 1;
}
if (xCounter != 0 && oCounter == 0)
{
xArray[xCounter] += 1;
}
}
for (int row = 0; row < board.length; row++)
{
xCounter = 0;
oCounter = 0;
for (int column = 0; column < board.length; column++)
{
if (row == 3 - column)
{
if (board[row][column] == CHARACTER_AI)
{
xCounter = xCounter + 1;
}
else if (board[row][column] == CHARACTER_PLAYER)
{
oCounter = oCounter + 1;
}
}
}
if (xCounter == 0 && oCounter != 0)
{
oArray[oCounter] += 1;
}
if (xCounter != 0 && oCounter == 0)
{
xArray[xCounter] += 1;
}
}
if (difficultyLevel == DifficultyLevels.HARD)
{
state.value = 6 * (xArray[2] - oArray[2]) +
(xArray[1] - oArray[1]) *3 +
(xArray[0] - oArray[0]);
} else
{
state.value = 3 * (oArray[0] + oArray[1] + oArray[2]) - 2 * (xArray[0] + xArray[2] + xArray[1]);
}
return state.value;
}
// MAX-VALUE FUNCTION
public int maxValue(GameState state, int alpha, int beta, long time)
{
// Calculate MAX DEPTH reached
if (maxDepthReached < state.depth)
{
maxDepthReached = state.depth;
}
// Check for terminal node and return heuristic
if (isTerminalNode(state))
{
return this.heuristicComputation(state);
}
long timeLimit = 6000;
if (difficultyLevel == DifficultyLevels.MEDIUM)
{
timeLimit = 1000;
}
// depth cutoff level =6
if ((System.currentTimeMillis() - time) > timeLimit || state.depth > MAX_DEPTH)
{
return this.evaluationFunction(state);
}
state.value = MIN_ALPHA_LIMIT;
ArrayList<GameState> allSuccessors = this.getAllSuccessors(state);
totalNodesGenerated = totalNodesGenerated + allSuccessors.size();
for (int successorIndex = 0; successorIndex < allSuccessors.size(); successorIndex++)
{
GameState successor = allSuccessors.get(successorIndex);
state.value = Math.max(state.value, minValue(successor, alpha, beta, time));
if (state.value > beta)
{
cuttingWithMaxValueCount += 1;
return state.value;
}
alpha = Math.max(alpha, state.value);
}
// add state to list of possible next moves
if (this.nextMoveStates(state) != null)
{
possibleNextMoves.add(state);
}
return state.value;
}
// MIN VALUE function
public int minValue(GameState state, int alpha, int beta, long time)
{
if (maxDepthReached < state.depth)
{
maxDepthReached = state.depth;
}
if (isTerminalNode(state))
{
return this.heuristicComputation(state);
}
long timeLimit = 6000;
if (difficultyLevel == DifficultyLevels.MEDIUM)
{
timeLimit = 1000;
}
if ((System.currentTimeMillis() - time) > timeLimit || state.depth > MAX_DEPTH)
{
return evaluationFunction(state);
}
state.value = MAX_ALPHA_LIMIT;
ArrayList<GameState> allSuccessors = this.getAllSuccessors(state);
totalNodesGenerated = totalNodesGenerated + allSuccessors.size();
for (int successorIndex = 0; successorIndex < allSuccessors.size(); successorIndex++)
{
GameState successor = allSuccessors.get(successorIndex);
state.value = Math.min(state.value, maxValue(successor, alpha, beta, time));
if (state.value < alpha)
{
cuttingWithMinValueCount += 1;
return state.value;
}
beta = Math.min(beta, state.value);
}
if (this.nextMoveStates(state) != null)
{
possibleNextMoves.add(state);
}
return state.value;
}
// call maxValue function
public int alphaBetaSearch(GameState currentNode, int alpha, int beta)
{
long start_time = System.currentTimeMillis();
return this.maxValue(currentNode, alpha, beta, start_time);
}
// Get next move
public GameState nextMoveStates(GameState currentNode)
{
if (currentNode.depth == 1)
{
return currentNode;
}
else
{
return null;
}
}
// get All successor of node
public ArrayList<GameState> getAllSuccessors(GameState currentState) {
ArrayList<GameState> allSuccessors = new ArrayList<GameState>();
ArrayList<int[]> emptySquaresOnBoard = this.scanAllEmptySquareOnBoard(currentState);
int numberOfEmptySquareOnBoard = emptySquaresOnBoard.size();
for (int i = 0; i < numberOfEmptySquareOnBoard; i++)
{
allSuccessors.add(this.getSuccessor(currentState, emptySquaresOnBoard.get(i)));
}
return allSuccessors;
}
public GameState initializeStateWithBoard(String[][] board)
{
GameState state = new GameState();
state.board = board;
state.nextPlayer = CHARACTER_AI;
return state;
}
// print board
public void printUpdatedBoard(String[][] board)
{
int boardSize = board.length;
System.out.println("Board :");
System.out.println();
for (int row = 0; row < boardSize; row++)
{
System.out.print("|");
for (int column = 0; column < boardSize; column++)
{
if (board[row][column] == null)
{
System.out.print(" " + " |");
buttons[row][column].setText("");
}
else
{
System.out.print(" " + board[row][column] + " |");
buttons[row][column].setText(board[row][column]);
buttons[row][column].setForeground(
board[row][column].equals(CHARACTER_PLAYER)
? Color.CYAN
: Color.RED
);
}
}
System.out.println();
System.out.print("-----------------");
System.out.println();
}
}
// print statistics
public void printStatistics()
{
System.out.println("Game Search Statistics :");
if (bIsCutoff)
{
System.out.println("Cutoff occurred");
bIsCutoff = false;
}
System.out.println("Maximum depth reached : " + maxDepthReached);
System.out.println("Total nodes generated : " + totalNodesGenerated);
System.out.println("Number of times cutting with MAX_VALUE function : " + cuttingWithMaxValueCount);
System.out.println("Number of times cutting with MIN_VALUE function : " + cuttingWithMinValueCount);
}
public GameState initState()
{
return new GameState();
}
public static void main(String args[])
{
Game game = new Game();
JFrame window = new JFrame("juaxix - TicTacToe 4x4");
window.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
window.getContentPane().add(game);
window.setBounds(333, 222, 333, 222);
window.setVisible(true);
game.startMatch();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment