abbiamo esplorato i concetti fondamentali dell’algoritmo Minimax attraverso un semplice gioco dei gettoni implementato in Python. Ora, per approfondire ulteriormente questa potente strategia decisionale utilizzata nell’intelligenza artificiale, ci cimenteremo con un classico: il gioco del Tris (Tic-Tac-Toe). Questo esercizio pratico in Python non solo consoliderà la tua comprensione del Minimax, ma introdurrà anche una tecnica di ottimizzazione cruciale come la potatura Alpha-Beta, dimostrando come un’IA può giocare in modo ottimale a un gioco più complesso.
L’algoritmo Minimax è una strategia di decisione che cerca di minimizzare la perdita massima possibile in scenari competitivi, ed è particolarmente utile nei giochi a somma zero e in situazioni dove è necessario prendere decisioni in ambienti avversari.
Il Gioco del Tris (Tic-Tac-Toe) con Minimax in Python
Questo è un classico esempio di applicazione del Minimax, ma implementato con tecniche moderne di programmazione Python.
Per comprendere meglio il funzionamento dell’algoritmo Minimax, osserviamo l’Albero Minimax semplificato per il Gioco del Tris :
In questo diagramma, ogni nodo rappresenta un possibile stato del gioco, ovvero una particolare configurazione della griglia del Tris. Partendo dalla radice (in questo caso, una tabella vuota), l’algoritmo esplora tutte le mosse possibili per il giocatore corrente.
Notiamo una distinzione fondamentale tra i livelli MAX e MIN. I nodi etichettati come (MAX) rappresentano i turni dell’Intelligenza Artificiale (il giocatore che cerca di massimizzare il proprio punteggio), mentre i nodi (MIN) rappresentano i turni del giocatore umano (che cerca di minimizzare il punteggio dell’AI, o equivalentemente, massimizzare il proprio).
I nodi foglia, situati alla fine di ogni ramo, rappresentano gli stati finali del gioco: una vittoria per l’AI (etichettata come “Vittoria (+10)”), una sconfitta per l’AI (etichettata come “Sconfitta (-10)”, che è una vittoria per l’umano), o un pareggio (etichettato come “Pareggio (0)”). A ciascuno di questi stati finali è associato un punteggio che riflette l’esito del gioco dal punto di vista dell’AI.
L’algoritmo Minimax opera in modo ricorsivo, risalendo l’albero dai nodi foglia verso la radice. Nei livelli MIN, l’algoritmo assume che l’avversario (il giocatore umano) giocherà in modo ottimale per minimizzare il punteggio dell’AI, quindi sceglie il ramo con il punteggio più basso. Nei livelli MAX, l’algoritmo assume che l’AI giocherà in modo ottimale per massimizzare il proprio punteggio, quindi sceglie il ramo con il punteggio più alto. In questo modo, l’algoritmo determina la mossa migliore da intraprendere nello stato corrente, considerando tutte le possibili sequenze di mosse future.
import numpy as np
import time
class TicTacToe:
def __init__(self):
# Inizializziamo la board 3x3 con valori 0 (vuoti)
self.board = np.zeros((3, 3), dtype=int)
self.human_player = -1 # Il giocatore umano userà -1 (O)
self.ai_player = 1 # L'AI userà 1 (X)
def print_board(self):
# Convertiamo i valori numerici in simboli per la visualizzazione
symbols = {0: ' ', 1: 'X', -1: 'O'}
print("-------------")
for i in range(3):
print("|", end=" ")
for j in range(3):
print(f"{symbols[self.board[i, j]]} |", end=" ")
print("\n-------------")
def is_winner(self, player):
# Controllo righe
for i in range(3):
if np.all(self.board[i, :] == player):
return True
# Controllo colonne
for i in range(3):
if np.all(self.board[:, i] == player):
return True
# Controllo diagonali
if np.all(np.diag(self.board) == player) or np.all(np.diag(np.fliplr(self.board)) == player):
return True
return False
def is_board_full(self):
return not np.any(self.board == 0)
def is_game_over(self):
return self.is_winner(self.human_player) or self.is_winner(self.ai_player) or self.is_board_full()
def get_empty_cells(self):
# Restituisce le coordinate delle celle vuote
empty_cells = np.where(self.board == 0)
return list(zip(empty_cells[0], empty_cells[1]))
def make_move(self, position, player):
# Esegue una mossa se la posizione è valida
i, j = position
if self.board[i, j] == 0:
self.board[i, j] = player
return True
return False
def minimax(self, depth, is_maximizing, alpha=float('-inf'), beta=float('inf')):
# Caso base: se il gioco è terminato, restituisce il punteggio
if self.is_winner(self.ai_player):
return 10 - depth # Vittoria dell'AI, punteggio positivo (più alto se vittoria veloce)
if self.is_winner(self.human_player):
return depth - 10 # Vittoria del giocatore umano, punteggio negativo
if self.is_board_full():
return 0 # Pareggio
# Turno dell'AI (massimizzare)
if is_maximizing:
best_score = float('-inf')
for cell in self.get_empty_cells():
self.board[cell] = self.ai_player
score = self.minimax(depth + 1, False, alpha, beta)
self.board[cell] = 0 # Annulla la mossa
best_score = max(score, best_score)
alpha = max(alpha, best_score)
if beta <= alpha:
break # Potatura alpha-beta
return best_score
# Turno del giocatore umano (minimizzare)
else:
best_score = float('inf')
for cell in self.get_empty_cells():
self.board[cell] = self.human_player
score = self.minimax(depth + 1, True, alpha, beta)
self.board[cell] = 0 # Annulla la mossa
best_score = min(score, best_score)
beta = min(beta, best_score)
if beta <= alpha: break # Potatura alpha-beta return best_score def get_best_move(self): best_score = float('-inf') best_move = None for cell in self.get_empty_cells(): self.board[cell] = self.ai_player score = self.minimax(0, False) self.board[cell] = 0 # Annulla la mossa if score > best_score:
best_score = score
best_move = cell
return best_move
def play_game(self):
print("Benvenuto nel gioco del Tris!")
print("Tu sei O, l'AI è X")
print("Per inserire una mossa, digita la riga (0-2) e la colonna (0-2) separate da uno spazio")
# Decidiamo chi inizia
turn = np.random.choice([self.human_player, self.ai_player])
while not self.is_game_over():
self.print_board()
if turn == self.human_player:
# Turno del giocatore umano
valid_move = False
while not valid_move:
try:
move = input("Inserisci la tua mossa (riga colonna): ")
i, j = map(int, move.split())
if 0 <= i <= 2 and 0 <= j <= 2:
valid_move = self.make_move((i, j), self.human_player)
if not valid_move:
print("Posizione già occupata, riprova.")
else:
print("Inserisci valori tra 0 e 2.")
except ValueError:
print("Inserisci due numeri validi separati da uno spazio.")
turn = self.ai_player
else:
# Turno dell'AI
print("L'AI sta pensando...")
time.sleep(1) # Breve pausa per l'AI
best_move = self.get_best_move()
self.make_move(best_move, self.ai_player)
print(f"L'AI ha scelto la posizione ({best_move[0]}, {best_move[1]})")
turn = self.human_player
# Gioco terminato
self.print_board()
if self.is_winner(self.human_player):
print("Hai vinto! Congratulazioni!")
elif self.is_winner(self.ai_player):
print("L'AI ha vinto!")
else:
print("Pareggio!")
# Esecuzione del gioco
if __name__ == "__main__":
game = TicTacToe()
game.play_game()
Spiegazione passo a passo:
Inizializzazione: Creiamo una classe TicTacToe che gestisce il gioco con una board 3×3 usando NumPy.
Rappresentazione dello stato: Usiamo una matrice dove 0 rappresenta celle vuote, 1 rappresenta l’AI (X) e -1 rappresenta il giocatore umano (O).
Funzioni di utilità: Implementiamo metodi per verificare vittorie, pareggi e visualizzare la board.
Algoritmo Minimax con potatura Alpha-Beta:
L’AI cerca di massimizzare il punteggio (turno dell’AI)
Il giocatore umano cerca di minimizzare il punteggio (turno del giocatore)
La potatura Alpha-Beta riduce il numero di nodi da valutare nell’albero di ricerca
Funzione di valutazione:
+10 per vittoria dell’AI (meno la profondità per favorire vittorie veloci)
-10 per vittoria del giocatore umano (più la profondità per favorire sconfitte lente)
0 per pareggio
Interfaccia utente: Implementiamo un semplice sistema di input per consentire al giocatore di fare mosse.
Questo esempio dimostra come l’algoritmo Minimax permetta all’AI di prendere decisioni ottimali in un gioco a somma zero come il Tris, rendendo l’AI praticamente imbattibile.
