Ing. Tarin Gamberini

Menu

• Home
• Curriculum Vitae
• Esame di Stato
• Studi Universitari
• Java
• Diceware in Italiano
• Chiave pubblica GPG
• Mappa del Sito
• Contatti

Citazione

Standard

Campagne

Barra di navigazione

Home > Studi Universitari > Progetti Universitari

Intelligenza Artificiale

Algoritmo dei Tagli Alfa-Beta

Durante il corso di Intelligenza Artificiale abbiamo studiato 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 dello 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.

• Introduzione
• 1 Principio di funzionamento
• 2 Diagramma di flusso dell'algoritmo
• 3 Analisi delle classi
  • 3.1 Descrittore dello stato di gioco
    • 3.1.1 Attributi
    • 3.1.2 Metodi
  • 3.2 Tagli Alfa-Beta
    • 3.2.1 Attributi
    • 3.2.2 Metodi
  • 3.3 Gioco generico
    • 3.3.1 Attributi
    • 3.3.2 Metodi
• 4 Verifica dell'implementazione in Java
• Conclusioni
• A Codice sorgente in linguaggio Java