Implementare l'algoritmo Minimax per l'IA in Python

L'algoritmo Mini-Max ha una storia ricca nell'IA, risalente agli anni Venti. Sebbene all'epoca non si usasse il termine IA per gli algoritmi informatici, questo algoritmo fondativo fornì sicuramente alcune delle prime intuizioni su come le macchine potessero prendere decisioni ottimali in scenari avversariali. L'algoritmo è stato formalizzato per la prima volta da John von Neumann nel suo articolo del 1928 “Zur Theorie der Gesellschaftsspiele” (Sulla teoria dei giochi di strategia), che ha posto le basi della moderna teoria dei giochi e degli algoritmi decisionali.

Nel 1997, Deep Blue di IBM sconfisse il campione del mondo di scacchi Garry Kasparov utilizzando varianti avanzate del Mini-max. Da allora, l'algoritmo è diventato la spina dorsale di approcci più sofisticati come la Monte Carlo Tree Search (MCTS) e i sistemi di apprendimento per rinforzo.

In questo articolo non ricostruiremo il famoso Deep Blue per gli scacchi, ma una versione molto più semplice per il tris in Python. Lungo il percorso, svilupperai una forte intuizione su come funziona l'algoritmo e su come applicarlo a giochi reali più complessi.

Cos'è l'algoritmo Minimax?

Minimax è di solito un algoritmo decisionale per giochi a due giocatori (come scacchi, tris o dama). Permette ai computer di pianificare diverse mosse assumendo che l'avversario giochi sempre al meglio. In questa sezione vedremo una panoramica dell'algoritmo attraverso l'esempio del tris.

Panoramica dell'algoritmo Minimax

In una partita reale di tris, ogni volta che tocca a te cerchi di fare la mossa migliore possibile, dando per scontato che anche l'avversario giocherà al meglio. È esattamente quello che fa l'algoritmo Minimax: aiuta un computer a fare la mossa migliore pensando in anticipo a tutte le mosse possibili.

L'algoritmo Minimax prende il nome dal suo funzionamento:

• “Mini” rappresenta l'avversario che cerca di minimizzare il tuo punteggio
• “Max” rappresenta te che cerchi di massimizzare il tuo punteggio

Quando è il tuo turno, vuoi fare mosse che ti diano le migliori possibilità di vincere (massimizzare). Quando è il turno dell'avversario, assumi che farà mosse che ti portano al risultato peggiore (minimizzare).

L'importanza di Minimax nell'IA

Minimax è molto importante nell'intelligenza artificiale per diversi motivi:

1. Aiuta i computer a prendere decisioni intelligenti nei giochi a due giocatori
2. È la base di molti sistemi moderni di IA per il gioco
3. Insegna ai computer a pensare in anticipo e pianificare le mosse

La parte più interessante? La stessa idea è usata in molte applicazioni reali:

• Avversari IA nei videogiochi
• Giochi di strategia come scacchi e dama
• Perfino alcuni strumenti di decisione aziendale

Anche se Minimax può sembrare complicato, in realtà si tratta di insegnare a un computer a pensare come un giocatore accorto che considera sia le proprie mosse che quelle dell'avversario prima di decidere.

Capire l'algoritmo Minimax

Vediamo nel dettaglio come funziona Minimax usando un semplice esempio di tris. Immagina di giocare come X e che il computer sia O.

Come pensa il computer

Quando tocca al computer, segue questi passaggi:

1. Guarda tutte le mosse possibili che può fare
2. Per ogni mossa, immagina cosa potresti fare tu dopo
3. Continua a pensare in avanti finché non raggiunge un punto finale (come una vittoria o un pareggio)
4. Sceglie la mossa che gli dà la migliore possibilità di vincere

Assegnare un punteggio alla partita

Il computer può usare un semplice sistema di punteggio:

• +10 punti se vince il computer
• -10 punti se vinci tu
• 0 punti se è un pareggio

Pensalo come un albero di possibilità:

• In cima c'è la scacchiera attuale
• Ogni ramo è una mossa possibile
• Alla base ci sono tutti i risultati possibili

Turni alternati

Il computer alterna due modalità di pensiero:

1. Modalità massimizzazione (turno del computer):

• Cerca mosse che ottengono il punteggio più alto
• Prova a vincere o forzare un pareggio

2. Modalità minimizzazione (turno del giocatore):

• Assume che tu farai mosse che portano al punteggio più basso
• Si prepara alle tue mosse migliori

Un esempio semplice

Diciamo che è il turno del computer (X) in questa partita:

Il computer farà:

1. Vede che ha 3 caselle vuote tra cui scegliere
2. Per ogni casella vuota, immagina tutte le mosse future possibili
3. Sceglie la mossa che porta al risultato migliore per sé
4. In questo caso, dovrebbe selezionare il centro in basso per bloccare la tua vittoria

Questo modo di pensare in anticipo aiuta il computer a giocare una partita perfetta di tris ogni volta!

Pseudocodice dell'algoritmo Minimax

Vediamo come scrivere l'algoritmo Minimax passo dopo passo. Non preoccuparti se sei nuovo allo pseudocodice: pensalo come scrivere i passaggi in semplice inglese prima di trasformarli in vero codice!

Spiegazione passo-passo

La funzione Minimax ha bisogno di tre elementi principali per funzionare:

1. La scacchiera attuale
2. La profondità (quante mosse in avanti stiamo guardando)
3. Se è il turno del giocatore massimizzante (computer) o del giocatore minimizzante (umano)

Ecco come appare lo pseudocodice di base:

function minimax(board, depth, isMaximizingPlayer):
   # First, check if the game is over
   if game is won:
       return +10 if computer wins, -10 if human wins
   if game is tied:
       return 0

   # If it's the computer's turn (maximizing)
   if isMaximizingPlayer:
       bestScore = -infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, false)
           undo the move
           bestScore = max(score, bestScore)
       return bestScore

   # If it's the human's turn (minimizing)
   else:
       bestScore = +infinity
       for each empty spot on board:
           make the move
           score = minimax(board, depth + 1, true)
           undo the move
           bestScore = min(score, bestScore)
       return bestScore

Sebbene la maggior parte degli esempi di pseudocodice sia in inglese e perfettamente comprensibile, quello sopra è diverso perché usa la ricorsione. La ricorsione è quando una funzione chiama sé stessa più e più volte per risolvere un problema più grande. Pensala come guardare in uno specchio che riflette un altro specchio: vedi la stessa immagine ripetuta molte volte, ogni volta più piccola.

Nel nostro algoritmo Minimax, abbiamo bisogno della ricorsione perché stiamo cercando di considerare tutte le mosse future possibili nel gioco. Ogni volta che la funzione chiama sé stessa, sta osservando la mossa successiva che potrebbe accadere. 

Questo ci aiuta a trovare la mossa migliore controllando ogni possibile evoluzione della partita, come un giocatore molto intelligente che pensa “Se faccio questo, allora lui potrebbe fare quello, poi io potrei fare questo…”, e così via fino alla fine del gioco. Per saperne di più sulla ricorsione, puoi leggere il nostro tutorial separato sulla ricorsione.

Esempio illustrativo

Vediamo come funziona in una situazione di gioco semplice:

1. Posizione iniziale:

2. Il computer pensa:

• “Se metto X in una qualsiasi casella vuota…”
• “Cosa farebbe l'umano dopo?”
• “E cosa potrei fare io dopo?”
• “Quale mossa mi dà il punteggio finale migliore?”

3. Per ogni casella vuota, il computer:

• Esegue una mossa
• Verifica se la partita è finita
• Se non è finita, immagina la migliore mossa dell'umano
• Continua finché non trova una conclusione
• Sceglie la mossa con il punteggio più alto

Pensala come negli scacchi: stai sempre pensando “Se mi muovo qui, lui si muoverà lì, poi io potrò muovermi qui…”, ma il computer può pensare a TUTTE le mosse possibili contemporaneamente!

La cosa interessante di questo algoritmo è che trova sempre la mossa migliore possibile, assumendo che entrambi i giocatori giochino perfettamente. È come avere una sfera di cristallo che ti mostra tutti i possibili futuri della partita!

Implementare Minimax per il tris passo dopo passo

In questa sezione costruiremo un'IA imbattibile per il tris alimentata dall'algoritmo Mini-max in puro Python. Scomporremo l'implementazione in passaggi semplici e spiegheremo l'intuizione dietro ciascuno e come si inserisce nel quadro generale del gioco.

Passo 1: Definire una classe TicTacToe

Per prima cosa, definiamo una classe che contenga tutta la logica e i metodi necessari per giocare a tris con i nostri computer:

class TicTacToe:
   def __init__(self):
       # Initialize empty board (using ' ' for empty squares)
       self.board = [" " for _ in range(9)]
       self.human_player = "O"
       self.ai_player = "X"

   def print_board(self):
       """Print the current state of the board"""
       for i in range(0, 9, 3):
           print(f"{self.board[i]} | {self.board[i+1]} | {self.board[i+2]}")
           if i < 6:
               print("---------")

   def available_moves(self):
       """Returns list of available moves (indices of empty squares)"""
       return [i for i, spot in enumerate(self.board) if spot == " "]

Sopra, il metodo __init__ inizializza una nuova scacchiera come una lista di 9 spazi vuoti (rappresentati da spazi " "), con indici 0-8 che rappresentano le posizioni da sinistra a destra, dall'alto verso il basso. Imposta anche due simboli per i giocatori: "O" per l'umano e "X" per l'IA.

Il metodo print_board fornisce un modo per visualizzare lo stato attuale della scacchiera. Stampa la griglia 3x3 con linee divisorie tra le righe, mostrando le mosse di ciascun giocatore nelle rispettive posizioni.

Il metodo available_moves restituisce un elenco di tutte le mosse valide ancora possibili. Lo fa controllando quali posizioni sulla scacchiera sono ancora vuote (contengono uno spazio " ") e restituendone gli indici. Questo sarà cruciale perché l'algoritmo minimax sappia quali mosse considerare.

Questi metodi costituiscono la base su cui costruiremo il nostro giocatore IA usando l'algoritmo minimax.

Facciamo un test rapido:

>>> game = TicTacToe()
>>> game.print_board()
  |   | 
---------
  |   | 
---------
  |   |

>>> game.available_moves()
[0, 1, 2, 3, 4, 5, 6, 7, 8]

Come previsto, al momento la scacchiera è vuota e tutte le mosse sono disponibili.

Passo 2: Implementare i metodi per effettuare una mossa e controllare lo stato della scacchiera

Ora aggiungiamo un metodo per effettuare una mossa:

class TicTacToe:
   ...
  
   def make_move(self, position, player):
       """Make a move on the board"""
       if self.board[position] == " ":
           self.board[position] = player
           return True
       return False

Abbiamo aggiunto il metodo make_move che:

• Riceve una posizione (0–8) e il simbolo del giocatore (“X” o “O”)
• Controlla se la posizione selezionata è vuota (“ ”)
• Se è vuota, posiziona il simbolo del giocatore e restituisce True
• Se la posizione è già occupata, restituisce False senza apportare modifiche

Facciamo qualche mossa e controlliamo quelle rimanenti:

>>> game = TicTacToe()

>>> game.make_move(0, "X")
>>> game.make_move(1, "O")

>>> game.print_board()
 X | O | 
-----------
   |   | 
-----------
   |   |

>>> game.available_moves()
[2, 3, 4, 5, 6, 7, 8]

Funziona bene. Il passo successivo è aggiungere un metodo per controllare se la scacchiera è piena:

class TicTacToe:
   ...

   def is_board_full(self):
       """Check if the board is full"""
       return " " not in self.board

is_board_full è un metodo booleano che verifica se ci sono ancora spazi vuoti sulla scacchiera.

Successivamente, aggiungiamo un metodo per verificare se è stato raggiunto uno stato vincente:

class TicTacToe:
   ...

   def check_winner(self):
       """Check if there's a winner. Returns winner symbol or None"""
       # Check rows
       for i in range(0, 9, 3):
           if self.board[i] == self.board[i + 1] == self.board[i + 2] != " ":
               return self.board[i]

       # Check columns
       for i in range(3):
           if self.board[i] == self.board[i + 3] == self.board[i + 6] != " ":
               return self.board[i]

       # Check diagonals
       if self.board[0] == self.board[4] == self.board[8] != " ":
           return self.board[0]
       if self.board[2] == self.board[4] == self.board[6] != " ":
           return self.board[2]

       return None

Il metodo check_winner valuta lo stato attuale della scacchiera del tris per determinare se c'è un vincitore. Controlla tutte le combinazioni vincenti possibili:

1. Righe (3 possibilità):

• Riga superiore (indici 0,1,2)
• Riga centrale (indici 3,4,5)
• Riga inferiore (indici 6,7,8)

2. Colonne (3 possibilità):

• Colonna sinistra (indici 0,3,6)
• Colonna centrale (indici 1,4,7)
• Colonna destra (indici 2,5,8)

3. Diagonali (2 possibilità):

• Dall'alto a sinistra al basso a destra (indici 0,4,8)
• Dall'alto a destra al basso a sinistra (indici 2,4,6)

Per ogni combinazione controlla se tutte e tre le posizioni contengono lo stesso simbolo del giocatore (X o O) e non sono spazi vuoti. Se trova una combinazione vincente, restituisce il simbolo del giocatore vincitore. Se non trova alcun vincitore dopo aver controllato tutte le possibilità, restituisce None.

Testiamo la funzione in stati vincenti e non:

game = TicTacToe()

# Winning state
game.make_move(0, "X")
game.make_move(1, "X")
game.make_move(2, "X")

>>> game.print_board()
 X | X | X
-----------
   |   | 
-----------
   |   |

>>> game.check_winner()
'X'

game = TicTacToe()

# Non-winning state
game.make_move(0, "X")
game.make_move(1, "O")
game.make_move(2, "O")
game.make_move(3, "X")

>>> game.print_board()
 X | O | O
-----------
 X |   | 
-----------
   |   |

>>> game.check_winner() is None
True

Infine, aggiungiamo un altro metodo booleano per specificare se la partita è finita o meno:

class TicTacToe:
   ...

   def game_over(self):
       """Check if the game is over"""
       return self.check_winner() is not None or self.is_board_full()

Il metodo restituisce True se è stato trovato un vincitore oppure se la scacchiera è piena.

A questo punto abbiamo costruito tutte le meccaniche di gioco principali:

• La scacchiera è rappresentata come una lista di 9 caselle inizializzate vuote
• print_board() mostra visivamente lo stato attuale del gioco
• available_moves() restituisce gli indici delle caselle vuote
• make_move() posiziona il simbolo di un giocatore sulla scacchiera
• check_winner() esamina righe, colonne e diagonali per rilevare una vittoria a ogni mossa
• is_board_full() determina se non restano mosse
• game_over() combina il controllo del vincitore e della scacchiera piena

Questi metodi forniscono le basi per creare un gioco giocabile, gestendo tutte le operazioni di base come effettuare mosse e determinare lo stato della partita.

Ora arriva la parte cruciale: dare al computer il “cervello” per giocare usando Minimax.

Passo 3: Implementare Minimax per il tris

Ora implementiamo l'algoritmo per il gioco in un nuovo metodo:

class TicTacToe:
   ...

   def minimax(self, depth, is_maximizing):
       """
       Minimax algorithm implementation
       Returns the best score possible for the current board state
       """
       # Base cases
       winner = self.check_winner()
       if winner == self.ai_player:
           return 1
       if winner == self.human_player:
           return -1
       if self.is_board_full():
           return 0

La funzione accetta due parametri:

• depth - Tiene traccia di quanti livelli in profondità siamo nella ricorsione. Può essere usata per limitare la profondità di ricerca in giochi molto complessi, anche se per il tris non è necessario.
• is_maximizing - Un flag booleano che indica se stiamo cercando il punteggio massimo (turno dell'IA) o minimo (turno dell'umano). Questo alterna a ogni chiamata ricorsiva man mano che i giocatori si alternano.

Nel corpo della funzione, iniziamo definendo i casi base: se la partita è vinta dall'IA (winner == ai_player), restituiamo 1 perché è il miglior esito per l'IA. Se vince l'umano (winner == human_player), restituiamo -1 perché è il peggiore. Se la scacchiera è piena senza vincitore, restituiamo 0 per un pareggio.

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       best_score = float("-inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(depth + 1, False)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = max(score, best_score)
       return best_score

Quando is_maximizing è True, stiamo simulando il turno dell'IA e vogliamo trovare la mossa che porta al punteggio più alto possibile. Iniziamo impostando best_score a meno infinito così qualsiasi punteggio reale sarà migliore. Poi, per ogni mossa disponibile:

1. Posizioniamo temporaneamente il simbolo dell'IA sulla scacchiera
2. Valutiamo ricorsivamente cosa succederebbe chiamando minimax con is_maximizing=False (dato che poi sarebbe il turno dell'umano)
3. Annulliamo la mossa temporanea per ripristinare lo stato della scacchiera
4. Teniamo traccia del punteggio più alto visto finora usando max()

Questo ci permette di controllare ogni possibile mossa che l'IA potrebbe fare. Per ciascuna, guardiamo cosa potrebbe accadere dopo, fino a quando qualcuno vince o la partita finisce in pareggio. Poi torniamo indietro per trovare quale prima mossa dà all'IA la migliore possibilità di vincere.

Ora, passiamo alla parte di minimizzazione per l'umano:

def minimax(self, depth, is_maximizing):
   ...

   # if it is the maximizing player's turn (AI), we want to maximize the score
   if is_maximizing:
       ...

   else:
       # if it is the minimizing player's turn (human), we want to minimize the score
       best_score = float("inf")
       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.human_player
           # Recursively call minimax with the next depth and the maximizing player
           score = self.minimax(depth + 1, True)
           # Reset the move
           self.board[move] = " "
           # Update the best score
           best_score = min(score, best_score)
       return best_score

Quando is_maximizing è False, stiamo simulando il turno del giocatore umano e vogliamo trovare la mossa che porta al punteggio più basso possibile (dato che un punteggio alto significa vittoria dell'IA). Partiamo con best_score a più infinito così qualsiasi punteggio reale sarà inferiore. Per ogni mossa disponibile:

1. Posizioniamo temporaneamente il simbolo dell'umano sulla scacchiera
2. Valutiamo ricorsivamente cosa succederebbe chiamando minimax con is_maximizing=True (dato che poi sarebbe il turno dell'IA)
3. Annulliamo la mossa temporanea per ripristinare lo stato della scacchiera
4. Teniamo traccia del punteggio più basso visto usando min()

Questo simula il giocatore umano che cerca di fare le mosse migliori per impedire all'IA di vincere. L'umano vuole minimizzare il punteggio perché i punteggi positivi rappresentano vittorie dell'IA. Alternando tra turni di massimizzazione e minimizzazione, l'algoritmo può determinare la sequenza di mosse ottimale per entrambi i giocatori.

Passo 4: Trovare la mossa migliore per l'IA usando Minimax

Ora che abbiamo l'algoritmo pronto, ci serve un altro metodo che usi il metodo minimax per determinare la mossa migliore per l'IA dopo ogni mossa dell'umano:

class TicTacToe:
   ...

   def get_best_move(self):
       """Find the best move for AI using minimax"""
       best_score = float("-inf")
       best_move = None

       for move in self.available_moves():
           # Make a calculating move
           self.board[move] = self.ai_player
           # Recursively call minimax with the next depth and the minimizing player
           score = self.minimax(0, False)
           # Reset the move
           self.board[move] = " "

           # Update the best score
           if score > best_score:
               best_score = score
               best_move = move

       return best_move

Il metodo get_best_move è responsabile di determinare la mossa ottimale per il giocatore IA utilizzando l'algoritmo minimax. Funziona così:

1. Parte da meno infinito come punteggio migliore e nessuna mossa selezionata

2. Per ogni mossa disponibile sulla scacchiera:

• Posiziona temporaneamente il simbolo dell'IA in quella posizione
• Usa minimax per valutare quanto è buona quella mossa simulando il resto della partita
• Annulla la mossa temporanea
• Se questa mossa porta a un punteggio migliore di quelli visti finora, aggiorna sia il punteggio migliore che la mossa migliore

3. Infine restituisce la mossa che ha portato al punteggio più alto

Questo approccio assicura che l'IA scelga la mossa che le dà la migliore possibilità di vincere, assumendo che anche il giocatore umano giochi in modo ottimale. Il metodo considera tutti i possibili stati futuri del gioco e sceglie il percorso che massimizza le chance dell'IA minimizzando quelle dell'umano.

Testiamolo su uno stato di gioco di esempio:

game = TicTacToe()

# Make a couple of moves
game.make_move(0, "X")
game.make_move(1, "O")

# Print the board

>>> game.print_board()
X | O | 
---------
  |   | 
---------
  |   |

>>> game.get_best_move()
3

# AI moves
>>> game.make_move(3, "X")

# I move
>>> game.make_move(4, "O")
>>> game.print_board()
X | O | 
---------
X | O | 
---------
  |   |

# Get the best move for AI
>>> game.get_best_move()
6

Come puoi vedere, l'IA ha trovato la combinazione vincente in base alle mie mosse (era uno stato fittizio, ma prova che il nostro algoritmo funziona).

Passo 5: Implementare un ciclo di gioco

Ora che abbiamo implementato e testato il nostro algoritmo minimax, creiamo un game loop che ci permetta di giocare contro l'IA.

class TicTacToe:

   ...

   def play_game(self):
       """Main game loop"""
       print("Welcome to Tic Tac Toe!")
       print("You are 'O' and the AI is 'X'")
       print("Enter positions (0-8) as shown below:")
       print("0 | 1 | 2")
       print("---------")
       print("3 | 4 | 5")
       print("---------")
       print("6 | 7 | 8")
       print("\n")

Il metodo play_game inizia mostrando un messaggio di benvenuto e le istruzioni per il giocatore. Indica che il giocatore umano usa ‘O’ e l'IA usa ‘X’. Poi stampa una griglia numerata (0–8) per mostrare quale numero corrisponde a ciascuna posizione sulla scacchiera. Questo rende facile per i giocatori sapere esattamente quale numero inserire per la mossa desiderata.

# ... the rest of the class
def play_game(self):
   ...

   # Randomly decide who goes first
   import random

   ai_turn = random.choice([True, False])

   while not self.game_over():
       self.print_board()

       if ai_turn:
           print("\nAI's turn...")
           move = self.get_best_move()
           self.make_move(move, self.ai_player)
       else:
           while True:
               try:
                   move = int(input("\nYour turn (0-8): "))
                   if 0 <= move <= 8 and self.make_move(move, self.human_player):
                       break
                   else:
                       print("Invalid move! Try again.")
               except ValueError:
                   print("Please enter a number between 0 and 8!")

       ai_turn = not ai_turn

Dopo aver mostrato le istruzioni iniziali, il gioco entra nel suo ciclo principale. La partita decide casualmente chi inizia — l'IA o il giocatore umano — usando random.choice([True, False]). Questo crea un elemento di equità e imprevedibilità all'inizio di ogni partita.

Il ciclo principale continua finché game_over() non restituisce True (qualcuno ha vinto o la scacchiera è piena). A ogni turno viene mostrato lo stato attuale della scacchiera con print_board().

Se è il turno dell'IA (ai_turn è True), il programma:

1. Stampa un messaggio che indica che l'IA sta pensando
2. Chiama get_best_move() per determinare la mossa ottimale usando l'algoritmo minimax
3. Esegue la mossa posizionando il simbolo dell'IA (‘X’) nella posizione scelta

Se è il turno dell'umano (ai_turn è False), il programma:

1. Entra in un ciclo per ottenere un input valido dal giocatore2. Richiede un numero di mossa tra 0–83. Valida che l'input sia:

• Un numero intero valido (usando try/except)
• All'interno dell'intervallo valido 0–8
• Riferito a una posizione vuota sulla scacchiera

4. Continua a chiedere finché non riceve un input valido. Esegue la mossa posizionando il simbolo del giocatore (‘O’) nella posizione scelta

Dopo ogni turno, ai_turn viene invertito usando not per alternare tra i giocatori. Questo crea il botta e risposta della partita, con i giocatori che si alternano finché qualcuno vince o la partita finisce in pareggio.

La validazione dell'input assicura che il gioco non vada in crash per input non validi e fornisce messaggi di errore utili per guidare il giocatore nell'inserire mosse corrette. Questo crea un'esperienza di gioco robusta e user-friendly.

def play_game(self):
   ...
   # Game over
   self.print_board()
   winner = self.check_winner()
   if winner == self.ai_player:
       print("\nAI wins!")
   elif winner == self.human_player:
       print("\nCongratulations! You win!")
   else:
       print("\nIt's a tie!")

Quando la partita finisce, lo stato finale della scacchiera viene mostrato con print_board() e il vincitore viene determinato da check_winner(). La partita può finire in tre modi:

1. Vince l'IA — Se check_winner() restituisce il simbolo dell'IA ('X'), indicando che l'IA ha realizzato una linea vincente
2. Vince l'umano — Se check_winner() restituisce il simbolo dell'umano ('O'), indicando che il giocatore ha realizzato una linea vincente
3. Pareggio — Se nessuno ha vinto ma la scacchiera è piena, quindi non sono più possibili mosse

Viene mostrato il messaggio appropriato per annunciare l'esito della partita. Questo fornisce un feedback chiaro al giocatore su come si è concluso il gioco.

Passo 6: Mettere tutto insieme

Ora è il momento di mettere tutto il codice scritto finora in uno script Python con la seguente clausola if/main alla fine:

# Start the game
if __name__ == "__main__":
   game = TicTacToe()
   game.play_game()

Questo permette di avviare il gioco non appena esegui lo script con python script.py. Se ti sei perso tra tutte le spiegazioni e i blocchi di codice, puoi trovare il codice completo del gioco in questa gist su GitHub.

Ecco un esempio di partita che ho giocato:

❯ python tic-tac-toe.py
Welcome to Tic Tac Toe!
You are 'O' and the AI is 'X'
Enter positions (0-8) as shown below:
0 | 1 | 2
---------
3 | 4 | 5
---------
6 | 7 | 8


  |   | 
---------
  |   | 
---------
  |   | 

Your turn (0-8): 4
  |   | 
---------
  | O | 
---------
  |   | 

AI's turn...
X |   | 
---------
  | O | 
---------
  |   | 

Your turn (0-8): 5
X |   | 
----------
  | O | O
----------
  |   | 

AI's turn...
X |   | 
---------
X | O | O
---------
  |   | 

Your turn (0-8): 6
X |   | 
---------
X | O | O
---------
O |   | 

AI's turn...
X |   | X
---------
X | O | O
---------
O |   | 

Your turn (0-8): 1
X | O | X
---------
X | O | O
---------
O |   | 

AI's turn...
X | O | X
---------
X | O | O
---------
O | X | 

Your turn (0-8): 8
X | O | X
---------
X | O | O
---------
O | X | O

It's a tie!

Ricorda: dato che il tris è un gioco semplice, non c'è modo di battere l'IA. O finisce in pareggio o perdi!

Formalizzare l'algoritmo Mini-max

Ora rivediamo la definizione generale dell'algoritmo al di là del semplice esempio del tris.

L'algoritmo Minimax può essere definito formalmente come una funzione ricorsiva che valuta le posizioni in un gioco a somma zero. Analizziamone le componenti e le proprietà formali.

Definizione matematica

Per uno stato di gioco s, il valore minimax V(s) è definito come:

V(s) =
   utility(s)                    if s is terminal
   max(V(s')) for all s' in S    if player = MAX
   min(V(s')) for all s' in S    if player = MIN

Dove:

• s’ rappresenta gli stati successori di s
• S è l'insieme di tutte le mosse legali dallo stato s
• utility(s) è la funzione di valutazione per gli stati terminali

Proprietà chiave

1. Informazione perfetta

• Tutti i giocatori hanno conoscenza completa dello stato del gioco
• Nessuna informazione nascosta o elementi aleatori
• Esiti deterministici

2. Natura a somma zero

• Il guadagno di un giocatore è esattamente la perdita dell'altro
• La somma delle utilità per tutti i giocatori è sempre zero
• Per i giochi a due giocatori, le utilità sono tipicamente {-1, 0, 1}

3. Gioco ottimale

• Assume che entrambi i giocatori prendano decisioni ottimali
• Garantisce il miglior risultato possibile contro un gioco perfetto
• Conduce a un equilibrio di Nash in termini di teoria dei giochi

Analisi della complessità

Complessità temporale: O(b^m)

• b = fattore di diramazione (numero di mosse legali a ogni stato)
• m = profondità massima dell'albero di gioco

Complessità spaziale: O(bm)

• Richiede di memorizzare lo stato di gioco a ogni livello
• Può essere ottimizzata con deepening iterativo

Funzione di valutazione

Per gli stati non terminali, la funzione di valutazione f(s) dovrebbe:

1. Correlare con la probabilità di vittoria
2. Essere computazionalmente efficiente
3. Mantenere una scala coerente durante il gioco

La definizione formale:

f(s) = w₁x₁ + w₂x₂ + ... + wₙxₙ

Dove:

• wᵢ sono i pesi per diverse caratteristiche
• xᵢ sono i valori delle caratteristiche dallo stato di gioco
• n è il numero di caratteristiche valutate

Garanzia di optimalità

L'algoritmo Minimax garantisce gioco ottimale a queste condizioni:

1. Informazione perfetta
2. Esiti deterministici
3. Ricerca completa fino agli stati terminali
4. Valutazione accurata degli stati terminali

Questo lo rende particolarmente adatto a giochi come scacchi, tris e dama, dove queste condizioni sono soddisfatte.

Varianti avanzate e limitazioni

Sebbene Minimax sia ottimo per giochi semplici come il tris, ha dei problemi con giochi più grandi. Vediamo come possiamo migliorarlo e dove fa fatica.

Rendere Minimax più veloce: potatura Alpha-beta

Immagina di giocare a scacchi e pensare alle tue mosse. Se hai trovato una mossa vincente, non hai bisogno di controllare tutte le altre, giusto? La potatura Alpha-Beta funziona allo stesso modo: aiuta il computer a saltare il controllo di mosse che sappiamo già non saranno migliori di quelle trovate.

Pensala così:

• Stai cercando la barretta di cioccolato più economica
• Hai 1$ da spendere
• Se trovi una barretta a 50¢, puoi saltare quelle che costano più di 1$
• Risparmi tempo!

Limiti di profondità: non guardare troppo avanti

Nei giochi grandi come gli scacchi, ci sono troppe mosse possibili per controllarle tutte. Quindi aggiungiamo un limite di profondità:

1. Guardiamo solo 4–5 mosse in avanti invece che fino alla fine
2. Facciamo una buona stima di quanto sia buona la posizione a quel punto
3. Scegliamo la mossa migliore basandoci su queste stime

Non puoi pianificare ogni mossa fino alla fine, ma puoi pianificarne alcune in avanti!

Dove Minimax va in difficoltà

Minimax non è perfetto. Ecco i suoi principali problemi:

1. Troppe scelte

• Giochi come Go hanno moltissime mosse possibili
• Anche i computer veloci non possono controllarle tutte
• Per questo servono altri metodi per i giochi davvero complessi

2. Problemi di tempo

• Più mosse guardi in avanti, più tempo serve
• Negli scacchi, i computer non possono valutare ogni mossa possibile
• Devono essere intelligenti nel selezionare quali mosse controllare

3. Non è ottimo per giochi incerti

• Minimax funziona meglio quando puoi vedere tutto
• Non è adatto a giochi di carte dove non conosci le carte degli altri
• Non gestisce bene gli eventi casuali (come i tiri di dado)

Soluzioni moderne

Le IA di gioco moderne spesso combinano Minimax con altre tecniche interessanti:

1. Apprendimento automatico

• I computer possono imparare osservando molte partite
• Questo li aiuta a fare stime migliori sulle mosse buone
• Giochi come AlphaGo lo usano per battere campioni umani

2. Riconoscimento di pattern

• Invece di controllare ogni mossa, cerca schemi ricorrenti
• Proprio come i giocatori umani riconoscono le mosse buone
• Questo rende il computer molto più veloce

3. Memoria

• Ricorda posizioni già viste
• Non perdere tempo a ricalcolare la stessa cosa due volte
• È come avere un bignami di mosse buone!

La parte più interessante? Questi miglioramenti aiutano i computer a giocare quasi come gli umani, e a volte anche meglio! Ma ricorda: anche con tutte queste aggiunte, Minimax resta il fondamento che fa funzionare tutto.

Conclusione

In questo tutorial abbiamo esplorato l'algoritmo Minimax dai concetti di base all'implementazione pratica. Ecco cosa abbiamo imparato:

1. Concetti chiave

• Come Minimax aiuta i computer a prendere decisioni nei giochi
• La differenza tra giocatori minimizzanti e massimizzanti
• Perché si chiama “minimax” e come funziona

2. Competenze di implementazione

• Costruire un gioco di tris da zero
• Scrivere l'algoritmo Minimax in Python
• Testare e fare debug della logica di gioco

3. Argomenti avanzati

• Rendere l'algoritmo più veloce con la potatura Alpha-Beta
• Gestire le limitazioni nei giochi complessi
• Miglioramenti moderni con il machine learning

E adesso?

L'algoritmo Minimax è solo un pezzo del puzzle dell'IA. Se sei entusiasta di imparare di più su IA e algoritmi, ecco alcune ottime risorse per continuare il tuo percorso:

1. Algoritmi correlati

• Tutorial sull'algoritmo A* — Impara gli algoritmi di pathfinding
• Guida al Gradient Boosting — Esplora gli algoritmi di machine learning

2. Applicazioni di Machine Learning

• Casi d'uso del Machine Learning — Vedi applicazioni nel mondo reale

3. Percorsi completi

• Sviluppo di applicazioni IA — Crea progetti IA pratici
• Fondamenti di IA — Padroneggia le basi dell'IA

Ricorda, che tu stia costruendo un gioco semplice o un sistema IA complesso, comprendere algoritmi come Minimax ti dà una solida base per argomenti più avanzati nell'intelligenza artificiale. Continua a esercitarti, continua a imparare e, soprattutto, continua a programmare!