Ho provato a risolvere un problema sul quale vorrei avere un riscontro (magari soluzione analitica, @zeunig356), in particolare ProjectEuler n.232. L'ho risolto numericamente con il massimo livello di efficienza che sono riuscito a codificare, anche facendo uso dei registri della CPU al posto della RAM e del calcolo parallelo (mi sembrava esagerato dover sfruttare anche un algoritmo di calcolo distribuito fra più macchine).
Comunque sia, la consegna che si trova per esteso al link precedente, la possiamo riassumere così:
- giocatore1 lancia una moneta, se esce testa guadagna un punto, croce zero punti
- giocatore2, che lancia per secondo, sceglie prima un numero T e lancia la moneta T-volte; se tutte le T-volte esce testa, guadagna 2T-1 punti, altrimenti se non si verifica questa condizione, guadagna zero punti
- giocatore2 sceglie il numero T affinché siano massimizzate le sue probabilità di vincita (considerazione mia, a seconda dell'esito del lancio del giocatore1, il numero T cambia, in particolare T=1 se giocatore1 ha guadagnato 0 punti, T=2 se giocatore1 ha guadagnato 1 punto)
- il pareggio non da punti a nessuno
- i giocatori continuano a lanciare la moneta alternandosi in questo modo, quando uno dei due giocatori con l'ultimo lancio arriva o supera 100, la partita termina e lui vince
- calcolare la probabilità di vincita del giocatore2
Con il mio algoritmo, credo di averlo implementato correttamente, i risultati ottenuti con un milione di iterazioni (per ogni iterazione, media di circa 189 giocate prima che uno dei due vinca) convergono a circa:
Quindi con una probabilità di circa 6% (100-47-47) che ci sia pareggio. Il tempo di esecuzione è di circa 8 secondi, volevo un'accuratezza discreta senza comunque una richiesta computazionale esagerata.
Il risultato è corretto? Eventualmente, quale procedura analitica si potrebbe applicare come verifica? 🙂
Riporto il codice in C (scriverlo più ottimizzato ed efficiente di così farei fatica).
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
int main(){
srand(time(0));
register unsigned short t1,t2;
register unsigned long int tot_ass1,tot_ass2;
register unsigned int N=1000000;
register unsigned int k,cont=0;
register bool temp;
tot_ass1=0;
tot_ass2=0;
#pragma omp parallel
{
for(k=0;k<N;k++){
t1=0;t2=0;
while(1){
if(t1>=100||t2>=100){break;}else{
t1+=(bool)(rand()%(2));
//valore atteso t2... calcolo T
if(t1==0){
//t2+=randomx(); //T=1
t2+=(bool)(rand()%(2));
}else{ //T=2
//temp=randomx();
temp=(bool)(rand()%(2));
if(temp==1){
//temp=randomx();
temp=(bool)(rand()%(2));
if(temp==1){
t2+=2;
}
}
}
cont++;
tot_ass1+=t1;
tot_ass2+=t2;
}
}
}
}
printf("totale giocate=%d\nmedia giocate=%.2f\n",cont,1.0*cont/N);
printf("P1=%f|tot1=%ld\nP2=%f|tot2=%ld\n",1.0*tot_ass1/cont,tot_ass1,1.0*tot_ass2/cont,tot_ass2);
return 0;
}