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.
Football is a zero-sum game as well as tic-tac-toe. But AI cannot simulate it that well.
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
minimaxFunction (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_moveFunction (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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
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() |
🙂