Analisi di strategie computazionali per il gioco Forza4 generalizzato

Colazzo, Lamberto (2022) Analisi di strategie computazionali per il gioco Forza4 generalizzato. [Laurea], Università di Bologna, Corso di Studio in Informatica [L-DM509], Documento full-text non disponibile
Il full-text non è disponibile per scelta dell'autore. (Contatta l'autore)

Abstract

L’Intelligenza Artificiale (IA), sin dalla sua introduzione, si è occupata dei giochi, ponendo l’attenzione a quelli detti a informazione perfetta e a somma zero e sequenziali (Tris, Scacchi e Forza4). Dalla Teoria dei Giochi è derivato il modello Minimax, che sfrutta l'albero di gioco per effettuare una ricerca in profondità allo scopo di minimizzare la massima perdita possibile per individuare la mossa migliore da giocare. Tuttavia, il limite di tale algoritmo risiede nel tempo necessario al calcolo (per alberi profondi e di grandi dimensioni) che, in alcuni casi, può essere considerevole. Per mitigare tale problema, è stato introdotta la proposta Alpha-Beta, che attua delle potature sull’albero di gioco grazie l’introduzione di due nuove variabili dette, appunto, alpha e beta. Tale approccio è stato ulteriormente migliorato ricorrendo all’utilizzo del concetto di funzione euristica e introducendo un limite di profondità al quale fermare la ricorsione del modello Alpha-Beta. Tale limite, tuttavia, determina il problema dell’effetto orizzonte, legato al fatto che fermarsi a una profondità intermedia dell’albero può portare l’algoritmo a non vedere delle alcune mosse migliori che possono situarsi nel sotto albero del nodo a cui si ferma la ricerca, appunto l’orizzonte. Ulteriori accorgimenti, come l'algoritmo ad approfondimento iterativo (Iterative Deepening) e il salvataggio degli stati di gioco in una tabella hash, possono ridurre in modo significativo il tempo di calcolo. Partendo da questi studi, sono stati sviluppati degli agenti software per ConnectX, un gioco sviluppato in Java a somma zero e a informazione perfetta come Forza4. Le implementazioni sono state testate su 39 diverse configurazioni di gioco, dimostrando che l'agente PlayerSoft risulta il più ottimale e che l'implementazione della funzione euristica rappresenta un buon compromesso tra complessità di calcolo e risultato atteso.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Colazzo, Lamberto
Relatore della tesi
Scuola
Corso di studio
Ordinamento Cds
DM509
Parole chiave
Teoria dei giochi,Modello Minimax,Algoritmi decisionali,Albero di gioco,Intelligenza artificiale
Data di discussione della Tesi
12 Ottobre 2022
URI

Altri metadati

Gestione del documento: Visualizza il documento

^