Implementing Minimax for Tic-Tac-Toe in Rust

Tic-Tac-Toe may seem like a simple game, but developing an AI that plays optimally requires a well-defined strategy. In this post, we’ll explore how to implement the Minimax algorithm to create an AI that plays perfect Tic-Tac-Toe.

Understanding Minimax

The Minimax algorithm is a decision-making strategy used in two-player games like Tic-Tac-Toe, Chess, and Connect Four. The goal is to minimize the opponent’s best possible outcome while maximizing the AI’s best possible outcome. This approach ensures that the AI always picks the optimal move.

How Minimax Works

  1. Recursively explore all possible game states.
  2. Assign scores to terminal states:
    • +10 if the AI wins.
    • -10 if the human player wins.
    • 0 for a draw.
  3. Backtrack through the game tree, allowing the AI to select the move that maximizes its chances while minimizing the opponent’s.
  4. Repeat until an optimal move is found.

Implementing Minimax in Rust

Game State Representation

Our GameState struct represents the board as a Vec<Option<char>> where None represents an empty cell, and 'X' or 'O' represent player moves.

Minimax Implementation

Below is our Minimax implementation in Rust:

impl GameState {
    fn minimax(&self, is_maximizing: bool) -> (i32, Option<usize>) {
        if let Some(winner) = self.check_winner() {
            return match winner {
                'X' => (-10, None), // Human wins
                'O' => (10, None),  // AI wins
                _ => (0, None),    // Draw
            };
        }

        if self.board.iter().all(|&square| square.is_some()) {
            return (0, None); // Draw
        }

        let mut best_score = if is_maximizing { i32::MIN } else { i32::MAX };
        let mut best_move = None;

        for &i in &self.available_moves() {
            let mut simulated_board = self.board.clone();
            simulated_board[i] = Some(if is_maximizing { 'O' } else { 'X' });

            let simulated_state = GameState {
                board: simulated_board,
                current_player: if is_maximizing { 'X' } else { 'O' },
                difficulty: self.difficulty,
            };

            let (score, _) = simulated_state.minimax(!is_maximizing);

            if is_maximizing {
                if score > best_score {
                    best_score = score;
                    best_move = Some(i);
                }
            } else {
                if score < best_score {
                    best_score = score;
                    best_move = Some(i);
                }
            }
        }

        (best_score, best_move)
    }

}

Explanation of the Code

  • Base Case: If a terminal state (win/loss/draw) is reached, return an appropriate score.
  • Recursive Case: For each available move, simulate the next board state and call minimax on it.
  • Backtracking: If the AI is playing (is_maximizing = true), choose the move that results in the highest score. Otherwise, choose the move that minimizes the opponent’s best outcome.

Conclusion

With Minimax, our Tic-Tac-Toe AI is now unbeatable. It plays optimally, never loses, and forces a draw when no win is possible. This same algorithm can be extended to more complex games like Chess by incorporating additional optimizations like Alpha-Beta Pruning.

Source Code

You can find the complete source code on GitHub: Tic-Tac-Toe Minimax Implementation.

Let us know in the comments if you have questions or improvements. Happy coding!