#include <stdio.h>
#ifdef __GNUC__
#include "clib.h"
#endif
#include "othello.h"


/* ================================================================ */
/*               A very simple bit vector package                   */


#define BITMAP(name, num_bits) \
    unsigned short   name[num_bits / 16 + 1]


#define SETBIT(arr, bit) \
    (arr[bit >> 4] |= bits[bit & 15])

#define CLEARBIT(arr, bit) \
    (arr[bit >> 4] &= ~bits[bit & 15])

#define TESTBIT(arr, bit) \
    (arr[bit >> 4] & bits[bit & 15])

#define ZERO(arr, numbits) \
    { int   i; \
      for (i = 0; i < numbits / 16 + 1; ++i) \
          arr[i] = 0; \
    }

unsigned short bits[16] = {
    0x0001, 0x0002, 0x0004, 0x0008,
    0x0010, 0x0020, 0x0040, 0x0080,
    0x0100, 0x0200, 0x0400, 0x0800,
    0x1000, 0x2000, 0x4000, 0x8000
};


/* ================================================================ */


short   edgeval_me_to_move[6561];
short   edgeval_you_to_move[6561];

BITMAP(convergedbits_me,  6561);
BITMAP(convergedbits_you, 6561);
BITMAP(use_staticval,     6561);

typedef Color   Row[10];
static Row   tempedge;

static int   get_score_my_move();
static int   get_score_your_move();


/* ================================================================ */


static int
get_index(row)
Row   row;
{
    int   index;
    int   i;

    index = 0;
    for (i = 1; i <= 8; ++i) {
	index *= 3;
	if (row[i] != EMPTY)
	    index += (row[i] == MYCOLOR ? 1 : 2);
    }

    return index;
}



/*
 * Store static values for all the position in tempedge[] into the
 * table edgeval_me_to_move[].
 */

#define   STABLE       0	/* Can never be turned */
#define   SEMISTABLE   1	/* Cannot be immediately turned */
#define   UNSTABLE     2	/* Can be turned next move */
#define   UNKNOWN      3	/* We don't know which yet */

static void
store_static_val()
{
    char    classes[10];
    Color   temp[10];
    bool    full;
    int     index;
    int     val;
    int     i;

    /* Classify the pieces in the square. */
    for (i = 1; i <= 8; ++i)
	classes[i] = UNKNOWN;

    /* Start with the UNSTABLE pieces. */
    for (i = 1; i <= 8; ++i) {

	/* If a square is empty, mark those pieces that are turned */
	/* when the computer puts a piece there as UNSTABLE. */
	if (temp[i] == EMPTY) {

	    /* try to turn pieces to the left. */
	    index = i;
	    while (tempedge[--index] == YOURCOLOR)
		/* NOTHING */;
	    if (tempedge[index] == MYCOLOR && index < i - 1) {
		while (++index != i)
		    classes[index] = UNSTABLE;
	    }

	    /* try to turn pieces to the right. */
	    index = i;
	    while (tempedge[++index] == YOURCOLOR)
		/* NOTHING */;
	    if (tempedge[index] == MYCOLOR && index > i + 1) {
		while (--index != i)
		    classes[index] = UNSTABLE;
	    }
	}
    }

    /* Now, check which pieces are STABLE. Start with a check */
    /* if all positions in the row are occupied. If so, all pieces */
    /* are stable. Otherwise, start with the ones in the corners */
    /* and proceed towards the center. */
    for (i = 1; (i <= 8) && (tempedge[i] != EMPTY); ++i)
	/* NOTHING */;
    if (i == 9) {
	full = TRUE;
	for (i = 1; i <= 8; ++i)
	    classes[i] = STABLE;
    } else {
	full = FALSE;
	if (tempedge[1] != EMPTY) {
	    for (i = 1; tempedge[i] == tempedge[1]; ++i)
		classes[i] = STABLE;
	}
	if (tempedge[8] != EMPTY) {
	    for (i = 8; tempedge[i] == tempedge[8]; --i)
		classes[i] = STABLE;
	}
    }
    
    /* Here we could go on and check for more stable pieces, but */
    /* we let it be for now, and may come back some other time and */
    /* improve this code. */


    /* All pieces that aren't STABLE or UNSTABLE are SEMISTABLE. */
    for (i = 1; i <=8; ++i) {
	if (classes[i] == UNKNOWN && tempedge[i] != EMPTY)
	    classes[i] = SEMISTABLE;
    }

    /* OK, now we have classified the edge, let's see what score */
    /* we assign to it. Note that each stable piece gets 100 additional */
    /* points in the function statevalue(). */
    {
	static int   initvals[3][8] = {
	    {600, 1100, 900, 900, 900, 900, 1100, 600}, /* STABLE */
	    {  0,  200, 200, 200, 200, 200,  200,   0}, /* SEMISTABLE */
	    {  0,  -25,  75,  50,  50,  75,  -25,   0}}; /* UNSTABLE */

	val = 0;
	for (i = 1; i <= 8; ++i) {
	    if (tempedge[i] != EMPTY) {
		val += (tempedge[i] == MYCOLOR ? 1 : -1)
		    * initvals[classes[i]][i - 1];
	    }
	}
    }
    
    index = get_index(tempedge);
    edgeval_me_to_move[index] = val;
    if (full) {
	SETBIT(convergedbits_me,  index);
	SETBIT(convergedbits_you, index);
    }
}


static void
init_static(piece)
int   piece;
{
    static Color   colors[] = {EMPTY, MYCOLOR, YOURCOLOR};
    int   i;

    for (i = 0; i < 3; ++i) {
	tempedge[piece] = colors[i];

	if (piece < 8)
	    init_static(piece + 1);
	else
	    store_static_val();
    }
}


/* ================================================================ */


static void
invert_row(result, arg)
Row   result;
Row   arg;
{
    int   i;

    for (i = 0; i < 10; ++i) {
	if (arg[i] == MYCOLOR || arg[i] == YOURCOLOR)
	    result[i] = OTHER(arg[i]);
	else
	    result[i] = arg[i];
    }
}

    
static int
combine_values(scores, probabilities, num_squares)
int   scores[9];
int   probabilities[9];
int   num_squares;
{
    int   best_legal_score;
    int   value;
    int   remaining_prob;
    int   i;
    int   j;
    int   temp;

    /* First sort all moves in descending order with respect to score. */
    /* Bubble sort should be sufficient. */
    for (i = 0; i < num_squares - 1; ++i) {
	for (j = i + 1; j < num_squares; ++j) {
	    if (scores[i] < scores[j]) {
		temp = scores[i];
		scores[i] = scores[j];
		scores[j] = temp;
		temp = probabilities[i];
		probabilities[i] = probabilities[j];
		probabilities[j] = temp;
	    }
	}
    }

    /* Then, find the score for the best legal move. */
    best_legal_score = -999999;
    for (i = 0; i < num_squares; ++i) {
	if (probabilities[i] == 100 && scores[i] > best_legal_score)
	    best_legal_score = scores[i];
    }

    value = 0;
    remaining_prob = 100;
    for (i = 0; i < num_squares && scores[i] >= best_legal_score; ++i) {
	if (probabilities[i] != 100) {
	    value += probabilities[i] * remaining_prob * scores[i] / 100;
	    remaining_prob -= probabilities[i] * remaining_prob / 100;
	}
    }
    
    if (best_legal_score != -999999)
	value += remaining_prob * best_legal_score;

    return value / 100;
}


/*
 * Try to make a move for color COLOR and turn the pieces in 
 * direction DIR starting from square SQ and return TRUE if
 * it was legal.
 */

static bool
turnpieces(row, sq, dir, color)
Row     row;
int     sq;
int     dir;
Color   color;
{
    bool   legal_move;
    int    i;

    /* try to turn pieces to the left. */
    legal_move = FALSE;
    i = sq + dir;
    while (row[i] == OTHER(color))
	i += dir;

    if (row[i] == color && i !=  sq + dir) {
	legal_move = TRUE;
	i -= dir;
	while (i != sq) {
	    row[i] = color;
	    i -= dir;
	}
    }

    return legal_move;
}
	

/*
 * Return the probability that the computer will be able to move to sq 
 * before the human does so. These figures are totally guesswork. They
 * should be measured somehow.
 *
 * Also, when this function is called we know that it is not legal
 * to make a direct move to SQ.
 */

static int
get_probability(row, sq)
Row   row;
int   sq;
{
    static int   probs[8] = {2, 10, 15, 15, 15, 15, 10, 2};
    Row   row2;
    int   i;

    for (i = 0; i <= 9; ++i)
	row2[i] = row[i];

    /* If the human can put a piece on SQ and this gives him a better */
    /* position than not doing it, it is very unlikey that the  */
    /* computer will be able to play there first. */
/*    if (turnpieces(row2, sq, -1, YOURCOLOR)
	| turnpieces(row2, sq, 1, YOURCOLOR)) {
	if ( get_score_my_move(row2) < edgeval_you_to_move[get_index(row)] )
	    return 3;
	else 
	    return 50;
    }
*/
    if (row[sq - 1] == row[sq + 1] && row[sq - 1] != EMPTY) {
	if (row[sq - 1] == MYCOLOR)
	    return 5;
	else
	    return 50;
    } else
	return probs[sq - 1];
}


static int
analyze_pattern(edge)
Row   edge;
{
    int    num_squares;
    int    scores[9];
    int    probabilities[9];
    Row    temp;
    bool   legal_move;
    int    value;
    int    index;
    int    sq;
    int    i;
    
    /* If the pattern in edge is already analyzed, return the score */
    /* immediately. */
    index = get_index(edge);
    if (TESTBIT(convergedbits_me, index))
	return edgeval_me_to_move[index];

    temp[0] = BORDER;
    temp[9] = BORDER;

    /* Check each square on the edge and see if it is legal to */
    /* move there by flipping edge pieces. If so, flip the affected */
    /* pieces, retrieve the score for the resulting position by */
    /* a recursive call to analyze_pattern() and store the score */
    /* in scores[].*/

    /* Start with NOMOVE. It is always a legal move, thus probability 100. */
    probabilities[0] = 100;
    if (TESTBIT(use_staticval, index)) {
	scores[0] = edgeval_me_to_move[index];
    } else {
	SETBIT(use_staticval, index);
	scores[0] = get_score_your_move(edge);
	CLEARBIT(use_staticval, index);
    }

    num_squares = 1;

    /* Now continue with the possible and legal moves. */
    for (sq = 1; sq <= 8; ++sq) {

	if (edge[sq] != EMPTY) 
	    continue;

	/* Start by analyzing what happens when the human puts a piece on */
	/* the board. */
	for (i = 1; i <= 8; ++i)
	    temp[i] = edge[i];
	temp[sq] = YOURCOLOR;
	(void) analyze_pattern(temp);

	/* Get the original pattern back. */
	temp[sq] = EMPTY;

	/* try to do a move on the square SQ. */
	/* If the move was legal, get the score of the new position. */
	/* If not, the move might be possible anyhow because of the */
	/* situation out at the board. */
	/* Store the probability for being able to move to the */
	/* square in probabilities[]; */
	legal_move = turnpieces(temp, sq, -1, MYCOLOR)
	    | turnpieces(temp, sq, 1, MYCOLOR);

	if (legal_move)
	    probabilities[num_squares] = 100;
	else {
	    probabilities[num_squares] = get_probability(temp, sq);
	}
	temp[sq] = MYCOLOR;
	scores[num_squares++] = get_score_your_move(temp);
    }

    /* Now we combine all possible and legal moves and their scores */
    /* into one value for the position in edge[]. This value is stored */
    /* edgeval_me_to_move[] and returned. The position is marked as */
    /* having converged. */
    value = combine_values(scores, probabilities, num_squares);
    edgeval_me_to_move[index] = value;
    SETBIT(convergedbits_me, index);

    invert_row(temp, edge);
    index = get_index(temp);
    edgeval_you_to_move[index] = -value;
    SETBIT(convergedbits_you, index);

    return value;
}



static int
get_score_my_move(row)
Row   row;
{
    int   index;

    index = get_index(row);
    if (!TESTBIT(convergedbits_me, index))
	analyze_pattern(row);
    
    return edgeval_me_to_move[index];
}


static int
get_score_your_move(row)
Row   row;
{
    int   index;
    Row   row2;

    index = get_index(row);
    if (!TESTBIT(convergedbits_you, index)) {
	invert_row(row2, row);
	analyze_pattern(row2);
    }
    
    return edgeval_you_to_move[index];
}



/*
 * Store the correct value into the table edgeval_you_to_move[] by taking
 * the value from edgeval_me_to_move[] with the colors for the index
 * reversed. Since the original value is calculated with the pieces reversed,
 * we also have to negate the value.
 */

static void
store_other_table()
{
    int   index_me;
    int   index_you;
    int   i;

    index_me = 0;
    index_you = 0;
    for (i = 1; i <= 8; ++i) {
	index_me *= 3;
	index_you *= 3;
	if (tempedge[i] != EMPTY) {
	    index_me += (tempedge[i] == MYCOLOR ? 1 : 2);
	    index_you += (tempedge[i] == MYCOLOR ? 2 : 1);
	}
    }
    
    edgeval_you_to_move[index_you] = -edgeval_me_to_move[index_me];
}


static void
init_other_table(piece)
int   piece;
{
    static Color   colors[] = {EMPTY, MYCOLOR, YOURCOLOR};
    int   i;

    for (i = 0; i < 3; ++i) {
	tempedge[piece] = colors[i];

	if (piece < 8)
	    init_other_table(piece + 1);
	else
	    store_other_table();
    }
}


/* ================================================================ */


void
init_edgevals()
{
    int   i;

    /* Initialize edgeval_me_to_move with static values. */
    tempedge[0] = BORDER;
    tempedge[9] = BORDER;
    ZERO(edgeval_me_to_move, 6561);
    ZERO(edgeval_you_to_move, 6561);
    ZERO(use_staticval, 6561)
    init_static(1);
    init_other_table(1);

    /* Now we do a dynamic analysis of the patterns in the table, */
    /* i.e. we check which positions can emerge from each start position */
    /* and evaluate them. The values will be merged into the score */
    /* for the originial position. */
    for (i = 1; i <= 8; ++i)
	tempedge[i] = EMPTY;
    analyze_pattern(tempedge);
}



int
get_edgeindex_row1(state)
State   *state;
{
    int   index;
    int   i;

    index = 0;
    for (i = 11; i < 19; ++i) {
	index *= 3;
	if (state->board[i] != EMPTY)
	    index += state->board[i] == MYCOLOR ? 1 : 2;
    }

    return index;
}


int
get_edgeindex_row8(state)
State   *state;
{
    int   index;
    int   i;

    index = 0;
    for (i = 81; i < 89; ++i) {
	index *= 3;
	if (state->board[i] != EMPTY)
	    index += state->board[i] == MYCOLOR ? 1 : 2;
    }

    return index;
}


int
get_edgeindex_col1(state)
State   *state;
{
    int   index;
    int   i;

    index = 0;
    for (i = 11; i < 90; i += 10) {
	index *= 3;
    	if (state->board[i] != EMPTY)
	    index += state->board[i] == MYCOLOR ? 1 : 2;
    }

    return index;
}


int
get_edgeindex_col8(state)
State   *state;
{
    int   index;
    int   i;

    index = 0;
    for (i = 18; i < 90; i += 10) {
	index *= 3;
    	if (state->board[i] != EMPTY)
	    index += state->board[i] == MYCOLOR ? 1 : 2;
    }

    return index;
}