#include <stdio.h>
#include "othello.h"
extern void fprintf();

extern char *progname;
bool do_move();

/* ======CUT ALL ABOVE THIS LINE WHEN THIS IS MERGED WITH THEGAME.C===== */

int    ABminimize();
int    ABmaximize();
bool   game_ended();
void   get_legal_moves();
Move   *alloc_move();
void    reuse_moves();
Move   *do_legal_moves();
Move   *sort_moves();
Move   *sort_move();
void   count_pieces();
int    statevalue();
int    endvalue();

extern long   rand();
extern long   random();
extern int    getpid();
extern void   exit();
extern void   bcopy();
extern char   *malloc();

/* ======MOVE ALL ABOVE THIS LINE WHEN THIS IS MERGED WITH THEGAME.C===== */


/*
 * Copy the state FROM into the state TO. Also make copies
 * of all lists.
 */

#define copy_state(from, to) \
    bcopy((char *)from, (char *)to, sizeof(State));



/*
 * Return the best move in the current position from the
 * computers limited point of view. If the look-ahead level is
 * equal to one, pick the best move in the list of legal moves.
 *
 * If the search level is deeper, start a minimax search with
 * alfa-beta cuts.
 */

Square
get_best_move(startstate, level)
State   *startstate;
int     level;
{
    Move     *moves;
    Move     *the_move;
    Square   best_sq;
    int      best_val;
    int      val;
    Square   sq;
    int      my_mobility;
    long     randval1;
    long     randval2;

    /* Get a list of all the legal moves in this situation. Since the */
    /* efficiency of the alfa-beta minimax algorithm is very sensitive */
    /* to the ordering of the moves, this list is sorted with the */
    /* the best move first in the list. */
    moves = do_legal_moves(startstate, startstate->neighbors, MYCOLOR,
			   &my_mobility);

    /* If the computer cannot move, then return a pass... */
    if (my_mobility == 0)
	return PASS;

    /* ...else step through the moves and get the best one. This */
    /* is done only when there is more than one move. */
    sq = moves->sq;
    if (my_mobility > 1) {

	best_val = VERY_VERY_BAD;
	the_move = moves;
	while (the_move != NULL) {

	    if (level == 1)
		val = the_move->val;
	    else
		val = ABminimize(the_move, level - 1,
				 best_val, VERY_VERY_GOOD, my_mobility);

/* printf("Value of %d is %d\n", the_move->sq, val);*/
	    if (val > best_val) {
	        best_val = val;
		randval1 = random();
		best_sq = the_move->sq;
	    } else if (val == best_val) {

	        /* Choose randomly between equally good moves. */
	        randval2 = random();
		if (randval2 > randval1) {
		    randval1 = randval2;
		    best_sq = the_move->sq;
		}
	    }
	    the_move = the_move->next;
	}
        sq = best_sq;
    }

    reuse_moves(moves);
    return sq;
}



/*
 * Do the minimizing step in an alfa-beta minimax search.
 */

int
ABminimize(move, level, alfa, beta, my_mobility)
Move   *move;
int    level;
int    alfa;
int    beta;
int    my_mobility;
{
    Move   *moves;
    Move   *the_move;
    int    your_mobility;
    int    val;
    int    best_val;
    
    if (game_ended( &(move->state) ))
	return endvalue( &(move->state) );
	
    moves = do_legal_moves( &(move->state), move->legal_moves,
			   YOURCOLOR, &your_mobility);

    /* bottom of search? */
    if (level == 1) {		
	if (your_mobility == 0)
	    val = move->val;	/* Human couldn't move -> value=last val */
	else
	    val = moves->val;

    } else if (your_mobility == 0) {
	/* Human couldn't make a move */
	if (my_mobility == 0)
	    /* Computer couldn't either last move -> game is over */
	    val = endvalue(&(move->state));
	else
	    /* Human had to pass. */
	    val = ABmaximize(move, level, alfa, VERY_VERY_GOOD,
			     your_mobility);
    } else {
	/* Continue with minimax search */
	best_val = VERY_VERY_GOOD;
	the_move = moves;
	while (the_move != NULL) {
	    val = ABmaximize(the_move, level - 1, alfa, best_val,
			     your_mobility);
	    if (val < best_val)
		best_val = val;
	    if (best_val < alfa)
		break;
	    the_move = the_move->next;
	}
	val = best_val;
    }
    
    reuse_moves(moves);

    return val;
}



int
ABmaximize(move, level, alfa, beta, your_mobility)
Move   *move;
int    level;
int    alfa;
int    beta;
int    your_mobility;
{
    Move   *moves;
    Move   *the_move;
    int    my_mobility;
    int    val;
    int    best_val;

    if (game_ended( &(move->state) ))
	return endvalue(&(move->state));
	
    moves = do_legal_moves( &(move->state), move->legal_moves,
			   MYCOLOR, &my_mobility);

    /* bottom of search? */
    if (level == 1) {		
	if (my_mobility == 0)
	    val = move->val;
	else
	    val = moves->val;

    } else if (my_mobility == 0) {
	/* Computer couldn't make a move */
	if (your_mobility == 0)
	    val = endvalue(&(move->state));
	else
	    val = ABminimize(move, level, VERY_VERY_BAD, beta,
			     my_mobility);

    } else {
	/* Continue with minimax search. */
	best_val = VERY_VERY_BAD;
	the_move = moves;
	while (the_move != NULL) {
	    val = ABminimize(the_move, level - 1, best_val, beta,
			     my_mobility);
	    if (val > best_val)
		best_val = val;
	    if (best_val > beta)
		break;
	    the_move = the_move->next;
	}
	val = best_val;
    }
    
    reuse_moves(moves);

    return val;
}



/*
 * Generate a sorted list of legal moves and their resulting 
 * boards for the player COLOR, starting from the position in 
 * STATE. The squares that should be tried is in the sqlist
 * SQLIST. This is an optimization so we don't have to check all
 * squares in the board.
 *
 * In each of the Move structures, also record the 
 * positions in which the other player can make a move.
 * Return the number of moves that was possible in *NUM_MOVES.
 */

Move *
do_legal_moves(startstate, sqlist, color, num_moves)
State    *startstate;
Sqlist   sqlist;
Color    color;
int      *num_moves;
{
    Move     *legal_moves;
    Move     *move;
    Square   sq;
    sl_traverse(pp);

    *num_moves = 0;
    legal_moves = NULL;
    move = alloc_move(startstate);
    for_all_in_sqlist(sqlist,pp,sq) {
	if ( do_move(&(move->state), sq, color) ) {
	    ++*num_moves;
	    move->sq = sq;

	    /* Link in the move. */
	    move->next = legal_moves;
	    legal_moves = move;

	    move = alloc_move(startstate);
	}
    }
    reuse_moves(move);
    legal_moves = sort_moves(legal_moves, color, *num_moves);

    return legal_moves;
}



/*
 * Return a sorted version of the list of moves MOVELIST. COLOR is
 * the color that made the last move in the positions in the list.
 * MOBILITY is the length of the list, i.e. the number of moves
 * COLOR was able to make in the position just before this one. This
 * is used in the evaluation of the positions when determining the
 * order of the moves.
 */

Move *
sort_moves(movelist, color, mobility)
Move    *movelist;
Color   color;
int     mobility;
{
    Move   *resultlist;
    Move   *move;
    int    other_mobility;

    /* If the list is empty, then there is nothing to sort. */
    if (mobility == 0)
        return NULL;

    /* Get the values for the first element in the sorted list. */
    /* Get all legal moves the other side can make in this position */
    /* and save them. We will have to have these anyhow on the next */
    /* level and we need the number of moves possible in the evaluation */
    /* of the position. */
    resultlist = NULL;
    /* Step throuhg the rest of the moves and sort them into the list. */
    while (movelist != NULL) {
	move = movelist;
	movelist = movelist->next;
	get_legal_moves( &(move->state), OTHER(color),
			 &(move->legal_moves), &other_mobility);
	move->val = statevalue( &(move->state), color,
			        mobility, other_mobility);
	resultlist = sort_move(resultlist, move, color);
    }

    return resultlist;
}

    

/*
 * Return TRUE if MOVE1 was better than MOVE2 for the
 * player with the color COLOR. ( Only used in sort_move() ).
 */

#define better(move1, move2, color) \
    (color == MYCOLOR ? (move1)->val > (move2)->val \
                      : (move1)->val < (move2)->val)

/*
 * Sort MOVE into the sorted list of moves MOVELIST.
 * If COLOR is MYCOLOR then the moves are sorted with the
 * highest value first.
 */

Move *
sort_move(movelist, move, color)
Move    *movelist;
Move    *move;
Color   color;
{
    Move   *mv1;
    Move   *mv2;

    /* Empty list? Return the element itself. */
    if (movelist == NULL) {
	move->next = NULL;
	return move;
    }

    /* Should MOVE be placed first? */
    if (better(move, movelist, color)) {
	move->next = movelist;
	return move;
    }

    /* The general case: put MOVE somewhere in the list. */
    /* 1) Find the proper place. */
    mv1 = movelist;
    while (mv1 != NULL && !better(move, mv1, color)) {
	mv2 = mv1;
	mv1 = mv1->next;
    }
    /* 2) Enter the move. */
    if (mv1 == NULL) {
	move->next = NULL;
	mv2->next = move;
    } else {
	move->next = mv1;
	mv2->next = move;
    }
    
    return movelist;
}


/************************ Move *************************/


/*
 * We want to  malloc() and free() as little as possible, so
 * all used moves are saved in a single linked list to be
 * reused later. OLD_MOVES is the head of this list.
 */

static Move   *old_moves = NULL; /* list of reusable Moves. */


/*
 * Return a pointer to a move. If there are no old moves to
 * reuse, malloc() one. Set the 'next' field of the move to
 * NULL.
 */

Move *
alloc_move(state)
State   *state;
{
    Move   *move;

    /* Reuse an old move if possible. */
    if (old_moves == NULL) {
	move = (Move *) malloc(sizeof(Move));
	if (move == NULL) {
	    fprintf(stderr, "%s: couldn't allocate space for a move\n",
		    progname);
	    exit(1);
	}
    } else {
	move = old_moves;
	old_moves = old_moves->next;
    }

    copy_state(state, &(move->state));
    move->next = NULL;

    return move;
}



/*
 * Take a list of moves and put them on the list of old moves
 * to be reused.
 */

void
reuse_moves(movelist)
Move   *movelist;
{
    Move   *next;

    while (movelist != NULL) {
	next = movelist->next;
	movelist->next = old_moves;
	old_moves = movelist;
	movelist = next;
    }
}


/************************ State *************************/


/*
 * This board decides how valuable each square is. The corners
 * don't have any points assigned to them because this is taken
 * care of by the dead piece calculation.
 */

/*int   value_board[] = {
      0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
      0,   0, -20,  19,  13,  13,  19, -20,   0,   0,
      0, -20, -52,  -8, -10, -10,  -8, -52, -20,   0,
      0,  19,  -8,   3,   0,   0,   3,  -8,  19,   0,
      0,  13, -10,   0,  -2,  -2,   0, -10,  13,   0,
      0,  13, -10,   0,  -2,  -2,   0, -10,  13,   0,
      0,  19,  -8,   3,   0,   0,   3,  -8,  19,   0,
      0, -20, -52,  -8, -10, -10,  -8, -52, -20,   0,
      0,   0, -20,  19,  13,  13,  19, -20,   0,   0,
      0,   0,   0,   0,   0,   0,   0,   0,   0,   0
};
*/
int   value_board[] = {
      0,   0,   0,   0,   0,   0,   0,   0,   0,   0,
      0,   0, -20,  19,  13,  13,  19, -20,   0,   0,
      0, -20, -52,  -8, -10, -10,  -8, -52, -20,   0,
      0,  19,  -8,   0,   0,   0,   0,  -8,  19,   0,
      0,  13, -10,   0,   0,   0,   0, -10,  13,   0,
      0,  13, -10,   0,   0,   0,   0, -10,  13,   0,
      0,  19,  -8,   0,   0,   0,   0,  -8,  19,   0,
      0, -20, -52,  -8, -10, -10,  -8, -52, -20,   0,
      0,   0, -20,  19,  13,  13,  19, -20,   0,   0,
      0,   0,   0,   0,   0,   0,   0,   0,   0,   0
};
#define squarevalue(square)   value_board[square]

int    stabilityvalue = 200;	/* value per stable piece */
int    mobilityvalue = 75;	/* max total value for mobility  */



/*
 * Calculate the static value of the position in STATE.
 * COLOR is the color that just made the move, MOBILITY
 * is the number of moves he could make, and OTHER_MOBILITY
 * is the number of moves that the opponent can make
 * from this state.
 */

int
statevalue(state, color, mobility, other_mobility)
State   *state;
Color   color;
int     mobility;
int     other_mobility;
{
    int      val;
    int      mobval;
    bool     i_have_none;
    bool     you_have_none;
    int      my_unstable;
    int      your_unstable;
    Square   sq;
    int      i, j;

    i_have_none =   !state->mystable;
    you_have_none = !state->yourstable;
/*    printf("my=%d your=%d mob=%d othermob=%d   ",
	   state->mystable, state->yourstable,
	   mobility, other_mobility);*/
    my_unstable = 0;
    your_unstable = 0;
    val = 0;
    
    for (i = 1; i <= 8; ++i) {
	for (j = 1; j <= 8; ++j) {
	    sq = SQ(i, j);
	    if (!member(state->stablepieces, sq)) {
		if (state->board[sq] == MYCOLOR) {
		    val += squarevalue(sq);
		    ++my_unstable;
		    i_have_none = FALSE;
		} else if (state->board[sq] == YOURCOLOR) {
		    val -= squarevalue(sq);
		    ++your_unstable;
		    you_have_none = FALSE;
		}
	    }
	}
    }

    /* If the game is ended, return a value for it. */
    /* This is the same evaluation as endvalue() gives. */
    if (i_have_none || you_have_none) {
	val = (i_have_none ? VERY_BAD : VERY_GOOD)
	        + state->mystable + my_unstable
		- state->yourstable - your_unstable;
/*printf("Value = %d\n", val);*/
	return val;
    }

    /* The general case: evaluate the two main factors, */
    /* stable pieces and mobility. */
    val += stabilityvalue * (state->mystable - state->yourstable);
    mobval = (mobilityvalue * (mobility - other_mobility))
             / (mobility + other_mobility + 2);
    if (color == MYCOLOR)
	val += mobval;
    else
	val -= mobval;
/*printf("Value = %d\n", val);*/
    return val;
}

	    

/*
 * This function returns the value of a position at the end of
 * a game. This is simpler to calculate since we only have to
 * count pieces and not take into consideration strategic
 * properties.
 */

int
endvalue(state)
State   *state;
{
    int   my;
    int   yours;

    count_pieces(state, &my, &yours);
    if (my > yours)
	return VERY_GOOD + my - yours;
    else if (my < yours)
	return VERY_BAD + my - yours;
    else
	return 0;
}