/* 
 * ALitM (Artificial Life in the Marketplace)
 *
 * Churns out Prisoner's Dilemma strategies via
 * a genetic algorithm.
 *
 * USAGE:
 *   alitm
 *
 * OUTPUT:
 *
 * On my Pentium 133, I let this run a few hours
 * before I see any output.  When there finally 
 * is some, it's cryptic.
 *
 * Here are two lines of typical output:
 *
 * tvtcdcctttttttttctctttctccttttttdtttdtttccvttttdtvcvcdtcctcttddt
 * dcctdtttttttctctttctccttttttdtttdtttcvvttttdtvcvcdtcctctdddttvtc
 *
 * How does one interpret this?  Well, let's see how the critters 
 * interpret it.
 *
 * Each line represents a critter's DNA/a strategy for the 
 * Prisoner's Dilemma. Each letter represents one round:
 *
 * t (Trade)      : I co-operate, he co-operates
 * v (Void)       : I defect,     he defects
 * c (Co-operate) : I co-operate, he defects
 * d (Defect)     : I defect,     he co-operates
 *
 *
 * Suppose a critter has been trading with another 
 * for three turns and their history looks like 
 * 
 * d  At first, I defected and that fool co-operated.
 * t  Then, we both co-operated.
 * c  Most recently, I co-operated, but that fink defected.
 *
 * The critter looks at each 4-strand of its DNA, holding 
 * it up to the history.  It looks for DNA strands that 
 * match recent history. Suppose its DNA started with 
 * "tvtcv".  Then it would start with the "tvtc" strand:
 *
 *  History DNA
 *  _______ ___
 *  d       t
 *  t       v
 *  c       t
 *         (c)
 *
 *  The "c" at the end of this 4-strand suggests that 
 *  the critter should co-operate.  However, the DNA doesn't 
 *  match the History at all.  Thus, the critter 
 *  won't give this suggestion much weight.
 *  
 *  Next, we try "vtcd":
 *  _______ ___
 *  d       v
 *  t       t
 *  c       c
 *         (v)
 *
 * The "v" at the end of this 4-strand suggests that the 
 * critter defect.  The DNA matches the history for the 
 * previous couple of rounds, and thus the critter will 
 * give this suggestion a lot of weight.
 *
 * COMPILING:
 *
 * I use "gcc -o alitm -lm -O alitm.c".
 *
 */

#include <stdlib.h>
#include <math.h> // REMIND sdev

#define WORLD_WIDTH   (60)
#define WORLD_HEIGHT  (20)

#define START_HEALTH (17)         // Critters' starting health

#define MAX_YEARS    (16000)      // How many ticks to run simulation?

struct Cell {
  int                 health;
  int                 age;
  unsigned long       memory[8];
  unsigned long       dna[4];
  char                face;
};

struct Cell   World[WORLD_HEIGHT][WORLD_WIDTH];
int           Incoming[WORLD_HEIGHT][WORLD_WIDTH];

unsigned int         Population;
unsigned int         AgeOfTheWorld;

void Init(void);
void StartGame(void);
void Trade(void);
void Wither(void);
void Breed(void);
void Report(void);
void PrintFinalDNA(void);
void AnalyzeBehavior(void);

int main(void) {
  Init();

 NEXT_GAME:
  StartGame();
  while ((Population > 0) && (AgeOfTheWorld < MAX_YEARS)) { 
    Trade();
    Wither();
    Breed();

    // Report(); // Uncomment this to get an ASCII representation of
                 // the world every few ticks.  When I was first getting
                 // the program working, this was useful for debugging.
                 // Now I find it useful for self-hypnosis.

    AgeOfTheWorld++;
  }

  if (AgeOfTheWorld < MAX_YEARS) { goto NEXT_GAME; } 

  PrintFinalDNA();  

  // AnalyzeBehavior(); // Uncomment this to generate a lot of 
                        // statistics about the DNA of the final
                        // generation of critters.

  goto NEXT_GAME;

  return 0;
}

void Init(void) { }

void StartGame(void) {
  int count1, count2;
  struct Cell* target;

  AgeOfTheWorld = 0;
  Population    = 0;

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      target = &World[count1][count2];
      if (rand() % 2) {
	target->health = START_HEALTH;

	target->dna[0] = rand();
	target->dna[1] = rand();
	target->dna[2] = rand();
	target->dna[3] = rand();

	target->face = (rand() % 26) + 'a';

	target->age    = 0;

	Population++;
      }
      else {
	target->health = 0;
	target->age    = 0;
      }
    }
  }
}

void Trade(void) { 
  int count1, count2, count3;
  int count4, count5;
  int memlen;
  int t1, t2;
  struct Cell *source, *target;
  unsigned long long ayes, nays;
  unsigned int bestMatchLen; // REMIND bestMatchLen

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      Incoming[count1][count2] = 0;
      for (count3 = 0; count3 < 8; count3++) {
	World[count1][count2].memory[count3] <<= 2;
      }
    }
  }

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {

      source = &World[count1][count2];

      if (source->health > 1) {
	for (count3 = 0; count3 < 8; count3++) {
	  switch (count3) {
	  case 0:
	    t1 = count1 - 1; t2 = count2 - 1;
	    break;
	  case 1:
	    t1 = count1 - 1; t2 = count2   ;
	    break;
	  case 2:
	    t1 = count1 - 1; t2 = count2 + 1;
	    break;
	  case 3:
	    t1 = count1    ; t2 = count2 - 1;
	    break;
	  case 4:
	    t1 = count1    ; t2 = count2 + 1;
	    break;
	  case 5:
	    t1 = count1 + 1; t2 = count2 - 1;
	    break;
	  case 6:
	    t1 = count1 + 1; t2 = count2    ;
	    break;
	  case 7:
	    t1 = count1 + 1; t2 = count2 + 1;
	    break;
	  }
	  target = &World[t1][t2];

	  if (!target->health) { continue; }

	  // Here's where source decides whether to trade with target.
	  // A "continue" means "don't trade" aka "defect".

	  memlen = 10;

	  if (source->age < memlen) { memlen = source->age; }
	  if (target->age < memlen) { memlen = target->age; }

	  ayes = 0;
	  nays = 0;
	  bestMatchLen = 0;

	  for (count4 = 0; count4 < 128; count4 += 2) {
	    unsigned long tempDNA;
	    unsigned long tempMemory;
	    int           suggest;

	    tempDNA = (source->dna[count4 / 32] >> (count4 % 32)) |
                      (source->dna[((count4 / 32) + 1) % 4] << 
		       (32 - (count4 % 32)));
	    tempMemory = source->memory[count3] >> 2;

	    suggest = tempDNA & 2;
	    tempDNA >>= 2;

	    for (count5 = 0; count5 < memlen; count5++) {
	      if ((tempDNA & 3) != (tempMemory & 3)) { break; }
	      tempDNA >>= 2;
	      tempMemory >>= 2;
	    }

	    if (count5 < bestMatchLen) { continue; }

	    if (count5 > bestMatchLen) {
	      bestMatchLen = count5;
	      ayes = 0;
	      nays = 0;
	    }

	    if (suggest) { ayes ++; } 
	    else { nays ++; } 
	  }

	  while ((ayes + nays) > 0x7fffff) {
	    ayes >>= 1;
	    nays >>= 1;
	  }

	  if ((rand() % (nays + ayes)) > ayes) { continue; }

	  source->health--;
	  Incoming[t1][t2]++;
	  World[t1][t2].memory[7-count3] |= 1;
	  World[count1][count2].memory[count3]   |= 2;

	  // If source is running low on cash, must stop trading
	  if (source->health < 2) { break; }
	}
      }
    }
  }

  // distribute the loot and increment age
  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      if (!World[count1][count2].health) { continue; }
      World[count1][count2].health += Incoming[count1][count2] * 2;
      World[count1][count2].age++;
    }
  }
}

void Wither(void) { 
  int count1, count2;

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      if (World[count1][count2].health) {
	World[count1][count2].health -= World[count1][count2].age / 16;

	if (World[count1][count2].health <= 0) {
	  World[count1][count2].health   = 0;
	  World[count1][count2].age      = 0;

	  Population--;
	}
      }
    }
  }
}

void Breed(void) { 
  int count;
  for (count = 0; count < (WORLD_WIDTH * WORLD_HEIGHT / 32); count++) {
    int c1, c2;  // crib
    int s1, s2;  // suitors
    int mom1, mom2, momHealth, dad1, dad2, dadHealth;

    c1 = rand() % (WORLD_HEIGHT-2) + 1;
    c2 = rand() % (WORLD_WIDTH-2) + 1;
    if (World[c1][c2].health) { continue; }

    momHealth = -1;
    dadHealth = -1;

    for (s1 = c1 - 1; s1 < c1 + 2; s1++) {
      for (s2 = c2 - 1; s2 < c2 + 2; s2++) {
	if (World[s1][s2].health > momHealth) { 
	  dadHealth = momHealth; dad1 = mom1; dad2 = mom2;
	  momHealth = World[s1][s2].health; mom1 = s1; mom2 = s2;
	  continue;
	}
	if (World[s1][s2].health > dadHealth) { 
	  dadHealth = World[s1][s2].health; dad1 = s1; dad2 = s2;
	  continue;
	}
      }
    }

    if (momHealth < (2 * START_HEALTH)) { continue; }

    // If there's a mom and a dad, do sex, maybe
    if ((dadHealth > (2 * START_HEALTH)) &&
	((rand() % momHealth) < dadHealth)) {

      World[c1][c2].dna[0] = World[mom1][mom2].dna[0];
      World[c1][c2].dna[1] = World[mom1][mom2].dna[1];
      if ((momHealth * 2) > (dadHealth * 3)) {
	World[c1][c2].dna[2] = World[mom1][mom2].dna[2];
      } else {
	World[c1][c2].dna[2] = World[dad1][dad2].dna[2];
      }
      World[c1][c2].dna[3] = World[dad1][dad2].dna[3];

      World[c1][c2].face = World[mom1][mom2].face;
      if (World[dad1][dad2].face < World[c1][c2].face) {
	World[c1][c2].face = World[dad1][dad2].face;
      }
      if (World[mom1][mom2].face != World[dad1][dad2].face) {
	World[c1][c2].face++;
	if (World[c1][c2].face ==  91) { World[c1][c2].face = 'a'; }
	if (World[c1][c2].face == 123) { World[c1][c2].face = 'a'; }
      }

    }
    else { // parthenogenesis (sp?)
      World[c1][c2].dna[0] = World[mom1][mom2].dna[0];
      World[c1][c2].dna[1] = World[mom1][mom2].dna[1];
      World[c1][c2].dna[2] = World[mom1][mom2].dna[2];
      World[c1][c2].dna[3] = World[mom1][mom2].dna[3];
      World[c1][c2].face = World[mom1][mom2].face;
    }

    // majorly mutate, maybe 
    if (!(rand() % 256)) {
      World[c1][c2].dna[0]  =  rand();
      World[c1][c2].dna[1]  =  rand();
      World[c1][c2].dna[2]  =  rand();
      World[c1][c2].dna[3]  =  rand();

      World[c1][c2].face = 'A';
    }

    // minorly mutate, maybe
    while (rand() % 2) {
      World[c1][c2].dna[rand() % 4] ^=  (1 << (rand() % 32));
    }

    // rotate mutate, maybe
    if (rand() % 64) {
      unsigned int swap;
      unsigned int offset;

      offset = (rand() % 16) * 2;

      swap = World[c1][c2].dna[0];

      World[c1][c2].dna[0] = World[c1][c2].dna[0] >> offset | 
	                     World[c1][c2].dna[1] << (32 - offset);
      World[c1][c2].dna[1] = World[c1][c2].dna[1] >> offset | 
	                     World[c1][c2].dna[2] << (32 - offset);
      World[c1][c2].dna[2] = World[c1][c2].dna[2] >> offset | 
	                     World[c1][c2].dna[3] << (32 - offset);
      World[c1][c2].dna[3] = World[c1][c2].dna[3] >> offset | 
	                     swap << (32 - offset);
    }

    World[c1][c2].health = START_HEALTH;
    World[c1][c2].age    = 0;
    Population++;
  }
}

void Report(void) { 
  int count1, count2;

  if (AgeOfTheWorld % 4) { return; }   

  printf("Year %u , Population %u \n", AgeOfTheWorld, Population);

  for (count1 = 0; count1 < WORLD_HEIGHT; count1++) {
    printf("  ");
    for (count2 = 0; count2 < WORLD_WIDTH; count2++) {
      if (!World[count1][count2].health) {
  	printf(".");
  	continue;
      }
      printf("%c", World[count1][count2].face);
    }    
    printf("\n");
  }
  printf("\n");

}

void PrintFinalDNA(void) {
  int count1, count2;
  int count3;
  unsigned long tempDNA;

  for (count1 = 1; count1 < WORLD_HEIGHT - 1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH - 1; count2++) {
      if (!World[count1][count2].health) { continue; }
      for (count3 = 0; count3 < 128; count3 += 2) {
	if (!(count3 % 32)) { 
	  tempDNA = World[count1][count2].dna[3 - (count3 / 32)];
	}
	switch (tempDNA & 0xC0000000) {
	case 0:
	  printf("v");
	  break;
	case 0x40000000:
	  printf("d");
	  break;
	case 0x80000000:
	  printf("c");
	  break;
	case 0xC0000000:
	  printf("t");
	  break;
	}
	tempDNA <<= 2;
      }
      printf("\n");
    }
  }
}

void AnalyzeBehavior(void) {
  unsigned long long int ayes, nays;
  unsigned int age, sampleHist;

  int histCount, count1, count2;
  int yearCount, geneCount;

  unsigned int tempGene, tempHist;

  float kind;
  float kindliness[WORLD_HEIGHT][WORLD_WIDTH];

  double sumKindliness;
  unsigned int numKindliness;
  double meanKindliness;

  for (age = 0; age < 7; age++) { 
  for (sampleHist = 0; sampleHist < (1 << (age * 2)); sampleHist++) {

  sumKindliness = 0;
  numKindliness = 0;

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      int longestHistLen;
      longestHistLen = 0;
      ayes = 0; nays = 0;
      for (geneCount = 0; geneCount < 128; geneCount++) {
	int suggest;
	tempHist = sampleHist;

	tempGene = (World[count1][count2].dna[geneCount / 32] >> 
		    (geneCount % 32)) |
	           (World[count1][count2].dna[((geneCount / 32) + 1) % 4] << 
		    (32 - (geneCount % 32)));

	suggest = tempGene & 2;
	tempGene >>= 2;
	for (yearCount = 0; yearCount < age; yearCount++) {
	  if ((tempGene & 3) != (tempHist & 3)) { break; }
	  tempGene >>= 2; 
	  tempHist >>= 2;
	}
	if (yearCount < longestHistLen) { continue; }
	if (yearCount > longestHistLen) { 
	  longestHistLen = yearCount;
	  ayes = 0; nays = 0;
	}
	if (suggest) { ayes ++; }
	else { nays ++; }
      }

      while ((ayes + nays) > 0x7fffff) {
	ayes >>= 1;
	nays >>= 1;
      }  

      kind = (float)((float)ayes / (float)(ayes + nays));
      kindliness[count1][count2] = kind;
      sumKindliness += kind;
      numKindliness ++;
    }
  }

  meanKindliness = sumKindliness / numKindliness;

  sumKindliness = 0;

  for (count1 = 1; count1 < WORLD_HEIGHT-1; count1++) {
    for (count2 = 1; count2 < WORLD_WIDTH-1; count2++) {
      sumKindliness += (kindliness[count1][count2] - meanKindliness) * 
	               (kindliness[count1][count2] - meanKindliness);
    }
  }

  sumKindliness /= (numKindliness - 1);
  printf("Age: %u:  Hist: %4u   Mean: %f Dev: %f \n", age, sampleHist, meanKindliness, sqrt(sumKindliness));

  }
  }
}