Alpha Beta Potatura in AI

Alpha beta potatura è un’ottimizzazione tecnica per l’algoritmo di minimax. Attraverso il corso di questo blog, discuteremo cosa significa la potatura alfa beta, discuteremo l’algoritmo minimax, le regole per trovare un buon ordine e altro ancora.

1. Introduzione
2. algoritmo di Minimax
3. i punti Chiave di una Potatura Alfa-beta
4. Lavoro di Potatura Alfa-beta
5. Sposta Ordine di Potatura
6. Regole di trovare Buoni di ordinazione
7. Codici in Python

Introduzione

La parola ‘potatura’ significa taglio di rami e foglie. Nella scienza dei dati la potatura è un termine molto usato che si riferisce a post e pre-potatura negli alberi decisionali e nella foresta casuale. La potatura alfa-beta non è altro che la potatura di rami inutili negli alberi decisionali. Questo algoritmo di potatura alfa-beta è stato scoperto indipendentemente dai ricercatori nel 1900.

La potatura alfa-beta è una tecnica di ottimizzazione per l’algoritmo minimax che viene discussa nella prossima sezione. La necessità di potatura deriva dal fatto che in alcuni casi gli alberi decisionali diventano molto complessi. In quell’albero, alcuni rami inutili aumentano la complessità del modello. Quindi, per evitare questo, la potatura Alfa-beta viene a giocare in modo che il computer non debba guardare l’intero albero. Questi nodi insoliti rendono l’algoritmo lento. Quindi rimuovendo questi nodi l’algoritmo diventa veloce.

Scopri un algoritmo*.

Algoritmo Minimax

Minimax è una classica tecnica di ricerca di profondità per un gioco sequenziale a due giocatori. I due giocatori sono chiamati MAX e MIN. L’algoritmo minimax è progettato per trovare la mossa ottimale per MAX, il giocatore nel nodo principale. L’albero di ricerca viene creato espandendo ricorsivamente tutti i nodi dalla radice in modo approfondito fino a raggiungere la fine del gioco o la profondità massima di ricerca. Cerchiamo di esplorare questo algoritmo in dettaglio.

Come già accennato, ci sono due giocatori nel gioco, vale a dire – Max e Min. Max gioca il primo passo. Il compito di Max è quello di massimizzare la sua ricompensa, mentre il compito di Min è quello di ridurre al minimo la ricompensa di Max, aumentando la propria ricompensa allo stesso tempo. Diciamo che Max può intraprendere azioni a, b o c. Quale di esse darà a Max la migliore ricompensa quando il gioco finisce? Per rispondere a questa domanda, dobbiamo esplorare l’albero del gioco a una profondità sufficiente e supporre che Min giochi in modo ottimale per ridurre al minimo la ricompensa di Max.

Ecco un esempio. Quattro monete sono in fila e ogni giocatore può prendere una moneta o due monete sul suo turno. Il giocatore che raccoglie l’ultima moneta vince. Supponendo che Max giochi per primo, quale mossa dovrebbe fare Max per vincere?

Se Max sceglie due monete, rimangono solo due monete e Min può scegliere due monete e vincere. Quindi raccogliere 1 moneta massimizzerà la ricompensa di Max.

Come avrai notato, i nodi dell’albero nella figura sottostante hanno alcuni valori inscritti su di essi, questi sono chiamati valore minimax. Il valore minimax di un nodo è l’utilità del nodo se si tratta di un nodo terminale.

Se il nodo è un non-terminale Max nodo, il minimax valore del nodo è il massimo minimax valori di tutti i nodi successori. D’altra parte, se il nodo è un nodo Min non terminale, il valore minimax del nodo è il minimo dei valori minimax di tutti i successori del nodo.

Ora discuteremo l’idea alla base della potatura alfa beta. Se applichiamo la potatura alfa-beta all’algoritmo minimax standard, dà la stessa decisione di quella dell’algoritmo standard, ma pota o riduce i nodi che sono insoliti nell’albero decisionale, cioè che non influenzano la decisione finale presa dall’algoritmo. Ciò contribuirà ad evitare la complessità nell’interpretazione di alberi complessi.

Guarda come funziona l’algoritmo KNN.

Ora discutiamo l’intuizione dietro questa tecnica. Proviamo a trovare la decisione minimax nell’albero sottostante :

In questo caso,

Qui il risultato di cui sopra è necessario disporre di un dubbio nella vostra mente che come possiamo trovare il massimo da valore mancante. Quindi, ecco anche la soluzione del tuo dubbio:

Nel secondo nodo scegliamo il valore minimo come c che è minore o uguale a 2 cioè c < = 2. Ora se c <= 3 e dobbiamo scegliere il massimo di 3, c, 2 il valore massimo sarà 3.

Abbiamo raggiunto una decisione senza guardare quei nodi. Ed è qui che entra in gioco la potatura alfa-beta.

Punti chiave nella potatura alfa-beta

• Alpha: Alpha è la scelta migliore o il valore più alto che abbiamo trovato in qualsiasi istanza lungo il percorso di Maximizer. Il valore iniziale per alfa è -∞.

• Beta: Beta è la scelta migliore o il valore più basso che abbiamo trovato in qualsiasi istanza lungo il percorso di Minimizer. Il valore iniziale per alpha è+∞.

• La condizione per la potatura alfa-beta è che α > = β.

• Ogni nodo deve tenere traccia dei suoi valori alfa e beta. Alpha può essere aggiornato solo quando è il turno di MAX e, allo stesso modo, beta può essere aggiornato solo quando è la possibilità di MIN.

• MAX aggiornerà solo i valori alfa e MIN player aggiornerà solo i valori beta.

• I valori dei nodi verranno passati ai nodi superiori invece dei valori di alfa e beta durante il go in reverse of tree.

• I valori Alfa e beta possono essere passati solo ai nodi figlio.

Lavoro di potatura Alfa-beta

1. Inizieremo prima con la mossa iniziale. Inizialmente definiremo i valori alfa e beta come il caso peggiore cioè α = – ∞ e β=+∞. Poteremo il nodo solo quando alfa diventa maggiore o uguale a beta.

2. Poiché il valore iniziale di alfa è inferiore a beta, non l’abbiamo potato. Ora tocca a MAX. Quindi, al nodo D, verrà calcolato il valore di alpha. Il valore di alpha al nodo D sarà max (2, 3). Quindi, il valore di alpha al nodo D sarà 3.

3. Ora la prossima mossa sarà sul nodo B e il suo turno per MIN ora. Quindi, al nodo B, il valore di alfa beta sarà min (3,∞). Quindi, al nodo B i valori saranno alfa= – ∞ e beta sarà 3.

Nella fase successiva, gli algoritmi attraversano il successivo successore del nodo B che è il nodo E, e verranno passati anche i valori di α= – ∞ e β= 3.

4. Ora tocca a MAX. Quindi, al nodo E cercheremo MAX. Il valore corrente di alfa a E è – ∞ e verrà confrontato con 5. Quindi, MAX ( – ∞ , 5) sarà 5. Quindi, al nodo E, alfa = 5, Beta = 5. Ora come possiamo vedere che alpha è maggiore di beta che soddisfa la condizione di potatura, quindi possiamo potare il successore giusto del nodo E e l’algoritmo non verrà attraversato e il valore al nodo E sarà 5.

6. Nel passaggio successivo l’algoritmo arriva nuovamente al nodo A dal nodo B. Al nodo A alfa verrà modificato il valore massimo come MAX ( – ∞ , 3). Quindi ora il valore di alfa e beta al nodo A sarà (3,+∞) rispettivamente e sarà trasferito al nodo C. Questi stessi valori saranno trasferiti al nodo F.

7. Al nodo F il valore di alpha verrà confrontato con il ramo sinistro che è 0. Quindi, MAX (0, 3) sarà 3 e quindi confrontato con il figlio giusto che è 1, e MAX (3,1) = 3 ancora α rimane 3, ma il valore del nodo di F diventerà 1.

8. Ora il nodo F restituirà il valore del nodo 1 a C e si confronterà con il valore beta a C. Ora tocca a MIN. Quindi, MIN ( + ∞ , 1) sarà 1. Ora al nodo C, α = 3 e β= 1 e alfa è maggiore di beta che soddisfa nuovamente la condizione di potatura. Quindi, il prossimo successore del nodo C cioè G sarà potato e l’algoritmo non ha calcolato l’intero sottoalbero G.

Ora, C restituirà il valore del nodo ad A e il valore migliore di A sarà MAX (1, 3) sarà 3.

L’albero sopra rappresentato è l’albero finale che mostra i nodi che sono calcolati e i nodi che non sono calcolati. Quindi, per questo esempio il valore ottimale del massimizzatore sarà 3.

Guarda le librerie Python open source.

Ordine di spostamento nella potatura

L’efficacia della potatura alfa – beta si basa sull’ordine in cui viene esaminato il nodo. Spostare ordinamento svolge un ruolo importante nella potatura alfa beta.

Ci sono due tipi di ordine di movimento in Alpha beta potatura:

1. Peggiore ordinamento: in alcuni casi di potatura alfa beta nessuno dei nodi potati dall’algoritmo e funziona come l’algoritmo minimax standard. Questo consuma un sacco di tempo a causa di fattori alfa e beta e inoltre non dà alcun risultato efficace. Questo è chiamato Peggiore ordinamento nella potatura. In questo caso, la mossa migliore si verifica sul lato destro dell’albero.
2. Ordinamento ideale: In alcuni casi di potatura alfa beta lotto dei nodi potati dall’algoritmo. Questo è chiamato ordinamento ideale nella potatura. In questo caso, la mossa migliore si verifica sul lato sinistro dell’albero. Applichiamo DFS quindi prima ricerca a sinistra dell’albero e andiamo in profondità due volte come algoritmo minimax nella stessa quantità di tempo.

Regole di trovare Buoni di ordinazione

• La mossa migliore che succede da un nodo più basso
• Utilizzare la conoscenza di dominio, mentre trovare la mossa migliore
• Ordine dei nodi devono essere in modo che il miglior nodi verranno calcolate prima

Check out questo Python Tutorial per Principianti

Codici in Python

class MinimaxABAgent: """ Minimax agent """ def __init__(self, max_depth, player_color): """ Initiation Parameters ---------- max_depth : int The max depth of the tree player_color : int The player's index as MAX in minimax algorithm """ self.max_depth = max_depth self.player_color = player_color self.node_expanded = 0 def choose_action(self, state): """ Predict the move using minimax algorithm Parameters ---------- state : State Returns ------- float, str: The evaluation or utility and the action key name """ self.node_expanded = 0 start_time = time.time() print("MINIMAX AB : Wait AI is choosing") list_action = AIElements.get_possible_action(state) eval_score, selected_key_action = self._minimax(0,state,True,float('-inf'),float('inf')) print("MINIMAX : Done, eval = %d, expanded %d" % (eval_score, self.node_expanded)) print("--- %s seconds ---" % (time.time() - start_time)) return (selected_key_action,list_action) def _minimax(self, current_depth, state, is_max_turn, alpha, beta): if current_depth == self.max_depth or state.is_terminal(): return AIElements.evaluation_function(state, self.player_color), "" self.node_expanded += 1 possible_action = AIElements.get_possible_action(state) key_of_actions = list(possible_action.keys()) shuffle(key_of_actions) #randomness best_value = float('-inf') if is_max_turn else float('inf') action_target = "" for action_key in key_of_actions: new_state = AIElements.result_function(state,possible_action) eval_child, action_child = self._minimax(current_depth+1,new_state,not is_max_turn, alpha, beta) if is_max_turn and best_value < eval_child: best_value = eval_child action_target = action_key alpha = max(alpha, best_value) if beta <= alpha: break elif (not is_max_turn) and best_value > eval_child: best_value = eval_child action_target = action_key beta = min(beta, best_value) if beta <= alpha: break return best_value, action_target

In questo documento abbiamo visto una componente importante della teoria dei giochi. Sebbene le prestazioni dell’algoritmo minimax siano buone, l’algoritmo è lento. Quindi, per renderlo veloce, usiamo l’algoritmo di potatura alfa-beta che ridurrà i nodi insoliti dall’albero decisionale per migliorare le prestazioni. Al giorno d’oggi l’algoritmo veloce e ben eseguito è ampiamente utilizzato.

Dai un’occhiata a questi corsi di intelligenza artificiale e apprendimento automatico da Grande apprendimento a upskill nel dominio e master Alpha Beta potatura e altri algoritmi di questo tipo.

Ulteriori letture

1. A* Algoritmo di ricerca in intelligenza artificiale (AI)
2. Algoritmo ad albero decisionale spiegato con esempi
3. Miglior primo algoritmo di ricerca in AI / Concetto | implementazione, vantaggi, svantaggi
4. Cos’è l’intelligenza artificiale? Come funziona l’IA, i tipi e il futuro dell’it?