The Minimax algorithm is a fundamental decision-making rule used in Artificial Intelligence (AI) for two-player, zero-sum games, such as Chess, Checkers, and, in our case, Tic-Tac-Toe. It works by exploring every possible future state of the game to find the move that maximizes the current player’s gain while assuming the opponent plays optimally to minimize that gain.

The Core Principle: Maximizing Gains, Minimizing Losses

The name “Minimax” perfectly describes its function:

• MAXimizing Player (e.g., the AI): Seeks to choose a move that leads to the highest score possible.
• MINimizing Player (e.g., the Human): Seeks to choose a move that leads to the lowest score for the Maximizing Player.

The entire process is a recursive simulation, creating a huge decision tree, where the algorithm predicts the opponent’s “best” (worst for the AI) response at every turn.

How Minimax Works in Code
The provided Python code illustrates this concept through two main functions: minimax and get_best_move.

• The Scoring System (Evaluation)

The algorithm first assigns a score to every possible end-state of the game (the “leaves” of the decision tree):

• • AI Win: Returns +1 (The best possible outcome).
  • Human Win: Returns -1 (The worst possible outcome for the AI).
  • Draw: Returns 0 (A neutral outcome).

• The minimax Function (The Simulation Engine)

This function is the heart of the AI. It uses recursion to simulate future gameplay by alternating between the two players:

• • Base Cases: The simulation stops when the board is full or a winner is found (returning +1, -1, or 0).
  • Maximizing Step (if is_maximizing): The AI tries every empty square, calls minimax recursively for the opponent, and chooses the move that returns the highest score (best_score = max(score, best_score)).
  • Minimizing Step (else): The algorithm assumes the human will try every move, calls minimax recursively for the AI, and chooses the move that returns the lowest score (best_score = min(score, best_score)). This simulates the optimal counter-strategy.

• The get_best_move Function (The Decision)

This function acts as the bridge between the simulation and the real game:

• • It iterates through every available move on the actual board.
  • For each move, it calls minimax(board, False) (since after the AI moves, it becomes the human’s minimizing turn).
  • It finds the move that resulted in the highest score (+1 being the highest priority, then 0, then -1).
  • It executes that single, optimal move on the physical board.

By using this recursive lookahead and prioritizing the move that guarantees the best minimum outcome (Minimax), the AI achieves a perfect, unbeatable strategy for simple games like Tic-Tac-Toe. The GitHub code is available here: https://github.com/Vitosh/Python_personal/blob/master/YouTube/047_Tic-Tac-Toe/tic-tac-toe.py

🙂 The whole code is below, if you do not want to click on the GitHub link:

import sys

def check_winner(board, player):
    win_lines = [
        (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_lines:
        if board[a] == player and board[b] == player and board[c] == player:
            return True
    return False

def is_full(board):
    return " " not in board

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

def minimax(board, is_maximizing):
    # Base Case
    if check_winner(board, "O"): return 1
    if check_winner(board, "X"): return -1
    if is_full(board): return 0

    # Maximizing Step (AI)
    if is_maximizing:
        best_score = -1000
        for i in range(9):
            if board[i] == " ":
                board[i] = "O"
                score = minimax(board, False)
                board[i] = " "
                best_score = max(score, best_score)
        return best_score
    
    # Minimizing Step (Human)
    else:
        best_score = 1000
        for i in range(9):
            if board[i] == " ":
                board[i] = "X"
                score = minimax(board, True)
                board[i] = " "
                best_score = min(score, best_score)
        return best_score

def get_best_move(board):
    best_score = -1000
    move = -1
    for i in range(9):
        if board[i] == " ":
            board[i] = "O"
            score = minimax(board, False)
            board[i] = " "
            if score > best_score:
                best_score = score
                move = i
    return move

def play_game():
    board = [" " for _ in range(9)]
    print_board(board)

    while True:
        user_input = input("Enter move 0-8 (or 'e' to exit): ")
        if user_input.lower() == 'e': sys.exit()

        try:
            choice = int(user_input)
            if board[choice] != " ": continue
            board[choice] = "X"
        except ValueError: continue

        print_board(board)
        if check_winner(board, "X"): print("You Win!"); break
        if is_full(board): print("Draw!"); break

        print("AI is calculating futures...")
        ai_move = get_best_move(board)
        board[ai_move] = "O"
        
        print_board(board)
        if check_winner(board, "O"): print("AI Wins!"); break
        if is_full(board): print("Draw!"); break

if __name__ == "__main__":
    play_game()

🙂