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

Entry *transposition_table;

int transposition_hits = 0;

long get_hash(Boardstate *b){
    // https://theartincode.stanis.me/008-djb2/
    unsigned int hash = 5381;

    for(int i = 0; i < (b->maxx * b->maxy); i++){
        hash = ((hash << 5) + hash) + b->board[i]; /* hash * 33 + c */
    }

    return hash;
}

long transposition_index(long hash){
    return hash % NUM_ENTRIES;
}

/* 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, int depth)
{
    long hash = get_hash(b);
    long index = transposition_index(hash);
    Entry table_entry = transposition_table[index];
    if (table_entry.hash == hash && table_entry.stored == 1){
        transposition_hits += 1;
        return table_entry.value;
    }else{
        long new_value = value1(b,player)-value1(b,otherplayer(player));
        if (depth >= table_entry.depth){
            Entry new_entry = {
                    .hash = hash,
                    .depth = depth,
                    .value = new_value,
                    .stored = 1
            };
            transposition_table[index] = new_entry;
        }
        return new_value;

    }
}

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, long alpha, long beta)
{
  *vp=alpha;

  // 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;
            if (depth > 0) {
                long x, y;
                bestmove(depth - 1, b1, &v, &x, &y, -beta, -*vp);
                v = -v;
            } else {
                v = value(b1, player, depth);
            }
            // 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;
                if (*vp >= beta) {
                    return;
                }
            }

            deleteboard(b1);
        }

    }
  return;
}

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

  transposition_table = calloc(NUM_ENTRIES, sizeof(Entry));

  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, -LONG_MAX, LONG_MAX);
  free(transposition_table);
  printf("Best move: %ld %ld Value: %ld\n", bestx+2, besty+2, value);
  printf("Number of Hits in Transposition Table: %d\n", transposition_hits);

    return 0;
}