Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa...

29
Monte-Carlo per il Monopoli

Transcript of Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa...

Page 1: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

Monte-Carlo per il Monopoli

Page 2: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Monterosa

GranSasso

Staz.Sud

Impr.TassaVicoloStrettoProb

Vesuvio

Vicolo Corto

Raff.

Verdi

Staz.Ovest

Prob.

Ate-neo

Soc.Elettrica

Dante

Acca-demia

Univ

Traia-no

Costantino

Staz.Nord

Acq.Pot.

Magel-lano

ImprGiulioCesare

MarcoPolo

Colombo

Giardini

Staz.Est

Tassa

Impero

Prob

Vittoria

Roma

Augusto

Impr.

ViaPrig.

Vaiin

prigione

Parcheggio

Page 3: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Probabilità

• 16 tra cui:– vai in carcere– vai al Via– vai al Vicolo Corto

Page 4: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Imprevisti

• 16 tra cui:– vai in Carcere– vai al Via– vai a Via Accademia– vai a Largo Colombo– vai a Stazione Nord– vai a Parco della Vittoria – fai 3 passi indietro

Page 5: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Turno di gioco

• Ad ogni turno ogni giocatore lancia i dadi, e a seconda del numero ottenuto muove il segnalino di altrettanti spazi sulla tavola.

• A seconda della casella su cui il segnalino si ferma, al giocatore si presentano le possibilità di diventare il proprietario del lotto, pagare l’affitto o le tasse, pescare dal mazzo di probabilità o imprevisti, o finire in prigione.

Page 6: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Tiri doppi

• Quando un giocatore, gettando i dadi, fa con entrambi dadi lo stesso numero, procede col suo segnalino come di solito e sopporta le conseguenze buone o cattive inerenti al terreno su cui è arrivato, ma deve tirare una seconda volta e spostare di nuovo il segnalino in rapporto al numero fatto.

• Tirando tre volte di seguito un numero doppio andrà in prigione.

Page 7: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Prigione

• Pagamento

• Tirando dadi doppi

• Utilizzando “uscite gratis di prigione”

• Condonato al terzo turno in prigione

Page 8: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Un primo modello: assunzioni

• Consideriamo come unica casella “speciale” la 31: Vai in prigione

• Se si finisce sulla casella “Vai in prigione” con un tiro doppio non si tira immediatamente per uscire di prigione

• Si simula un solo giocatore• Ci si disinteressa di come si esce dalla

prigione

Page 9: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il tabellone

• Nel tabellone ci sono 40 caselle• Alcune caselle speciali richiedono azioni

particolari (ad es Vai in prigione)

• Rappresentiamo il tabellone con un vettore di 40 elementi, in cui memorizzeremo il numero di volte che un giocatore passa in ogni casella

Page 10: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il tabellone

>> tabellone=zeros(1,40)

• La funzione zeros(M,N) crea una matrice MxN di zeri. In tal modo inizializzamo il vettore delle visite delle caselle a zero.

• Es: il numero di volte che si passe sulla casella 7 (Bastion Gran Sasso) è

>> tabellone(6)

che sarà inizialmente 0, mentre alla fine avrà un valore on nullo

Page 11: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il tabellone

>> azioni=[1, 2, 3, 2, 4, …

• Per rappresentare le diverse tipologie di caselle creiamo un vettore 1x40 azioni che contiene il codice che rappresenta il tipo della casella corrispondente:

– 1: Via– 2: Terreno– 3: Tassa– 4: Probabilità– 5: Imprevisti– 6: Vai in Prigione

• Es: Data la posizione 15 sul tabellone

>> tabellone(15)

dà il numero di volte che quella casella è stata visitata, mentre

>> azioni(15)

indica il tipo di casella. azioni(15) vale 2, che indica essere un terreno (Piazza Università)

Page 12: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il lancio di dadi

• Il lancio di un dado può essere modellato attraverso la funzione rand().La funzione restituisce un valore (reale) pseudo-casuale estratto dall’intervallo [0,1]

0 1

Page 13: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il lancio di dadi

• Per ottenere da un intervallo reale i valori interi che ci servono, dividiamo l’intervallo in regioni, ed ogni numero appartenente ad una determinata regione indicherà la regione

0 1

Regione 1

Regione 2

Regione 3

Regione 4

Regione 5

Regione 6

Page 14: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il lancio di dadi

• Se dividiamo l’intervallo in maniera equispaziata (tutte le regioni hanno la stessa dimensione), anche le probabilità di finire dentro ad una regione sono uguali

0 6

1 2 3 4 5

Regione corrispondente ad estrarre 1

Regione corrispondente ad estrarre 6

Page 15: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il lancio di dadi

>> dado= ceil(6*rand(1));

0 6

1 2 3 4 5

Regione corrispondente ad estrarre 1

Regione corrispondente ad estrarre 6

Page 16: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Modellare il lancio di dadi

• Dal momento che è necessario lanciare 2 dadi alla volta, estraiamo 2 valori, e li inseriamo in un vettore 1x2 lancio:

>> lancio=ceil( 6 * rand(1,2) );

Page 17: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Turno di lancio di un giocatore

Ad ogni turno un giocatore tira due dadi, si sposta del numero indicato dai dadi, e poi, nel caso abbia fatto doppio, tira ancora fino ad un massimo di tre volte di fila.

Page 18: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Turno di lancio di un giocatore

• Creiamo una funzione che simuli questo turno di lancio, restituendo un vettore 1x4 con la somma dei due lanci per ogni tiro (eventuale).

• I valori nulli nel vettore indicano che non sono stati effettuati quei lanci

• Nel caso in cui ci siano valori non nulli in tutti gli elementi del vettore significa che si è tirato 3 volte doppio

Page 19: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Turno di lancio di un giocatore

function passi=Turno() passi=zeros(1,4); nlanci=1; exit_cond=1;while(exit_cond) lancio=ceil(6*rand(1,2)); passi(nlanci)=sum(lancio); nlanci=nlanci+1; exit_cond=(diff(lancio)==0) & nlanci<=4;end;

Page 20: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Turno di lancio di un giocatore

• Si inizializza il vettore 1x4 passi a 0, e il numero di lanci nlanci a 1

• Si impone la condizione di terminazione del ciclo while exit_cond a 1 in modo che almeno alla prima iterazione si esegua il ciclo

• Si calcola il lancio dei due dadi e si memorizza la somma dei dadi nella variabile passi, nella posizione corrispondete al numero del lancio effettuato

• Si incrementa il numero di lanci nlanci di 1• Si controlla di non aver superato il numero massimo di

lanci e di non aver fatto doppio: se una delle due condizioni è verificata exit_cond diventa 0 ed il ciclo si interrompe

Page 21: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Movimento di un giocatore

• Una volta che si hanno i lanci effettuati da un giocatore, bisogna spostare la sua posizione, un lancio alla volta, aggiornando il numero di viste delle caselle in cui si ferma al termine di ogni movimento.

• Bisogna controllare anche:– Se capita nella casella “Vai in prigione” il turno termina e la

posizione del giocatore diventa la prigione (casella 10)

– Se ci sono tre lanci doppi (quattro valori non nulli nel vettore passi)il giocatore deve andare in prigione

Page 22: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Movimento di un giocatore (1)

function [pos_out,tabellone]=Muovi(pos_in,passi,tabellone,azioni) nlanci=1;while(passi(nlanci)>0 & nlanci<=3) pos_fin=pos_in+passi(nlanci); pos_fin=mod(pos_fin-1,40)+1; if(pos_fin==31), pos_out=11; tabellone(pos_out)=tabellone(pos_out)+1; return; else tabellone(pos_fin)=tabellone(pos_fin)+1; end; pos_in=pos_fin; nlanci=nlanci+1;end;

. . . . . . .

Page 23: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Movimento di un giocatore (1)

• Si inizializza il numero di lanci nlanci a 1, dal momento che sarà sempre presente almeno il primo valore nel vettore passi.

• Si controlla che ci sia un lancio valido (passi(nlanci)>0), e che non si sia superato il numero di lanci consentito.

• Si sposta il giocatore dalla posizione iniziale pos_in di tante caselle quanto è il lancio dei dadi passi(nlanci)e si fa in modo che se si supera l’ultima casella (caselle 40), si ritorni all’inizio

• Se la casella in cui il giocatore si è mosso pos_fin è la casella “Vai in prigione”, il movimento termina con la posizione finale pos_out in prigione (casella 11), ed il corrispondente valore del numero di visite di tabellone(11) incrementato 1.

• Altrimenti si incrementa il numero delle visite della posizione corrispondente tabellone(pos_fin), si aggiorna la posizione iniziale in modo che l’eventuale tiro ulteriore parta dall’ultima posizione, e si incrementa il numero di lanci

Page 24: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Movimento di un giocatore (2)

• Bisogna ancora controllare se però il giocatore dopo gli eventuali primi due movimenti abbia fatto ancora doppio.

• Nel qual caso bisogna imporre come casella d’arrivo del turno la prigione, e togliere l’incremento dell’ultima casella visitata (corrispondente al movimento effettuato con il terzo lancio doppio)

Page 25: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Movimento di un giocatore (2)

function [pos_out,tabellone]=Muovi(pos_in,passi,tabellone,azioni) nlanci=1;while(passi(nlanci)>0 & nlanci<=3) pos_fin=pos_in+passi(nlanci); pos_fin=mod(pos_fin-1,40)+1; if(pos_fin==31), pos_out=11; tabellone(pos_out)=tabellone(pos_out)+1; return; else tabellone(pos_fin)=tabellone(pos_fin)+1; end; pos_in=pos_fin; nlanci=nlanci+1;end;

if(all(passi)>0) pos_out=11; tabellone(pos_out)=tabellone(pos_out)+1; tabellone(pos_fin)=tabellone(pos_fin)+1;else pos_out=pos_fin;end;

Page 26: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Simulare qualche turno

• Dopo aver scritto le funzioni che gestiscono il lancio dei dadi ed il movimento, possiamo simulare qualche turno di un giocatore

Page 27: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Simulare qualche turno

tabellone=zeros(1,40);azioni=zeros(1,40);azioni=[1,2,3,2,4,2,2,5,2,2,…

0,2,2,2,2,2,2,3,2,2,…0,2,5,2,2,2,2,2,2,2,…6,2,2,3,2,2,5,2,4,2];

Nturni=1000;pos_in=1; for ct=1:Nturni,

passi=Turno(); [pos_fin,tabellone]=Muovi(pos_in,passi,tabellone,azioni); pos_in=pos_fin;end;

Page 28: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Simulare qualche turno

• Qui si vogliono simulare Nturni di un giocatore, per vedere quante volte ogni casella è visitata nel corso di questi turni

• Si imposta un cicle for, ad ogni iterazione un giocatore tira i dadi e si muove, ed il numero di visite delle caselle in tabellone viene aggiornato

Page 29: Monte-Carlo per il Monopoli. DEI - Univ. Padova (Italia) Monte rosa Gran Sasso Staz. Sud Impr.Tassa Vicolo StrettoProb Vesu vio Vicolo Corto Raff. Verdi.

DEI - Univ. Padova (Italia)

Risultati

Prigione

Staz. Ovest

Probabilità

CorsoMagellano

VialeCostantino

Vai inPrigione