In base ai risultati ottenuti nell'applicazione dell'algoritmo di gestione dei con itti proposto negli scenari con veicoli, si è ipotizzato la creazione di un secondo algoritmo, volto alla conoscenza degli agenti in base al comportamento tenuto nello scontro. In base alla PdA su cui vengono creati i giochi, alla priorità di accesso privata e a quella pubblica è infatti possibile de nire il numero di passi che l'avversario eettuerà prima di lasciare lo scontro. L'agente che risulta vincitore, conoscendo la traiettoria degli scon tti, può ricavare da essa la priorità di accesso pubblica e i passi eettuati nel con itto. E' stato quindi ipotizzato un metodo che consentisse di ricavare anche le PdA proprio a partire dalle traiettorie degli scon tti. In base a tale valore, sarà possibile individuare l'attitudine dell'agente avversario, cioè la sua tendenza a lasciare o rimanere all'interno del con itto. Curiosamente, la probabilità di azione nasce come una ipotesi sulle azioni degli altri, ma entra profondamente nella scelta delle proprie, in uenzando sia le matrici, come visto in 2.2, sia il Learning, come visto in 2.3.
Si introduce il concetto di Attitudine dell'agente avversario a rimanere nel con itto, indicata con i termini di Vincente (in quanto tende a rimanere in gioco per più tempo), Neutro e Perdente (in quanto tende a lasciare presto il gioco), in base al valore della PdA caricati in memoria del giocatore. Le tre attitudini, infatti, saranno caratterizzate da P (L|Gk
p) diverse. Si avrà che P (L|G k
p)V incente <
P (L|Gkp)N eutro< P (L|Gkp)P erdente e P (L|Gkv)V incente> P (L|Gkv)N eutro> P (L|Gkv)P erdente.
A partire dalle simulazioni eettuate, sono state create delle tabelle caricate nella memoria di ogni agente contenenti il numero di passi eettuati in funzione della priorità di accesso e delle attitudini
possibili di un agente. In base ad esse, dopo una serie di scontri, l'agente vincitore arriverà ad un unico valore possibile di attitudine per ogni avversario, capace di combinare i valori riscontrati nei con itti. L'algoritmo di identi cazione segue il presente schema:
I passi che devono essere compiuti dall'algoritmo di Identi cazione sono i seguenti: • Inizializzazione:
Caricamento delle Tabelle di Identi cazione nella memoria dell'agente; • Confronto:
Compimento di uno scontro tra agenti tramite l'algoritmo di gestione dei con itti ∗ Memorizzazione delle traiettorie degli avversari;
In base al risultato dello scontro:
∗ Se l'agente risulta scon tto, i dati ricavati non sono sfruttabili in quanto incompleti; ∗ Se l'agente risulta vincitore, i numero di passi eettuati dagli avversari sono confrontati
con le tabelle memorizzate. Per ogni agente viene ipotizzata una possibile attitudine; Ripetizione del passo di Confronto no a raggiungere una delle condizioni di conclusione; • Conclusione:
Combinando i risultati di successivi scontri, l'agente riesce a identi care l'attitudine degli avversari;
Combinando i risultati di successivi scontri, l'agente ottiene informazioni contrastanti, non riscontrabili dalle tabelle, che non permettono l'identi cazione, quindi uno o più avversari non rientrano nelle attitudini previste.
E' possibile tradurre i passi dell'algoritmo nel seguente pseudo codice Algoritmo 2.2 Identi cazione
1. load(Tabels, Ident_0) 2. Ident = Ident_0
3. while Ident 6= error or size(Ident) 6= 1 4. Result = play(Algoritm 1)
5. if Result = Success then
6. [Start, N_Step]=get(Trajectory_adversary) 7. Ident_ip=search(Tabels(Start), N_step) 8. if Ident_ip T Ident 6= Ø then
9. Ident = Ident_ip T Ident 10. else Ident = error
11. end 12. end
Attitudine\PAp 1 2 3 4 5 6 7 8 Vincente 4 4 5 6 7 8 10 10
Neutro 3 4 5 5 7 7 9 9 Perdente 3 3 6 6 7 7 10 9 Tabella 2.1: Esempio di Tabella per l'Identi cazione
Attitudine Ea0 Da0
I con itto II con itto I con itto II Con itto Agente A Neutra 10 10 10 10 Agente B Vincente 4 6 10 10
Tabella 2.2: Esempio di condizioni Iniziali
Per poter eettuare la fase di confronto, quindi, sono state create una serie di tabelle, una per ogni possibile posizione iniziale degli avversari, simili a quella visibile in Tab. 2.1, contenenti il numero passi che un giocatore fa prima di lasciare il con itto in funzione della priorità di accesso privata e della propria attitudine all'interno del gioco. La memorizzazione della traiettoria degli altri agenti è una azione già prevista dall'algoritmo di gestione, quindi non è necessario richiedere l'acquisizione di altre informazioni. A questo punto, il vincitore può leggere quali sono le possibili combinazioni di Attitudine\PAp per avere quella risposta. Dato che è possibile avere la stessa risposta in più casi, saranno necessari più con itti per identi care il tipo di un avversario. Si riporta in seguito un esempio per capire la struttura, facendo riferimento alla tabella già presentata e nel caso di due agenti coinvolti.
Si suppongono due agenti con Attitudini diverse, partenti dalle condizioni iniziali visibili in Tab 2.2 e sfruttando la tabella già mostrata per comodità. L'agente B lascia dopo un numero di passi pari a 6, di conseguenza A può dedurre che ci si trova nelle combinazioni [Vincente-4], [Perdente-3] o [Perdente- 4]. Dopo un secondo con itto, risulta che B lascia dopo 8 passi, e l'unica combinazione possibile è [Vincente-6]. A questo punto si può restringere il campo delle possibilità alla sola Attitudine Vincente e identi care B.
E' importante notare che è possibile non riuscire a concludere l'algoritmo di Identi cazione, cioè che, dopo una serie di con itti, l'agente non riesca a de nire l'attitudine di qualcuno degli avversari, perché successivi scontri non aumentano il set di informazioni a sua disposizione. Si rimanda al capitolo 4 per un analisi su questo aspetto in base alle simulazioni eettuate.
L'algoritmo di Identi cazione può essere applicato in contemporanea su molti agenti avversari, a patto che l'agente possa distinguerli in qualche modo. Se ciò non è possibile, l'agente non è capace di riconoscere a quale giocatore corrisponda un dato ricavato. Di conseguenza, potrà essere applicato su un solo avversario alla volta, sfruttando con itti a due giocatori.
Capitolo 3
Aspetti computazionali
In questo capitolo saranno discussi gli aspetti relativi all'implementazione dell'algoritmo per le simu- lazioni. Nella prima parte sarà presentato il modo usato per la scelta della strategia da applicare da parte dei singoli agenti. La seconda sezione mostrerà il design usato per la creazione del gioco, cioè la de nizione di guadagni, passo di previsione e probabilità. Nella terza parte saranno arontati alcuni aspetti relativi ai con itti a più di due giocatori.
3.1 La scelta della strategia
La scelta di un equilibrio, ci consente di de nire le strategie per tutti i giocatori. Le sequenze di azioni da parte dei giocatori che porteranno a quell'equilibrio saranno quelle cercate. Scelto che tipo di equilibrio si deve cercare nel capitolo precedente, si deve ora de nire come cercarlo.
3.1.1 Numero di Giocatori
L'algoritmo presentato è stato sviluppato per risolvere con itti con un numero di agenti qualsiasi. Se questo non comporta problemi al livello teorico, la realizzazione pratica risulta di coltosa. Tralasciando momentaneamente gli aspetti di maggiore carico computazionale, argomento che verrà ripreso in 3.3, l'individuazione degli equilibri in questi casi risulta problematica. Da decenni esistono metodi per ricavare gli equilibri in presenza di due giocatori. Da decenni esistono metodi per ricavare gli equilibri in presenza di due giocatori. Ad esempio, l'algoritmo Lemke-Howson, metodo che verrà presentato successivamente, è del 1964 e su di esso esistono molti testi in letteratura che ne valutano pregi e difetti. Lo sviluppo di metodi per giochi a più di due dimensioni, invece, è molto più recente. L'algoritmo considerato oggi come migliore in questi ambiti è il Govindan-Wilson, indicato anche come The Global Newton Method ([34]), nato nel 2003 e del quale si hanno sviluppi e analisi solo in tempi più recenti. Tale metodo presenta però ancora molte aspetti da migliorare, in quanto richiede spesso di adattare opportunamente i giochi e non sempre riesce ad arrivare ad una conclusione in tempo nito [35]. Per questo motivo si è preferito testare l'algoritmo presentato all'interno di questa Tesi sfruttando un metodo sicuro e riducendo le simulazioni a confronti tra due giocatori. Si sottolinea, però, come solo quanto indicato per la scelta della strategia non è adattabile in con itti a più giocatori, mentre il resto della tesi è stato sviluppato in maniera indipendente dal numero di agenti presenti.
3.1.2 Algoritmo di Lemke-Howson
L'algoritmo usato per trovare gli Equilibri Bayesiani del gioco è detto di Lewke-Howson, è de nito come The best known among the combinatorial algorithms for nding a Nash equilibrium [36]. Il metodo è applicabile nei casi di bimatrix game, cioè nei casi in cui il gioco è esprimibile tramite due matrici contenenti entrambi i guadagni di un giocatore, con payo positivi. L'algoritmo fornirà in uscita due distribuzioni di probabilità sulle azioni possibili di ogni giocatore, in quanto è applicabile solo in caso di equilibri misti.
L'applicazione dell'algoritmo nella simulazione avverrà tramite il metodo Luenberger presentato in [37], cioè tramite minimizzazione di una funzione, seguendo questo percorso:
• Divisione della matrice combinata (chiamata G da globale) in due parti, ognuna coi guadagni di un singolo giocatore (indicate con Greal per quanto riguarda quella del giocatore A e con Gimag per quelli di B);
• De nire la variabile in base alla quale minimizzare la funzione. Essa sarà composta 2(N +1)+ 2
elementi, così divisi:
X : 2N elementi corrispondenti alla densità di probabilità sulle strategie del giocatore A;
Y : 2N elementi corrispondenti alla densità di probabilità sulle strategie del giocatore B;
Q : Un elemento corrispondente al limite inferiore della combinazione lineare di Greal e Y; P : Un elemento corrispondente al limite inferiore della combinazione lineare di Gimag e X; • De nizione della funzione da minimizzare
XT(−Greal)Y + XT(−Gimag)Y + Q + P (3.1) • De nizione dei vincoli
Equazioni di vincolo che garantiscano che le densità di probabilità abbiano somma uguale a 1: 2N X i Xi= 1 (3.2) 2N X i Yi= 1 (3.3)
Disequazioni di vincolo inferiore alle combinazioni delle matrici e delle probabilità:
GimagTX > P I (3.4) Greal Y > Q I (3.5) Disequazioni di vincolo inferiore ai valori di densità di probabilità:
Xi> 0 (3.6)
Yi> 0 (3.7)
• Inserimento della funzione e dei vincoli all'interno di un formula fmincon del software MATLAB. Questo metodo consegna due densità di probabilità sulle strategie del giocatore e dell'avversario. In base a queste verrà scelto un equilibrio in particolare, cioè la strategia da applicare e quella ipotizzata per l'avversario.
Posizione 1 2 3 4 5 6 7 8 strategia LLL LLV LVL LVV VLL VLV VVL VVV strategia corrispondente LLL VLL VVL VVV Probabilità 0.002 0.002 0.002 0.002 0.05 0.05 0.6 0.22
Tabella 3.1: Esempio di distribuzione di probabilità sulle strategie
3.1.3 Strategia Piani cata
Il metodo proposto consegna quindi una serie di equilibri misti ai quali è associata una distribuzione di probabilità sulle sequenze di azioni possibili. Per essere coerenti con la teoria, il giocatore dovrebbe eettuare una estrazione a sorte tra le varie possibilità, pesate in base alle probabilità calcolate, ed applicare quella che ottiene. Questo metodo, però, non può essere applicato in una situazione in cui la scelta di una azione può comportare pesanti ripercussioni. In linea di principio, si può avere un caso in cui un giocatore debba applicare una strategia che risulti ampiamente sfortunata, cioè con probabilità molto minore alle altre. Per evitare questo comportamento comunque aleatorio, si impone che ogni agente debba applicare la strategia associata alla probabilità maggiore.
Dal punto di vista del software, la sequenza di azioni da seguire è la seguente:
• Presa la distribuzione di probabilità, ordinate in un vettore in maniera progressiva in base alla strategia associata (da LLL... a VVV...), si ricerca il valore di probabilità maggiore
Nel caso di probabilità uguali, viene presa quella più in basso nella sequenza; questo signi ca scegliere una sequenza con più azioni V di seguito, invitando l'agente a continuare il gioco per migliorare la propria condizione;
La posizione della probabilità scelta nel vettore è legata al numero di azioni V in sequenza nella strategia; questo esempio spiega questo principio:
∗ Si supponga un passo di previsione di 3, che comporta 8 strategie possibili, e che la distribuzione di probabilità presente in Tab 3.1:
∗ Se la strategia migliore è in posizione 2(N )(in questo caso 8), corrisponde ad una sequenza
di V lunga N;
∗ Per le altre sequenze, se la posizione è minore o uguale del valorePhp=12(N −p), corrisponde
ad una strategia di V lunga h-1
· 1,2,3 e 4 sono minori o uguali di 2(N −1), quindi h è 1, quindi la strategia è fatta da
sole L;
· 5 e 6 sono maggiori di 2(N −1), ma minori di 2(N −1)+2(N −2), quindi h è 2 e la sequenza
di azioni prevede 2-1=1 azioni V;
∗ Nella distribuzione sopra, l'algoritmo trova che la probabilità maggiore è in posizione 7, cioè 2(3)− 1 < 23, quindi corrisponde ad una sequenza di V lunga 3-1=2.
• Individuata la strategia, viene applicata la sequenza di V di lunghezza de nita.
3.1.4 Strategia ipotizzata dell'avversario
Per poter indicare una strategia ipotizzata per l'avversario, si segue lo stesso schema visto sopra, appli- candolo alla distribuzione di probabilità del secondo giocatore data dall'algoritmo di Lemke-Howson. Si
Figura 3.1: Esempio di Matrice con N=3
otterrà quindi una sequenza di V lunga un certo numero di passi (al più pari a N), che verrà confrontata con quella poi applicata realmente dall'avversario. La dierenza tra le due strategia sarà poi usata nel Learning.