Advanced AI — Alpha Beta Pruning in Python through Tic-Tac-Toe
Introduction:
Tic-Tac-Toe, a classic game enjoyed by all ages, may seem simple, but mastering it can be a daunting challenge. As artificial intelligence (AI) continues to advance, implementing efficient algorithms becomes crucial. Enter alpha-beta pruning, a technique that revolutionizes AI gameplay by significantly reducing the number of explored game states. In this article, we’ll explore how alpha-beta pruning enhances the performance of an AI playing Tic-Tac-Toe and enables it to make optimal decisions.
Understanding Alpha-Beta Pruning:
Alpha-beta pruning is an optimization technique used in game-playing AI algorithms. It eliminates the need to explore portions of the game tree that are guaranteed to be irrelevant to the final decision. This reduction in search space drastically improves the efficiency and performance of the algorithm.
The Basics of Tic-Tac-Toe:
Before diving into alpha-beta pruning, let’s recap the fundamentals of Tic-Tac-Toe. The game is played on a 3x3 grid, where two players, X and O, take turns placing their respective symbols in empty cells. The objective is to form a line of three symbols horizontally, vertically, or diagonally. The first player to achieve this wins the game.
Minimax Algorithm:
The minimax algorithm serves as the foundation for Tic-Tac-Toe AI. It exhaustively explores the game tree, considering all possible moves and their subsequent outcomes, to determine the best move for the current player. However, without optimization, the algorithm can become computationally expensive.
The Power of Pruning:
Alpha-beta pruning optimizes the minimax algorithm by discarding portions of the game tree that are deemed irrelevant. It achieves this by maintaining two values: alpha and beta. Alpha represents the best value the maximizing player (X) has found so far, while beta represents the best value the minimizing player (O) has found.
The Pruning Process:
During the recursive traversal of the game tree, when evaluating the child nodes, the algorithm compares the current value (alpha or beta) with the previously determined value. If the new value indicates that the opponent will never choose that path, the algorithm prunes it by stopping the exploration of that subtree. This reduces the number of nodes evaluated, saving computational resources.
Optimal Move Selection:
By employing alpha-beta pruning, the AI can focus its search on the most promising moves, discarding inferior options early on. This reduction in the search space allows the AI to make optimal decisions more efficiently. With each subsequent move, the AI refines its understanding of the game state, incrementally improving its gameplay.
Implementation in Tic-Tac-Toe AI:
To apply alpha-beta pruning to a Tic-Tac-Toe AI, several modifications are needed to the minimax algorithm. The key additions include tracking the alpha and beta values during traversal and using them to determine when to prune irrelevant branches of the game tree.
Conclusion:
With the integration of alpha-beta pruning, an AI playing Tic-Tac-Toe can make strategic decisions more effectively, significantly reducing the number of game states evaluated. This optimization technique empowers AI algorithms to compete at a higher level, challenging human opponents and providing a thrilling gameplay experience.
As AI continues to advance, the application of alpha-beta pruning extends beyond Tic-Tac-Toe. It finds utility in various games and puzzles, where exploring the entire game tree is impractical or computationally infeasible.
In summary, alpha-beta pruning unlocks the full potential of AI gameplay in Tic-Tac-Toe, enabling faster and more efficient decision-making. By harnessing the power of this optimization technique, AI agents can master the game, providing users with challenging and rewarding experiences.
NOW THAT THE BACKGROUND IS OUT THE WAY, LETS FOCUS ON THE PART EVERYONE WANTS, THE CODE!
We will build our Game environment in PyGame:
Note: This should be its own script file and is the main file that will be executed in a terminal.
import pygame
import sys
import time
# import tictactoe as ttt
import tictactoe_alpha_beta_prune as ttt
pygame.init()
size = width, height = 600, 400
# Colors
black = (0, 0, 0)
white = (255, 255, 255)
screen = pygame.display.set_mode(size)
mediumFont = pygame.font.Font("OpenSans-Regular.ttf", 28)
largeFont = pygame.font.Font("OpenSans-Regular.ttf", 40)
moveFont = pygame.font.Font("OpenSans-Regular.ttf", 60)
user = None
board = ttt.initial_state()
ai_turn = False
while True:
for event in pygame.event.get():
if event.type == pygame.QUIT:
sys.exit()
screen.fill(black)
# Let user choose a player.
if user is None:
# Draw title
title = largeFont.render("Play Tic-Tac-Toe", True, white)
titleRect = title.get_rect()
titleRect.center = ((width / 2), 50)
screen.blit(title, titleRect)
# Draw buttons
playXButton = pygame.Rect((width / 8), (height / 2), width / 4, 50)
playX = mediumFont.render("Play as X", True, black)
playXRect = playX.get_rect()
playXRect.center = playXButton.center
pygame.draw.rect(screen, white, playXButton)
screen.blit(playX, playXRect)
playOButton = pygame.Rect(5 * (width / 8), (height / 2), width / 4, 50)
playO = mediumFont.render("Play as O", True, black)
playORect = playO.get_rect()
playORect.center = playOButton.center
pygame.draw.rect(screen, white, playOButton)
screen.blit(playO, playORect)
# Check if button is clicked
click, _, _ = pygame.mouse.get_pressed()
if click == 1:
mouse = pygame.mouse.get_pos()
if playXButton.collidepoint(mouse):
time.sleep(0.2)
user = ttt.X
elif playOButton.collidepoint(mouse):
time.sleep(0.2)
user = ttt.O
else:
# Draw game board
tile_size = 80
tile_origin = (width / 2 - (1.5 * tile_size),
height / 2 - (1.5 * tile_size))
tiles = []
for i in range(3):
row = []
for j in range(3):
rect = pygame.Rect(
tile_origin[0] + j * tile_size,
tile_origin[1] + i * tile_size,
tile_size, tile_size
)
pygame.draw.rect(screen, white, rect, 3)
if board[i][j] != ttt.EMPTY:
move = moveFont.render(board[i][j], True, white)
moveRect = move.get_rect()
moveRect.center = rect.center
screen.blit(move, moveRect)
row.append(rect)
tiles.append(row)
# import pdb
# pdb.set_trace()
game_over = ttt.terminal(board)
player = ttt.player(board)
# Show title
if game_over:
winner = ttt.winner(board)
if winner is None:
title = f"Game Over: Tie."
else:
title = f"Game Over: {winner} wins."
elif user == player:
title = f"Play as {user}"
else:
title = f"Computer thinking..."
title = largeFont.render(title, True, white)
titleRect = title.get_rect()
titleRect.center = ((width / 2), 30)
screen.blit(title, titleRect)
# Check for AI move
if user != player and not game_over:
if ai_turn:
time.sleep(0.5)
move = ttt.minimax(board)
board = ttt.result(board, move)
ai_turn = False
else:
ai_turn = True
# Check for a user move
click, _, _ = pygame.mouse.get_pressed()
if click == 1 and user == player and not game_over:
mouse = pygame.mouse.get_pos()
for i in range(3):
for j in range(3):
if (board[i][j] == ttt.EMPTY and tiles[i][j].collidepoint(mouse)):
board = ttt.result(board, (i, j))
if game_over:
againButton = pygame.Rect(width / 3, height - 65, width / 3, 50)
again = mediumFont.render("Play Again", True, black)
againRect = again.get_rect()
againRect.center = againButton.center
pygame.draw.rect(screen, white, againButton)
screen.blit(again, againRect)
click, _, _ = pygame.mouse.get_pressed()
if click == 1:
mouse = pygame.mouse.get_pos()
if againButton.collidepoint(mouse):
time.sleep(0.2)
user = None
board = ttt.initial_state()
ai_turn = False
pygame.display.flip()Tic-Tac-Toe Alpha Beta Pruning AI
Note: This script is the helper script and will need to be in the same directory/folder as the script above. It should be named tictactoe_alpha_beta_prune.py else you will need to change the import statement in the script above!
"""
Tic Tac Toe Player
"""
import math
X = "X"
O = "O"
EMPTY = None
def initial_state():
"""
Returns starting state of the board.
"""
return [[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY]]
def player(board):
"""
Returns player who has the next turn on a board.
"""
cnt_X = 0
cnt_o = 0
# Count X and O's on the game board
for i in range(3):
for j in range(3):
if board[i][j] == X:
cnt_X += 1
elif board[i][j] == O:
cnt_o += 1
if cnt_X == cnt_o:
return X
elif cnt_X > cnt_o:
return O
else:
return X
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
# Each action is represented as a tuple (i, j) where i corresponds to the row of the move (0, 1, or 2) and j corresponds to which cell in the row corresponds to the move (also 0, 1, or 2).
actions = set()
for i in range(3):
for j in range(3):
if board[i][j] == None:
actions.add((i, j))
return actions
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
# If action is not a valid action for the board, the program should raise an exception
if action not in actions(board):
raise Exception("Invalid Action")
# Make a copy of the board (Important, else can run into some hard to debug state errors)
new_board = [row[:] for row in board]
# making move (i, j) on the board
new_board[action[0]][action[1]] = player(board)
return new_board
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
# Return tictactoe winner if there is one
for i in range(3):
# Check rows
if board[i][0] == board[i][1] == board[i][2]:
if board[i][0] != None:
return board[i][0]
# Check columns
if board[0][i] == board[1][i] == board[2][i]:
if board[0][i] != None:
return board[0][i]
# Check Diagonals
if board[0][0] == board[1][1] == board[2][2]:
if board[0][0] != None:
return board[0][0]
if board[0][2] == board[1][1] == board[2][0]:
if board[0][2] != None:
return board[0][2]
return None
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
# Check if there is a winner
if winner(board) != None:
return True
else:
# Check if the board is full
for i in range(3):
for j in range(3):
if board[i][j] == None:
return False
return True
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
if winner(board) == X:
return 1
elif winner(board) == O:
return -1
else:
return 0
def max_value(board, alpha, beta):
"""
Returns the maximum value for the current player on the board
using alpha-beta pruning.
"""
if terminal(board):
return utility(board)
v = -math.inf
for action in actions(board):
v = max(v, min_value(result(board, action), alpha, beta))
alpha = max(alpha, v)
if alpha >= beta:
break
return v
def min_value(board, alpha, beta):
"""
Returns the minimum value for the current player on the board
using alpha-beta pruning.
"""
if terminal(board):
return utility(board)
v = math.inf
for action in actions(board):
v = min(v, max_value(result(board, action), alpha, beta))
beta = min(beta, v)
if alpha >= beta:
break
return v
def minimax(board):
"""
Returns the optimal action for the current player on the board
using the minimax algorithm with alpha-beta pruning.
"""
if terminal(board):
return None
if player(board) == X:
v = -math.inf
opt_action = None
for action in actions(board):
new_value = min_value(result(board, action), -math.inf, math.inf)
if new_value > v:
v = new_value
opt_action = action
return opt_action
elif player(board) == O:
v = math.inf
opt_action = None
for action in actions(board):
new_value = max_value(result(board, action), -math.inf, math.inf)
if new_value < v:
v = new_value
opt_action = action
return opt_actionFREE ChatGPT Document Q&A: Get questions answered about any document type of any length!
Plug: Please purchase my book ONLY if you have the means to do so, I usually do not advertise, but I am struggling to stay afloat. Imagination Unleashed: Canvas and Color, Visions from the Artificial: Compendium of Digital Art Volume 1 (Artificial Intelligence Draws Art) — Kindle edition by P, Shaxib, A, Bixjesh. Arts & Photography Kindle eBooks @ Amazon.com.
