Golden monkey simulation

golden_monkey_monte_carlo.c

/*
 * golden_monkey_monte_carlo.c
 *
 * Calculate draws to get the Golden Monkey assuming no cards added to deck 
 * (e.g., via Entomb, Gang Up, etc)
 *
 * On my machine, it seemed to converge to 26.81, or 27.
 *
 * Also ignores coining out/innervating Elise on turns prior to 4
 * 
 * This code is GPL-licensed. <http://www.gnu.org/licenses/gpl-3.0.en.html>
 */

#include <stdio.h>
#include <sys/time.h>
#include <stdlib.h>
#include <gsl/gsl_rng.h>

#define DECK_SIZE 30
#define ELISE_COST 4

gsl_rng* rng;

unsigned long int random_seed()
{
    struct timeval tv;
    
    int failure = gettimeofday(&tv,0);

    if (failure) {
	fprintf(stderr, "Couldn't get time of day, bailing out\n");
	exit(EXIT_FAILURE);
    }
    
    return tv.tv_sec + tv.tv_usec;
}

unsigned long random_deck_index(int remaining_cards)
{
    return gsl_rng_uniform_int(rng, remaining_cards) + 1;
}

int draws_to_golden_monkey()
{
    int remaining_cards = DECK_SIZE;
    
    // draw elise
    unsigned long elise_draws = random_deck_index(remaining_cards);

    // assume Elise not played before turn 4
    if (elise_draws < ELISE_COST) {
	elise_draws = ELISE_COST;
    }
    
    remaining_cards -= elise_draws;

    if (remaining_cards == 0) {
	return DECK_SIZE;
    }
    
    // shuffle map in
    remaining_cards++;

    // draw the map
    unsigned long map_draws = random_deck_index(remaining_cards);

    remaining_cards -= map_draws;

    if (remaining_cards == 0) {
	return DECK_SIZE;
    }

    unsigned long monkey_draws = random_deck_index(remaining_cards);

    remaining_cards -= monkey_draws;

    return DECK_SIZE - remaining_cards;
}

int main(int argc, char **argv)
{
    rng = gsl_rng_alloc(gsl_rng_mt19937);
    long seed = random_seed();

    printf("Seeding with seed = %ld\n", seed);
    
    // seed with current time
    gsl_rng_set(rng, (unsigned long) seed);

    if(argc < 2) {
	fprintf(stderr, "Must provide # of trials as parameter\n");
	exit(EXIT_FAILURE);
    }
    
    long trials = atol(argv[1]);

    printf("Trials = %ld\n", trials);

    double average = 0.0;

    long counts[DECK_SIZE];
    long i;
    
    for(i = 0; i < DECK_SIZE; i++) {
	counts[i] = 0;
    }
    
    for(i = 0; i < trials; i++) {
	int total_draws = draws_to_golden_monkey();

	if (total_draws < 1 || total_draws > DECK_SIZE) {
	    fprintf(stderr, "total_draws = %d, out of range\n", total_draws);
	    gsl_rng_free(rng);
	    exit(EXIT_FAILURE);
	}

	counts[total_draws-1]++;
	
	average = (average*i + (double)total_draws)/(i+1);
    }

    printf("Average = %2.2f\n", average);

    for(i = 0; i < DECK_SIZE; i++) {
	printf("%ld\t%ld\n", i+1, counts[i]);
    }
    
    gsl_rng_free(rng);
    
    exit(EXIT_SUCCESS);
}

Makefile

all: golden_monkey_monte_carlo.c
	gcc -m64 -O3 -std=c99 -Wall -Werror -Wextra -Wshadow -pedantic \
		-Wextra -Wunknown-pragmas -Wfloat-equal -Wcast-qual \
		-o gmmc golden_monkey_monte_carlo.c \
		-lgsl -lgslcblas -lm

Note that this does not correspond to turns in the game as different cards in the deck can influence card draw.

This gives an answer of about 26.81 on my machine.