Analisi di strategie computazionali per il gioco Forza4 generalizzato

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.