#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <limits.h>
#include <string.h>
#include "common.h"

/* every set stone increases the value of all fields that can be part
   of a winning constallation that includes the stone; the overall
   value is sum(4^value_of_field) */
long value1(Boardstate *b, char player)
{
  // printboard(b);
  long mx = b->maxx+4;
  long my = b->maxy+4;
  long mx1 = mx+4;
  long my1 = my+4;
  long result = 0;
  char other = otherplayer(player);
  // printf("player=%c other=%c\n",player,other);
  char *vals = calloc(mx1*my1,1);
  char *v = &vals[4*mx1+4]; /* the point in v for the start of b->board */
  for (long i=0; i<b->maxy; i++)
    for (long j=0; j<b->maxx; j++) {
      if (b->board[i*b->maxx+j]==player) {
        long first,last;
        /* horizontal */
        for (first=1; first<=4; first++) {
          if (j-first<0) {
            first=4;
            break;
          }
          if (b->board[i*b->maxx+j-first]==other) {
            first--;
            break;
          }
        }
        for (last=1; last<=4; last++) {
          if (j+last>=b->maxx) {
            last=4;
            break;
          }
          if (b->board[i*b->maxx+j+last]==other) {
            last--;
            break;
          }
        }
        // printf("\nhorizontal: first=%ld last=%ld\n",first,last);
        if (last+first>=4)
          for (long k=-first; k<=last; k++)
            v[i*mx1+j+k]++;

        /* vertical */
        for (first=1; first<=4; first++) {
          if (i-first<0) {
            first=4;
            break;
          }
          if (b->board[(i-first)*b->maxx+j]==other) {
            first--;
            break;
          }
        }
        for (last=1; last<=4; last++) {
          if (i+last>=b->maxy) {
            last=4;
            break;
          }
          if (b->board[(i+last)*b->maxx+j]==other) {
            last--;
            break;
          }
        }
        // printf("  vertical: first=%ld last=%ld\n",first,last);
        if (last+first>=4)
          for (long k=-first; k<=last; k++)
            v[(i+k)*mx1+j]++;
        
        /* diagonal / */
        for (first=1; first<=4; first++) {
          if (j-first<0 || i-first<0) {
            first=4;
            break;
          }
          if (b->board[(i-first)*b->maxx+j-first]==other) {
            first--;
            break;
          }
        }
        for (last=1; last<=4; last++) {
          if (j+last>=b->maxx || i+last>=b->maxy) {
            last=4;
            break;
          }
          if (b->board[(i+last)*b->maxx+j+last]==other) {
            last--;
            break;
          }
        }
        // printf("diagonal /: first=%ld last=%ld\n",first,last);
        if (last+first>=4)
          for (long k=-first; k<=last; k++)
            v[(i+k)*mx1+j+k]++;

        /* diagonal \ */
        for (first=1; first<=4; first++) {
          if (j-first<0 || i+first>=b->maxy) {
            first=4;
            break;
          }
          if (b->board[(i+first)*b->maxx+j-first]==other) {
            first--;
            break;
          }
        }
        for (last=1; last<=4; last++) {
          if (j+last>=b->maxx || i-last<0) {
            last=4;
            break;
          }
          if (b->board[(i-last)*b->maxx+j+last]==other) {
            last--;
            break;
          }
        }
        // printf("diagonal \\: first=%ld last=%ld\n",first,last);
        if (last+first>=4)
          for (long k=-first; k<=last; k++)
            v[(i-k)*mx1+j+k]++;
      }
    }
  /* in theory a v[...] can contain values up to 32, leading to an
     overflow in the computation below, but in practice it will be
     much less */
  // printf("\n\n");
  // printboard(b);
  for (long i=my-1; i>=-4; i--) {
    for (long j=-4; j<mx; j++) {
      // printf("%x",v[i*mx1+j]);
      result += 1<<(2*v[i*mx1+j]);
    }
    // printf("\n");
  }
  free(vals);
  // printf(" %ld",result);
  return result;
}

long value(Boardstate *b, char player)
{
  return value1(b,player)-value1(b,otherplayer(player));
}

Boardstate *copyboard(Boardstate *b)
{
  Boardstate *b1 = malloc(sizeof(Boardstate));
  *b1 = *b;
  b1->board = malloc(b->maxx*b->maxy);
  memcpy(b1->board,b->board,b->maxx*b->maxy);
  return b1;
}

void deleteboard(Boardstate *b)
{
  free(b->board);
  free(b);
}

/* best move when looking ahead from the boardstate b for depth
   levels, and finally using value(); stores the best move in the
   longs pointed to by bestx and besty, and the value in the long
   pointed to by vp; this function implements the negamax()
   algorithm */
void bestmove(int depth, Boardstate *b, long *vp, long *bestx, long *besty)
{
  *vp=-LONG_MAX;
  // printf("\n");
  for (long i=-2; i<b->maxy+2; i++)
    for (long j=-2; j<b->maxx+2; j++)
      if (moveok(b,j,i)) {
        Boardstate *b1 = copyboard(b);
        char player = b1->toplay;
        // printf("%*c%ld %ld",20-depth,' ',j+2,i+2);
        int win = plyfull(b1,j,i);
        assert(win!=-1);
        if (win==1) {
          *vp=LONG_MAX-1; /* the -1 avoids cases where bestx and besty are not set */
          deleteboard(b1);
          *bestx=j;
          *besty=i;
          return;
        }
        long v=value(b1,player);
        if (depth>0) {
          long x, y;
          bestmove(depth-1,b1,&v, &x, &y);
          v = -v;
        }
        // printf("%*c%ld %ld",20-depth,' ',j+2,i+2);
        // printf(" %ld%c\n",v,(v>*vp)?'*':' ');
        if (v>*vp) {
          *vp=v;
          *bestx=j;
          *besty=i;
        }
        deleteboard(b1);
      }
  return;
}

int main(int argc, char *argv[])
{
  Boardstate *b;
  int depth;
  long bestx, besty, value;

  if (argc != 3) {
    fprintf(stderr,"%s <depth> <infile>\n",argv[0]);
    exit(1);
  }
  depth=atoi(argv[1]);
  if (depth<0) {
    fprintf(stderr,"depth must be positive\n");
    exit(1);
  }
  b = loadboard(argv[2]);
  printf("Position:\n");
  printboard(b);
  printf("\n");
  bestmove(depth, b, &value, &bestx, &besty);
  printf("Best move: %ld %ld Value: %ld\n", bestx+2, besty+2, value);
  return 0;
}