TicTocToe with Minimax_Algorithm AI

Hello! This is a simple console based TicTocToe game. You can play with Minimax Algorithm AI.

Prerequisites

• Docker

Running the Project

To run this project using Docker, follow the steps below:

Clone the Repository and run docker commands

git clone https://github.com/Keizo410/TicTacToe_AI.git
cd tictactoe
docker build -t tictactoe .
docker run -it --rm tictactoe

Implementation

How to calculate Heuristics:

Thanks to the simplicity and limited state space of this game nature, heuristics is simple enough to be calculated just based on either win or lose. If we won, +10. Tie means 0. Lose -10.

TicTacToe_AI/Player_AI.java

Lines 17 to 27 in 8c17966

	public int score(String winner) {
	int score = -100;
	if (winner.equals(" X ")) {
	score = 10;
	} else if (winner.equals(" O ")) {
	score = -10;
	} else if (winner.equals("tie")) {
	score = 0;
	}
	return score;
	}

How to initiate the minimax algorithm:

This method is sometimes called decision function, which literally decides which action to be taken for AI player side.

TicTacToe_AI/Player_AI.java

Lines 29 to 55 in 1711fb4

	public int[] bestmove(TicTacPho game) {
	int bestscore = (int) Double.NEGATIVE_INFINITY;
	int[] bestmove = null;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	if (game.board[i][j] == null) {
	// myturn, and next turn will be opponent, so it is not maximizing -> false
	// if ai is second player, change score reverse, isMaximizing true, game playAI
	// to "O"
	game.playAI(i, j, " X ");
	int score = minimax(game, 0, false);
	System.out.println(score);
	game.board[i][j] = null;
	if (score > bestscore) {
	bestscore = score;
	bestmove = new int[] { i, j };
	}
	}
	}
	}
	return bestmove;
	}

How MinMax algorithm Works:

There are several ways to implement minmax algorithm. Some people creates 2 different function min and max for simulating the state each other. For this implementation, I used isMaximizing parameter to identify which player's turn this is. Important: You have to adjust the decision, heuristics, recusive call parameters depend on which player is responsible for the FIRST move. If this was not properly implemented, AI player chooses self-destructive move. On this implementation, AI is assumed to be the first move player, which means isMaximizing should be set to be FALSE in the decision method above as we start simulating the second player's move.

TicTacToe_AI/Player_AI.java

Lines 57 to 95 in ab1003e

	public int minimax(TicTacPho game, int depth, boolean isMaximizing) {
	String result = game.checkWinner(game.board);
	int score;
	if (result != null) {
	return this.score(result);
	}
	if (isMaximizing) {
	int bestscore = (int) Double.NEGATIVE_INFINITY;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	if (game.isAvailable(i, j)) {
	game.playAI(i, j, " X ");
	score = minimax(game, depth + 1, false);
	game.board[i][j] = null;
	bestscore = Math.max(score, bestscore);
	}
	}
	}
	return bestscore;
	} else {
	int bestscore = (int) Double.POSITIVE_INFINITY;
	for (int i = 0; i < 3; i++) {
	for (int j = 0; j < 3; j++) {
	if (game.isAvailable(i, j)) {
	game.playAI(i, j, " O ");
	score = minimax(game, depth + 1, true);
	game.board[i][j] = null;
	bestscore = Math.min(score, bestscore);
	}
	}
	}
	return bestscore;
	}
	}

These state space search AI for game playing is heavily based on how the game is implemented. TicTacToe is fairly simple and fun to program for beginners like me:)

Enjoy!