#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

/* Original Hi-Q board, and the one I recall from VanDine Horton.

   MCV, January 2005
*/

// The board is always symmetrical along both the vertical and horizontal axis.
// There are also always the same number of rows as columns (although some
// specific cells may be inactive throughout the game.

#define BOARDWIDTH    7

#define MAXMOVES       40
#define NPOPULATION   100
#define NGENERATIONS 2500
#define TOPNTILE       10

#define TRUE            1
#define FALSE           0

#define UNUSED         -1
#define IN_USE         '1'
#define VACANT         '0'

#define OFFSET          0
#define DIRECTION       1

#define EAST            0
#define NORTH           1
#define WEST            2
#define SOUTH           3
#define RESULTSFILE "HIQGA_GAMES_E.TXT"

typedef struct {
   int   score;
   int   nmoves;
   char *moves[MAXMOVES];
} member;

member population[NPOPULATION];

typedef struct {
   int row;
   int col;
   int direction;
} move;

char *initial_english_board =
/*  0 */ "--111--"
/*  1 */ "--111--"
/*  2 */ "1111111"
/*  3 */ "1110111"
/*  4 */ "1111111"
/*  5 */ "--111--"
/*  6 */ "--111--"
;

char *initial_french_board =
/*  0 */ "--011--"
/*  1 */ "-11111-"
/*  2 */ "1111111"
/*  3 */ "1111111"
/*  4 */ "1111111"
/*  5 */ "-11111-"
/*  6 */ "--111--"
;

// Actual number of moves is # of marbles in the game - 1 (since one is always
// left over.)  # of marbles = (# rows * # columns), minus # of inactive cells,
// minus the blank middle cell the game starts with.
//
// For the English board, marbles = (7 * 7) - (4 * 4)- 1 - 1 = 31
// For the French board, marbles = (7 * 7) - (3 * 3) - 1 - 1 = 35

#define NPEGSENGLISH          32 // Pegs for the English board
#define NPEGSFRENCH           36 // Pegs for the French board

char *initial_board;
int   npegs;

void create_population(void);
void evolve(int);
void main(int,char **);
int  next_move(int,int);
int  score(int);    
int  sort_function(const void *,const void *);

/* ------------------------------------------------------------ */
void create_population()
{
   int  i;
   int  j;
   int  ctr;
   // char str[BOARDWIDTH * BOARDWIDTH + 1];

   // Allocate memory for the move arrays
   for (i = 0;i < NPOPULATION;i++)
      for (j = 0;j < MAXMOVES;j++)
         population[i].moves[j] = (char *)calloc(BOARDWIDTH * BOARDWIDTH,sizeof(char));

   for (i = 0;i < NPOPULATION;i++) {
      ctr = 0;
      while (next_move(i,ctr) == TRUE)
         ctr++;

      population[i].nmoves = ctr;
      population[i].score  = score(i);
   }
}
/* ------------------------------------------------------------ */
int score(int popnum)
{
   int   n;
   char *board;
   int   ctr;

   // Usually, the score will be the number of moves in a game saved in the
   // population array.  Since a marble is removed on each move in a game, there
   // will be a limit on the possible moves.
   //
   // In the English version of the game, the 'best' solution is taken to be a
   // single peg remaining in the center hole, so we will double the score if we
   // find that to be true. (In the French game, a single peg in the middle
   // can't happen).

   n = population[popnum].nmoves;

   // Look at the array that represents the board in its final state
   board = population[popnum].moves[n - 1];
   ctr   = population[popnum].nmoves;

   if (ctr == (npegs - 1)) {
      if (npegs == NPEGSENGLISH) {// Higher score if remaining peg is in the middle
         if (*(board + ((3 * BOARDWIDTH) + 3)) == IN_USE)
            ctr *= 2;
      }
      else {
      // In the French board, ending with one peg in the middle is mathematically
      // impossible.  In fact, starting with the missing peg in the middle will
      // never get you a better end score than 2!  Martin Gardner proposed the
      // board we use here, with the missing peg in the top right.  And we will
      // (arbitrarily) favor an ending with a single peg in the bottom right.

         if (*(board + ((6 * BOARDWIDTH) + 4)) == IN_USE)
            ctr *= 2;
      }
   }

   return(ctr);
}
/* ------------------------------------------------------------ */
int next_move(int popnum,int movenum)
{
   int   matrix[BOARDWIDTH][BOARDWIDTH]; 
   int   newmatrix[BOARDWIDTH][BOARDWIDTH];
   char *board;
   int   i;
   int   j;
   char  c;
   int   offset;
   int   move_ctr;
   move  fair[BOARDWIDTH * BOARDWIDTH];
   int   choice;
   int   row;
   int   col;

   // Construct a matrix of the board in some state, ennumerate available moves,
   // and choose one at random.
   //
   // Return TRUE if a move is chosen, FALSE if no alternatives exist.
   
   if (movenum == 0) // First move of the game
      board = initial_board;
   else
      board = population[popnum].moves[movenum - 1];

   for (i = 0;i < BOARDWIDTH;i++)
      for (j = 0;j < BOARDWIDTH;j++) {
         offset = (i * BOARDWIDTH) + j;
         c = *(board + offset);
         matrix[i][j] = ((c == '-') ? UNUSED : ((c == VACANT) ? 0 : 1));
      }

   // A legal move is defined by the slot from which it begins, and the direction
   // it will go.

   move_ctr = 0;
   for (i = 0;i < BOARDWIDTH;i++) {
      for (j = 0;j < BOARDWIDTH;j++) {
         if (matrix[i][j] == 1) {  // If there is a peg at this offset
            // Direction 0 (look east)
            if (j < (BOARDWIDTH - 2)) {
               if ((matrix[i][j + 1] == 1) && (matrix[i][j + 2] == 0)) {
                  fair[move_ctr].row       = i;
                  fair[move_ctr].col       = j;
                  fair[move_ctr].direction = EAST;
                  move_ctr++;
               }
            }
            // Direction 1 (look north)
            if (i > 1) {
               if ((matrix[i - 1][j] == 1) && (matrix[i - 2][j] == 0)) {
                  fair[move_ctr].row       = i;
                  fair[move_ctr].col       = j;
                  fair[move_ctr].direction = NORTH;
                  move_ctr++;
               }
            }
            // Direction 2 (look west)
            if (j > 1) {
               if ((matrix[i][j - 1] == 1) && (matrix[i][j - 2] == 0)) {
                  fair[move_ctr].row       = i;
                  fair[move_ctr].col       = j;
                  fair[move_ctr].direction = WEST;
                  move_ctr++;
               }
            }
            // Direction 3 (look south)
            if (i < (BOARDWIDTH - 2)) {
               if ((matrix[i + 1][j] == 1) && (matrix[i + 2][j] == 0)) {
                  fair[move_ctr].row       = i;
                  fair[move_ctr].col       = j;
                  fair[move_ctr].direction = SOUTH;
                  move_ctr++;
               }
            }
         }
      }
   }

   // If there are no moves available, time to go.
   if (move_ctr == 0)
      return(FALSE);

   // Otherwise, choose randomly from the available moves, populate a move string,
   // update the move array, and exit.

   choice = random(move_ctr);

   for (i = 0;i < BOARDWIDTH;i++)
      for (j = 0;j < BOARDWIDTH;j++)
         newmatrix[i][j] = matrix[i][j];

   row = fair[choice].row;
   col = fair[choice].col;

   switch (fair[choice].direction) {
      case EAST:
         newmatrix[row][col + 0] = 0;
         newmatrix[row][col + 1] = 0;
         newmatrix[row][col + 2] = 1;
         break;
      case NORTH:     
         newmatrix[row - 0][col] = 0;
         newmatrix[row - 1][col] = 0;
         newmatrix[row - 2][col] = 1;
         break;
      case WEST:    
         newmatrix[row][col - 0] = 0;
         newmatrix[row][col - 1] = 0;
         newmatrix[row][col - 2] = 1;
         break;
      case SOUTH:  
         newmatrix[row + 0][col] = 0;
         newmatrix[row + 1][col] = 0;
         newmatrix[row + 2][col] = 1;
         break;
   }
                                    
   board = population[popnum].moves[movenum];
   for (i = 0;i < BOARDWIDTH;i++)
      for (j = 0;j < BOARDWIDTH;j++) {
         offset = (i * BOARDWIDTH) + j;
         c = ((newmatrix[i][j] == UNUSED) ? '-' : ((newmatrix[i][j] == 1) ? IN_USE : VACANT));
         *(board + offset) = c;
      }

   return(TRUE);
}
/* ------------------------------------------------------------ */
void evolve(int n)
{
   int   i;
   int   j;
   int   k;
   int   ctr;
   char  str[BOARDWIDTH * BOARDWIDTH + 1];
   int   parent;
   int   random_move;
   int   high_score = 0;
   FILE *f1;

   // Open and close the results file to clear it
    if ((f1 = fopen(RESULTSFILE, "wt")) == NULL) {
       fprintf(stderr, "Could not open output file for Hi-Q GA solutions.\n");
       exit(1);
    }
    fclose(f1);

   // Sort the population by fitness (highest to lowest).  From the TOPNTILE
   // members (which we'll leave alone), populate the next generation with
   // copies of these, with a chance of mutation.
   
   memset(str,'\0',BOARDWIDTH * BOARDWIDTH + 1);

   qsort(population,NPOPULATION,sizeof(member),sort_function);

   for (i = 0;i < n;i++) {

      // Repopulate the generation using our highest-fitness parents

      for (j = TOPNTILE;j < NPOPULATION;j++) {

         // Choose a parent
         parent = random(TOPNTILE);

         // Since we always save exact copies of our most successful parents,
         // ALL of the children will be subject to mutation, although the point
         // in any given game where a possible change occurs will be random.

         random_move = random(population[parent].nmoves);
         for (k = 0;k < random_move;k++)
            strncpy(population[j].moves[k],population[parent].moves[k],
               BOARDWIDTH * BOARDWIDTH);

         ctr = random_move;
         while (next_move(j,ctr) == TRUE)
            ctr++;

         population[j].nmoves = ctr;
         population[j].score  = score(j);
      }

      qsort(population,NPOPULATION,sizeof(member),sort_function);

      strncpy(str,population[0].moves[population[0].nmoves - 1],BOARDWIDTH * BOARDWIDTH);
      printf("Generation %03d: %03d %03d %s\n",
         i,population[0].nmoves,population[0].score,str);

      // If this generation produces a new high score, write out its details to
      // the output file.  Generation, move, total moves, score, board for each move.

      if (population[0].score > high_score) {
         if ((f1 = fopen(RESULTSFILE, "a+t")) == NULL) {
            fprintf(stderr, "Could not open output file for Hi-Q GA solutions.\n");
            exit(1);
         }

         for (j = 0;j < population[0].nmoves;j++) {
            strncpy(str,population[0].moves[j],BOARDWIDTH * BOARDWIDTH);
            fprintf(f1,"%03d,%03d,%03d,%03d,%s\n",
               i,j,population[0].nmoves,population[0].score,str);
         }
         fclose(f1);

         high_score = population[0].score;
      }

   }
}
/* ------------------------------------------------------------ */
int sort_function(const void *a,const void *b)
{
   member *x;
   member *y;
   int value;

   x = (member *)a;
   y = (member *)b;

   if (y -> score  > x -> score)
      value =  1;
   else if (y -> score  < x -> score)
      value = -1;
   else
      value =  0;

   return(value);
}
/* ------------------------------------------------------------ */

void main(int argc,char **argv)
{
   int ngen;
   
   // Initiate the random number generator.  We leverage this whenever we choose
   // a move.

   randomize();

   initial_board = initial_english_board;
   npegs         = NPEGSENGLISH;

   // initial_board = initial_french_board;
   // npegs         = NPEGSFRENCH;

   create_population();

   ngen = 0;
   if (argc > 1)
     ngen = atoi(argv[1]);

   if (ngen == 0)
      ngen = NGENERATIONS;

   evolve(ngen);
}