From Confusion to Clarity: Understanding the Minimax Algorithm with Tic-Tac-Toe

Hello everyone,
I’m Varada Raju. Recently, while learning AI concepts, I came across the Minimax algorithm, and I wanted to share my understanding and experience implementing it.

If you’re new to Minimax, I’ll start with a brief introduction based on how I understood it.

What is the Minimax Algorithm?

The Minimax algorithm is a classic AI algorithm used in games that involve a non-human opponent, such as Tic-Tac-Toe, Chess, and similar turn-based games.

Many of these games support:

(i) Two-player mode (human vs human)

(ii) Single-player mode (human vs computer)

But this raises an obvious question:
How does a game that normally requires two players work with only one human?

The answer is simple the second player is the computer, acting as an intelligent opponent.

The computer is designed to make moves that push itself toward winning, while forcing the human player toward losing or at least drawing. This decision-making process is where the Minimax algorithm comes into play.

The Core Idea Behind Minimax :

The main idea of Minimax is to choose a move that leads to the best possible outcome in the future, assuming the opponent also plays optimally.

In simple terms:

The algorithm looks at all possible future moves from the current game state.

It evaluates each outcome.

It then chooses the move that gives the best guaranteed result, regardless of how the opponent responds.

Minimax works using two types of players:

(i) Maximizing player – tries to maximize the score (in my case, the computer)

(ii) Minimizing player – tries to minimize the score (the human)

So the computer always assumes:

“My opponent will try their best to make me lose.”

Based on this assumption, the algorithm selects the safest and strongest move.

By this point, you should have a rough idea of how Minimax thinks and makes decisions.

Why I Chose Tic-Tac-Toe

After understanding the theory, I wanted to apply the algorithm rather than just read about it.

I chose Tic-Tac-Toe because:

The game logic is simple

The state space is small

It’s perfect for understanding recursion and decision trees

I implemented the game using basic Python, without any external libraries.

I fixed:

'O' → Human player

'X' → Computer (AI)

After every move, the program checks for:

A winner

A draw

When it’s the computer’s turn, it calls the minimax function to decide the best move.

Implementation (Python)

Below is the code I wrote for the game, including the Minimax logic:

creating empty board

board = [' ' for _ in range(9)]

def print_board():
print()
print(f" {board[0]} | {board[1]} | {board[2]} ")
print("---+---+---")
print(f" {board[3]} | {board[4]} | {board[5]} ")
print("---+---+---")

print(f" {board[6]} | {board[7]} | {board[8]} ")
print()

def check_winner(board_state, player):
win_combinations = [
(0,1,2), (3,4,5), (6,7,8),
(0,3,6), (1,4,7), (2,5,8),
(0,4,8), (2,4,6)
]
for a, b, c in win_combinations:
if board_state[a] == board_state[b] == board_state[c] == player:
return True
return False

def is_draw(board_state):
return ' ' not in board_state

def minimax(board_state, is_maximizing):
if check_winner(board_state, 'X'):
return 1
if check_winner(board_state, 'O'):
return -1
if ' ' not in board_state:
return 0

if is_maximizing:
    best_score = -float('inf')
    for i in range(9):
        if board_state[i] == ' ':
            board_state[i] = 'X'
            score = minimax(board_state, False)
            board_state[i] = ' '
            best_score = max(score, best_score)
    return best_score
else:
    best_score = float('inf')
    for i in range(9):
        if board_state[i] == ' ':
            board_state[i] = 'O'
            score = minimax(board_state, True)
            board_state[i] = ' '
            best_score = min(score, best_score)
    return best_score

def best_move(board):
best_score = -float('inf')
move = None
for i in range(9):
if board[i] == ' ':
board[i] = 'X'
score = minimax(board, False)
board[i] = ' '
if score > best_score:
best_score = score
move = i
return move

current_player = 'O' # Human starts first

while True:
print_board()

if current_player == 'O':
    move = int(input("Choose a position (0-8): "))
    if board[move] != ' ':
        print("Position already taken. Try again.")
        continue
else:
    print("AI is making a move...")
    move = best_move(board)

board[move] = current_player

if check_winner(board, current_player):
    print_board()
    print(f"Player {current_player} wins!")
    break

if is_draw(board):
    print_board()
    print("It's a draw!")
    break

current_player = 'O' if current_player == 'X' else 'X'

If there are improvements that can be made to this code, I’d really appreciate suggestions in the comments.

Limitations of Minimax

One major drawback of the Minimax algorithm is its recursive nature.

For a small game like Tic-Tac-Toe:

The number of recursive calls is limited

Performance is not an issue

But consider a game like Chess, which has:

An 8×8 board

A massive number of possible game states

In such cases, pure Minimax would:

Consume a lot of memory

Become extremely slow

What’s Next: Alpha-Beta Pruning

To solve this performance issue, an optimization technique called Alpha-Beta Pruning is used.

It follows the same logic as Minimax but:

Avoids exploring branches that won’t affect the final decision

Reduces unnecessary recursive calls

I’ve just been introduced to this concept and I’m excited to learn and implement it next.

Thanks for reading!
If you found this helpful, feel free to like the post and share feedback or suggestions. I’d be happy to learn and improve.