Nash meraviglioso

Oggi avevo poca voglia di selezionare canzoni per la mia tragedia e così, invece di sforzarmi e farmi cattivo sangue, ho deciso di fare qualcosa di diverso per rilassarmi...

Qualche mese fa ho provato a seguire un corso in linea di “Teoria dei Giochi”: argomento che mi è sempre interessato ma che all'università non ho avuto modo di studiare. Sfortunatamente il corso in questione era fatto troppo male: in pratica si limitavano a ripetere le formule in maniera arida e massiccia e quindi, dopo la prima lezione, l'ho prontamente abbandonato.
Eppure fra i vari argomenti affrontati mi aveva colpito l'equilibrio di Nash: onestamente non lo capii per bene nel video né persi tempo a riguardarmelo con calma ma il concetto base mi parve interessante. In alcune tipologie di giochi esiste una strategia che massimizza il risultato per tutti i giocatori. Da un certo punto di vista questo rende il gioco poco interessante perché, conoscendo la strategia giusta, le varie scelte divengono meccaniche. Però identificare una tale strategia può essere molto interessante.

Dopo aver abbandonato Candy Crush (v. il corto Raggiunto! dello scorso aprile) ho iniziato a giocare intensivamente a un altro gioco su FB: Marvel: Avengers Alliance.
In tale gioco bisogna costruire una squadra di tre eroi e portare a termine diverse avventure fra cui combattere contro le squadre di altri giocatori.
Ogni eroe ha diverse caratteristiche ma, al di là delle differenze, ne esistono sei tipologie: generalista, stratega, energetico, spia, picchiatore e combattente.
Il “generalista” è neutro, non avendo né particolari pregi né difetti, ma tutte le altri tipologie dominano un'altra classe e sono a loro volta dominate da un'altra.

Lo schema è il seguente:

stratega >> energetico >> picchiatore > combattente >> spia > stratega

dove “>>” significa “molto meglio” mentre “>” significa “meglio”.

Chiaramente negli scontri contano gli specifici eroi coinvolti, l'abilità del giocatore e la fortuna. Però un fattore molto importante sono le tipologie delle squadre di eroi che si affrontano.

Quando iniziai a giocare (avevo anche poca scelta) parti con: generalista, energetico ed energetico.
Il problema è che, quando trovavo anche un solo stratega nella squadra avversaria, andavo in grande difficoltà. Alla fine decisi di puntare sui combattenti perché quando affrontavo un picchiatore ero comunque in grado di cavarmela giocando bene ed ero in grande vantaggio se trovavo una spia.
Infatti adesso gioco con: generalista, combattente e combattente.

Inutile dire che, sempre più spesso, mi capita di giocare contro squadre che hanno uno o più picchiatori!

Mi chiedevo quindi quale fosse (e se esistesse!) la composizione più efficace per la propria squadra cosa che, ovviamente, dipende dalle scelte degli altri giocatori...
Avevo la sensazione che l'equilibrio di Nash fosse una squadra tutta di generalisti ma non avrei saputo spiegarne il motivo matematicamente: però l'idea della mancanza di pregi o difetti mi suggeriva una sorta di equilibrio...

Così oggi mi sono divertito a fare una simulazione (*1) col calcolatore per studiare alcune dinamiche collegate alla scelta della squadra.

Inizialmente ho creato 108 squadre (tutte le combinazione delle sei tipologie di eroe) e le ho fatte “combattere” casualmente fra loro per 20 scontri: cioè ogni squadra combatteva 20 scontri con altrettante squadre diverse. Alla fine dei 20 scontri tutte le squadre che ne avevano persi più di 10 si “rafforzavano” sostituendo casualmente un proprio eroe con uno, selezionato a sorte, delle squadre da cui erano state sconfitte. L'idea era che si cercava di imitare le squadre vincenti...
Tutto questo ripetuto per 100 iterazioni.

Ho poi esportato i risultati su LibreOffice Calc (*2) e questo è il risultato:

Prevedibilmente si osservano degli andamenti ciclici. Inizialmente il numero di picchiatori aumenta ma questo porta col tempo a un aumento degli energetici che fanno crollare il numero di picchiatori. Ma se gli energetici crescono allora gli strateghi sono favoriti e aumentano a loro volta... etc...
A parte questi andamenti ciclici c'è il problema che alcune tipologie rischiano quasi di sparire totalmente e, quando ciò avviene, le classi dominate possono crescere incontrastate...
Inoltre non è chiaro, visto il numero di iterazioni limitato a 100, se si tenda o meno a una situazione di equilibrio.

Per cercare di ovviare a questo problema ho triplicato le squadre di partenza portandole da 108 a 324. Il risultato è il seguente:

Più o meno il grafico è come il precedente ma in questo caso si osserva una leggera, ma costante, crescita dei generalisti (che è quello che mi aspettavo di ottenere). A questo punto ho così supposto che, aumentando le iterazioni (sempre fisse a 100) i generalisti avrebbero preso il sopravvento.
Per questo ho raddoppiato le iterazioni, portandole a 200, e aumentato le squadre iniziali a 540 perché alcune tipologie si estinguevano completamente...

E infatti, anche in questo grafico, sul finale, le spie vanno a 0...
La tendenza dei generalisti pare confermata, eppure...
Eppure c'era qualcosa che non mi convinceva: nel gioco non mi sembrava di aver osservato una dominanza ciclica così forte dei picchiatori né, contemporaneamente, di non vedere mai o quasi alcune tipologie di eroi.
Questo mi ha fatto dubitare della bontà del mio modello e, ragionandoci, mi è venuta in mente una nuova idea: per rafforzare la mia squadra io (KGB) non scelgo eroi della stessa tipologia di quelli più frequentemente incontrati bensì la loro classe antagonista!
Facendo questo piccolo aggiustamento al mio modello ho ottenuto il seguente risultato:

Questo grafico mi è parso subito molto più realistico!
Le classi che, per esperienza, considero più deboli (perché più marcatamente dominate dalle loro antagoniste) sono proprio gli energetici e le spie. Queste classi però non rischiano di sparire ma tendono a oscillare in una fascia ben definita. I picchiatori continuano a essere gli eroi più frequenti ma non raggiungono più le percentuali di dominanza assoluta dei grafici precedenti.
Combattenti (i miei!) e strateghi si contendono il secondo posto.
Questo è molto interessante! Per contrastare i picchiatori avevo una mezza idea di sostituire uno dei miei due combattenti con un energetico (l'antagonista dei picchiatori) ma temevo che gli strateghi mi avrebbero causato troppi problemi. La simulazione pare confermare questa tendenza: quando il numero di picchiatori cresce, invece di puntare direttamente sugli energetici, è meglio optare per gli strateghi!
Infine nei generalisti non è possibile osservare alcuna tendenza ben definita.

È presto per trarre delle conclusioni definitive: ci sarebbero da fare molte altre prove per avere risultati statistici più attendibili, giocare sul numero di iterazioni, e vari aggiustamenti al modello (*3)

Conclusione: interessante! Stasera farò altri esperimenti ma domani torno alla tragedia...

Nota (*1): Qui il file jar con tutto il codice. Solo quattro classi di cui una, la Dado, di cui uso solo un paio di funzioni statiche. Se qualcuno è interessato ai dettagli mi faccia sapere!
Modificato 2/1/2015: Attenzione! Come spiegato nel corto Errore buffo nel codice proposto c'è un errore: fortunatamente (e stranamente!) l'errore colpisce statisticamente in ugual misura tutte le tipologie di eroe e quindi il risultato dei grafici è comunque attendibile. La correzione del codice è lasciata per esercizio al lettore: in verità mi fa fatica scaricarne una nuova versione su Dropbox!
Nota (*2): Questo è il foglio di calcolo da cui ho tratto i grafici, uno per sheet...
Nota (*3): ad esempio adesso il rimpiazzo di un eroe avviene considerando solo gli antagonisti degli eroi appartenenti a squadre che ci hanno sconfitto ma probabilmente sarebbe più corretto considerare tutte le squadre affrontate...

Share