Università degli studi di SalernoCorso di Laurea Magistrale in Ingegneria InformaticaAnno 2015/2016

Corso di Intelligenza ArtificialePresentazione progetto Mrs. PacMan vs Ghosts Team

Gruppo: Capozzoli Settimio – Di Gruttola Carmine – Esposito Emiddio

2

Outline

• Introduzione• Agente basato su utilità• Agente basato su obiettivo• Ottimizzazione• Conclusione

3

Introduzione (1/2)

• Obiettivo: Sviluppare un controllore per Mrs. PacMan.• Gioco a livelli, con quattro ambienti ciclici, dove

attraverso pillole si accumulano punti.• Nell’ambiente un gruppo di fantasmi attacca Mrs.

PacMan, se viene toccato per tre volte il gioco finisce.• Ogni livello finisce quando finiscono le pillole.

4

Introduzione (2/2)

• Si accumulano punti anche mangiando i fantasmi, dopo aver mangiato apposite power pill.

• Il controllore dovrà decidere le mosse al fine di massimizzare il punteggio.

• Vincolo: la decisione dovrà essere presa in 40ms.• I fantasmi possono essere controllati con quattro strategie

diverse: Legacy, Starter, Random, Aggressive. • Si è presa in considerazione la strategia Starter.

5

Agente basato su utilità (1/4)

• Massimizza una funzione di utilità nello spazio degli stati.

• Strategia di ricerca: branching factor, profondità, vincoli temporali.

• Si è scelta la strategia Breadth First per esplorare tutte le possibili mosse iniziali.

• Si termina la ricerca solo allo scadere dei 40ms.• Si seleziona la mossa che porta allo stato trovato con la

massima utilità.

6

Agente basato su utilità (2/4)

• Funzione di utilità: =

7

Agente basato su utilità (3/4)

• I contributi positivi sono i contributi che l’agente deve aumentare, ad esempio il punteggio

• I contributi negativi sono i contributi da annullare, ad esempio numero di pillole o distanza di fantasmi mangiabili.

• Sono stati aggiunte penalizzazioni o premi costanti per alcuni eventi, quali perdita di vite o mosse opposte.

• I pesi di ogni contributo sono stati identificati in maniera empirica.

8

Agente basato su utilità (4/4)

• L’agente, pur avendo un comportamento medio accettabile, presenta comportamenti problematici che ne limitano le prestazioni.

• La struttura ha limitato la possibilità di intervenire per eliminare questi comportamenti.

• Si è quindi valutato un secondo approccio: un agente basato su obiettivo.

9

Agente basato su obiettivo (1/4)

• Diviso in due livelli: scelta dell’obiettivo e scelta del percorso per raggiungerlo.

• Primo livello: si seleziona l’obiettivo attraverso un albero decisionale.

• Secondo livello: si sceglie il percorso attraverso un A* sul grafo dell’ambiente.

• Si seleziona la prima mossa da effettuare per seguire il percorso trovato.

10

Agente basato su obiettivo (2/4)• Il primo livello decide

sulla base di distanze da alcuni elementi quali distanze dalla pillola più «vicina», dal fantasma più vicino, dal fantasma mangiabile più «vicino» e dalla power pill più vicina.

11

Agente basato su obiettivo (3/4)

• Il secondo livello assegna ad ogni nodo un peso sulla base della posizione e del contenuto e calcola il percorso a peso minimo attraverso un A*.

12

Agente basato su obiettivo (4/4)

• Attraverso diverse prove empiriche sono state fissati dei valori per i parametri sia del primo che del secondo livello.

• Sono state effettuate 1000 prove e sono stati calcolati i punteggi minimo, massimo e medio.Risultati

Minimo 1.120Media 6.295

Massimo 23.640

13

Ottimizzazione (1/3)

• Nel corso delle prove empiriche si è notato un comportamento sensibile ai parametri dell’algoritmo.

• Si è quindi pensato di ottimizzare le prestazioni in maniera automatica.

• Si è deciso di utilizzare un Random Mutation Hill Climbing per identificare i parametri ottimali.

14

Ottimizzazione (2/3)

• Il valore di ogni soluzione (combinazione di parametri) è stato valutato utilizzando la media del punteggio su 100 partite.

• La soluzione di partenza è stata generata in due modi distinti: in maniera casuale e a partire dai valori trovati empiricamente.

• Il vicino è stato generato a caso tra tutti i possibili spostamenti di passo fissato, e selezionato il primo con valore maggiore.

• Si è imposto il limite a 20 spostamenti non migliorativi per risolvere il problema delle spalle.

15

Ottimizzazione (3/3)

• Il miglior risultato è stato ottenuto partendo dalla soluzione generata in modo casuale.

• In seguito ne sono state valutate le prestazioni effettuando una ulteriore prova di 1000 partite e selezionando punteggio minimo, massimo e medio.Risultati

Minimo 1.100Media 6.525

Massimo 23.750

16

Conclusioni

• Sono stati valutati diversi approcci per sviluppare un agente intelligente in un ambiente competitivo.

• Sono state valutate le caratteristiche dell’approccio selezionato ed è stato utilizzato un ulteriore livello di intelligenza per ottimizzarne le prestazioni.

17

Grazie per l’attenzione