Semi-genetic "survival of the fittest" algorithm for getting the best campaign strategy.

dilemma.c

// tests the President's Dilemma through genetic algorithm
// Princeton Ferro - Jun 9, 2014
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define FUND 100
#define N 1000 // members per generation

#define DEBUG 0

typedef struct {
	int ia; // Iowa (6 electoral votes)
	int co; // Colorado (9 electoral votes)
	int va; // Virginia (13 electoral votes)
	int pa; // Pennsylvania (20 electoral votes)
	unsigned long wins; // number of won rounds
} strategy; // how much of $1M should go to each state

void print_strategy(strategy s) {
	printf("{ .ia = %d, .co = %d, .va = %d, .pa = %d }\n",
		s.ia, s.co, s.va, s.pa);
}

void initialize(strategy *strats, int start) {
	int s;
	for (s=start; s<N; s++) {
		int total = FUND;
		strats[s].ia = rand()%(total+1);
		total -= strats[s].ia;
		strats[s].co = rand()%(total+1);
		total -= strats[s].co;
		strats[s].va = rand()%(total+1);
		total -= strats[s].va;
		strats[s].pa = total;
		strats[s].wins = 0L;
	}
}

// compare strategies[s] to all other strategies
// increase win count for each win
void compare(strategy *strategies, int s) {
	int i;
	for (i=0; i<N; i++) {
		if (i == s) continue;
		short ia = strategies[s].ia >= strategies[i].ia,
		      co = strategies[s].co >= strategies[i].co,
		      va = strategies[s].va >= strategies[i].va,
		      pa = strategies[s].pa >= strategies[i].pa;
		int sum_s = ia*6 + co*9 + va*13 + pa*20;
		if (sum_s >= 25)
			strategies[s].wins++;
	}
}

int main(int argc, char **argv) {
	if (argc == 1) {
		fprintf(stderr, "You must enter number of iterations.\n");
		return 1;
	}
	srand(time(NULL));
	strategy strats[N];
	
	time_t before;
	time(&before);
	int generations = atoi(argv[1]);
	int s, g, b = 0; // b = best
	for (g=0; g<generations; g++) {
		initialize(strats, (g==0) ? 0 : 1);
		for (s=0; s<N; s++) {
			compare(strats, s); // compare strategy s to all
			if (DEBUG)
				printf("Strategy %d has %lu wins.\n",
					s, strats[s].wins);
		}

		// get best
		for (s=1; s<N; s++)
			if (strats[s].wins > strats[b].wins)
				b = s;

		if (DEBUG) {
			printf("Best strategy: ");
			print_strategy(strats[b]);
		}
		
		// copy best to first
		strats[0].ia = strats[b].ia;
		strats[0].co = strats[b].co;
		strats[0].va = strats[b].va;
		strats[0].pa = strats[b].pa;
		strats[0].wins = 0L;
		
		b = 0;
	}

	printf("Absolute best strategy: ");
	print_strategy(strats[0]);
	printf("Time: %f seconds\n", difftime(time(NULL), before));

	return 0;
}