Algoritmi su grafi per la scelta dinamica del percorso migliore

Abstract

Questa tesi presenta lo sviluppo e l'analisi di tre algoritmi per l'automazione del movimento di PacMan: l'algoritmo Random, che determina le mosse in maniera casuale, gli algoritmi Conservative e Balanced, che utilizzano una rappresentazione della mappa come grafo orientato e pesato per calcolare il percorso migliore. L'obiettivo della tesi è valutare l'efficacia, misurata in termini di tempo di sopravvivenza e punteggio ottenuto, degli algoritmi basati sulla logica dei grafi rispetto all'algoritmo casuale.

Per valutare l'efficacia degli algoritmi sviluppati, sono state effettuate 50 simulazioni per ciascun algoritmo, ogni simulazione con un'inizializzazione randomica delle variabili iniziali, così da garantire una robusta analisi statistica. I risultati raccolti sono stati analizzati utilizzando Matlab, grazie al quale è stato possibile rappresentare graficamente l'andamento delle medie all'aumentare delle simulazioni, le distribuzioni dei tempi di sopravvivenza e punteggi ottenuti, i corrispondenti box plot e di effettuare il t-test di Student per valutare la significatività statistica dei diversi risultati ottenuti.

L'analisi dei risultati ha mostrato come gli algoritmi basati sulla logica dei grafi hanno una performance visibilmente migliore rispetto all'algoritmo casuale. Il t-test ha confermato la significatività statistica delle differenze, confermando così che gli algoritmi Conservative e Balanced sono in grado di utilizzare la rappresentazione in grafi della mappa di gioco per ottimizzare il movimento di Pac-Man.

In conclusione, questa tesi suggerisce che è possibile trasformare una mappa discreta in un grafo e sviluppare su di esso algoritmi efficaci per il calcolo del percorso migliore.

This thesis presents the development and analysis of three algorithms for the automation of PacMan movement: the Random algorithm, which determines the moves randomly, the Conservative and Balanced algorithms, which use a representation of the map as a directed graph and weighted to calculate the best path. The objective of the thesis is to evaluate the effectiveness, measured in terms of survival time and score obtained, of algorithms based on graph logic compared to the random algorithm.

To evaluate the effectiveness of the developed algorithms, 50 simulations were run for each algorithm, each simulation with a random initialization of the initial variables, so as to ensure a robust statistical analysis. The collected results were analyzed using Matlab, thanks to which it was possible to graphically represent the trend of the averages as the simulations increased, the distributions of survival times and scores obtained, the corresponding box plots, and to perform Student's t-test to assess the statistical significance of the different results obtained.

The analysis of the results showed that algorithms based on graph logic have a better performance than the random algorithm. The t-test confirmed the statistical significance of the differences, thus confirming that the Conservative and Balanced algorithms are able to use the graph representation of the game map to optimize Pac-Man's movement.

In conclusion, this thesis suggests that it is possible to transform a discrete map into a graph and develop on it effective algorithms for calculating the best path.