Algoritmo dei tagli alfa-beta
Durante il corso di Intelligenza Artificiale abbiamo studiato, fra l’altro, una particolare categoria di giochi aventi le seguenti caratteristiche:
- sono presenti solo due giocatori che eseguono alternativamente una mossa alla volta.
- sono giochi a conoscenza perfetta: entrambi i giocatori hanno le stesse informazioni.
Tipici giochi a conoscenza perfetta sono la dama, gli scacchi, ecc… mentre tipici giochi a conoscenza imperfetta sono quelli di carte come poker, bridge, ecc… Lo svolgersi del gioco si può interpretare attraverso un albero, detto spazio degli stati, in cui ogni nodo rappresenta uno stato di gioco. Si comincia da uno stato iniziale in cui si è stabilito il giocatore che ha il diritto di compiere una mossa (tale diritto di mossa è detto in gergo avere il gioco in mano o più brevemente avere la mano o essere di mano). Il giocatore che è di mano attraverso una mossa raggiunge uno stato successivo in cui la mano passa all’altro giocatore. Così via fino al raggiungimento di uno stato finale: una foglia dell’albero nello spazio degli stati in cui non sia possibile alcuna altra mossa.
Un tipico approccio per risolvere un gioco consiste in una ricerca nello spazio degli stati condotta da algoritmi. Durante il corso abbiamo studiato gli algoritmi del MIN-MAX e quello dei Tagli Alfa-Beta.
In questa relazione abbiamo implementato l’algoritmo dei Tagli Alfa-Beta in linguaggio Java.
La verifica della correttezza dell’implementazione è stata condotta su alcuni esercizi proposti in alcune sessioni d’esame e corredati di soluzione.
Download
Scarica la relazione relativa all’algoritmo dei Tagli Alfa-Beta:
Verifica la firma GPG con la mia vecchia chiave pubblica.