0:00

Oh, finalmente, eccoci di nuovo qui. È un po' che non ci sentiamo, vero? Purtroppo,

0:06

in queste ultime settimane, anzi, diciamo più mesi, sono stato davvero sommerso dal lavoro

0:13

e non ho avuto modo di seguire questo progetto quanto avrei voluto e quanto avevo detto che

0:18

avrei fatto. Però oggi sono di nuovo qui e ricominciamo alla grande parlando di uno

0:23

di quegli argomenti principe di pensieri in codice, e cioè uno di quei tanti algoritmi

0:28

che utilizziamo ogni giorno ma magari nemmeno sappiamo di farlo. In questo episodio, infatti,

0:35

ritorniamo a parlare di come funzionano i nostri software ed in particolare di

0:41

algoritmo TIT4TAT e protocollo BitTorrent.

0:59

Iniziamo subito con un po' di storia che non fa mai male. Negli anni 50 del secolo scorso,

1:06

il matematico canadese Albert Tucker formulò un problema nell'ambito della teoria dei giochi,

1:13

il quale sarebbe presto divenuto famoso anche fra i non addetti ai lavori. Spesso definito

1:20

come paradosso, il dilemma del prigioniero, questo è il nome del gioco, consiste nel

1:25

prendere due ipotetici soggetti, due prigionieri appunto, e metterli di fronte ad una scelta che

1:32

determinerà i vantaggi che otterranno e le conseguenze che dovranno poi subire. Nello

1:37

specifico, nella sua formulazione più classica, il dilemma suona più o meno in questo modo. Due

1:43

malviventi vengono arrestati ed accusati di un crimine. I due poi vengono tenuti in celle

1:49

separate, non possono comunicare, ma ciascuno è a conoscenza del fatto che è stata arrestata

1:55

anche un'altra persona per il suddetto crimine. A questo punto gli investigatori iniziano con

2:01

degli interrogatori separati e danno ad entrambi la possibilità di confessare e accusare il complice

2:07

per avere in cambio maggiore clemenza. Ciò vuol dire in pratica che ciascuno può facilitare le

2:13

indagini scaricando la colpa del crimine sull'altra persona, con lo scopo di vedere ridotta la propria

2:20

pena. E siccome parliamo di un gioco matematico, a questo punto si vengono a configurare tre

2:25

possibili scenari ben distinti. Numero uno, entrambi i soggetti decidono di non confessare,

2:31

attenendosi ad una sorta di codice morale del criminale e non accusandosi l'un l'altro. In

2:37

questo scenario gli inquirenti non sono in grado di dimostrare la loro colpevolezza per il crimine

2:43

in questione ed entrambi vengono condannati ad un solo anno di reclusione per un crimine minore.

2:50

Nel secondo scenario invece uno dei due decide di tradire l'altro. In questo caso il primo,

2:57

cioè il traditore, se la cava senza scontare un giorno di galera, mentre il secondo ci rimarrà

3:03

per ben sei anni. E infine nel terzo scenario entrambi i criminali decidono di tradirsi l'un

3:09

l'altro. In pratica accusandosi vicendevolmente di crimini gravi, entrambi otterranno uno sconto

3:17

e verranno condannati a tre anni ciascuno. Ora puoi mettere pausa e fermarti a riflettere sul

3:23

problema o magari su cosa faresti tu o qualcuno che conosci, ma conti alla mano e visto che quelle

3:31

che ti ho dato sono le uniche informazioni disponibili per la scelta, dovrebbe apparire

3:37

subito chiaro che la migliore strategia da attuare per entrambi sia quella di tradirsi a vicenda e

3:44

beccarsi tre anni a testa. Certo c'è l'opzione in cui entrambi non collaborano, nella quale

3:50

prendono un anno di galera ciascuno, ma senza informazioni su come l'altro si potrebbe comportare

3:56

conviene maggiormente dare per scontato che questi cercherà di prendere la decisione migliore per se

4:02

stesso, puntando quindi a collaborare per ridurre o a zerare la pena. In tale condizione la cosa più

4:10

saggia che uno dei due possa fare è comunque collaborare con gli investigatori e tradire il

4:16

proprio compagno. Nel migliore dei casi l'altro non avrà collaborato e quindi il traditore se la

4:22

caverà senza pena. Nel peggiore anche l'altro avrà collaborato e il traditore prenderà comunque tre

4:29

anni invece di sei. Dunque questa decisione da prendere in tale contesto viene definita appunto

4:35

dilemma del prigioniero. Descritto in questo modo un problema del genere può apparire un bel

4:41

giochino da raccontare al bar davanti a una birra ma niente di più e invece il dilemma del prigioniero

4:48

rappresenta la logica di fondo di molti comportamenti umani. Un esempio che tutti noi conosciamo è ciò

4:55

che hanno fatto stati uniti ed unione sovietica durante la cosiddetta guerra fredda. Se ci pensi

5:02

la situazione è la stessa, le scelte non sono più se collaborare o meno con la polizia ma diventano

5:08

se competere o meno nella corsa agli armamenti nucleari e di conseguenza gli scenari diventano

5:15

uno. Entrambe le potenze decidono di non investire in armamenti e risparmiare così enormi risorse da

5:22

destinare ad usi ben più meritevoli. Due, una delle due potenze decide di armarsi e l'altra no, la

5:30

prima sprecherà tantissimi soldi in spese militari ma la seconda rischierà la cancellazione dalla

5:35

faccia della terra da parte dell'avversario. Tre, entrambe le potenze decidono di armarsi e

5:41

spendere miliardi di dollari per mantenere l'equilibrio strategico e guarda un po' come

5:47

ben sappiamo la scelta è stata quella dell'escalation degli armamenti, lo scenario numero 3, svantaggiosa

5:53

per entrambi ma la scelta migliore nell'ottica dell'impossibilità di sapere realmente cosa

6:01

avrebbe fatto l'avversario. Ma come dicevo prima questo è solo un esempio fra i tanti possibili,

6:07

schemi del genere si possono ritrovare continuamente nel comportamento di persone, comunità, aziende e

6:13

persino stati. In tali scenari la strategia più vantaggiosa viene definita equilibrio di Nash ed è

6:21

in pratica quella scelta in cui ciascun soggetto non ha modo di migliorare ulteriormente la propria

6:28

situazione facendo ricorso solo alle proprie forze. Tieni ben presente infatti che se è pur vero che

6:35

gli scenari possibili sono tre, in realtà le scelte possibili per ciascun prigioniero sono soltanto

6:43

due. Questo è un passaggio fondamentale da capire. I due soggetti dell'esperimento infatti possono

6:49

scegliere se confessare o negare, se collaborare o non collaborare, se investire in armamenti

6:55

nucleari o meno. Ma gli scenari risultano essere il frutto della somma delle scelte effettuate da

7:03

entrambi. Nessuno dei due può determinare la propria situazione in maniera totalmente autonoma

7:08

ma deve in qualche modo subire anche la scelta dell'avversario. Ok, tutto bellissimo. Spero di

7:21

non essere stato troppo prolisso e di essermi spiegato in maniera sufficientemente chiara,

7:26

ma sono certo che ora ti starai chiedendo perché tutto questo parlare di teoria dei giochi? Beh,

7:33

per capirlo dobbiamo fare un altro piccolo sforzo, un piccolo passo in più. Un passo che può sembrare

7:40

banale ma che ti assicuro rende tutto il nostro discorso molto più interessante. In pratica,

7:46

per come te l'ho descritto finora, il dilemma del prigioniero è un evento singolo. Due attori

7:52

vengono messi di fronte ad una scelta e per ciascuno le due opzioni disponibili risultano

7:57

essere più o meno vantaggiose in relazione alla scelta dell'altro. Questi due scelgono,

8:03

ottengono un qualche risultato e l'equilibrio di Nash ci dice qual è il risultato ottimale

8:10

ottenibile in autonomia. Fine. Ma se invece considerassimo una serie di dilemmi del prigioniero

8:17

che si susseguono nel tempo? Mi spiego. Se invece di un'unica occasione di scelta gli attori in

8:23

gioco avessero tante possibilità e potessero decidere in base non solo alle opzioni disponibili

8:30

in un singolo momento ma anche in base a delle scelte fatte in precedenza? Così non ti sembra

8:37

più interessante. Certo non possiamo pensare che ci sia una guerra fredda ogni settimana,

8:43

né spero per te che tu possa pensare di essere arrestato o arrestata ogni mese, ma quello che

8:49

possiamo invece fare è inventarci una nostra situazione, ad esempio un piccolo semplice gioco.

8:55

E proviamo a immaginarlo questo gioco. Ci sono due giocatori, questi due giocatori passeggiano

9:02

seguendo percorsi casuali in un parco relativamente piccolo, quindi si incontrano con una certa

9:08

frequenza. Quando le loro strade si incontrano ciascuno dei due ha due possibilità. Può salutare

9:17

l'avversario oppure tirargli un bello schiaffo. Salutandosi entrambi i due giocatori totalizzano

9:23

due punti ciascuno, scenario 1. Se invece uno saluta e l'altro schiaffeggia allora l'equilibrio

9:30

viene meno e chi ha schiaffeggiato guadagna tre punti mentre chi ha salutato ed ha preso la sberla

9:37

non fa punti, scenario 2. Infine prendendosi a schiaffi entrambi i due totalizzano mezzo punto

9:45

ciascuno, scenario 3. È chiaramente una situazione simile a quelle precedenti e l'unica differenza sta

9:51

nel fatto che si ripete nel tempo permettendo ai giocatori di effettuare più scelte in sequenza e

9:58

di cumulare i punti relativi. Come starai già immaginando ora le scelte diventano molto più

10:05

interessanti. Finché i due scelgono sempre di salutarsi mantengono un buon punteggio globale ma

10:11

per nessuno dei due si tratta del punteggio ottimale. Al primo incontro infatti avranno due

10:17

punti a testa poi quattro poi sei dopo cinque saluti siamo a dieci punti ciascuno cioè 20

10:24

punti globali. Però ad un certo punto uno dei due potrebbe pensare che mollare schiaffoni sia

10:31

una scelta migliore. D'altronde se l'altro fosse un pacifista e continuasse sempre a salutare la

10:38

situazione sarebbe più o meno questa. Primo incontro pacifista 0 violento 3 secondo incontro

10:45

pacifista sempre 0 violento 6. Dopo cinque incontri il violento avrebbe totalizzato ben

10:52

15 punti mentre il pacifista sarebbe a 0. La situazione del violento sarebbe molto migliore

10:59

di quella di prima e quella del pacifista molto peggiore. Ma se in fondo il pacifista non fosse

11:05

poi così tanto pacifista magari dopo il primo schiaffo potrebbe iniziare a menare anche lui le

11:11

mani e quindi avremmo primo incontro 3 a 0 per il violento ma poi schiaffi a non finire. Secondo

11:18

incontro 3 e mezzo a mezzo. Ti ricordo che picchiarsi entrambi fa totalizzare solo mezzo

11:24

punto ciascuno. Poi 4 a 1 poi 4 e mezzo a 1 e mezzo e così via fino ad un risultato dopo 5

11:31

incontri di 5 a 2. Certo quello che ha iniziato a picchiare per primo avrebbe un punteggio più

11:37

alto dell'altro giocatore ma comunque un punteggio molto più basso di quelli totalizzati con le

11:44

strategie precedenti. In definitiva la strategia collaborativa cioè quella di salutarsi sarebbe

11:50

la scelta globalmente più vantaggiosa quindi quella che darebbe il maggior numero di punti

11:57

ad entrambi. E quindi? Già capito dove voglio arrivare? Ora la situazione non è più semplice

12:04

come lo era con il dilemma del prigioniero preso come evento singolo. Gli arrestati infatti avevano

12:09

come migliore opzione quella di accusarsi vicendevolmente perché senza avere altre

12:14

informazioni ciascuno sceglieva razionalmente la soluzione meno brutta per se stesso. Ma qui

12:21

nel nostro gioco del parco ci sono altre informazioni che sono quelle sul comportamento

12:28

passato dell'avversario. Come si è comportato durante l'incontro precedente e in quello prima

12:34

ancora? E se gli incontri fossero 10, 100 o 1000? Ecco che si crea lo spazio per immaginare una

12:41

strategia di comportamento più interessante e complessa e ovviamente noi da buoni informatici

12:48

sappiamo che il termine strategia spesso è sinonimo di algoritmo. Questo particolare

12:55

algoritmo prende il nome di tit for tat e alla fine non si tratta di niente di nuovo o rivoluzionario,

13:02

in italiano noi lo chiamiamo semplicemente occhio per occhio e consiste appunto nel rispondere con

13:08

lo stesso comportamento che si riceve da parte di un altro soggetto. In poche parole se l'altro si

13:15

comporta in modo cooperativo allora noi ci comporteremo in modo cooperativo a nostra volta,

13:20

se l'altro invece si comporta in modo egoistico allora anche noi ci comporteremo in modo simile,

13:26

almeno finché l'altro non mostri una maggiore disponibilità a migliorare il proprio atteggiamento.

13:32

Rapportato al nostro gioco di prima vuol dire che di base ogni giocatore inizia col salutare

13:39

l'altro quando lo incontra ma se in un qualsiasi momento riceve uno schiaffo allora dal turno

13:45

successivo restituirà a sua volta uno schiaffo. La strategia tit for tat è molto efficace in

13:51

molti contesti e questo poiché incoraggia i giocatori a comportarsi in modo cooperativo ed

13:57

ad evitare comportamenti egoistici che si approfittano degli altri senza contribuire a

14:04

propria volta. Guarda caso questo particolare algoritmo volto ad incoraggiare il comportamento

14:15

cooperativo in informatica è largamente utilizzato in particolare per applicazioni

14:21

basate su operazioni dirette fra i singoli soggetti come ad esempio nel caso di BitTorrent.

14:27

Ora sono sicuro che tutti abbiamo utilizzato BitTorrent almeno una volta nella vita ma è

14:32

sempre meglio fare un piccolo ripasso. BitTorrent è un protocollo di condivisione file peer-to-peer

14:39

detto P2P studiato per consentire agli utenti di condividere file di grandi dimensioni in modo

14:46

efficace. Per fare ciò in questo protocollo i file vengono suddivisi in piccoli pacchetti

14:52

dati che possono essere scaricati e condivisi indipendentemente l'uno dall'altro. Ciò significa

14:58

che ogni utente può scaricare una parte del file e iniziare immediatamente a ricondividerla anche se

15:05

il download del file intero non è ancora stato completato ed inoltre è possibile ricevere diversi

15:11

pacchetti di dati da più fonti contemporaneamente e in questo modo velocizzarne il download. Quando

15:18

un utente vuole scaricare un file sfruttando BitTorrent utilizza il proprio client per

15:23

connettersi ad un sistema chiamato tracker che è adibito a gestire la rete di condivisione dei

15:30

file. Il tracker fornisce al client l'elenco di altri client che condividono il file richiesto e

15:37

di conseguenza questo può iniziare a scaricare uno o più pacchetti di dati da più sorgenti. Ciascun

15:45

client BitTorrent oltre ad effettuare il download dei file richiesti lavora contemporaneamente per

15:50

ridistribuire i pacchetti di dati di cui è già in possesso quindi di fatto ciascun utente mentre

15:57

scarica un file ricarica anche automaticamente le porzioni di tale file di cui già dispone e

16:04

questo meccanismo di ridistribuzione è proprio alla base del funzionamento del protocollo

16:09

BitTorrent ed è il motivo principale della sua estrema efficienza e della sua grande diffusione

16:15

ed è dunque fondamentale che il comportamento di tutti i client mantenga un certo livello di

16:21

correttezza e cooperazione senza il quale tutto il sistema verrebbe meno. Se infatti ci fossero in

16:28

giro applicazioni implementate per mantenere un atteggiamento parassitario scaricando solamente

16:34

da chiunque si trovi a tiro senza mai ricondividere quanto ottenuto allora la velocità ed efficienza

16:41

del protocollo ne verrebbero danneggiate a scapito degli utilizzatori onesti. Come avrai

16:52

quindi certamente già capito l'algoritmo TIT4TAT risulta essere una base di partenza molto adatta

16:59

in questo tipo di situazioni per determinare come un client BitTorrent dovrebbe comportarsi

17:05

nei confronti degli altri. L'idea alla base è abbastanza semplice ogni client dovrebbe essere

17:11

disposto a condividere file con gli altri ma solo se anche questi sono disposti a farlo a loro volta.

17:17

Proprio come accadeva per la strategia ottimale dei nostri giocatori nel parco finché ciascuno

17:23

dei due manteneva un rapporto cordiale salutando e non aggredendo l'altro anche l'altro continuava

17:30

ad essere cooperativo. Appena uno dei due veniva meno al tacito patto di collaborazione anche

17:36

l'altro reagiva nello stesso modo. In altre parole nel protocollo BitTorrent un client risponde con

17:44

lo stesso comportamento che riceve dagli altri client se l'altro è disposto a condividere file

17:50

allora lui è disposto a fare lo stesso se invece l'altro non è disposto a condividere allora lui

17:57

risponde non condividendo a sua volta con quel client. Infine come sarai certamente intuendo

18:04

c'è anche da considerare che la strategia tit for tat può essere anche soggetta ad un fenomeno

18:09

chiamato punizioni a catena nel quale i soggetti decidono di non cooperare a oltranza. Se ad

18:17

esempio due client iniziano a rifiutare la condivisione l'un l'altro si rischia di entrare

18:22

in un circolo che può portare al risultato peggiore per entrambi. Quindi per tenere conto di

18:29

ciò nell'implementazione reale all'interno del protocollo BitTorrent la versione dell'algoritmo

18:35

tit for tat utilizzata è ovviamente un po' più avanzata della sua formulazione base. Esistono

18:42

infatti degli accorgimenti che puntano a mantenere un minimo di apertura verso qualsiasi nodo e questo

18:49

proprio per evitare situazioni di stallo in cui dei nodi si ritrovino ignorati da tutti gli altri.

18:56

Per fare ciò innanzitutto ogni client prova a riaprire la condivisione con cadenza periodica

19:02

alla ricerca di una reazione positiva anche dai nodi più avari diciamo così. In secondo luogo

19:09

poi il nodo battezzato come parassita non viene effettivamente disconnesso ma gli viene lasciato

19:16

l'accesso ad una connessione con un minimo di banda per dargli la possibilità di migliorare

19:22

il proprio upload e quindi riguadagnare uno status accettabile agli occhi degli altri. Infine due

19:29

nodi che sono in fase di scambio tendono a massimizzare i vantaggi reciproci cercando

19:34

l'uno nell'altro i pacchetti di cui hanno bisogno e per fare ciò estremizzano il concetto di

19:41

collaborazione tra i client al punto da rendere possibile per uno condividere verso l'altro anche

19:49

più di quanto l'altro possa ricambiare. Insomma grazie all'implementazione di questa strategia

19:55

TIT4TAT avanzata il protocollo BitTorrent è in grado di mantenere un proprio equilibrio e di

20:02

fornire un servizio funzionale ed efficiente. Tra i vari nodi della rete presi a due a due si

20:09

raggiunge quindi quella che viene definita efficienza di pareto cioè uno stato di equilibrio

20:16

in cui non ci sono ulteriori opportunità di scambio che potrebbero portare ad una situazione

20:22

migliore di quella corrente. Bene grazie per aver ascoltato questo episodio di pensieri in codice

20:33

io come al solito spero sia stato di tuo interesse e spero anche che ti sia mancato almeno quanto è

20:38

mancato a me. Un piccolo ringraziamento speciale va a Edoardo e Carlo che hanno continuato a

20:44

credere nel progetto nonostante lo stop improvviso di oltre tre mesi e che me l'hanno

20:50

dimostrato con le loro donazioni mensili. Ti ricordo che sul sito pensieriincodice.it trovi

20:56

tutti i link del progetto gruppo telegram donazioni affiliazioni eccetera e mi raccomando fai ascoltare

21:03

questo episodio a qualcun altro un amico un parente un conoscente un estraneo che se ognuno di noi

21:09

porta anche un ascoltatore in più tra una settimana siamo già il doppio. In ultimo ti

21:14

do appuntamento al prossimo episodio e non dimenticare mai che un informatico risolve

21:20

problemi a volte anche usando il computer