/******************************************************************/ /* */ /* Program: yahtzee.c */ /* */ /* Description: */ /* */ /* Suppose you throw 5 dice. */ /* This program calculates the probability to get Yahtzee */ /* (i.e. 5 equal dice) in "throw" throws by a Monte Carlo */ /* simulation. After each throw it is supposed that you keep */ /* the dice with the number (eyes) that is most frequent. */ /* */ /* The number of dice "dice" can be changed in the program code. */ /* The number of eyes "eyes" on the dice can be changed in */ /* the program code. */ /* */ /* Parameters: */ /* */ /* throw = Maximum numbers of throws (3). */ /* sim = Starting number of simulations (1000). */ /* inc = Number of times sim is increased by a factor 10 (3). */ /* seed = Integer random seed (3). */ /* */ /* Try the values in brackets ! */ /* */ /* >yatzy 3 1000 3 3 */ /* */ /* */ /* Algorithm and program by: Stefan Spaennare, Lund, Sweden */ /* */ /* E-mail: stefan@spaennare.se */ /* */ /* First version: October 1992 */ /* Latest update: 2003-02-19 */ /* */ /* *****/ /* Benchmark */ /* ========= */ /* */ /* The test was run on a Intel Celeron (Tualatin core) computer */ /* with 256 kbyte cache memory and 512 Mbyte primary memory. */ /* The operating system was Red Hat 7.2 Linux. Compiler tested */ /* was GNU GCC 2.96 (gcc) for Linux. Under Windows XP the compiler */ /* GNU DJGPP 3.0.4 (gcc, djgpp) for DOS was used. */ /* */ /* Numbers tested: */ /* --------------- */ /* */ /* throw=3, inc=0, seed=3 */ /* */ /* na = sim = 1000000 = 10^6 */ /* */ /* nb = sim = 10000000 = 10*10^6 */ /* */ /* Results: */ /* -------- */ /* */ /* n: Computer: CPU-time (s): Compiler options: */ /* ================================================================ */ /* */ /* na Celeron 1200 MHz 1.77 gcc -O3 */ /* na Celeron 1200 MHz 1.65 gcc -O2 (djgpp) */ /* */ /* nb Celeron 1200 MHz 17.62 gcc -O3 */ /* nb Celeron 1200 MHz 16.87 gcc -O2 (djgpp) */ /* */ /* */ /* *****/ /* */ /* Old benchmark */ /* ============= */ /* */ /* throw=3, sim=1000000, inc=0, seed=3 */ /* */ /* dice=5, eyes=6, (in the code) */ /* */ /* Computer: CPU-time (s): Compilation: */ /* */ /* Pentium 180 MHz 19.78 gcc -O3 */ /* */ /******************************************************************/ /********************************************************************************/ /* */ /* Notice */ /* ====== */ /* */ /* I make no warranties that this program is (1) free of errors, (2) consistent */ /* with any standard merchantability, or (3) meeting the requirements of a */ /* particular application. This software shall not, partly or as a whole, */ /* participate in a process, whose outcome can result in injury to a person or */ /* loss of property. It is solely designed for analytical work. Permission to */ /* use, copy and distribute is hereby granted without fee, providing that the */ /* header above including this notice appears in all copies. */ /* */ /* Stefan Spaennare */ /* */ /********************************************************************************/ #include #include #include #include #include double timetic=(double)(CLOCKS_PER_SEC); #define IM1 2147483563 #define IM2 2147483399 #define AM (1.0/IM1) #define IMM1 (IM1-1) #define IA1 40014 #define IA2 40692 #define IQ1 53668 #define IQ2 52774 #define IR1 12211 #define IR2 3791 #define NTAB 32 #define NDIV (1+IMM1/NTAB) #define EPS 1.2e-7 #define RNMX (1.0-EPS) double ran2(idum) long *idum; { int j; long k; static long idum2=123456789; static long iy=0; static long iv[NTAB]; double temp; if (*idum <= 0) { if (-(*idum) < 1) { *idum=1; } else { *idum=-(*idum); } /* if */ idum2=(*idum); for (j=NTAB+7; j>=0; j--) { k=(*idum)/IQ1; *idum=IA1*(*idum-k*IQ1)-k*IR1; if (*idum < 0) { *idum += IM1; } /* if */ if (j < NTAB) { iv[j]=*idum; } /* if */ } /* for j */ iy=iv[0]; } /* if */ k=(*idum)/IQ1; *idum=IA1*(*idum-k*IQ1)-k*IR1; if (*idum < 0) { *idum += IM1; } /* if */ k=idum2/IQ2; idum2=IA2*(idum2-k*IQ2)-k*IR2; if (idum2 < 0) { idum2 += IM2; } /* if */ j=iy/NDIV; iy=iv[j]-idum2; iv[j] = *idum; if (iy < 1) { iy += IMM1; } /* if */ temp=AM*(double)(iy); if (temp > RNMX) { return(RNMX); } else { return(temp); } /* if */ } /* ran2 */ int main(argc,argv) int argc; char *argv[]; { int dice,eyes; int n,k2,k1,s,s2,s3,z,i,j,j2; int m,m2,r,r2,i2,v2,k0,r3,seed; long idum; double eyesd; int *v; int *k; clock_t time1,timediff; if (argc != 5) { printf("Usage: %s throwi simi inci seedi\n",argv[0]); exit(0); } /* if */ r2=atoi(argv[1]); s=atoi(argv[2]); s2=atoi(argv[3]); seed=atoi(argv[4]); dice=5; /* Number of dice */ eyes=6; /* Maximum number of eyes (sides) on the dice */ v=(int *)calloc(eyes+1,sizeof(int)); k=(int *)calloc(r2+1,sizeof(int)); eyesd=(double)(eyes); idum=-abs(seed)-1; printf("\n"); printf("Yahtzee\n"); printf("=======\n"); printf("\n"); for (i=1; i<=r2; i++) { k[i]=0; } /* for i */ s3=1; for (i=1; i<=s2; i++) { s3=s3*10; } /* for i */ n=0; z=s; time1=clock(); for (j2=1; j2<=s3; j2++) { for (j=1; j<=s; j++) { m=0; i2=0; r=0; do { for (i=1; i<=eyes; i++) { if (i != i2) { v[i]=0; } /* if */ } /* for i */ m2=dice-m; for (i=1; i<=m2; i++) { k2=(int)(eyesd*ran2(&idum))+1; v[k2]++; } /* for i */ m=v[1]; i2=1; for (i=2; i<=eyes; i++) { v2=v[i]; if (v2 > m) { m=v2; i2=i; } /* if */ } /* for i */ r++; if (m == dice) { k[r]++; } /* if */ } while ((m < dice) && (r < r2)); } /* for j */ n=n+s; if (n == z) { z=z*10; timediff=clock()-time1; printf("Sim: %10d ; ",n); printf("CPU-time: %10.2f s\n",(double)(timediff)/timetic); printf("\n"); printf(" T N(t=T) P(t=T) N(t<=T) P(t<=T)"); printf(" 1/P(t=T) 1/P(t<=T)\n"); i=r2; while (k[i] == 0 ) { i--; } /* while */ r3=i; k0=0; for (i=1; i<=r3; i++) { k1=k[i]; k0=k0+k1; printf("%4d %9d %12.8f %9d %12.8f",i,k1,(double)(k1)/(double)(n), k0,(double)(k0)/(double)(n)); if (k1 > 0) { printf("%18.8f %18.8f\n",(double)(n)/(double)(k1), (double)(n)/(double)(k0)); } else { printf("\n"); } /* if */ } /* for i */ printf("\n\n"); } /* if */ } /* for j2 */ } /* End */