Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algoritmi giochi con avversario (Algoritmo minimax ricorsivo (Complessità…
Algoritmi giochi con avversario
Valore minimax
2 tipi di scelte
MAX scelta
interna
MIN scelta
esterna
Minimizzando il guadagno massimo dell'altro minimizza la propria perdita
Algoritmo minimax ricorsivo
Complessità temporale esponenziale
Complessità spaziale lineare
Completo in grafi finiti
Ottimale se MAX e MIN giocano in modo ottimale
Minimax con potatura Alfa-Beta
sopperisce al costo temporale di minimax
#
Pota i rami meno promettenti
senza seguirli
Beta-Prnuning
Funzionamento
Ogni nodo ha un valore N che cambia durante esploraz. sottoalberi
Esplorazione aggiorna estremi intervallo alpha e beta
alpha =
max lower bound
beta =
min upper bound
Aggiornati man mano che la ricerca procede
Si esplora nodo solo se il suo valore N è compreso tra alpha e beta
Confronto algoritmi
#
#
Sono equivalenti
Trovano la stessa
mossa ottima
per nodo radice
Attribuiscono al nodo radice
stessa valutaz.
Alfa beta dimezza esponenziale
Efficace a seconda
dell'ordine
di considerazione successori
Killer move
si trovano tramite
Apprendimento
Combinazione potatura alpha beta con iterative deepening
Uso di
tabelle di trasposizione
Conservate in
hash table
Se nuovo stato corrisponde a quello di una trasposizione non viene esplorato