2
\$\begingroup\$

this is my first post here!

I am working on a Tic Tac Toe AI in Python that uses the Minimax Algorithm to beat either a computer or a normal player. As of now, It has approximately 70% chance of winning each game, but I am trying to increase that number. Here are a few tests that show results of the Perfect Player, which uses the minimax algorithm, against a normal computer player, which randomly chooses spots to play during the game:

First test: Perfect Player X won 67 time(s), Player O won 25 time(s), and there were 8 tie(s).

Second test: Perfect Player X won 70 time(s), Player O won 21 time(s), and there were 9 tie(s).

Third test: Perfect Player X won 68 time(s), Player O won 25 time(s), and there were 7 tie(s).

The code I have for both the algorithm player (PerfectPlayer), as well as the normal computer player (ComputerPlayer), is below.

# Recognise the player as an object, with a specific letter (X or O)
class Player:

    # Set the player's letter (noughts or crosses)
    def __init__(self, letter): self.letter = letter

    # Turn-based system
    def get_move(self, game): pass

# Perfect Tic Tac Toe AI using the Minimax Algorithm
class PerfectPlayer(Player):

    # Initialize the player and it's letter
    def __init__(self, letter):
        super().__init__(letter)

    # Get the pefect move for the game -- where the MAGIC happens!
    def get_move(self, game):
        
        # If all moves are open, then do any random move
        if len(game.open_moves()) == 9: choice = random.choice(game.open_moves())

        # If there are tokens on the board, then find the optimal move based on that token's position
        else: choice = self.minimax(game, self.letter)["position"]

        return choice

    # Minimax, the engine for the magic!
    def minimax(self, state, player):

        # Get which player is who
        max_player = self.letter
        opponent = "O" if player == "X" else "X"

        # Check if game is over
        if state.current_winner == opponent:

            return {
                    "position": None,
                    "score": 1 * (state.empty_square_vals() + 1) if opponent == max_player else -1 * (state.empty_square_vals() + 1)
                    }

        # Check if there are no empty squares
        elif not state.empty_squares():
            
            return {
                    "position": None,
                    "score": 0
                    }

        if player == max_player:
            
            # Each score should maximize
            best = {
                    "position": None,
                    "score": -math.inf
                    }

        else:
            # Each score should minimize
            best = {
                    "position": None,
                    "score": math.inf
                    }

        for possible_move in state.open_moves():

            # Try a spot
            state.make_move(possible_move, player)

            # Simulate a game with that move
            sim_score = self.minimax(state, opponent)

            # Undo the move (remember, it's only the simulation)
            state.board[possible_move] = " "
            state.current_winner = None
            sim_score["position"] = possible_move

            # Maximize the 'max_player'
            if player == max_player:

                # If the simulated score from a specific move is the best option, do it
                if sim_score["score"] > best["score"]:
                    best = sim_score

            # Minimize the 'opponent'
            else:

                if sim_score["score"] < best["score"]:
                    best = sim_score

            return best

# Use the inheritance of classes to create a computer player that uses the 'Player' class
class ComputerPlayer(Player):

    # Set the computer's letter with teh super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get a random move from all open possibilities
    def get_move(self, game):
        choice = random.choice(game.open_moves())
        return choice

Does anyone have any recommendations on how to improve my algorithm? Alternatively, suggestions for different methods to win also work.

Also, please let me know if I am lacking any necessary code (not all is included here, but I can provide more if wanted). Thank you in advance!

EDIT: I've been informed that I should include a few bits of code, so here they are.

game.py:

# Import other Python file and classes for game
from player import NormalPlayer, ComputerPlayer, PerfectPlayer
from store import store_results

empty = " "

# Store results?
store = True

def update_board(this):
    print("╭-----------╮")
    this.print_board_values()
    print("|-----------|")
    this.print_board()
    print("╰-----------╯")

# Tic Tac Toe game
class TicTacToe:

    # Initialize the game features
    def __init__(self):

        # Create an empty board list with 9 free spots
        self.board = [empty for _ in range(9)]
    
        # Track the current winner of the game
        self.current_winner = None

    # Method to print the board
    def print_board(self):

        # Create the board rows and print
        for row in  [self.board[x * 3: (x + 1) * 3] for x in range(3)]:
            print("| " + " | ".join(row) + " |")

    # This is a static method, as it doesn't require the 'self' parameter
    def print_board_values(self):

        # Set the board with spot values
        # | 0, 1, 2... 6, 7, 8 |
        number_board = [[str(value) for value in range(row * 3, (row + 1) * 3)]  for row in range(3)]

        # Print out the board with the spot values
        for row in number_board: print("| " + " | ".join(row) + " |")

    # Check for all the possible moves for the game
    def open_moves(self):

        # Enumerate, or list, all spot values that are empty
        return [i for i, spot in enumerate(self.board) if spot == empty]

    # Return all the empty board spots
    def empty_squares(self): return empty in self.board

    # Return the number of possible moves
    def empty_square_vals(self): return self.board.count(empty)

    # Method to update the board with player moves
    def make_move(self, choice, letter):

        # If the spot is open, then set the board accordingly
        if self.board[choice] == empty:
            self.board[choice] = letter

            # Check for the winner
            if self.winner(choice, letter): self.current_winner = letter
            return True
        
        return False


    # If any player makes 3 in a row, they are the winner
    def winner(self, choice, letter):

        # Check rows for tic tac toe
        row_ind = choice // 3
        row = self.board[row_ind * 3 : (row_ind + 1) * 3]

        if all([spot == letter for spot in row]): return True

        # Check columns for tic tac toe
        col_ind = choice % 3
        col = [self.board[col_ind + i * 3] for i in range(3)]

        if all([spot == letter for spot in col]): return True

        # Check diagonals for tic tac toe
        if choice % 2 == 0:

            # Left to right
            diagonal1 = [self.board[i] for i in [0, 4, 8]]

            if all([spot == letter for spot in diagonal1]): return True

            # Right to left
            diagonal2 = [self.board[i] for i in [2, 4, 6]]

            if all([spot == letter for spot in diagonal2]): return True


def  play(game, x_player, o_player, print_game = True):

    # Print the board
    if print_game:
        print("")
        update_board(game)
        print("")

        # Cross player statrts
        letter = "X"

        # Keep running the game procedure as long s no one has won, and there are empty spaces
        while game.empty_squares():

            # If the noughts player is going, ask for their move
            if letter == "O": choice = o_player.get_move(game)
        
            # If the crosses player is going, ask for their move
            else: choice = x_player.get_move(game)

            # Print out the game updates
            if game.make_move(choice, letter):

                # Print which player went, and where
                if print_game:
                    print("")
                    print("Player " + letter + " played " + str(choice) + "!")
                    update_board(game)
                    print("")

                # If there is a winner, announce who won!
                if game.current_winner:

                    if print_game: print(letter + " won the game!")

                    return letter


            # Switch the player turns
            letter = "O" if letter == "X" else "X"

    # If no one wins, say it is a tie
    if print_game: print("It's a tie!")

# Play the game
if __name__ == "__main__":

    x_wins = 0
    o_wins = 0
    ties = 0

    # Check how many times the game should be run
    games = input("How many games do you want to run? ")

    if games == "": games = 100

    # Repeat game over and over 
    for _ in range(int(games)):
        
        x_player = PerfectPlayer("X") # Minimax Player
        o_player = ComputerPlayer("O")

        ttt = TicTacToe()

        result = play(ttt, 
                        x_player, 
                        o_player, 
                        print_game = True)

        if result == "X": x_wins += 1
        elif result == "O": o_wins += 1
        else: ties += 1 

    # Say who won how many times    
    print("Perfect Player X won " + str(x_wins) + " time(s), Player O won " + str(o_wins) + " time(s), and there were " + str(ties) + " tie(s).")

    if type(x_player).__name__ == "PerfectPlayer" and type(o_player).__name__ == "ComputerPlayer" and store:
        
        print("")
        # Store results
        store_results(x_wins, o_wins, ties)

player.py:

# Things to keep in mind...
# The official term for the X's and O's in Tic-Tac-Toe are Noughts (O) and Crosses (X)
# The board is stored as a list, with values ranging from 0 (top left) to 8 (bottom right)
# The Tic-Tac-Toe AI uses the minimax algorthim, that predicts possible moves from the current board state

# All imports here!
import math
import random

empty = " "


# Recognise the player as an object, with a specific letter (X or O)
class Player:

    # Set the player's letter (noughts or crosses)
    def __init__(self, letter): self.letter = letter

    # Turn-based system
    def get_move(self, game): pass

# Use the inheritance of classes to create a computer player that uses the 'Player' class
class ComputerPlayer(Player):

    # Set the computer's letter with teh super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get a random move from all open possibilities
    def get_move(self, game):
        choice = random.choice(game.open_moves())
        return choice

# Use the inheritance of classes for the user object that uses the 'Player' class
class NormalPlayer(Player):

    # Set the user's letter with the super class
    def __init__(self, letter): super().__init__(letter)

    # Turn-based system, get the player's movement choice
    def get_move(self, game):

        # Player's choice must first be verified
        verified = False

        # The spot value of the move the player wants to make
        value = None

        # Ask for the player's move
        while not verified:
            choice = input(self.letter + "'s turn. Which spot do you want to play? ")

            # Check if the player's choice is valid...
            try:

                # Turn the input into an integer
                value = int(choice)
                verified = True

                # If the spot value is not available, catch the error and tell the player
                if value not in game.open_moves():
                    verified = False
                    raise ValueError

            # ...if it is, then announce it
            except ValueError:

                # If the choice was invalid, have the player decide their move again
                print("The spot value is not valid. Please choose another spot.")

        return value


# Perfect Tic Tac Toe AI using the Minimax Algorithm
class PerfectPlayer(Player):

    # Initialize the player and it's letter
    def __init__(self, letter): super().__init__(letter)

    # Get the pefect move for the game -- where the MAGIC happens!
    def get_move(self, game):
        
        # If all moves are open, then do any random move
        if len(game.open_moves()) == 9: choice = random.choice(game.open_moves())

        # If there are tokens on the board, then find the optimal move based on that token's position
        else: choice = self.minimax(game, self.letter)["position"]

        return choice

    # Minimax, the engine for the magic!
    def minimax(self, state, player):

        # Get which player is who
        max_player = self.letter
        opponent = "O" if player == "X" else "X"

        # Check if game is over
        if state.current_winner == opponent:

            return {
                    "position": None,
                    "score": 1 * (state.empty_square_vals() + 1) if opponent == max_player else -1 * (state.empty_square_vals() + 1)
                    }

        # Check if there are no empty squares
        elif not state.empty_squares():
            
            return {
                    "position": None,
                    "score": 0
                    }

        if player == max_player:
            
            # Each score should maximize
            best = {
                    "position": None,
                    "score": -math.inf
                    }

        else:
            # Each score should minimize
            best = {
                    "position": None,
                    "score": math.inf
                    }

        for possible_move in state.open_moves():

            # Try a spot
            state.make_move(possible_move, player)

            # Simulate a game with that move
            sim_score = self.minimax(state, opponent)

            # Undo the move (remember, it's only the simulation)
            state.board[possible_move] = empty
            state.current_winner = None
            sim_score["position"] = possible_move

            # Maximize the 'max_player'
            if player == max_player:

                # If the simulated score from a specific move is the best option, do it
                if sim_score["score"] > best["score"]:
                    best = sim_score

            # Minimize the 'opponent'
            else:

                if sim_score["score"] < best["score"]:
                    best = sim_score

            return best


    

Also, please note that the minimax user does indeed lose at time. Although ~70% of the games are won by it, it does lose and tie a small fraction of games to the randomized choice opponent.

\$\endgroup\$
7
  • 3
    \$\begingroup\$ Welcome to CR! This site is for reviews of code that works to the best of your knowledge. If you intend 100% non-loss rate for your AI (you can't guarantee anything better than a draw given perfect play on both sides), there's more work to be done before the question is ready for CR. Thanks. \$\endgroup\$
    – ggorlen
    May 29, 2021 at 14:07
  • 1
    \$\begingroup\$ "As of now, It has approximately 70% chance of winning each game, but I am trying to increase that number." Are the rest of the games a draw, or does the computer lose a portion of the games as well? This is important to determine whether your program indeed works. \$\endgroup\$
    – Mast
    Jun 1, 2021 at 16:37
  • \$\begingroup\$ Hello please can you include the code for game in your question. The inclusion of missing imports, such as math, would also help. Thanks. \$\endgroup\$
    – Peilonrayz
    Jun 1, 2021 at 19:49
  • \$\begingroup\$ Thank you all so much for your advice! I've edited my original post with the required code, and the information you asked for. No, the minimax user does not always win, and does lose at times. I've included the two main files, game.py and player.py, into my post, which has the imports needed for the project. if necessary, it is perfectly possible to copy-paste the code into an IDE to test the code for yourself. Once again, thank you so much! \$\endgroup\$
    – Bubbly
    Jun 2, 2021 at 2:19
  • \$\begingroup\$ One of the main "issues" in terms of TTT is that no player can force a victory. A single experienced player, no matter their turn order, can force a tie every single time. So the question becomes how the learning algorithm treats a tie. Is it considered a defeat? A victory? Should the engine risk a move where they could win or lose, if there is also the option of forcing a tie, i.e. does the engine avoid loss or does it seek victory? Do tied games "not exist" in terms of the learning experience? These valuations matter, but they are subjective. \$\endgroup\$
    – Flater
    Jun 2, 2021 at 10:53

1 Answer 1

1
\$\begingroup\$

Tic-tac-toe is easily solved. That means there's no reason for your PerfectPlayer to not actually be perfect: It should never loose (and against a moves-randomly opponent, it should win quite often).

So clearly there's something wrong with your minimax algorithm. Why is the scoring so complicated? Why does the algorithm care who's turn it "really" is? Is return best supposed to be inside the for possible_move... loop?

  • Keep your formatting boring. You can use a checker like pycodestyle. (I don't like all its rules, but the point of a checker is to not spend the time worrying if your code's correctly formatted.)
  • Try to make invalid states unrepresentable. Using strings for data that isn't arbitrary text isn't great. Using dicts for data with known structure also isn't great.
  • For the purpose of limiting what's "representable", I like to use type annotations. But note that python doesn't inherently check types; if you want your type annotations to be anything more than fancy comments, you'll have to use an external tool like mypy
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.