lunedì 5 gennaio 2009

IL TORNEO DEL PRIGIONIERO! Partecipa!!

Sono veramente felice di presentarvi il
TORNEO DEL PRIGIONIERO!

Il torneo si baserà sul gioco del dilemma del prigioniero, che sicuramente alcuni di voi conosceranno già. Prendendo spunto da Axelrod che un ventennio fa organizzò questo tipo di torneo chiamando a raccolta la crema degli intellettuali, ho pensato che un'esperienza simile tra i blogger sarebbe stata una cosa davvero entusiasmanete!! Non sapete cos'è questo dilemma? Non preoccupatevi, ecco tutte le informazioni di cui avete bisogno!
Se invece sapete già tutto e non avete voglia di ripassare potete passare direttamente alla spiegazione su come partecipare : )

  • IL DILEMMA DEL PRIGIONIERO
Il dilemma del prigioniero è un tipo di gioco interessante e molto semplice da capire. Si gioca in due. Per spiegarlo userò l'esempio tratto da Dawkins, Il gene egoista: ogni giocatore ha due carte coperte, una "Collaborazione", l'altra "Defezione". I giocatori scelgono la propria carta e la girano nello stesso istante. Ci sono quattro possibilità:
1) entrambi giocano la carta "collaborare";
2) A collabora ma B no;
3) B collabora ma A no;
4) Né a né B collaborano;
Ogni alternativa avrà i propri punteggi. Ecco qui la tabella dei punteggi con le quattro combinazioni di Collaborazione (1) e Non Collaborazione (0):

I punteggi non sono assegnati a caso e, soprattutto, il gioco non è puramente speculativo. Per capire il significato di questi punteggi immaginiamo che A e B siano 2 scimmie che debbano scegliere se spulciarsi o meno. Il beneficio massimo è uguale a 5. Ci sono 4 alternative:
1) Entrambe le scimmie si spulciano a vicenda (in alto a sinistra). Il beneficio massimo di 5 è abbassato dal costo di dover spulciare l'altra scimmia.
2) A collabora ma B no (nella tabella in basso a sinistra). In questo caso la scimmia B viene spulciata e non dà nulla in cambio. La scimmia A a si affatica per spulciare l'amica e inoltre il suo atto di gentilezza non viene ricambiato. E' quindi il caso peggiore per A.
3) Come 2, ma in questo caso è B che collabora e A no (in alto a destra). E' il caso peggiore per B.
4) Nessuna delle due scimmie si spulcia. Non ricevono benefici ma almeno non si stancano nello spulciare l'altra (in basso a destra).
La cosa interessante di questo gioco è che, se consideriamo le diverse alternative, ci converrebbe SEMPRE "non collaborare". Immaginiamo infatti di essere la scimmia A.
Scegliamo infatti "non collaborare". La scimmia B può Collaborare o Non Farlo. Nel caso che non collabori avremo entrambi punteggio di 1, nel caso collabori lei avrà punteggio di 0 e noi di 5. Proviamo a scegliere "collaborare" e vedremo che i risultati saranno meno positivi (se l'altra scimmia collabora otterremo 3, se non collabora 0!).
Da questo ragionamento sembrerebbe che convenga essere cattivi e menefreghisti! Ma è proprio vero?
Se tutte e due le scimmie adottassero questa strategia utilitaristica (entrambe "non collaborando") otterrebbero un punteggio di 1, molto più basso del caso di reciproca collaborazione (punteggio 3 a testa)! Il problema è che ogni scimmia non sa cosa farà l'altra. Se quindi si sente buona e collabora rischierà che l'altra scimmia non collabori, tradendo la fiducia a suo beneficio. Il punto fondamentale è conoscere lo stile dell'avversario; ad esempio, se notiamo che l'avversario non collabora MAI per noi sarebbe meglio non collaborare. Quindi le partite interessanti sono quelle che durano molte manche.
Spero sia tutto chiaro! Vediamo ora cos'è questo torneo del prigioniero.


  • IL TORNEO! COME PARTECIPARE?
Axelrod negli anni ottanta organizzò un torneo nel quale diverse strategie si scontravano tra loro. Si trattava ovviamente di software che adottavano diversi comportamenti di collaborazione o defezione, alcuni molto complesse e altri semplici. Ho pensato di simulare la stessa cosa, creando un programma che permetta di far funzionare dei software nel gioco del prigioniero. Ho utilizzato Visual Basic 6.0. I partecipanti non saranno i pochi fortunati intellettuali chiamati da Axelrod, ma chiunque voglia! Immaginate cosa potrebbe essere far scontrare due software creati da, per dire, malvino e l'estinto!
Per partecipare basterà inviarmi via mail la vostra strategia, semplicemente in italiano. La mia mail è -> onepiece888 AT tin PUNTO it ; questo perché le strategie devono ovviamente essere segrete agli altri. Ogni partecipante dovrà lasciare un commento IN QUESTO POST nel quale si comunica la propria partecipazione, in modo che ognuno sappia chi partecipa. Le uniche limitazioni saranno date dalla vostra fantasia e dalla mia scarsa capacità di programmatore : D Mi raccomando comunque di essere molto precisi in modo da permettere una facile traduzione in linguaggio basic. Chi ne ha voglia ed è capace può inviarmi il software direttamente in linguaggio basic.
La vittoria andrà al creatore del software che totalizzerà più punti ALLA FINE DEL TORNEO in 300 manche con ogni avversario. Questo vuol dire che un software può anche PERDERE SEMPRE con i singoli avversari, ma può risultare vincitore del torneo se LA SOMMA DEL PUNTEGGIO DI TUTTE LE SFIDE è maggiore della somma dei puntaggi degli altri software. Una volta inseriti i software basterà avviarli e faranno tutto in pochi istanti. Sarà possibile far scontrare singolarmente i software ma, la cosa più interessante è appunto avviare un torneo generale nel quale ogni software si scontrerà con ogni altro.
Nel frattempo rilascio la versione provvisoria del programma dove potrete far combattere diversi software e magari prendere qualche idea. Potete anche giocare "in prima persona" contro uno dei software. Ovviamente sono solo dei programmi base, quelli interessanti dovrete farli voi : D Un programma "minimo" dovrebbe essere in grado di totalizzare più punti di questo tipo di programma stupido!
Le iscrizioni saranno aperte per molto tempo. Mi piacerebbe avere qualcosa come 15-20 partecipanti, ma questo lo vedremo in seguito.

Sarei molto grato a chiunque volesse segnalare questa idea nel proprio blog.

SCARICA -> dilemma del prigioniero v0.6 (sono pochi kb)


se qualcuno vuole controllare il codice può scaricare questo pacchetto (10 kb) (per visualizzare il codice c'è bisogno di vb6.0 e derivati, suppongo)

20 commenti:

Vaaal ha detto...

alcune informazioni:
1) siate il più precisi possibili nello specificare la vostra strategia. Ad esempio non ditemi "dopo un po' il programma sceglie collaborare", ma "dopo x mosse sceglie di collaborare". X può anche essere casuale, ma dovrete specificarlo;
2) potrei non accettare alcuni programmi troppo complessi: questo perché sono un dilettante della programmazione. Se non li accetto potrete ovviamente mandarne uno più semplice

IL LAICISTA ha detto...

Conosco, anche se non approfonditamente, il dilemma del prigioniero soprattutto per le sue applicazioni teoriche nella teoria dell'evoluzione.

Spero di avere il tempo per partecipare.

L'ho pubblicizzato da me. :)

gians ha detto...

interessante, per quanto posso, cercherò di metterlo in evidenza da me. un saluto, sono in arrivo dall'amico il laicista.

Knulp ha detto...

Sono un po incasinato in questi giorni. Quanto tempo mi dai?

Domande:
1) ho la possibilità di sapere con chi mi sto battendo? (potrei costruire uno storico del comportamento dei vari concorrenti)

2) collegato al punto 1: si possono proporre strategie adattive? (cattivo con gli stronzi, buono con i buoni)

3) posso mandarti direttamente il codice del mio programma? teoricamente dovrei essere un buon programmatore, anche se di VB non mi ricordo quasi niente! :)

Saluti!

Knulp ha detto...

ps: nel caso ti vada bene il punto 3) devi ovviamente darmi il codice e non solo l'.exe

Vaaal ha detto...

Grazie ad Il Laicista e Gians e Knulp per la segnalazione sui rispettivi blog : D

ecco le risposte a knulp:
1)puoi sapere il nome dei partecipanti, non le strategie che adottano. Queste verranno ovviamente rivelate alla fine del gioco. Conoscendo una certa strategia viene ovviamente la voglia di aggirarla, quindi meglio giocare "all'oscuro".
Per lo storico degli incontri: L'idea era appunto di implementare una lista per visualizzare i risultati dei vari "scontri", e non solo il risultato finale. In effetti la cosa più interessante è vedere il risultato contro specifici avversari.

2) Certo! Ovviamente non sapendo in anticipo il comportamento dell'avversario dovrai memorizzare il comportamento dell'avversario tenuto fino a quel momento e basarti su quello. Puoi proporre qualsiasi tipo di strategia che riesci a simulare con un elaboratore.

3) molto meglio! : D Ho inserito nel post anche il necessario per agire sul codice. Tieni conto che per il torneo dovrò cambiare tutto quindi non so quanto possa servirti il sorgente di QUESTA versione. Appena programmo il seguito lo posterò.

A proposito, non farti problemi di tempo, non vado di fretta (e poi avrò bisogno di tempo per programmare le cose, visto che è da più di due anni che non tocco vb) : D

Vaaal ha detto...

aggiornato il programma. Ora potete avere una idea di come si simuleranno le partite. Per ora l'unico software è Casuale, che fa mosse a caso : D
L'ultimo passo sarà creare l'interfaccia per il torneo, dopodiché basterà inserire le strategie (sperando che partecipi un po' di gente !!) e farlo partire.

Miki ha detto...

Peccato! con VB non posso proprio partecipare, anche se avrei tanto voluto.

In effetti programmare una ESS è davvero una sfida interessante, dipende sempre dal contesto.

Se lo rifarai in Python fammi uno squillo, e buon divertimento a tutti!

Vaaal ha detto...

Miki ma non c'è bisogno di utilizzare il VB! Puoi descrivere tutto a parole, poi lo tradurrò io in VB6. Magari se hai un po' di esperienza puoi utilizzare un linguaggio informatico generale, tipo IF, CICLI ecc., ma comunque non è essenziale.

Forza, che nessuno si scoraggi : O

Marco F ha detto...

La strategia migliore, per gli etologi, è questa:
http://en.wikipedia.org/wiki/Tit_for_tat
Se i due animali si conoscono e hanno la possibilità di rincontrarsi. Se è un one shot, meglio non collaborare.

Bleek ha detto...

Interessante questo dilemma del prigioniero...

Ti rispondo alla domanda fatta da Metil.
http://pensodiazepine.blogspot.com/

Bleek

Vaaal ha detto...

bene bleek, visiterò il tuo blog : D

Marco se vedi il mio programma potrai notare che avevo già inserito Tit for tat. Potrai vedere tu stesso come Tit for Tat non vince né contro Casuale né contro "Non Collabora mai". E' facile rendersi conto del perché, se si osservano le singole mosse.
Non ho ancora programmato la modalità torneo, quindi non ne sono sicuro, ma non darei per scontata la vittoria di tit for tat. Dipende dalla composizione della popolazione, quindi dagli altri partecipanti.

Marco F ha detto...

La condizione essenziale è la frequentazione degli individui per più di un incontro (meglio molti) come accade nella maggior parte delle popolazioni animali. È ovvio (direi matematico...) che tit for tat perde contro le altre mosse. Ma se la popolazione è costante e gli individui si conoscono tit for tat dovrebbe vincere sempre. Tieni presente che queste considerazioni valgono per animali relativamente sociali o molto sociali (scimmie per esempio, o delfini, ma anche vampiri - pipistrelli, non quelli di Twilight), che fra l'altro possono passare la "conoscenza" alle generazioni successive. Quali sono le condizioni del tuo torneo?

Vaaal ha detto...

come ho già specificato nel post gli gli individui (software che adottano una certa strategia), in numero costante, si affrontano per molte manche (avevo stabilito 300, ma possiamo anche fare 50'000, il mio programma lo consente).
Il problema nel dilemma del prigioniero è proprio che gli individui non si conoscono. Non sanno cosa farà un avversario prima che questo faccia la propria mossa. Possono inferire strategie, ma non possono essere sicuri di aver indovinato la strategia dell'avversario.
Un animale riuscirà abbastanza facilmente a individuare una strategia. E'invece più difficile (MOLTO più difficile) programmare un software che lo faccia. Per questo un torneo di questo tipo potrebbe essere interessante.

Marco F ha detto...

Scusa se insisto, ma una frase di questo tipo "Il punto fondamentale è conoscere lo stile dell'avversario; ad esempio, se notiamo che l'avversario non collabora MAI per noi sarebbe meglio non collaborare" mi ha fatto pensare che gli avversari (programmi) finirebbero per conoscersi dopo qualche mossa. O il problema non è tanto il "dilemma del prigioniero", ma il dilemma del "con chi l'ho fatto prima"? Non ti sto prendendo in giro, se insisto è perché non ho capito.

Vaaal ha detto...

certo che gli avversari si conosceranno dopo qualche mossa. Il punto è proprio questo. Bisogna ideare programmi in grado di ideare strategie abbastanza buone per fare punti contro avversari di volta in volta diversi gli avversari, il tutto applicato al gioco dilemma del prigioniero. Non vedo quale sia il problema.

ENTJ ha detto...

Se avessi letto questo post vent'anni fa, sarei stato risucchiato istantaneamente in un vortice competitivo di quelli che non dormi più la notte e giochi al dilemma del prigioniero anche coi sassi. Largo ai giovani e buon divertimento!

Riccardo ha detto...

Il modo migliore sarebbe fare un programma che risponde bene all'avversario più comune :D

Anonimo ha detto...

molto intiresno, grazie

Anonimo ha detto...

leggere l'intero blog, pretty good

post correlati