APICe » Courses » Autonomous Systems » 2014/2015 » Projects » Il tesoro dei pirati

Il tesoro dei pirati

Team

  • Alessia Papini

Introduzione

In questo elaborato si vuole descrivere lo sviluppo di un progetto nell’ambito del corso di Sistemi Autonomi. In particolare si vuole sviluppare un sistema basato su agenti autonomi in grado di giocare una partita a “Il tesoro dei pirati”.

Questo progetto ha rilevanza nel contesto dei sistemi autonomi in quanto permetterà di definire il processo deliberativo degli agenti ed esplorare il concetto di "trust" tra gli agenti stessi. Ogni agente, infatti, potrà scegliere dove posizionare le proprie pedine all’interno della griglia di gioco e l'avversario potrà decidere se credere o meno alle informazioni fornite dal contesto.

Vision

Si vogliono modellare i 2 giocatori come agenti autonomi in grado di ragionare, interagire con l’ambiente ed inoltre con la capacità di mentire posizionando le proprie pedine e credere o meno alle mosse effettuate dall'avversario. Si vuole mostrare il processo deliberativo dei due agenti in gioco e come essi siano in grado di organizzarsi sfruttando la propria conoscenza e quella acquisita dall’ambiente in modo da poter vincere la partita.

Goals

Realizzare un prototipo del sistema descritto e definire i particolari profili di gioco degli agenti in base a livelli di "trust" nei confronti dell'avversario.

Requisiti

I requisiti del sistema sono dati dalle regole di gioco:

Sono presenti 2 giocatori, 8 pirati, una griglia di gioco condivisa da entrambi i giocatori e 16 tasselli che identificano lettere e numeri (es. “A”, “B”, “1”, “2”, etc.).

Lo scopo del gioco è trovare il tesoro nascosto.

Inizialmente vengono estratti due tasselli, una lettera e un numero: queste coordinate identificheranno la posizione del tesoro e rimarranno coperte per l’intero svolgimento della partita. Si distribuiscono, in egual modo, i restanti tasselli tra i due giocatori. Ogni giocatore possiede 4 pedine (pirati) che possono essere posizionate sulla griglia di gioco, per “scommettere” su quale casella sarà stato nascosto il tesoro. Vengono estratti i turni con cui i due giocatori potranno piazzare i propri pirati.

Alla fine del posizionamento di tutti i pirati, il gioco termina rivelando i tasselli che identificano la posizione del tesoro e svelando il giocatore che è riuscito ad indovinarla.

Aspetti di interesse nei Sistemi Autonomi

Il sistema che si vuole realizzare deve sicuramente prevedere l'utilizzo di entità autonome ed intelligenti in grado di prendere decisioni e compiere azioni in base alla percezione che hanno dell'ambiente. Se così non fosse i pirati potrebbero essere posizionati in caselle casuali della griglia, senza che si riesca, salvo fortuiti casi, a trovare il tesoro. In una partita reale, invece, ogni giocatore ragionerebbe sulla mossa da eseguire ed utilizzerebbe gli indizi dell'avversario per poter vincere la partita, rivelando un certo livello di intelligenza. Inoltre, la rappresentazione e percezione dell'ambiente è fondamentale, in quanto permette al giocatore di considerare le mosse da lui effettuate e quelle avversarie, in modo da riconoscere quali informazioni possono essergli utili per poter trovare il tesoro e quali invece possono essere ignorate. Inoltre i giocatori non devono essere entità statiche, al contrario, devono essere dinamiche ed in grado di "cambiare" sia per quanto riguarda la strategia di gioco, sia nell'acquisizione di molteplici informazioni che possono modificare la conoscenza fin'ora assimilata. I giocatori hanno la caratteristica di essere "entità sociali", in modo da poter interagire con l'avversario ed il processo deliberativo che porta un giocatore a posizionare un pirata in una particolare casella, dev'essere frutto di un ragionamento che considera la conoscenza acquisita, utilizzandola per fare scelte non deterministiche, in quanto l'avversario non dovrà essere in grado di prevedere le mosse che saranno effettuate.

Analisi dei requisiti

La griglia rappresenta l’ambiente che permette lo scambio di conoscenza tra i due agenti in gioco, infatti ogni agente dovrà basare il proprio ragionamento sulla conoscenza acquisita dai tasselli posseduti e dai pirati posizionati sulla griglia di gioco grazie alle azioni dell’avversario. Ogni agente ha la percezione di ciò che accade nell’ambiente ed è a conoscenza delle caselle libere, di quelle occupate dai propri pirati e di quelle occupate dai pirati dell’avversario. Quando un giocatore posiziona il proprio pirata in una casella appartenente alla griglia, il ragionamento del suo avversario deve prevedere due scelte:

  • Credere al giocatore che ha effettuato la mossa e includere l’indizio nella propria conoscenza;
  • Non credere all’informazione data dal giocatore che ha effettuato la mossa e non prendere in considerazione l’indizio.

Glossario dei termini

TermineDescrizione
PartitaSerie di azioni volte alla simulazione di una partita reale a "Il tesoro dei pirati"
GiocatoreEntità autonoma in grado di effettuare scelte e perseguire l'obiettivo di gioco
TurnoSituazione in cui un giocatore può effettuare la propria azione per vincere la partita
GrigliaAmbiente di gioco condiviso tra i giocatori, formato da 8 righe e 8 colonne identificate rispettivamente da lettere e numeri
CasellaPosizione identificata da una lettera e da un numero (“A2”, etc.)
TasselloIdentifica una lettera o un numero ("A", "1", etc.)
PirataPedina posizionata da un giocatore in una casella
TesoroObiettivo del gioco, identificato da due coordinate (lettera, numero)

Modello del dominio

Si definisce il modello delle entità specificate nei requisiti del sistema.

Pirata

Pedina posizionata dai giocatori in una casella della griglia di gioco in cui si ipotizza possa trovarsi il tesoro.

public interface IPirate {
	
	public void setPosition(IPosition pos);
	public IPosition getPosition();
	public String getPlayerName();
	
}

Tassello

Tessera che identifica una coordinata lettera/numero sulla griglia di gioco.

public interface ICard {
	
	public String getType();
	public String getValue();
	public void setConfidence(int confidence);
	public int getConfidence();
	
}

Agente

Un agente software è un entità computazionale in grado di agire in modo autonomo, percependo informazioni dall’ambiente in cui si trova ed agendo secondo la propria base di conoscenza al fine di soddisfare i propri obiettivi (goals).

Ogni agente interagisce con l’ambiente ed effettua azioni atte a recuperare conoscenza utile per il perseguimento dei propri goals inoltre, ogni agente è proattivo in quanto ha la capacità di prendere iniziative non solo in base agli stimoli esterni ma anche in base a ciò che deve raggiungere.

In questo caso gli agenti hanno un proprio profilo definito ed “infuso” in base al livello di “trust" nei confronti dell’avversario e hanno come unico goal quello di riuscire a vincere la partita.

Struttura

public interface IPlayerAgent {
	/**
	 * 
	 * @return nome del giocatore
	 */
	public String getName();
	
	/**
	 * Distribuisce al giocatore i tasselli per
	 * iniziare la partita
	 */
	public void setCards(ArrayList<Card> cards);
	
	public void setMissingCards(ArrayList<Card> cards);
	
	/**
	 * Comunicazione di inizio del turno del giocatore
	 */
	public void startTurn();
	
	/**
	 * Processo di ragionamento con il quale il giocatore
	 * sceglie la mossa da fare in base alla conoscenza 
	 * in suo possesso
	 */
	public void deliberate();
	
	/**
	 * Posizionamento del pirata sulla griglia di gioco
	 */
	public void positionPirate(ICard x, ICard y);
	
	/**
	 * Comunicazione di fine del turno del giocatore
	 */
	public void endTurn();
	
}

Interazione

Un agente può interagire con:

  • un altro agente: deve avere percezione dell'avversario, per poter decidere se credere o meno alle sue mosse ed inoltre deve inviare una comunicazione al termine del proprio turno.
  • l'ambiente: prima del posizionamento di ogni pirata, l'agente deve ottenere informazioni dai posizionamenti dei pirati dell'avversario e di conseguenza posizionare il proprio pirata sulla griglia di gioco.
Comportamento

agentBehavior.png

Griglia

Rappresenta l'ambiente di gioco sul quale si svolgono le azioni dei giocatori.

grid.png

Struttura

public interface IGrid {
	
	/**
	 * Utilizzato per posizionare un pirata sulla
	 * griglia di gioco
	 * 
	 * @param pos identifica la casella nella quale si vuole posizionare
	 * 		  il pirata
	 * @param pirate identifica il pirata che si vuole posizionare
	 * 
	 */
	public void setPirate(Position pos, Pirate pirate);
	
	/**
	 * Controlla lo stato della griglia di gioco
	 * 
	 * @return lista dei pirati posizionati sulla griglia
	 */
	public List<IPirate> allPiratePosition();
	/**
	 * Controlla che in una specifica posizione
	 * non sia stato posizionato nessun pirata
	 * 
	 * @param box identifica la casella scelta
	 * @return false se la posizione richiesta è già occupata
	 */
	public boolean isFree(Position box);
	
	public void printPosition();
	
}

Interazione

Durante la partita ogni giocatore può interagire, secondo il proprio turno, con la griglia di gioco sia per posizionare i propri pirati sia per acquisire ulteriore conoscenza dalle azioni dell'avversario. Quando viene completato il posizionamento di un pirata, questo non potrà più essere spostato.

Comportamento

setPirate(Position pos, Pirate pirate) : permette di posizionare un pirata sulla griglia di gioco.

allPiratePosition() : ritorna l'insieme dei pirati posizionati sulla griglia e le relative posizioni così da permettere di controllare lo stato della griglia di gioco.

Analisi del problema

Appare evidente dall'analisi dei requisiti che la complessità del sistema è determinata dalla realizzazione del processo decisionale degli agenti e dalla definizione di "trust" che ogni agente deve possedere e gestire.

Per quanto riguarda il processo decisionale ogni agente deve essere in grado di valutare, in ogni turno, il proprio set di mosse possibili e tra queste scegliere quella da eseguire, considerando gli indizi in suo possesso e la propria possibilità di mentire. La mossa sarà scelta dall'agente in modo non deterministico tra il set di mosse possibili ma sempre considerando il perseguimento dei propri obiettivi di gioco. Per effettuare il proprio ragionamento al fine di scegliere la mossa da eseguire, l'agente dovrà tenere conto anche dell'avversario che avrà di fronte, per questo è importante approfondire il concetto di "trust".

Trust

Di norma le informazioni scambiate tra due agenti sono considerate veritiere e di conseguenza gli agenti sono da ritenersi "sinceri", in questo caso lo scambio di informazioni/indizi tra i due giocatori può determinare per il giocatore che riceve l'indizio un considerevole vantaggio nel perseguire l'obiettivo di gioco. Per questo motivo è necessario che gli agenti abbiano diversi profili di gioco che spazino tra le caratteristiche di agente sincero e quelle di agente bugiardo, di conseguenza questo implicherà che alcune azioni eseguite rappresenteranno "falsi indizi" per l'avversario. Introducendo "falsi indizi", per poter bilanciare la partita e per fare in modo che sia il più realistica possibile, si dovranno dotare gli agenti di un concetto di "trust", ossia un livello di fiducia che un giocatore possiede nei confronti di ogni avversario che affronta, in modo da permettere all'agente stesso di dubitare delle azioni eseguite dall'avversario sulla griglia di gioco. L'idea è che questo livello di "trust" possa essere aggiornato nel caso il giocatore affronti nuovamente lo stesso avversario, in modo da avere un informazione sempre più attendibile.



In conclusione le criticità evidenziate per la realizzazione del sistema sono le seguenti:

  • definire il processo deliberativo dell'agente, ovvero il ragionamento seguito per effettuare determinate scelte
  • gestire i profili di gioco che caratterizzino giocatori più o meno "sinceri"
  • gestire il livello di "trust" in modo che possa essere modificato a fronte di ulteriori informazioni acquisite sull'avversario

Progetto

Sarà ora trattata la realizzazione del sistema precedentemente descritto, affrontando le criticità riscontrate e ponendo inizialmente l'attenzione sul concetto di agente e su come poter realizzare tale entità autonoma.

Agenti BDI e Jason

Per la programmazione degli agenti intelligenti presenti nel sistema si è scelto di utilizzare l'approccio BDI. Il modello BDI si ispira ai processi di ragionamento dell'uomo ed individua tre aspetti fondamentali come:

  • Belief: insieme delle informazioni riguardanti l'ambiente
  • Desire (Goal): rappresenta lo stato motivazionale dell’agente ossia l’obiettivo che vuole conseguire
  • Intention: rappresenta il processo deliberativo dell’agente ossia i Desires per i quali ha pianificato le azioni da eseguire
Questo modello permette, inoltre, di definire dei piani che rappresentano un insieme di azioni che l'agente può svolgere per raggiungere i propri goals. Per concretizzare questo modello si è deciso di scegliere Jason come framework per sistemi multi-agente. Jason è implementato in Java e rappresenta un estensione del linguaggio AgentSpeak. Questo framweork presenta diverse caratteristiche importanti che permettono di semplificare la realizzazione di un sistema multi-agente, infatti consente di personalizzare completamente l’architettura di un agente, permette le comunicazioni inter-agente ed è presente la nozione di ambiente multi-agente che può essere implementato in Java.

Struttura

La struttura di un agente è definita in termini di belief, goal e plans.

Belief

I belief rappresentano le informazioni necessarie all'agente per giocare la partita e possono essere aggiornate durante le fasi di gioco. Ogni giocatore conosce sia il proprio indice di "bluff", in base al quale potrà mentire sulle mosse effettuate, sia un indice di "trust" che rappresenta la fiducia nei confronti dell'avversario. Questo argomento verrà trattato meglio in seguito.

bluff().
trust().

Il giocatore ha conoscenza dei propri tasselli e dei tasselli mancanti. I tasselli mancanti sono rappresentati da tutte le possibili combinazioni in cui il giocatore può pensare ci sia il tesoro e proprio tra queste informazioni sarà presente la mossa che il giocatore potr effettuare.

cardsOnHand().
missingCards().

Ogni giocatore ha necessariamente un riferimento al giocatore avversario in modo da poter costruire uno storico sulle sue caratteristiche e un riferimento al turno corrente in modo da poter sapere quando sarà il proprio turno per poter posizionare il proprio pirata.

otherPlayer().
turn().

Interazione

Gli agenti comunicano tra loro per avvertire l'avversario di controllare se è il proprio turno.

Infatti, la gestione dei turni non è alternata (es. player1, player2, player1, etc.) ma la sequenza dei turni è creata grazie ad un'estrazione randomica, quindi ad ogni fine turno, ogni giocatore deve controllare se tocca ancora a lui o se invece è il turno dell'avversario.

Per questo ad ogni turno terminato, il giocatore che ha appena effettuato la mossa, invia un messaggio all'avversario per avvertirlo della fine del turno.

Comportamento

Il comportamento è definito dai piani descritti nel corpo dell'agente che specificano:

-l'inizio della partita.L'agente deve controllare se è il suo turno e quindi procedere con o invece deve attendere;

+!startGame : canStart & not gameEnded <- -canStart; 
			                  !movePirate. 				
+!startGame : not canStart & not gameEnded <- true.

-il posizionamento del pirata, considerando il proprio livello di bluff;

+!selectPosition : true <- selectRandom(missingCards);
			   !endTurn.

-l'aggiornamento e verifica del turno, in cui si occupa di inviare un messaggio all'altro giocatore in modo che anch'esso possa controllare il turno corrente;

+!updateTurn : not gameEnded <-  continueMatch(N);
				 ?otherPlayer(Player);
				 .send(Player,achieve,startGame);
				 !startGame.

-l'aggiornamento dell'indice di "trust" nei confronti dell'avversario;

+!savePlayer : gameEnded <- controlPlayer(nameAgent).

Gestione "trust" e "bluff"

Per infondere al giocatore un profilo sincero/bugiardo si è scelto di associare al giocatore stesso un indice che rappresenti: *trust : fiducia nei confronti dell'avversario, quindi con quanta probabilità credere alle mosse effettuate dall'avversario; *bluff : percentuale di bluff che caratterizza il giocatore, ovvero con quantà probabilità il giocatore potrà scegliere di mentire nel posizionamento del proprio pirata, fornendo all'avversario indizi errati. Ad ogni turno, per ogni posizionamento di un pirata verranno valutati questi due indici, permettendo al giocatore di agire di conseguenza.

Storico caratteristiche dell'avversario

L'indice di "trust" può essere aggiornato, così da poter tener conto di ulteriori informazioni date dalle varie partite effettuate con lo stesso giocatore. Alla fine della partita, il giocatore può controllare se le mosse dell'avversario sono state sincere o meno, aggiornando di conseguenza l'indice di "trust". Il nome dell'avversario e valore dell'indice di "trust" verrà salvato in un file ".txt" e aggiornato nel caso ci siano più partite con lo stesso avversario di gioco. Questo garantisce al giocatore di poter valutare al meglio le mosse dell'avversario.

+!savePlayer : gameEnded <- controlPlayer(nameAgent).

Implementazione

Per la realizzazione del prototipo del sistema è stato usato il plugin Jason per Eclipse e il linguaggio Java. E' presente un solo tipo di agente, in quanto il comportamente di gioco è il medesimo per tutti i giocatori, che è possibile configurare con indici più o meno elevati di "trust" e "bluff".

gameImpl.png

Il codice del prototipo è disponibile al seguente repository: https://github.com/ilTesoroDeiPirati/sa1415_ilTesoroDeiPirati