Algoritmo Min Max in AI: componenti, proprietà, vantaggi e limitazioni

L' algoritmo min max nell'IA, popolarmente noto come minimax, è un algoritmo di backtracking utilizzato nel processo decisionale, nella teoria dei giochi e nell'intelligenza artificiale (AI). Viene utilizzato per trovare la mossa ottimale per un giocatore, supponendo che anche l'avversario stia giocando in modo ottimale. I popolari giochi per computer a due giocatori o online come Scacchi, Tris, Dama, Go, ecc. utilizzano questo algoritmo.

Un algoritmo di backtracking viene utilizzato per trovare una soluzione ai problemi di calcolo in modo tale che un candidato sia costruito in modo incrementale verso una soluzione, un passo alla volta. E il candidato che non riesce a portare a termine una soluzione viene immediatamente abbandonato.

Come funziona?

Nell'algoritmo min max in AI, ci sono due giocatori, Maximiser e Minimiser. Entrambi questi giocatori giocano mentre uno cerca di ottenere il punteggio più alto possibile o il massimo beneficio mentre l'avversario cerca di ottenere il punteggio più basso o il vantaggio minimo.

Ad ogni tabellone di gioco è assegnato un punteggio di valutazione, quindi il Maximiser selezionerà il valore massimizzato e il Minimiser selezionerà il valore ridotto al minimo con contromosse. Se il Maximiser ha il sopravvento, il punteggio del board sarà un valore positivo, e se il Minimiser ha il sopravvento, il punteggio del board sarà un valore negativo.

Questo si basa sul concetto di gioco a somma zero in cui il punteggio di utilità totale viene diviso tra i due giocatori. Pertanto, un aumento del punteggio di un giocatore porta a una diminuzione del punteggio del giocatore avversario, rendendo il punteggio totale sempre zero. Quindi, affinché un giocatore vinca, l'altro deve perdere.

Partecipa ai corsi Machine Learning Certification e AI online delle migliori università del mondo. Guadagna Master, Executive PGP o ACP per accelerare la tua carriera.

Scomposizione dell'algoritmo min max in AI

L'albero di gioco completo viene esplorato con un algoritmo di ricerca in profondità nell'algoritmo min max in AI. Procede interamente fino al nodo terminale dell'albero e poi torna indietro attraverso l'albero.

L'obiettivo è trovare la migliore mossa possibile per un giocatore. Questo può essere fatto scegliendo il nodo con il miglior punteggio di valutazione. La scelta migliore verrà fatta dopo aver valutato tutte le potenziali mosse dell'avversario. L'algoritmo guarda avanti a tutti i valori possibili fino alla fine e prende una decisione per il giocatore.

Fonte

L'albero di gioco sopra è una struttura di dati annidata che viene utilizzata per valutare le mosse. Qui il nodo radice è il livello 0, che si dirama in nodi di livello 1 o padre, che si diramano ulteriormente in nodi di livello 2 o figli. La ramificazione può continuare a molti livelli, avendo il potenziale di infiniti livelli. Il livello 0 è come lo stato attuale del tabellone, mentre il livello 1 è tutti i possibili stati del tabellone a seconda della mossa successiva.

Quindi, se il giocatore 2 ha fatto una mossa, possiamo presumere che il nodo principale sia lo stato corrente del tabellone, in attesa della mossa del giocatore 1. I nodi di livello 1 contengono tutte le possibili mosse per il giocatore 1 e i nodi di livello 2 contengono tutte le possibili mosse per il giocatore 2 in base a ciascuna possibile mossa del giocatore 1.

Considera un esempio in cui ci sono quattro stati finali e il percorso per raggiungerli va dalla radice alle quattro foglie di un albero. I valori delle quattro foglie sono 3, 6 a sinistra e 4, 7 a destra. È il turno del Maximiser/Giocatore 1 di fare una mossa. Per eseguire l'algoritmo, è necessario formulare ipotesi per ogni mossa.

Se il Giocatore 1 sceglie di andare a sinistra, il Minimizzatore/Giocatore 2 deve scegliere il minimo tra 3 e 6, quindi sceglierà 3. Mentre se il Giocatore 1 sceglierà a destra, il Giocatore 2 sceglierà 4, che è il minimo dei due valori, 4 e 7. Quindi, il livello 1 ora ha i valori 3 e 4.

Poiché è il turno del Giocatore 1/Maximizer, deve scegliere il massimo di nodi di Livello 1. Quindi, sceglieranno 3. Quindi la scelta ottimale è andare a sinistra.

I passaggi per l' algoritmo min max in AI possono essere indicati come segue:

1. Crea l'intero albero di gioco.
2. Valuta i punteggi per i nodi foglia in base alla funzione di valutazione.
3. Backtrack dalla foglia ai nodi radice:

Per Maximizer, scegli il nodo con il punteggio massimo.

Per Minimizer, scegli il nodo con il punteggio minimo.

4. Al nodo radice, scegli il nodo con il valore massimo e seleziona la rispettiva mossa.

Leggi anche: Idee per progetti di apprendimento automatico

Proprietà dell'algoritmo min max in AI

• L'algoritmo è completo, il che significa che in un albero di ricerca finito si troverà sicuramente una soluzione.
• È ottimale se entrambi i giocatori stanno giocando in modo ottimale.
• A causa della Depth-First Search (DFS) per l'albero del gioco, la complessità temporale dell'algoritmo è O(b m ), dove b è il fattore di ramificazione e m è la profondità massima dell'albero.
• Come DFS, la complessità spaziale di questo algoritmo è O(bm).

Vantaggi

• Viene eseguita una valutazione approfondita dello spazio di ricerca.
• Il processo decisionale nell'IA è facilmente possibile.
• Con questo algoritmo vengono sviluppate macchine nuove e intelligenti.

Limitazioni

• A causa dell'enorme fattore di ramificazione, il processo per raggiungere l'obiettivo è più lento.
• La valutazione e la ricerca di tutti i possibili nodi e rami degradano le prestazioni e l'efficienza del motore.
• Entrambi i giocatori hanno troppe scelte tra cui decidere.
• Se c'è una restrizione di tempo e spazio, non è possibile esplorare l'intero albero.

Ma con Alpha-Beta Pruning, l'algoritmo può essere migliorato.

Conclusione

Questo articolo spiega tutti gli aspetti dell'algoritmo min-max nell'IA. In primo luogo, viene fornita un'introduzione della teoria con esempi di dove viene utilizzata, dopodiché c'è una descrizione di come funziona l'algoritmo in un gioco.

L'algoritmo è suddiviso per spiegare come viene presa la decisione di fare una mossa ottimale in base alle mosse e alle contromosse dei giocatori. Vengono quindi elencate le proprietà dell'algoritmo. Infine, vengono forniti i vantaggi e gli svantaggi dell'algoritmo.

Se sei interessato a saperne di più sull'apprendimento automatico, dai un'occhiata al programma Executive PG di IIIT-B e upGrad in Machine Learning e AI , progettato per i professionisti che lavorano e offre oltre 450 ore di formazione rigorosa, oltre 30 casi di studio e incarichi, IIIT -B Status di Alumni, oltre 5 progetti pratici pratici e assistenza sul lavoro con le migliori aziende.