Building a Smart Tic-Tac-Toe AI: The Minimax Approach

Building a Smart Tic-Tac-Toe AI: The Minimax Approach

Unveiling the Minimax Strategy: Crafting an Intelligent Tic-Tac-Toe AI for a Challenging Gaming Experience

Getting Started

In one of our engaging AI/ML classes, our professor dived into the world of the minimax algorithm, illustrating its prowess with examples from chess and various games. Intrigued by its potential, I couldn’t help but think about how this strategy could be applied in a more relatable setting. Enter Tic-Tac-Toe, a game we all know and love for its simplicity and strategy. The idea hit me — why not use minimax to create a smart Tic-Tac-Toe opponent? Fueled by this burst of inspiration, I decided to bring the concept to life and explore the magic of the minimax algorithm within the familiar boundaries of this timeless game.

What is Minimax Algorithm ?

The minimax algorithm, in a nutshell, is a decision-making strategy used in two-player games. Whether it’s chess, Tic-Tac-Toe, or other adversarial games, minimax aims to find the best possible move. The idea is to minimize potential losses while maximizing potential gains. Imagine each move as a branch on a decision tree, with the algorithm exploring all possible outcomes, assuming that the opponent plays optimally. It’s like a game of chess where you’re thinking several moves ahead to anticipate and counter your opponent’s every move. In essence, minimax is a clever way for a computer to play strategically, making it a fascinating concept in the world of game development and artificial intelligence.

Minimax algorithm explained in this image

Check out to to get directly into the code : github.com/ezhillragesh/AI-Tic-Tac-Toe

Give a Star ⭐to the Repository if you found it useful.

Setting Up the Board

Creating the foundation for our Tic-Tac-Toe game involves a few key elements: the game squares, player turns, and the game status. Let’s take a closer look:

const [squares, setSquares] = useState(Array(9).fill(null));

We track whose turn it is using the xIsNext state. If xIsNext is true, it’s the X player’s turn; otherwise, it’s the O player’s turn.

const [xIsNext, setXIsNext] = useState(true);

Handling Clicks

When a player clicks on a square, the handleClick function is called. If it’s X’s turn and the clicked square is empty, ‘X’ is placed in that square. If it’s O’s turn, the AI makes a move using the minimax algorithm.

function handleClick(i) {
  if (!xIsNext || squares[i] || calculatewinner(squares) || isBoardFull(squares)) {
    return;
  }

  const nextSquares = squares.slice();
  nextSquares[i] = 'X';
  setSquares(nextSquares);
  setXIsNext(false);
}

Game Status

The status variable displays the current game status. If there’s a winner, it announces the winner. If the game is a draw, it says so. Otherwise, it indicates the next player to move.

const winner = calculatewinner(squares);
let status;

if (winner) {
  status = 'Winner: ' + winner;
} else if (isBoardFull(squares)) {
  status = "It's a draw!";
} else {
  status = 'Next player: ' + (xIsNext ? 'X' : 'O');
}

Resetting the Game

The “Reset” button allows players to start a new game by resetting the board.

function reset() {
  setSquares(Array(9).fill(null));
  setXIsNext(true);
}

Finding the Best Move

The findBestMove function utilizes the minimax algorithm to determine the best move for the AI (represented by ‘O’).

function findBestMove(board) {
  let bestMove = -1;
  let bestScore = -Infinity;

  for (let i = 0; i < board.length; i++) {
    if (!board[i]) {
      board[i] = 'O';
      const score = minimax(board, 0, false);
      board[i] = null;

      if (score > bestScore) {
        bestScore = score;
        bestMove = i;
      }
    }
  }

  return bestMove;
}

Minimax Algorithm

The minimax function is the heart of the AI decision-making process. It recursively explores possible moves and assigns scores to determine the optimal move for both players.

function minimax(board, depth, isMaximizing) {
  const winner = calculatewinner(board);

  if (winner === 'O') {
    return 1;
  }
  if (winner === 'X') {
    return -1;
  }
  if (isBoardFull(board)) {
    return 0;
  }

  if (isMaximizing) {
    let bestScore = -Infinity;
    for (let i = 0; i < board.length; i++) {
      if (!board[i]) {
        board[i] = 'O';
        const score = minimax(board, depth + 1, false);
        board[i] = null;
        bestScore = Math.max(score, bestScore);
      }
    }
    return bestScore;
  } else {
    let bestScore = Infinity;
    for (let i = 0; i < board.length; i++) {
      if (!board[i]) {
        board[i] = 'X';
        const score = minimax(board, depth + 1, true);
        board[i] = null;
        bestScore = Math.min(score, bestScore);
      }
    }
    return bestScore;
  }
}

Deciding the Winner

The calculate winner function checks for a winner based on the predefined winning combinations.

function calculatewinner(squares) {
  const lines = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6]
  ];//all combinations of winner

  for (let i = 0; i < lines.length; i++) {
    const [a, b, c] = lines[i];
    if (squares[a] && squares[a] === squares[b] && squares[a] === squares[c]) {
      return squares[a];
    }
  }
  return null;
}

In conclusion, this blog has explored the creation of a dynamic Tic-Tac-Toe game using React, enhanced with an intelligent AI opponent powered by the minimax algorithm. The code snippets provided encapsulate the essence of a strategic and engaging gaming experience. By embedding the Gist, you can easily incorporate this robust implementation into your projects. Feel free to experiment, enhance, and share this game, and may your coding journey continue to unfold with exciting challenges and creative solutions. Happy coding! 🚀

https://gist.github.com/ezhillragesh/73f80fd5b88ecd363156e6aadbe58163

Future Ideas

In the future, I plan to enhance the efficiency of our Tic-Tac-Toe AI even further by implementing the Alpha-Beta Pruning algorithm. This optimization technique aims to reduce the number of nodes evaluated by the minimax algorithm, making our AI smarter and faster in decision-making.

Thanks for Reading.

Happy Coding!

Ezhill Ragesh

github.com/ezhillragesh

ezhillragesh@gmail.com || ragesh.me