Simone Cacace @ 2021
|
Il leggendario videogioco Pacman, inizialmente Pakku-Man (Uomo-Disco), fu concepito da Tohru Iwatani negli anni 80, osservando attentamente una pizza a cui mancava una fetta. Il resto è storia! Lo scopo del gioco è condurre una creatura gialla (Pacman) all’interno di un labirinto e mangiare tutte le pillole presenti. Il giocatore può interagire con Pacman modificando la sua direzione di marcia, fuggendo da quattro fantasmini colorati che, a loro volta, tentano di mangiarlo. Un grande aiuto per vincere è il fatto che i fantasmini hanno un comportamento prestabilito e non cooperativo. Inoltre Pacman può mangiare alcune pillole speciali, che rendono i fantasmini temporaneamente vulnerabili, e anche sfruttare due tunnel orizzontali per spostarsi istantaneamente da un estremo all'altro del labirinto. PacmanHJ è una rivisitazione del classico Pacman in chiave matematica! Pur mantendendo la struttura, la grafica e i suoni del gioco originale, PacmanHJ è realizzato in 3D e contiene un motore matematico, che si basa sulla risoluzione numerica di alcune equazioni alle derivate parziali di tipo Hamilton-Jacobi, legate a particolari problemi di controllo ottimo e giochi differenziali. Questo si traduce nel fatto che i fantasmini sono ora in grado di cooperare e di attuare strategie di gioco ottimali, al fine di catturare Pacman nel minor numero di mosse possibile. Di conseguenza, anche Pacman deve muoversi nel migliore dei modi per poter vincere. Ogni singola mossa diventa preziosa e può cambiare l'esito della partita, il che rende PacmanHJ un vero e proprio puzzle-game! Per illustrare qualitativamente gli aspetti più matematici dei problemi affrontati durante la sua realizzazione, PacmanHJ consiste nei tre seguenti mini-giochi di complessità crescente. Play for your pill. Lo scopo di questo mini-gioco è far mangiare a Pacman un'unica pillola presente nel labirinto, in assenza di fantasmini e nel numero di mosse assegnato. All'inizio di ogni partita, la posizione della pillola viene estratta casualmente, mentre Pacman viene posto alla massima distanza da essa. Si tratta di un classico problema nella Teoria del Controllo Ottimo, ovvero trovare il cammino di lunghezza minima che collega Pacman alla pillola, dove per controllo si intende proprio l'insieme delle mosse da attuare per raggiungere l'obbiettivo. La difficoltà del gioco dipende dalla posizione della pillola, che a sua volta determina il numero esatto di mosse per vincere la partita. Inoltre la struttura complessa del labirinto fa sì che la soluzione al problema spesso non sia unica! Il motore matematico di PacmanHJ contiene al suo interno il risultato del calcolo della distanza minima dalla pillola, per tutte le 224 caselle del labirinto e per tutte le 224 posizioni della pillola stessa. In altri termini, per ogni coppia di caselle del labirinto, è stato calcolato e memorizzato un singolo "valore", che rappresenta esattamente la minima distanza tra le due caselle, misurata come il minimo numero di caselle che le separa. A partire da questa singola informazione è possibile calcolare in tempo reale la strategia ottimale: fissata la posizione della pillola, Pacman dovrà semplicemente leggere i "valori" delle caselle a lui vicine, e spostarsi in una casella che ha un valore inferiore a quello della propria casella. Reiterando questo procedimento, Pacman si ritroverà nell'unica casella che ha il valore (zero) più basso di tutte le altre, ovvero la casella che contiene la pillola da mangiare! Il problema "globale" e complicato del cammino minimo è stato dunque ridotto ad una sequenza di problemi "locali" più facili da risolvere. Questa idea tanto semplice (almeno apparentemente) quanto potente, dovuta a Richard Bellman negli anni 50, è alla base della Teoria del Controllo Ottimo ed è nota come Principio di Programmazione Dinamica. Ma come si calcolano praticamente questi valori? Il principio viene applicato a ritroso, partendo dall'unico dato del problema, ovvero dal fatto che la distanza minima dalla pillola è pari a zero nella casella della pillola stessa. Si passa dunque alle prime caselle vicine, per le quali la distanza minima dalla pillola corrisponde chiaramente ad una casella. Reiterando il procedimento, ogni casella avrà un valore pari a una casella, necessaria a raggiungere una casella vicina, sommata al migliore (il più piccolo) tra i valori delle caselle vicine già calcolate, e così via fino a determinare i valori in tutte le caselle del labirinto. Questo modo di procedere "all'indietro" rende la risoluzione del gioco non banale per un giocatore umano, che istintivamente tende a immedesimarsi in Pacman e a moversi "in avanti" verso il traguardo, il che produce spesso solo strategie sub-ottime! Play for your life. Lo scopo di questo mini-gioco è far sfuggire Pacman alla cattura da parte di due fantasmini che lo inseguono, in assenza di pillole e per un numero di mosse assegnato. All'inizio di ogni partita, le posizioni dei due fantasmini vengono estratte casualmente, mentre Pacman viene posto in una posizione tale da rendere massimo il numero di mosse che lo separano dalla cattura. Rispetto al mini-gioco precedente, qui si entra in un ambito matematico molto più complesso, quello della Teoria dei Giochi, in cui ogni giocatore tenta di attuare la migliore strategia possibile per realizzare un determinato obbiettivo. Nel caso specifico di Pacman contro i fantasmini, i giocatori hanno obbiettivi contrapposti, il vantaggio di Pacman corrisponde esattamente allo svantaggio dei fantasmini e viceversa, pertanto il gioco viene detto a somma zero. Più precisamente, Pacman tenta evitare la cattura, massimizzando il numero di mosse, laddove i fantasmini tentano la cattura minimizzando lo stesso numero di mosse. È importante notare che i fantasmini attuano le loro strategie in piena cooperazione, e pertanto possono essere considerati come un unico meta-giocatore che agisce tramite due corpi distinti. Il problema si traduce dunque nel calcolo del "tempo" di cattura, inteso come numero di mosse necessarie alla cattura, per ogni posizione di Pacman e per ogni posizione dei due fantasmini all'interno del labirinto. Poiché il labirinto è composto da 224 caselle, l'inisieme delle possibili configurazioni ammonta a 2243 elementi, per ognuno dei quali occorre calcolare e memorizzare il tempo di cattura corrispondente. La buona notizia è che, per questo specifico gioco, vale un Principio di Programmazione Dinamica analogo a quello descritto precedentemente. La soluzione può essere calcolata partendo dall'unico dato del problema, ovvero dal fatto che il tempo di cattura è pari a zero per tutte le configurazioni in cui Pacman occupa la stessa casella di almeno uno dei due fantasmini. Si procede poi a ritroso, questa volta "massiminimizzando", ovvero scegliendo i valori delle caselle vicine che da un lato fanno diminuire il tempo di cattura muovendo i fantasmini, dall'altro lo fanno aumentare muovendo Pacman. Questo calcolo risulta molto oneroso dal punto di vista computazionale e richiede una procedura iterativa che, per effetto della competizione tra massimizzazione e minimizzazione, ritorna più volte a modificare i valori associati alle singole configurazioni, fino al raggiungimento di un equilibrio che realizza il miglior risultato possibile per tutti i giocatori. Una volta ottenuta questa soluzione, le strategie ottimali possono essere calcolate in tempo reale in maniera analoga al mini-gioco precedente. Il risultato più importate per questo problema è che il tempo di cattura è sempre finito per ognuna delle 2243 configurazioni, vale a dire che la cattura è sempre garantita, indipendentemente dalla forma del labirinto e dalle posizioni iniziali dei giocatori! Se si considerasse lo stesso gioco, ma con un singolo fantasmino, è facile intuire che Pacman potrebbe muoversi ciclicamente creando un percorso chiuso all'interno del labirinto, rendendo così infinito il tempo di cattura. Invece, la presenza di due fantasmini impedisce questa strategia, perché uno dei due può sempre posizionarsi in modo da interrompere il cammino ciclico di Pacman. Per il labirinto di PacmanHJ il massimo tempo di cattura corrisponde a 50 mosse, e si ottiene in corrispondenza di alcune particolari configurazioni iniziali. Infine, rispetto al videogioco originale, in PacmanHJ non sono presenti i due tunnel di teletrasporto e il numero di fantasmini è ridotto da 4 a 2. Si è infatti notato che i fantasmini tendevano sempre a usare i tunnel anticipando notevolmente la cattura, laddove la presenza di 4 fantasmini riduceva il tempo massimo di cattura a meno di 10 mosse. Queste scelte rendono dunque PacmanHJ maggiormente giocabile per un giocatore umano, ma vincere è tutt'altro che banale! Play puzzle. Questo mini-gioco è il più simile al videogioco originale. Lo scopo è far raccogliere a Pacman tutte le pillole presenti nel labirinto, sfuggendo alla cattura da parte dei due fantasmini. All'inizio di ogni partita, Pacman e i fantasmini vengono posizionati al centro del labirinto, in corrispondenza di alcune caselle fisse. Pacman è da subito libero di muoversi, mentre i fantasmini gli concedono un vantaggio stazionando per 7 mosse. L'unico modo per vincere è sfruttare nel migliore dei modi le pillole speciali, ovvero non lanciandosi all'inseguimento dei fantasmini, temporaneamente vulnerabili, con l'intento di mangiarli, ma guadagnando mosse preziose per spostarsi in una zona non ancora battuta del labirinto. Infatti i fantasmini si muovono utilizzando lo stesso motore matematico del mini-gioco precedente, che garantisce la cattura in un numero finito di mosse, ma sono totalmente ignari della presenza delle pillole speciali, proprio perché non sono state inserite nel modello matematico del gioco. La raccolta di queste pillole determina un temporaneo abbandono della strategia di cattura ottimale da parte dei fantasmini, il cui obbiettivo è ora dirigersi verso la casella del labirinto alla massima distanza da Pacman, sfruttando le soluzioni di cammino minimo ottenute per il primo mini-gioco. Una volta raggiunto questo traguardo, la strategia di cattura cooperativa viene ripristinata, a meno che uno o entrambi i fantasmini non siano stati mangiati! In tal caso, sempre sfruttando le soluzioni di cammino minimo, ognuno dei fantasmini mangiati ritorna nella casella centrale del labirinto per rigenerarsi, stazionando nuovamente per 7 mosse, mentre l'eventuale fantasmino ancora vivo tenta da solo di raggiungere Pacman. Per questo mini-gioco, a differenza dei precedenti, non è attualmente disponibile una soluzione matematica esatta, che possa essere calcolata e con cui realizzare la migliore strategia vincente. Nonostante sia possibile formulare il problema in modo matematicamente corretto, includendo simultaneamente nel modello tutte le componenti descritte, il numero delle configurazioni possibili risulta talmente grande da rendere il calcolo e la memorizzazione della soluzione impraticabile. Questa soluzione sicuramente esiste, semplicemente perché, provando e riprovando, è possibile vincere! La migliore partita realizzata finora corrisponde a completare il gioco in 308 mosse. Questo risultato può essere quasi certamente migliorato, ma non è ancora possibile dire di quanto e, soprattutto, come. Non resta che... cominciare a giocare! Come giocare a PacmanHJ Menù Principale
Per ulteriori informazioni/commenti/suggerimenti, o anche solo per inviare uno screenshot che attesti un record nel terzo mini-gioco (in caso di vittoria viene visualizzato il numero di mosse effettuate), scrivere qui: cacace@mat.uniroma3.it |
per riavviare il mini-gioco corrente
per tornare al menù principale
per attivare/disattivare la visualizzazione dei controlli ottimi per la mossa corrente di Pacman
per attivare/disattivare la visualizzazione, tramite colori dal blu al rosso, dei valori associati alla distanza minima (primo mini-gioco) o al tempo di cattura (secondo mini-gioco) delle caselle del labirinto
per attivare/disattivare la modalità automatica di gioco ottimale per Pacman