/**********************************************************************c4.c
   Purpose:
      This file contains a program that plays the game Connect 4.

   Written by Stuart Hansen
   Date : November 23, 1996

**************************************************************************/

//#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream.h>

#define INFINITY 15000
#define zero 0
#define one 1
#define two 2
#define three 3

#define X 'X'
#define O 'O'
#define blank '_'


/* This structure represents a Connect 4 game position.  It contains
   the board and information about the current game position */
typedef struct
{
  char board[6][7];  /* the game board */
  int score;         /* the backed up score of the current position */

  int Xcol;   /* the last column that the computer played in */
  int Ocol;   /* the last column the user played in */
  char over;  /* X or O depending on who has won the game */
} position;


/* This is a node for our linked list of positions */
typedef struct QN
{
    position *p;
    struct QN *next;
} QNode;


/*Function to manipulate our linked list */
int isempty(QNode * head);
void insert(position *p, QNode ** head);
void Delete_Q(QNode * node);
position *Qremove(QNode ** head);


/* Functions to manipulate our positions */
void init_position (position *pp);
void print_result(position *p);
inline void copy_position (position *dest, position *source);
inline int static_eval(char xo, int depth, position *pp);
int legal_move(int j, position *pp);
position *make_move(int column, char xo, position *pp);
int gameover(position *pp);
void print_position (position *p);


/* init_position is the constructor.  It sets the board to empty */
void init_position (position *pp)
{
   int i,j;
   for (i=0; i<6; ++i)
      for (j=0; j<7; ++j)
         pp->board[i][j] = '_';

   pp->score = -1;
   pp->Xcol  = -1;
   pp->Ocol = -1;
   pp->over = 0;
}


/* This function copies one position into another one */
inline void copy_position (position *dest, position *source)
{
   int i, j;
   for (i=0; i<6; i++)
      for(j=0; j<7; j++)
         dest->board[i][j] = source->board[i][j];

  dest->score = source->score;
  dest->Xcol = source->Xcol;
  dest->Ocol = source->Ocol;
  dest->over = source->over;
}


/* This function prints a position to the screen */
void print_position (position *pp)
{
   int i, j;
   cout << endl << endl;
   for (i=5; i>=0; i--)
   {
	  for (j=0; j<7; j++)
		 cout << pp->board[i][j] << " ";
	  cout << endl;
   }

   if (pp->Ocol >= 0)
	  cout << "Your last move " << pp->Ocol << endl;
   if (pp->Xcol >=0)
	  cout << "My last move " << pp->Xcol << endl;
}


/* This function prints who has won the game */
void print_result (position *pp)
{
   if (pp->over == X)
	  cout << "Computer wins big time!!" << endl;
   else if (pp->over == O)
	  cout << "You got lucky and won this time!!" << endl;
   else
	  cout << "The game was a draw!" << endl;
}


/* Places xo into col in pp */
position *make_move (int col, char xo, position *pp)
{
  position *posptr;
  int i;

  posptr = (position *) malloc (sizeof(position));
  copy_position (posptr, pp);
  i=0;
  while (pp->board[i][col] != '_') i++;
  posptr->board[i][col] = xo;
  if (xo == X)
    posptr->Xcol = col;
  else
	posptr->Ocol = col;

  return posptr;
}


/* Checks to make sure it is legal to play in column j */
int legal_move (int j, position *pp)
{
  return (pp->board[5][j] == '_'); //  && !gameover(pp));
}


/* Checks to see if the game is over.
   It loops through the rows, the columns and the diagonals
   to see if anyonw has won. */
int gameover(position *pp)
{
   int i, j, over;
   if (pp->over) return pp->over;

   over = 1;

   for (j=0; j<7; ++j)
     if (pp->board[5][j] == blank) over = 0;

   for (i=0; i<6; ++i)
      for (j=0; j<4; ++j)
      {
         if (pp->board[i][j] != blank &&
             pp->board[i][j] == pp->board[i][j+1] &&
             pp->board[i][j] == pp->board[i][j+2] &&
             pp->board[i][j] == pp->board[i][j+3])
         {
	      over = pp->board[i][j];
         }
      }

   for (j=0; j<7; ++j)
      for (i=0; i<3; ++i)
      {
	 if (pp->board[i][j] != blank &&
             pp->board[i][j] == pp->board[i+1][j] &&
             pp->board[i][j] == pp->board[i+2][j] &&
             pp->board[i][j] == pp->board[i+3][j])
         {
	    over = pp->board[i][j];
         }
      }

   for (i=0; i<3; ++i)
      for (j=0; j<4; ++j)
      {
         if (pp->board[i][j] != blank &&
             pp->board[i][j] == pp->board[i+1][j+1] &&
             pp->board[i][j] == pp->board[i+2][j+2] &&
             pp->board[i][j] == pp->board[i+3][j+3])
         {
	    over = pp->board[i][j];
         }
      }

   for (i=5; i>2; --i)
       for (j=0; j<4; ++j)
       {
	  if (pp->board[i][j] != blank &&
              pp->board[i][j] == pp->board[i-1][j+1] &&
              pp->board[i][j] == pp->board[i-2][j+2] &&
              pp->board[i][j] == pp->board[i-3][j+3])
          {
             over = pp->board[i][j];
          }
       }

   pp->over = over;
   return over;
}



/* Checks to see if the linked list is empty */
int isempty(QNode * head)
{
   return (head == 0);
}


/* Removes the front element from the list */
position *Qremove(QNode ** head)
{
    QNode *q = *head;
    position *p = q->p;
    (*head) = (*head)->next;
    free (q);
    return p;
}


/* This function deletes the entire position Queue */
void Delete_Q(QNode * node)
{
   QNode *temp;
   while (!isempty(node))
   {
      temp = node;
      node = node->next;
      free (temp->p);
      free (temp);
   }
}


/* Insert a position into the list */
void insert(position *p, QNode ** head)
{
   QNode *qp;
   qp = (QNode*) malloc(sizeof (QNode));

   qp->p = p;
   if (isempty(*head))
   {
	  *head = qp;
	  (*head)->next = 0;
   }
   else
   {
      qp->next = *head;
      *head = qp;
   }
}


/* This function generates the next set of possible moves
   and places them into the pQ linked list */
QNode *generatenext(char xo, position *pp)
{
   int j, i=3;
   QNode *pQ = 0;
   for (j=3; j>0; --j)
   {
	  if (legal_move(i+j, pp))  insert(make_move(i+j, xo, pp), &pQ);
      if (legal_move(i-j, pp))  insert(make_move(i-j, xo, pp), &pQ);
   }
   if (legal_move(i, pp))  insert(make_move(i, xo, pp), &pQ);
   return pQ;
}


// This function searches through potential positions to find the
// best next move.
position *minimax (position *b, int depth, int alpha, int beta, char xo)
{

   position *temppos;   // a temporary position holder
   position  *nextpos;  // the next position to be looked at
   position *bestpos;   // the best next position found so far

   QNode *pq;           // the queue of next positions

   int temp;            // the score of the current move
   int max;             // the score of the current best move
   char ox;             // X of O depending on whose move it is

   temppos = 0;
   nextpos = 0;
   bestpos = 0;

   pq = 0;

   if (xo == X)	ox = O; else ox = X;
   max = -INFINITY;

   if ((depth == 0) || (gameover(b)))
   {
      static_eval(xo, depth, b); 
      return b;
   }
   else
   {
      pq = generatenext(xo, b);
      while (!isempty(pq))
      {
         temppos = Qremove(&pq);
         nextpos = minimax(temppos, depth-1, -1*beta, -1*alpha, ox);
	 temp = -1 * nextpos->score;
         if (nextpos != temppos) free(nextpos);
         if (temp > max)
         {
	    temppos->score = temp;
            max = temp;
            if (max > alpha)
               alpha = max;
            if (bestpos != 0) free(bestpos);
               bestpos=temppos;

            if (max > beta)
            {
               Delete_Q(pq);
  	       return bestpos;
            };

         }
         else
         {
            free(temppos);
         }
      }
      Delete_Q(pq);
      return bestpos;
   }
}


// This function gets a move from the user and makes the
// play on the board 
void make_user_move (position *pp)
{
   int col;
   position *temp_p;
   col = 0;

   cout << "Enter the column in which to play (0-6) -->";
   cin >> col;
   while ((col <0) || col>6 || !legal_move(col, pp) )
   {
     cout <<"Illegal move!" << endl
          << "Enter the column in which to play (0-6) -->";
     cin >> col;
   }

   temp_p = make_move(col, O, pp);
   copy_position(pp, temp_p);
}


void main (int argc, char * argv[])
{
   position *p = new position;         /* the current board position */
   char user_first;    /* flag to see who goes first */
   int strength;

   /* See how strong of game the user want to play */
   if (argc >  1)
   {
      strength = atoi(argv[1]);
      if (strength < 1) strength = 1;
   }
   else
      strength = 5;

   init_position(p);

   /* Check to see who plays first */
   cout << "Do you want to go first (Y or N) -->";
   cin >> user_first;

   if (user_first == 'Y' || user_first == 'y')
   {
      make_user_move(p);
      print_position(p);
   }

   /* Continue playing until the game is over */
   while (!gameover(p))
   {
      p = minimax(p, strength, -INFINITY, INFINITY, X);
      print_position (p);

      if (!gameover(p))
      {
         make_user_move(p);
         print_position(p);
      }
   }
   print_result(p);
}

// This function assigns a score to 4 elements, along a row, column or diagonal
inline int quad (char xo, char w, char x, char y, char z) 
{
  int xocount = 0;
  int oxcount = 0;

  if (w==xo) xocount++; else if (w!=blank) oxcount++;
  if (x==xo) xocount++; else if (x!=blank) oxcount++;
  if (y==xo) xocount++; else if (y!=blank) oxcount++;
  if (z==xo) xocount++; else if (z!=blank) oxcount++;
  if (!xocount || !oxcount) return xocount-oxcount; else return 0;
}

inline int static_eval (char xo, int depth, position *p){
  char ox;
  int i, j, total=0;
  if (xo == X) ox = O; else ox = X;
  int go = gameover(p);
  if (go == xo)
  {
     p->score = 500+depth;
     return 500+depth;
  }
  else if (go == ox)
  {
     p->score = -500-depth;
     return -500-depth;
  }
  
  // Count some points for the rows
  for (i=0; i<6; ++i)
    for (j=0; j<4; ++j)
    {
      total = total + quad (xo, p->board[i][j], p->board[i][j+1],
                            p->board[i][j+2], p->board[i][j+3]);
    }

  // Count some points for the columns
  for (j=0; j<7; ++j)
    for (i=0; i<3; ++i)
    {
      total = total + quad (xo, p->board[i][j], p->board[i+1][j],
                            p->board[i+2][j], p->board[i+3][j]);
    }

  // count across the diagonals
  for (i=0; i<3; ++i)
    for (j=0; j<4; ++j)
    {
      total = total + quad (xo, p->board[i][j], p->board[i+1][j+1],
                            p->board[i+2][j+2], p->board[i+3][j+3]);
    }

  for (i=3; i<6; ++i)
    for (j=0; j<4; ++j)
    {
      total = total + quad (xo, p->board[i][j], p->board[i-1][j+1],
                            p->board[i-2][j+2], p->board[i-3][j+3]);
    }
  return total;
}