Ricerca con Avversari Flashcards
Giochi a Somma zero a due giocatori
Sono giochi deterministici, a due giocatori, a turni, con:
* Informazione perfetta: completamente osservabile
* Somma zero: ciò che va a vantaggio di un giocatore, danneggia l’altro
Stato Iniziale ci fornisce la configurazione del gioco
AZIONI: mosse legali nello stato s
RISULTATO: modello di transizione dopo un azione
Stato Terminale: se fa concludere la partita
Utilità: valore che determina l’utilità dello stato terminale
Come fare scelte ottimali in un gioco
Lo stato iniziale, la funzione AZIONI e la funzione RISULTATO definiscono il grafo dello spazio degli stati, un grafo in cui i vertici sono stati, gli archi sono mosse e uno stato può essere raggiunto da più cammini
Su parte di tale grafo possiamo sovrapporre un albero di ricerca per determinare quale mossa effettuare.
(albero di gioco)
Algoritmo di ricerca minmax
Algoritmo di ricerca che trova la mossa migliore per MAX provando tutte le azioni e scegliendo quella per cui lo stato di arrivo ha il valore MINIMAX più alto
Caratteristiche:
*Completo, se lo spazio degli stati è finito
*Ottimo
*Per la complessità, si nota che è un algoritmo di ricerca in profondità
Potatura alpha-beta
Con l’algoritmo minimax, il numero di stati del gioco cresce esponenzialmente!
Il processo di potatura alpha-beta ci permette di ridurre il numero di stati da esplorare.
Ricerca alpha-beta euristica
Per sfruttare al meglio il nostro tempo di calcolo, che è limitato, possiamo interrompere la ricerca in anticipo e applicare una funzione di valutazione euristica agli stati, considerando i nodi non terminali come se lo fossero (sostituiamo la funzione UTILITA’ con EVAL).
Inoltre sostituiamo il test di terminazione con un test di taglio (cutoff test) che deve restituire vero per gli stati terminali, ma per il resto è libero di decidere quando interrompere la ricerca in base alla profondità della stessa e a qualsiasi proprietà dello stato che sceglie di considerare.
Potatura in avanti
La potatura in avanti taglia quelle che appaiono cattive mosse, ma potrebbero invece essere buone. La strategia, quindi, fa risparmiare tempo di calcolo ma introduce il rischio di commettere un errore.
Giochi stocastici
I giochi stocastici ci portano un po’ più vicino all’imprevedibilità della vita reale includendo un elemento casuale, come il lancio di un dado.
