TIC-TAC-TOE Game using Heuristic Alpha-Beta Tree Search Algorithm
Introduction:
- This project aims to implement the Heuristic Alpha-Beta Tree Search Algorithm in Tic-Tac-Toe. The algorithm combines heuristic evaluation and alpha-beta pruning to create an intelligent AI opponent for the game. The goal is to showcase the algorithm’s effectiveness, analyze its performance, and evaluate its strategic decision-making capabilities.
2. Algorithm Description: The Heuristic Alpha-Beta Tree Search Algorithm combines minimax search and pruning techniques. It evaluates game states using heuristics and optimizes the search process by pruning unnecessary branches.
3. Program Design: The program simulates a Tic-Tac-Toe game environment with functions for player moves, AI moves, game state evaluation, and winner determination. It is designed for code reusability, readability, and maintainability.
4. Code Explanations: Key functions include handling moves, evaluating game states, and implementing the algorithm through minimax with alpha-beta pruning.
5. Experimental Results: Experimental results assess the AI opponent’s performance based on win rate, average moves to win, and game completion time. The algorithm can be tested against different opponents or difficulty levels.
6. Analysis: The analysis interprets results, discusses strengths and weaknesses, compares with other algorithms, and evaluates computational complexity.
7. Recommendations and Future Development: Recommendations include fine-tuning heuristics, exploring enhancements to alpha-beta pruning, and extending the algorithm to other games or environments.
Overall, this project demonstrates the potential of the Heuristic Alpha-Beta Tree Search Algorithm in Tic-Tac-Toe and contributes to the understanding of heuristic algorithms in game theory and AI.
# Algorithm Description:
This project implements the Heuristic Alpha-Beta Tree Search Algorithm for Tic-Tac-Toe. The algorithm combines heuristic evaluation and alpha-beta pruning to create an intelligent AI opponent. It utilizes minimax search and pruning techniques to evaluate game states efficiently. The program includes functions for player and AI moves, game state evaluation, and determining the winner. Experimental results evaluate AI performance, and the analysis discusses strengths, weaknesses, and potential improvements. The project contributes to game theory and AI understanding.
# Program Design:
- The program follows a modular design with separate functions for different tasks.
- It implements the Heuristic Alpha-Beta Tree Search algorithm.
- Object-oriented programming principles are utilized.
- The choice of programming language and libraries is not specified.
- The program may include a graphical user interface.
- The design emphasizes modularity, efficiency, and user-friendliness.
# Function of each piece of code:
1.import libraries:
from random import choice
from math import infThe first piece of code imports the “choice” function from the “random” library and the “inf” constant from the “math” library.
2. The board:
# The Tic-Tac-Toe board
board = [[0, 0, 0],
[0, 0, 0],
[0, 0, 0]]The second piece of code defines the initial state of the Tic-Tac-Toe board. It is represented as a 3x3 nested list where each element represents a cell on the board. The value 0 indicates an empty cell.
3. display and clear the game board:
# Function to display the game board
def Gameboard(board):
chars = {1: 'X', -1: 'O', 0: ' '}
for x in board:
for y in x:
ch = chars[y]
print(f'| {ch} ', end='')
print('|\n' + '_____________')
print("")
print('===============')
print("")
# Function to clear the game board
def Clearboard(board):
for x, row in enumerate(board):
for y, col in enumerate(row):
board[x][y] = 0The third piece of code includes two functions related to the game board.
ِA. Gameboard(board):
- This function takes the current state of the board as input.
- It maps the numeric values on the board to their corresponding symbols (‘X’, ‘O’, or empty space).
- It then displays the board on the console, showing the current positions of the players.
B. Clearboard(board):
- This function clears the game board by setting all the cells to 0 (empty).
- It iterates through each cell of the board and assigns the value 0 to it.
- This function is used to reset the board for a new game or when needed.
4. Check The won:
# Function to check if a player has won
def winningPlayer(board, player):
conditions = [[board[0][0], board[0][1], board[0][2]],
[board[1][0], board[1][1], board[1][2]],
[board[2][0], board[2][1], board[2][2]],
[board[0][0], board[1][0], board[2][0]],
[board[0][1], board[1][1], board[2][1]],
[board[0][2], board[1][2], board[2][2]],
[board[0][0], board[1][1], board[2][2]],
[board[0][2], board[1][1], board[2][0]]]
if [player, player, player] in conditions:
return True
return False
# Function to check if the game has been won
def gameWon(board):
return winningPlayer(board, 1) or winningPlayer(board, -1)
# Function to print the game result
def printResult(board):
if winningPlayer(board, 1):
print('Player has won! ' + '\n')
elif winningPlayer(board, -1):
print('AI has won! ' + '\n')
else:
print('The game is over with the result of Draw' + '\n')The fourth piece of code includes functions related to checking the game’s winning condition and printing the game result.
A. winningPlayer(board, player):
- This function takes the game board and a player (-1 for AI, 1 for the player) as input.
- It checks all possible winning conditions on the board to determine if the specified player has won.
- The function returns True if the player has won and False otherwise.
B. gameWon(board):
- This function takes the game board as input.
- It uses the winningPlayer() function to check if either the player or the AI has won the game.
- The function returns True if either player has won and False otherwise.
C. printResult(board):
- This function takes the game board as input.
- It uses the winningPlayer() function to determine the game’s result.
- If the player has won, it prints “Player has won!”
- If the AI has won, it prints “AI has won!”
- If the game is a draw, it prints “The game is over with the result of Draw.”
These functions are responsible for checking the game’s outcome and printing the corresponding result on the console.
5. Check The board:
# Function to get the list of blank positions on the board
def blanks(board):
blank = []
for x, row in enumerate(board):
for y, col in enumerate(row):
if board[x][y] == 0:
blank.append([x, y])
return blank
# Function to check if the board is full
def boardFull(board):
if len(blanks(board)) == 0:
return True
return FalseThe fifth piece of code includes functions related to checking the board’s status and available moves.
A. blanks(board):
- This function takes the game board as input.
- It iterates through each cell of the board and checks if it is empty (marked with 0).
- The function collects the coordinates of empty cells and returns them as a list.
B. boardFull(board):
- This function takes the game board as input.
- It uses the blanks() function to obtain the list of empty positions.
- If the length of the list is zero, it means the board is full.
- The function returns True if the board is full and False otherwise.
These functions help determine the availability of moves on the board. The blanks() function provides a list of empty positions, and the boardFull() function checks if the board is completely filled with moves.
6. The Move:
# Function to set a move on the board
def setMove(board, x, y, player):
board[x][y] = player
# Function to evaluate the game state
def evaluate(board):
if winningPlayer(board, 1):
return 1
elif winningPlayer(board, -1):
return -1
else:
return 0
# Heuristic function for the AI
def heuristic(board):
return evaluate(board)The sixth piece of code includes functions related to setting moves, evaluating the game state, and defining the heuristic function for the AI.
ِA. setMove(board, x, y, player):
- This function takes the game board, row index (x), column index (y), and player (-1 or 1) as input.
- It sets the specified position on the board with the player’s mark.
- The function modifies the board in-place.
B. evaluate(board):
- This function takes the game board as input.
- It checks if either the player or the AI has won the game by calling the winningPlayer(board, player) function.
- If the player has won, it returns 1.
- If the AI has won, it returns -1.
- If the game is a draw, it returns 0.
C. heuristic(board):
- This function takes the game board as input.
- It calls the evaluate(board) function to determine the game state.
- The function returns the evaluation value as the heuristic value for the current board state.
These functions are used in the Alpha-Beta Minimax algorithm to evaluate the game state and assign heuristic values to different board configurations. The setMove() function updates the board with a player’s move, while the evaluate() function checks if the game has been won and returns the corresponding value. The heuristic() function provides the heuristic value for a given board state.
7. Heuristic Alpha-Beta (Tree Search):
# Alpha-Beta Minimax algorithm for choosing the best move
def abminimax(board, depth, alpha, beta, player):
row = -1
col = -1
if depth == 0 or gameWon(board):
return [row, col, heuristic(board)]
best_score = -inf if player == 1 else inf
moves = blanks(board)
for cell in moves:
setMove(board, cell[0], cell[1], player)
score = abminimax(board, depth - 1, alpha, beta, -player)
setMove(board, cell[0], cell[1], 0)
if player == 1:
if score[2] > best_score:
best_score = score[2]
row = cell[0]
col = cell[1]
alpha = max(alpha, best_score)
if alpha >= beta:
break
else:
if score[2] < best_score:
best_score = score[2]
row = cell[0]
col = cell[1]
beta = min(beta, best_score)
if alpha >= beta:
break
return [row, col, best_score]- The
abminimaxfunction implements the Alpha-Beta Minimax algorithm. - It recursively explores the game tree to determine the best move.
- The function considers the current game board, depth, alpha, beta, and player.
- It checks if the depth limit or a winning condition has been reached.
- If so, it returns the best move and its heuristic score.
- Otherwise, it initializes the best score based on the player.
- The function generates possible moves and evaluates each move’s score.
- It updates the best score and move based on the player’s turn.
- Alpha and beta values are updated for pruning.
- If alpha >= beta, the function stops searching.
- Finally, it returns the best move and score found.
8. AI Moves for ‘O’ and ‘X’ Players:
# Function for the AI's move (playing as O)
def o_comp(board):
if len(blanks(board)) == 9:
x = choice([0, 1, 2])
y = choice([0, 1, 2])
setMove(board, x, y, -1)
Gameboard(board)
else:
result = abminimax(board, len(blanks(board)), -inf, inf, -1)
setMove(board, result[0], result[1], -1)
Gameboard(board)
# Function for the AI's move (playing as X)
def x_comp(board):
if len(blanks(board)) == 9:
x = choice([0, 1, 2])
y = choice([0, 1, 2])
setMove(board, x, y, 1)
Gameboard(board)
else:
result = abminimax(board, len(blanks(board)), -inf, inf, 1)
setMove(board, result[0], result[1], 1)
Gameboard(board)
A. o_comp:
- The
o_compfunction handles the AI's move when playing as "O" (AI player). - If the board is empty, it selects a random position as the first move.
- Otherwise, it uses the Alpha-Beta Minimax algorithm to determine the best move.
- The function calls the
abminimaxfunction with appropriate parameters. - It sets the move on the board based on the result obtained.
- Finally, it displays the updated game board using the
Gameboardfunction.
B. x_comp:
- The
x_compfunction handles the AI's move when playing as "X" (AI player). - If the board is empty, it selects a random position as the first move.
- Otherwise, it uses the Alpha-Beta Minimax algorithm to determine the best move.
- The function calls the
abminimaxfunction with appropriate parameters. - It sets the move on the board based on the result obtained.
- Finally, it displays the updated game board using the
Gameboardfunction.
9.Handle the Player’s Move:
# Function for a player's move
def playerMove(board):
valid_input = False
while not valid_input:
try:
position = int(input("Enter the position (1-9): "))
if position >= 1 and position <= 9:
row = (position - 1) // 3
col = (position - 1) % 3
if board[row][col] == 0:
setMove(board, row, col, 1)
valid_input = True
else:
print("Invalid move. The position is already occupied.")
else:
print("Invalid input. Please enter a number from 1 to 9.")
except ValueError:
print("Invalid input. Please enter a number from 1 to 9.")
Gameboard(board)- The
playerMovefunction handles a player's move in the game. - It prompts the player to enter a position (1–9) on the board.
- It checks if the input is a valid number within the range.
- If the position is valid and not already occupied, it sets the move on the board using the
setMovefunction. - If the position is invalid or already occupied, it displays an appropriate error message.
- Finally, it displays the updated game board using the
Gameboardfunction.
10. player vs player mode:
# Function for player vs. player mode
def pvp():
Clearboard(board)
currentPlayer = 1
while not (boardFull(board) or gameWon(board)):
if currentPlayer == 1:
print("The move of Player is: ")
playerMove(board)
else:
print("The move of AI is: ")
o_comp(board)
currentPlayer *= -1
printResult(board)- The
pvpfunction represents the player vs. player mode in the game. - It starts by clearing the game board using the
Clearboardfunction. - It initializes the current player as Player 1.
- Inside a loop, it checks if the board is full or if any player has won.
- If the current player is Player 1, it prompts for their move and updates the board accordingly.
- If the current player is Player 2, it prompts for their move and updates the board accordingly.
- After each move, it switches the current player by multiplying it by -1.
- Once the loop ends, it displays the game result using the
printResultfunction.
11. AI vs AI mode:
# Function for AI vs. AI mode
def ai_vs_ai():
Clearboard(board)
currentPlayer = 1
while not (boardFull(board) or gameWon(board)):
if currentPlayer == 1:
print("The move of AI 1 is: ")
x_comp(board)
else:
print("The move of AI 2 is: ")
o_comp(board)
currentPlayer *= -1
printResult(board)- The
ai_vs_aifunction represents the AI vs. AI mode in the game. - It starts by clearing the game board using the
Clearboardfunction. - It initializes the current player as Player 1.
- Inside a loop, it checks if the board is full or if any player has won.
- If the current player is Player 1, it performs the AI’s move by calling the
makeMovefunction with the appropriate parameters. - If the current player is Player 2, it performs the AI’s move by calling the
makeMovefunction with the appropriate parameters. - After each move, it switches the current player by multiplying it by -1.
- Once the loop ends, it displays the game result using the
printResultfunction.
12. The Result:
# Main driver code
print("__________________________________________________________________")
print("TIC-TAC-TOE Game using Heuristic Alpha-Beta Tree Search Algorithm")
print("__________________________________________________________________")
try:
mode = int(input("Choose the mode: \n1. Player vs AI \n2. AI vs AI\n"))
except ValueError:
print("Invalid input. Please enter a number.")
if mode == 1:
pvp()
elif mode == 2:
ai_vs_ai()
else:
print("Invalid mode selected.")- The main driver code begins by displaying a header for the Tic-Tac-Toe game.
- It prompts the user to choose a game mode: Player vs. AI or AI vs. AI.
- It reads the user’s input and stores it in the
modevariable. - If the chosen mode is 1 (Player vs. AI), it calls the
pvpfunction to start the game. - If the chosen mode is 2 (AI vs. AI), it calls the
ai_vs_aifunction to start the game. - If the chosen mode is neither 1 nor 2, it displays an error message indicating an invalid mode selection.
# Results of the experiment:
- The program was executed and tested with various scenarios.
- The expected outputs of the program are as follows:
- For Player vs. AI mode: The program should display the game board and prompt the player and AI to make their moves alternately until the game is won by either the player or the AI, or the game ends in a draw. The program should also display the result of the game.
- For AI vs. AI mode: The program should display the game board and simulate the moves made by AI players until the game is won by either AI player or the game ends in a draw. The program should also display the result of the game.
- The correctness of the outputs was verified by visually inspecting the displayed game board, ensuring that the moves made by the players and AI were valid and followed the rules of the game. The result of the game was compared with the expected outcome based on the game state.
#Analysis and Discussion:
- Performance Analysis: The algorithm used in Tic-Tac-Toe shows good performance and efficient decision-making.
- Efficiency Evaluation: The algorithm has a manageable time and space complexity, providing quick responses and requiring moderate memory.
- Pros of Practical Use: Strategic decision-making, adaptability to different game rules, and optimal or near-optimal solutions.
- Cons of Practical Use: Not suitable for real-time games and high computational cost for large game trees.
# Summary and Recommendations:
- The project involved developing a Tic-Tac-Toe game using a Heuristic Alpha-Beta Tree Search Algorithm.
- The game allows players to play against each other or against an AI opponent.
- The code consists of functions for managing the game board, making moves, evaluating game states, and implementing the AI’s decision-making process.
- During testing, the program performed as expected, providing an interactive and challenging gaming experience.
- Recommendations for future development and improvement:
- Enhance the user interface with better graphics and user-friendly input methods.
- Implement different difficulty levels for the AI opponent.
- Include game statistics tracking for wins, losses, and draws.
- Add online multiplayer capabilities.
- Optimize the code for better performance and efficiency.
By implementing these recommendations, the Tic-Tac-Toe game can be enhanced and provide a more engaging experience for players.
# References:
- https://github.com/anmolchandelCO180309/tic-tac-toe-using-alpha-beta-pruning/tree/main
- Chat gpt was used as an aid in editing the code and writing the report.
# Appendices:
Code file download link with ipynb extension.
https://drive.google.com/file/d/1FPGXf0Nadi_hp8cVJTNBNAaxIlvZmJ8D/view?usp=sharing