• L'algoritmo Mini-max è un algoritmo ricorsivo o backtracking utilizzato nel processo decisionale e nella teoria dei giochi. Fornisce una mossa ottimale per il giocatore presupponendo che anche l'avversario stia giocando in modo ottimale.
• L'algoritmo Mini-Max utilizza la ricorsione per effettuare ricerche nell'albero del gioco.
• L'algoritmo Min-Max viene utilizzato principalmente per i giochi in AI. Come scacchi, dama, tris, go e vari giochi con giocatori di traino. Questo algoritmo calcola la decisione minimax per lo stato attuale.
• In questo algoritmo due giocatori giocano, uno si chiama MAX e l'altro si chiama MIN.
• Entrambi i giocatori combattono poiché il giocatore avversario ottiene il vantaggio minimo mentre ottiene il massimo beneficio.
• Entrambi i giocatori del gioco sono avversari l'uno dell'altro, dove MAX selezionerà il valore massimizzato e MIN selezionerà il valore minimizzato.
• L'algoritmo minimax esegue un algoritmo di ricerca approfondita per l'esplorazione dell'albero di gioco completo.
• L'algoritmo minimax procede fino al nodo terminale dell'albero, quindi torna indietro lungo l'albero come ricorsione.

Pseudo-codice per l'algoritmo MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Chiamata iniziale:

Minimax(nodo, 3, vero)

Funzionamento dell'algoritmo Min-Max:

• Il funzionamento dell'algoritmo minimax può essere facilmente descritto utilizzando un esempio. Di seguito abbiamo preso un esempio di albero di gioco che rappresenta il gioco a due giocatori.
• In questo esempio, ci sono due giocatori, uno si chiama Maximizer e l'altro si chiama Minimizer.
• Maximizer proverà a ottenere il punteggio massimo possibile, mentre Minimizer proverà a ottenere il punteggio minimo possibile.
• Questo algoritmo applica DFS, quindi in questo albero di gioco dobbiamo percorrere tutto il percorso attraverso le foglie per raggiungere i nodi terminali.
• Nel nodo terminale vengono forniti i valori terminali, quindi confronteremo tali valori e torneremo indietro sull'albero finché non si verifica lo stato iniziale. Di seguito sono riportati i passaggi principali necessari per risolvere l'albero di gioco a due giocatori:

Passo 1: Nella prima fase, l'algoritmo genera l'intero albero del gioco e applica la funzione di utilità per ottenere i valori di utilità per gli stati terminali. Nel diagramma ad albero sottostante, prendiamo A come lo stato iniziale dell'albero. Supponiamo che il massimizzatore effettui il primo turno che ha valore iniziale nel caso peggiore = - infinito, e il minimizzatore esegua il turno successivo che ha valore iniziale nel caso peggiore = +infinito.

Passo 2: Ora, per prima cosa troviamo il valore delle utilità per Maximizer, il suo valore iniziale è -∞, quindi confronteremo ciascun valore nello stato terminale con il valore iniziale di Maximizer e determineremo i valori dei nodi più alti. Troverà il massimo tra tutti.

• Per il nodo D max(-1,- -∞) => max(-1,4)= 4
• Per il nodo E max(2, -∞) => max(2, 6)= 6
• Per il Nodo F max(-3, -∞) => max(-3,-5) = -3
• Per il nodo G max(0, -∞) = max(0, 7) = 7

Passaggio 3: Nel passaggio successivo, tocca al minimizzatore, quindi confronterà il valore di tutti i nodi con +∞ e troverà i 3^rdvalori dei nodi di livello.

• Per il nodo B= min(4,6) = 4
• Per il nodo C= min (-3, 7) = -3

Passaggio 4: Ora è il turno di Maximizer, che sceglierà nuovamente il valore massimo di tutti i nodi e troverà il valore massimo per il nodo radice. In questo albero del gioco ci sono solo 4 livelli, quindi raggiungiamo immediatamente il nodo radice, ma nei giochi reali ci saranno più di 4 livelli.

• Per il nodo A max(4, -3)= 4

Questo era il flusso di lavoro completo del gioco minimax a due giocatori.

Proprietà dell'algoritmo Mini-Max:

Completare-L'algoritmo Min-Max è completo. Troverà sicuramente una soluzione (se esiste), nell'albero di ricerca finito.Ottimale-L'algoritmo Min-Max è ottimale se entrambi gli avversari giocano in modo ottimale.Complessità temporale-Poiché esegue DFS per l'albero del gioco, lo è anche la complessità temporale dell'algoritmo Min-Max O(b^M) , dove b è il fattore di ramificazione dell'albero da gioco e m è la profondità massima dell'albero.Complessità spaziale-Anche la complessità spaziale dell'algoritmo Mini-max è simile a DFS che lo è Di .

Limitazione dell'algoritmo minimax:

Lo svantaggio principale dell'algoritmo minimax è che diventa molto lento per giochi complessi come gli scacchi, il go, ecc. Questo tipo di giochi ha un enorme fattore di ramificazione e il giocatore ha molte scelte tra cui decidere. Questa limitazione dell'algoritmo minimax può essere migliorata da potatura alfa-beta di cui abbiamo parlato nel prossimo argomento.