How to increase the success rate of my Tic Tac Toe AI that uses the Minimax Algorithm?

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.

• 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. May 29, 2021 at 14:07
• "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.
– Mast
Jun 1, 2021 at 16:37
• Hello please can you include the code for game in your question. The inclusion of missing imports, such as math, would also help. Thanks. Jun 1, 2021 at 19:49
• 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! Jun 2, 2021 at 2:19
• 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. Jun 2, 2021 at 10:53

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?