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.
gamein your question. The inclusion of missing imports, such asmath, would also help. Thanks. \$\endgroup\$