Skip to content
TheChatArchiveThe Chat Archive
o1-preview-2024-09-12· OpenAIAi2 WildChat-4.8M (AI2)

How to create an AI model that does tic tac toe VERY WELL in python

  1. User

    How to create an AI model that does tic tac toe VERY WELL in python

  2. Assistant

    Creating an AI that plays Tic Tac Toe flawlessly in Python is an excellent way to learn about game algorithms and artificial intelligence principles. Since Tic Tac Toe is a relatively simple game with a finite number of possible states, it's an ideal candidate for implementing the Minimax algorithm, which allows the AI to make optimal moves.

    In this guide, we'll walk through how to build a Tic Tac Toe AI that plays optimally using Python. We'll cover:

    1. Understanding the Minimax algorithm.
    2. Representing the game state.
    3. Implementing the Minimax algorithm.
    4. Adding an AI to play against a human.

    Let's get started!


    1. Understanding the Minimax Algorithm

    The Minimax algorithm is a recursive or backtracking algorithm used in decision-making and game theory to find the optimal move for a player, assuming that the opponent also plays optimally.

    • Maximizing Player: The AI tries to maximize its score.
    • Minimizing Player: The opponent tries to minimize the AI's score.

    In Tic Tac Toe, the AI will consider all possible moves, recursively evaluate the game state that would result from each move, and choose the move with the best outcome.

    Base Cases:

    • If the AI wins, it returns a positive score.
    • If the AI loses, it returns a negative score.
    • If it's a draw, it returns zero.

    2. Representing the Game State

    First, we'll represent the Tic Tac Toe board as a list of lists (a 3x3 matrix):

    # Initialize the empty board
    board = [
        [' ', ' ', ' '],
        [' ', ' ', ' '],
        [' ', ' ', ' ']
    ]
    

    We can also use a single list to represent the board:

    board = [' ' for _ in range(9)]
    

    For simplicity, we'll use the single list representation.


    3. Implementing the Minimax Algorithm

    Let's implement the Minimax algorithm step by step.

    Define Helper Functions

    First, we need functions to:

    • Print the board
    • Check for a win or draw
    • Get available moves
    def print_board(board):
        for row in [board[i*3:(i+1)*3] for i in range(3)]:
            print('| ' + ' | '.join(row) + ' |')
    
    def check_winner(board, player):
        # Check rows, columns, and diagonals for a win
        win_conditions = [
            [board[0], board[1], board[2]],  # Row 1
            [board[3], board[4], board[5]],  # Row 2
            [board[6], board[7], board[8]],  # Row 3
            [board[0], board[3], board[6]],  # Column 1
            [board[1], board[4], board[7]],  # Column 2
            [board[2], board[5], board[8]],  # Column 3
            [board[0], board[4], board[8]],  # Diagonal 1
            [board[2], board[4], board[6]],  # Diagonal 2
        ]
        return [player, player, player] in win_conditions
    
    def is_board_full(board):
        return ' ' not in board
    
    def get_available_moves(board):
        return [i for i, spot in enumerate(board) if spot == ' ']
    

    Implement the Minimax Function

    The Minimax function will recursively evaluate all possible game states:

    def minimax(board, depth, is_maximizing):
        if check_winner(board, 'O'):
            return 1  # AI wins
        elif check_winner(board, 'X'):
            return -1  # Human wins
        elif is_board_full(board):
            return 0  # Draw
    
        if is_maximizing:
            best_score = -float('inf')
            for move in get_available_moves(board):
                board[move] = 'O'
                score = minimax(board, depth + 1, False)
                board[move] = ' '
                best_score = max(score, best_score)
            return best_score
        else:
            best_score = float('inf')
            for move in get_available_moves(board):
                board[move] = 'X'
                score = minimax(board, depth + 1, True)
                board[move] = ' '
                best_score = min(score, best_score)
            return best_score
    

    Explanation:

    • Base Cases: Check if the game has a winner or is a draw.
    • Recursive Case:
      • If it's the AI's turn (is_maximizing is True), it tries to maximize the score.
      • If it's the player's turn, it tries to minimize the score.

    Choosing the Best Move for the AI

    We need a function to choose the best move for the AI by evaluating all possible moves using the Minimax function.

    def ai_move(board):
        best_score = -float('inf')
        move = None
        for i in get_available_moves(board):
            board[i] = 'O'  # AI makes a move
            score = minimax(board, 0, False)
            board[i] = ' '  # Undo move
            if score > best_score:
                best_score = score
                move = i
        board[move] = 'O'
    

    Explanation:

    • The AI tries each available move.
    • It uses the Minimax function to evaluate the move.
    • It chooses the move with the highest score.

    4. Putting It All Together: Play Against the AI

    Now, let's create a game loop where a human can play against the AI.

    def player_move(board):
        move = int(input("Enter your move (1-9): ")) - 1
        if board[move] == ' ':
            board[move] = 'X'
        else:
            print("Spot already taken. Try again.")
            player_move(board)
    
    def main():
        board = [' ' for _ in range(9)]
        print("Welcome to Tic Tac Toe!")
        print_board(board)
    
        while True:
            # Player's turn
            player_move(board)
            print_board(board)
            if check_winner(board, 'X'):
                print("You win!")
                break
            elif is_board_full(board):
                print("It's a draw!")
                break
    
            # AI's turn
            ai_move(board)
            print("AI's move:")
            print_board(board)
            if check_winner(board, 'O'):
                print("AI wins!")
                break
            elif is_board_full(board):
                print("It's a draw!")
                break
    
    if __name__ == "__main__":
        main()
    

    Notes:

    • The player is prompted to enter a move (1-9).
    • Input validation should be added to handle invalid inputs (omitted for brevity).
    • The game loop continues until there's a winner or a draw.

    Complete Code

    Here's the complete code, including comments:

    def print_board(board):
        """Prints the current state of the board."""
        for row in [board[i*3:(i+1)*3] for i in range(3)]:
            print('| ' + ' | '.join(row) + ' |')
    
    def check_winner(board, player):
        """Checks if the specified player has won."""
        win_conditions = [
            [board[0], board[1], board[2]],  # Rows
            [board[3], board[4], board[5]],
            [board[6], board[7], board[8]],
            [board[0], board[3], board[6]],  # Columns
            [board[1], board[4], board[7]],
            [board[2], board[5], board[8]],
            [board[0], board[4], board[8]],  # Diagonals
            [board[2], board[4], board[6]],
        ]
        return [player, player, player] in win_conditions
    
    def is_board_full(board):
        """Checks if the board is full."""
        return ' ' not in board
    
    def get_available_moves(board):
        """Returns a list of available moves."""
        return [i for i, spot in enumerate(board) if spot == ' ']
    
    def minimax(board, depth, is_maximizing):
        """Minimax algorithm implementation."""
        if check_winner(board, 'O'):
            return 1
        elif check_winner(board, 'X'):
            return -1
        elif is_board_full(board):
            return 0
    
        if is_maximizing:
            best_score = -float('inf')
            for move in get_available_moves(board):
                board[move] = 'O'
                score = minimax(board, depth + 1, False)
                board[move] = ' '
                best_score = max(score, best_score)
            return best_score
        else:
            best_score = float('inf')
            for move in get_available_moves(board):
                board[move] = 'X'
                score = minimax(board, depth + 1, True)
                board[move] = ' '
                best_score = min(score, best_score)
            return best_score
    
    def ai_move(board):
        """Determines the best move for the AI."""
        best_score = -float('inf')
        move = None
        for i in get_available_moves(board):
            board[i] = 'O'
            score = minimax(board, 0, False)
            board[i] = ' '
            if score > best_score:
                best_score = score
                move = i
        board[move] = 'O'
    
    def player_move(board):
        """Prompts the player to enter a move."""
        try:
            move = int(input("Enter your move (1-9): ")) - 1
            if board[move] == ' ' and move in range(9):
                board[move] = 'X'
            else:
                print("Invalid move. Try again.")
                player_move(board)
        except (ValueError, IndexError):
            print("Please enter a number between 1 and 9.")
            player_move(board)
    
    def main():
        """Main game loop."""
        board = [' ' for _ in range(9)]
        print("Welcome to Tic Tac Toe!")
        print_board(board)
    
        while True:
            # Player's turn
            player_move(board)
            print_board(board)
            if check_winner(board, 'X'):
                print("You win!")
                break
            elif is_board_full(board):
                print("It's a draw!")
                break
    
            # AI's turn
            ai_move(board)
            print("AI's move:")
            print_board(board)
            if check_winner(board, 'O'):
                print("AI wins!")
                break
            elif is_board_full(board):
                print("It's a draw!")
                break
    
    if __name__ == "__main__":
        main()
    

    Enhancements

    While the above implementation works well for Tic Tac Toe, here are some enhancements you might consider:

    • Alpha-Beta Pruning: Optimizes Minimax by eliminating branches that don't need to be evaluated.
    • Randomness in AI Moves: If multiple moves have the same score, choose randomly among them to add unpredictability.
    • Improved User Interface: Make the game interface more user-friendly, perhaps using a graphical interface with libraries like Tkinter or Pygame.

    Implementing Alpha-Beta Pruning

    Here's how you can modify the Minimax function to include alpha-beta pruning:

    def minimax(board, depth, alpha, beta, is_maximizing):
        if check_winner(board, 'O'):
            return 1
        elif check_winner(board, 'X'):
            return -1
        elif is_board_full(board):
            return 0
    
        if is_maximizing:
            max_eval = -float('inf')
            for move in get_available_moves(board):
                board[move] = 'O'
                eval = minimax(board, depth + 1, alpha, beta, False)
                board[move] = ' '
                max_eval = max(eval, max_eval)
                alpha = max(alpha, eval)
                if beta <= alpha:
                    break
            return max_eval
        else:
            min_eval = float('inf')
            for move in get_available_moves(board):
                board[move] = 'X'
                eval = minimax(board, depth + 1, alpha, beta, True)
                board[move] = ' '
                min_eval = min(eval, min_eval)
                beta = min(beta, eval)
                if beta <= alpha:
                    break
            return min_eval
    

    And update the ai_move function accordingly:

    def ai_move(board):
        best_score = -float('inf')
        move = None
        for i in get_available_moves(board):
            board[i] = 'O'
            score = minimax(board, 0, -float('inf'), float('inf'), False)
            board[i] = ' '
            if score > best_score:
                best_score = score
                move = i
        board[move] = 'O'
    

    Conclusion

    By implementing the Minimax algorithm, we've built an AI that plays Tic Tac Toe optimally. This AI will never lose, and the best a human player can hope for is a draw.

    This project demonstrates fundamental AI concepts and provides a foundation for exploring more complex games and AI strategies. Feel free to extend and enhance this code, experiment with different algorithms, or apply similar techniques to other games.


    References:

    Let me know if you have any questions or need further assistance!