/*
* This AI works with a combination of minimizing losses, 
* evaluating and pruning a minimax-tree and square-value avaluation.
*
* All features can be tuned with the parameters in the beginning of the file.
*/

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include "board.h"
#include "game.h"
#include "player.h"
#include "util.h"

//#define float float_t

/* 
* Tune these for performance
* INITIAL_GAME_TREE_DEPTH must be >= 2
*/
// -------- Game Tree building --------
// - normal parameters -
#define INITIAL_GAME_TREE_DEPTH 4
#define BRANCHING_FACTOR 3

// Game tree extension:
#define EXTEND_GT_TIMES 2
#define EXTEND_DEPTH 1
#define EXTEND_BRANCHING_FACTOR 2

// - end-game parameters -
#define END_GAME_THRESHOLD 10

#define EG_INITIAL_GAME_TREE_DEPTH 10
#define EG_BRANCHING_FACTOR 3

// Game tree extension:
#define EG_EXTEND_GT_TIMES 0
#define EG_EXTEND_DEPTH 1
#define EG_EXTEND_BRANCHING_FACTOR 2

// -------- Desicion making coefficients --------
// worst case from initial game tree
#define WC_CE 5.0
// Minimax average from extended game tree
#define MM_CE 10.0
// Mobility factor out of two levels of initial game tree
#define MO_CE 1.5

// Same for end-game
#define EG_WC_CE 1.0
#define EG_MM_CE 0.0

// A smaller MOBILITY_COEFFICIENT gives mobility a bigger effect (~4)
#define MOBILITY_COEFFICIENT 4

// -------- Values for different square types --------
#define DEFAULT_SQUARE_VALUE 1
#define EDGE_CENTER_VALUE 2
#define CENTER_VALUE 0.5
#define CORNER_VALUE 35
#define X_SQUARE_VALUE -10
#define C_SQUARE_VALUE -2
#define EDGE_CONTROL_VALUE 5
// because some squares have nagative values, there must an offset to
// avoid false value ratios. e.g. 10/-5 == -10/5
// SCORE_OFFSET makes all scores positive
#define SCORE_OFFSET 50
// maximum value for any board ratio
#define MAX_POINTS 300

/* --------- Game State ------------- */
typedef struct GameState_s {
	struct Game *game;
	float value;
} *GameState;

/** Construct new gamestate from game **/
GameState gameStateConstruct(struct Game* game);

/** Destruct gameState **/
void gameStateDestruct(GameState state);

/** Free resources used by Game-pointer in gamestate **/
void gameStateFreeGame(GameState state);

/** calculate disc-square table **/
float** getSquareValues(struct Game const* game, int player);

/** destruct disc-square table **/
void squareValuesDestruct(float** values);

/** tell if game is starting to end **/
int isEndGame(struct Game const* game);

/** calculate value for current game state in tree according to disc-square table **/
void gameStateCalculateValue(GameState state, int player);

/** calculate value for current game state in tree according to raw score ratio **/
void gameStateCalculateValueRaw(GameState state, int player);

/* ------------- (Game) Tree: ------------- */
// Data abstraction
typedef GameState Data;
#define dataDestruct gameStateDestruct

typedef struct Tree_s {
	Data data;
	struct Tree_s* parent;
	struct Tree_s** children;
	unsigned int num_children; // number of children
	unsigned int num_child;    // tree is num_child:st child of parent
} *Tree;

/** construct new tree with data in it **/
Tree treeConstruct(Data data);

/**  add child to tree **/
void treeAddChild(Tree tree, Tree child);

/** Remove (and destruct) tree **/
void treeRemove(Tree tree);

/** Detach tree from parent **/
void treeDetach(Tree tree);

/** Destruct tree **/
void treeDestruct(Tree tree);

/** get last child at far left **/
Tree treeGetFirstLeaf(Tree tree);

/** get next leaf **/
Tree treeGetNextLeaf(Tree tree);

/** Get first child of tree **/
Tree treeGetFirstChild(Tree tree);

/** get next sibling **/
Tree treeGetNextSibling(Tree tree);

/** return 1 if tree is descendant of ancestor, else 0 **/
int treeIsDescendantOf(Tree tree, Tree ancestor);

/** return 1 if parent has child child, else 0 **/
int treeHasChild(Tree parent, Tree child);

/*  ------------- Initial moves ------------------- */
typedef struct InitialMove_s {
	int elements; // number of elements
	Tree *trees; // trees corrensponding to moves
	struct Coord *moves; // coordinates of moves
	float *wc_values; // worst-case-values
	float *mm_values; // minimax-pruned values
	float *mobility_factors;
} *InitialMove;

/** Construct new set of initial moves **/
InitialMove initialMoveConstruct(void);

/** add a new move **/
void initialMoveAdd(InitialMove im, Tree tree, struct Coord move);

/** remove all "dead" trees from initial move -sets **/
void initialMoveUpdate(InitialMove im, Tree root);

/** evaluate worst case values for initial moves **/
void initialMoveEvaluateWC(InitialMove im);

/** evaluate minimax values for initial moves (worst case) **/
void initialMoveEvaluateMM(InitialMove im);

/** evaluate mobility coefficient **/
void initialMoveEvaluateMobility(InitialMove im);

/** Destruct set of moves **/
void initialMoveDestruct(InitialMove im);

/* ----------Game tree buildining & pruning   ----------------- **/
/** build a game tree depth high, scores corresponding to player.
*   Save initial moves into moves if moves != NULL
**/
void buildGameTree(Tree tree, int depth, int player, InitialMove im, int endgame);

/** Extend game tree. New game trees are built downwars from leaves of tree.
*   New trees are depth deep and have branching factor of brancing_factor.
*   current_depth is depth in whole game tree (current state depth = 0)
**/
void extendGameTree(Tree tree, int current_depth, int depth, int branching_factor, int player, int endgame);

/** Populate game-tree node with children representing all valid moves.
*   Save initial moves into moves if moves != NULL
**/
int treePopulateNode(Tree tree, InitialMove moves);

/** Prune game tree using minimax method **/
void pruneMinimax(Tree tree, unsigned int branching_factor, int invert);
void pruneMin(Tree tree, unsigned int branching_factor);
void pruneMax(Tree tree, unsigned int branching_factor);

/** calculate tree values according to worst case from children (recursive) **/
float treeUpdateValues(Tree root);

/*
* "Main" functions.
*/
/** Get best possible move from inital move structure **/
struct Coord getBestMove(InitialMove im);

/** Get best possible move from inital move structure for end game **/
struct Coord getBestMoveEG(InitialMove im);

/** Play as player, using artificial intelligence. Returns the player's move. **/
struct Coord aiPlay(struct Game const* game) {
	struct Coord best_move_coords;
	InitialMove im;
	int player = gameCurrentPlayer(game);
	
	Data data = gameStateConstruct(gameCopy(game));
	Tree root = treeConstruct(data);
	im = initialMoveConstruct();
	
	if (!isEndGame(game)) {
		// Build & prune initial game tree
		buildGameTree(root, INITIAL_GAME_TREE_DEPTH, player, im, 0);
		
		// evaluate worst case and mobility
		initialMoveEvaluateWC(im);
		initialMoveEvaluateMobility(im);
		
		// prune initial game tree
		pruneMinimax(root, BRANCHING_FACTOR, 0);
		initialMoveUpdate(im, root);
		
		// Extend while pruning
		int depth = INITIAL_GAME_TREE_DEPTH;
		for (int i = 0; i < EXTEND_GT_TIMES; i++) {
			extendGameTree(root, depth, EXTEND_DEPTH, EXTEND_BRANCHING_FACTOR, player, 0);
			depth += EXTEND_DEPTH;
		}
		
		// evaluate minimax-value
		initialMoveEvaluateMM(im);
		
		best_move_coords = getBestMove(im);
	} else {
		// Build & prune initial game tree
		buildGameTree(root, EG_INITIAL_GAME_TREE_DEPTH, player, im, 1);
		
		// evaluate worst case and mobility
		initialMoveEvaluateWC(im);
		
		// prune initial game tree
		pruneMinimax(root, EG_BRANCHING_FACTOR, 0);
		initialMoveUpdate(im, root);
		
		// Extend while pruning
		int depth = INITIAL_GAME_TREE_DEPTH;
		for (int i = 0; i < EG_EXTEND_GT_TIMES; i++) {
			extendGameTree(root, depth, EG_EXTEND_DEPTH, EG_EXTEND_BRANCHING_FACTOR, player, 1);
			depth += EG_EXTEND_DEPTH;
		}
		
		// evaluate minimax-value
		initialMoveEvaluateMM(im);
		
		best_move_coords = getBestMoveEG(im);
	}
	
	// Clean up
	initialMoveDestruct(im);
	treeDestruct(root);
	
	return best_move_coords;
}

struct Coord getBestMove(InitialMove im) {
	float best_value = 0, value;
	struct Coord best_move;

	for(int i = 0; i < im->elements; i++) {
		value = (WC_CE * im->wc_values[i] +
			MM_CE * im->wc_values[i] +
			MO_CE * im->mobility_factors[i])
			/ (WC_CE + MM_CE + MO_CE);
		if (value > best_value) {
			best_value = value;
			best_move = im->moves[i];
		}
	}
	
	return best_move;
}

struct Coord getBestMoveEG(InitialMove im) {
	float best_value = 0, value;
	struct Coord best_move;

	for(int i = 0; i < im->elements; i++) {
		value = (EG_WC_CE * im->wc_values[i] +
			 EG_MM_CE * im->wc_values[i])
			/ (EG_WC_CE + EG_MM_CE);
		if (value > best_value) {
			best_value = value;
			best_move = im->moves[i];
		}
	}
	
	return best_move;
}

/*
* Game tree pruning and building
*/
void buildGameTree(Tree tree, int depth, int player, InitialMove im, int endgame) {
	int game_end = 0;
	Tree root = tree;
	
	// first moves
	game_end = treePopulateNode(tree, im);
	
	for (int i = 0; i < depth && !game_end; i++) {
		tree = treeGetFirstLeaf(root);
		do {
			game_end = treePopulateNode(tree, NULL);
		} while((tree = treeGetNextLeaf(tree)) && treeIsDescendantOf(tree, root));
	}
	
	// Calulate values for leaves
	tree = treeGetFirstLeaf(root);
	do {
		if (endgame) {
			gameStateCalculateValueRaw(tree->data, player);
		} else {
			gameStateCalculateValue(tree->data, player);
		}
	} while((tree = treeGetNextLeaf(tree)) && treeIsDescendantOf(tree, root));
	
	// Calculate in-tree-values for nodes to correspond to worst possible case
	treeUpdateValues(root);
}

void extendGameTree(Tree tree, int current_depth, int depth, int branching_factor, int player, int endgame) {
	Tree root = tree;
	int invert = current_depth % 2;

	tree = treeGetFirstLeaf(tree);
	do {
		buildGameTree(tree, depth, player, NULL, endgame);
		treeUpdateValues(tree);
		pruneMinimax(tree, branching_factor, invert);
		
	} while((tree = treeGetNextLeaf(tree)) && treeIsDescendantOf(tree, root));
	
}

int treePopulateNode(Tree tree, InitialMove moves) {
	unsigned int x, y;
	struct Coord move;
	int game_end = 0;
	int flips;
	
	if(!gameCurrentPlayer(tree->data->game)) return -1;
	
	// Go through each square
	for (x = 0; x < 8; x++) {
		for (y = 0; y < 8; y++) {
			move = coord(x, y);
			if((flips = gameNumFlips(tree->data->game, move)) == 0) {
				continue; // Move not valid
			}
			
			struct Game *new_game = gameCopy(tree->data->game);
			game_end = gamePlayCurrent(new_game, move);
			Data data = gameStateConstruct(new_game);
			Tree child = treeConstruct(data);
			treeAddChild(tree, child);
			
			if (moves) initialMoveAdd(moves, child, move);	
			
			// If one player wins, the minimax is worst in any case...
			if (game_end) break;
		}
		if (game_end) break;
	}
	
	// Destruct game to save memory...
	gameStateFreeGame(tree->data);
	return game_end;
}

void pruneMinimax(Tree tree, unsigned int branching_factor, int invert) {
	if (tree->num_children == 0) return;
	
	Tree child;
	
	// prune
	if(!invert) {
		pruneMin(tree, branching_factor);
	} else {
		pruneMax(tree, branching_factor);
	}
	
	// invert 'invert'
	invert = (invert + 1) % 2;
	child = tree->children[0];
	do {
		pruneMinimax(child, branching_factor, invert);
	} while ((child = treeGetNextSibling(child)));
}

void pruneMin(Tree tree, unsigned int branching_factor) {
	if (tree->num_children == 0) return;
	
	Tree child, min_child = NULL;
	float min_value, value;
	while (tree->num_children > branching_factor) {
		min_value = INFINITY;
		child = tree->children[0];
		do {
			value = child->data->value;
			if (value < min_value) {
				min_value = value;
				min_child = child;
			} else if( value == min_value) { // Pseudo-random replace
				if(((unsigned int)((7 +  2 * tree->num_child) * value)) % 2) {
					min_child = child;
				}
			}
		} while ((child = treeGetNextSibling(child)));
		
		treeRemove(min_child);
	}
}

void pruneMax(Tree tree, unsigned int branching_factor) {
	if (tree->num_children == 0) return;
	
	Tree child, max_child = NULL;
	float max_value, value;
	while (tree->num_children > branching_factor) {
		max_value = 0;
		child = tree->children[0];
		do {
			value = child->data->value;
			if (value > max_value) {
				max_value = value;
				max_child = child;
			} else if( value == max_value) { // Pseudo-random replace
				if(((unsigned int)((7 +  2 * tree->num_child) * value)) % 2) {
					max_child = child;
				}
			}
		} while ((child = treeGetNextSibling(child)));
		
		treeRemove(max_child);
	}	
}

float treeUpdateValues(Tree root) {
	float min_value = INFINITY, child_value;
	
	for (unsigned int i = 0; i < root->num_children; i++) {
		child_value = treeUpdateValues(root->children[i]);
		if (child_value < min_value) {
			min_value = child_value;
		}
	}
	if (min_value < INFINITY) {
		root->data->value = min_value;
	}
	return root->data->value;
}


/* Game state functions:
* struct GameState_s {
*	struct Game *game;
*	float value;
* };
*/
GameState gameStateConstruct(struct Game* game) {
	GameState game_state = (GameState) malloc(sizeof(struct GameState_s));
	game_state->game = game;
	game_state->value = -1;
	
	return game_state;
}

void gameStateDestruct(GameState state) {
	if (state->game != NULL) {
		gameDestruct(state->game);
	}
	free(state);
}

void gameStateFreeGame(GameState state) {
	if (state->game != NULL) {
		gameDestruct(state->game);
	}
	state->game = NULL;
}

void gameStateCalculateValue(GameState state, int player) {
	unsigned int x, y;
	int square_type;
	struct Coord coord;
	float my_points = 0, opponent_points = 0;
	
	float** my_matrix = getSquareValues(state->game, player);
	float** opponent_matrix = getSquareValues(state->game, (player % 2) + 1);
	
	for (x = 0; x < 8; x++) {
		for (y = 0; y < 8; y++) {
			coord.x = x;
			coord.y = y;
			square_type = gameSquareType(state->game, coord);
			if (square_type == player) {
				my_points += my_matrix[x][y];
			} else if (square_type != 0) {
				opponent_points += opponent_matrix[x][y];
			}
		}
	}
	
	squareValuesDestruct(my_matrix);
	squareValuesDestruct(opponent_matrix);
	
	// Apply offset to avoid negative ratios:
	my_points += SCORE_OFFSET;
	opponent_points += SCORE_OFFSET;
	
	if (opponent_points == 0) { // avoid div-by-zero
		state->value = MAX_POINTS;
		return;
	}
	
	state->value = my_points / opponent_points;
}

void gameStateCalculateValueRaw(GameState state, int player) {
	unsigned int x, y;
	int square_type;
	struct Coord coord;
	float my_points = 0, opponent_points = 0;
	
	for (x = 0; x < 8; x++) {
		for (y = 0; y < 8; y++) {
			coord.x = x;
			coord.y = y;
			square_type = gameSquareType(state->game, coord);
			if (square_type == player) {
				my_points++;
			} else if (square_type != 0) {
				opponent_points++;
			}
		}
	}
	
	if (opponent_points == 0) { // avoid div-by-zero
		state->value = MAX_POINTS;
		return;
	}
	
	state->value = my_points / opponent_points;
}

float** getSquareValues(struct Game const* game, int player) {
	int opponent = (player % 2) + 1;
	
	float **matrix = (float**) malloc(8 * sizeof(float*));
	for (int i = 0; i < 8; i++) {
		matrix[i] = (float*) malloc(8 * sizeof(float));
	}
	for(int x = 0; x < 8; x++) {
		for(int y = 0; y < 8; y++) {
			matrix[x][y] = DEFAULT_SQUARE_VALUE;
		}
	}
	
	// Give edge centers and center squares values
	matrix[0][3] = matrix[0][4] = matrix[7][3] = matrix[7][4] =
	matrix[3][0] = matrix[4][0] = matrix[3][7] = matrix[4][7] = EDGE_CENTER_VALUE;
	
	matrix[3][3] = matrix[3][4] = matrix[4][3] = matrix[4][4] = CENTER_VALUE;
	
	// Give corners a big value and 'corner give' locations small value
	// Also, if an edge is free of the opponent, give 'edge control'
	// squares big value
	matrix[0][0] = matrix[0][7] = matrix[7][0] = matrix[7][7] = CORNER_VALUE;
	if (gameSquareEmpty(game, coord(0,0))) {
		matrix[1][1] = X_SQUARE_VALUE;
		matrix[0][1] = matrix[1][0] = C_SQUARE_VALUE;
		if (gameSquareType(game, coord(0,1)) != opponent &&
		    gameSquareType(game, coord(0,2)) != opponent &&
		    gameSquareType(game, coord(0,3)) != opponent &&
		    gameSquareType(game, coord(0,4)) != opponent &&
		    gameSquareType(game, coord(0,5)) != opponent &&
		    gameSquareType(game, coord(0,6)) != opponent &&
		    gameSquareType(game, coord(0,7)) != opponent) {
			matrix[0][2] = matrix[0][5] = EDGE_CONTROL_VALUE;
		}
	}
	if (gameSquareEmpty(game, coord(0,7))) {
		matrix[1][6] = X_SQUARE_VALUE;
		matrix[0][6] = matrix[1][7] = C_SQUARE_VALUE;
		if (gameSquareType(game, coord(1,7)) != opponent &&
		    gameSquareType(game, coord(2,7)) != opponent &&
		    gameSquareType(game, coord(3,7)) != opponent &&
		    gameSquareType(game, coord(4,7)) != opponent &&
		    gameSquareType(game, coord(5,7)) != opponent &&
		    gameSquareType(game, coord(6,7)) != opponent &&
		    gameSquareType(game, coord(7,7)) != opponent) {
			matrix[2][7] = matrix[5][7] = EDGE_CONTROL_VALUE;
		}
	}
	if (gameSquareEmpty(game, coord(7,0))) {
		matrix[6][1] = X_SQUARE_VALUE;
		matrix[7][1] = matrix[6][0] = C_SQUARE_VALUE;
		if (gameSquareType(game, coord(0,0)) != opponent &&
		    gameSquareType(game, coord(1,0)) != opponent &&
		    gameSquareType(game, coord(2,0)) != opponent &&
		    gameSquareType(game, coord(3,0)) != opponent &&
		    gameSquareType(game, coord(4,0)) != opponent &&
		    gameSquareType(game, coord(5,0)) != opponent &&
		    gameSquareType(game, coord(6,0)) != opponent) {
			matrix[2][0] = matrix[5][0] = EDGE_CONTROL_VALUE;
		}
	}
	if (gameSquareEmpty(game, coord(7,7))) {
		matrix[6][6] = X_SQUARE_VALUE;
		matrix[6][7] = matrix[7][6] = C_SQUARE_VALUE;
		if (gameSquareType(game, coord(7, 0)) != opponent &&
		    gameSquareType(game, coord(7, 1)) != opponent &&
		    gameSquareType(game, coord(7, 2)) != opponent &&
		    gameSquareType(game, coord(7, 3)) != opponent &&
		    gameSquareType(game, coord(7, 4)) != opponent &&
		    gameSquareType(game, coord(7, 5)) != opponent &&
		    gameSquareType(game, coord(7, 6)) != opponent) {
			matrix[7][2] = matrix[7][5] = EDGE_CONTROL_VALUE;
		}
	}

	return matrix;
}

void squareValuesDestruct(float** values) {
	for (int i = 0; i < 8; i++) {
		free(values[i]);
	}
	free(values);
}

int isEndGame(struct Game const* game) {
	unsigned int empty_squares = 0;
	
	for (int x = 0; x < 8; x++) { 
	for (int y = 0; y < 8; y++) {
		if (!gameSquareType(game, coord(x, y))) empty_squares++;
	}}
	
	if(empty_squares <= END_GAME_THRESHOLD) return 1;
	return 0;
}

/* Tree functions 
* struct Tree_s {
*	Data data;
*	struct Tree_s* parent;
*	struct Tree_s** children;
*	unsigned int num_children;
*	unsigned int num_child;
* }
*/
Tree treeConstruct(Data data) {
	Tree tree = (Tree) malloc(sizeof(struct Tree_s));
	tree->data = data;
	tree->parent = NULL;
	tree->children = (Tree*) malloc(sizeof(Tree));
	tree->children[0] = NULL;
	tree->num_children = 0;
	tree->num_child = 0;
	
	return tree;
}

void treeRemove(Tree tree) {
	treeDetach(tree);    // Detach from parent
	treeDestruct(tree);  // Recursive destruct
}

void treeDestruct(Tree tree) {
	// Destruct children
	for (unsigned int i = 0; i < tree->num_children; i++) {
		treeDestruct(tree->children[i]);
	}
	
	// Ddestruct self
	dataDestruct(tree->data);
	free(tree->children);
	free(tree);
}

void treeAddChild(Tree tree, Tree child) {
	tree->num_children++;
	tree->children = (Tree*) realloc(tree->children, tree->num_children * sizeof(Tree));
	tree->children[tree->num_children - 1] = child;
	child->parent = tree;
	child->num_child = tree->num_children;
}

void treeDetach(Tree tree) {
	Tree parent = tree->parent;
	if(!parent) return;
	
	// Move and update num_child for siblings of tree
	for(unsigned int i = tree->num_child - 1; i < (parent->num_children - 1); i++) {
		parent->children[i] = parent->children[i + 1];
		parent->children[i]->num_child = i + 1;
	}
	parent->num_children--;
	parent->children = (Tree*) realloc(parent->children, parent->num_children * sizeof(Tree));
}

Tree treeGetFirstLeaf(Tree tree) {
	if(tree->num_children == 0) return tree;
	if(tree == NULL) return NULL;
	
	while(tree->num_children > 0) {
		tree = tree->children[0];
	}
	
	return tree;
}

Tree treeGetNextSibling(Tree tree) {
	if (tree->parent == NULL) return NULL; // Special case...
	if (tree->parent->num_children <= tree->num_child) return NULL;
	return tree->parent->children[tree->num_child];
}

Tree treeGetNextLeaf(Tree tree) {
	Tree temp;
	
	// Get next sibling if applicable
	if ((temp = treeGetNextSibling(tree))) return temp;
	
	// Go up in tree as long as node is the last child of its parent
	while(tree->parent && !treeGetNextSibling(tree)) {
		tree = tree->parent;
	}
	
	// Get next sibling or return null if end has been reached
	if (!(tree = treeGetNextSibling(tree))) return NULL;
	
	// Go back to bottom level
	return treeGetFirstLeaf(tree);
}

Tree treeGetFirstChild(Tree tree) {
	if (tree->num_children == 0) return NULL;
	return tree->children[0];
}

int treeIsDescendantOf(Tree tree, Tree ancestor) {
	if (tree == NULL) return 0;
	while ((tree = tree->parent)) {
		if (tree == ancestor) return 1;
	}
	return 0;
}

int treeHasChild(Tree parent, Tree child) {
	Tree test;
	for(test = treeGetFirstChild(parent); test; test = treeGetNextSibling(test)) {
		if (test == child) return 1;
	}
	return 0;
}
	
/* Initial moves

 * typedef struct InitialMove_s {
 *	int elements;
 *	Tree *trees;
 *	float *values;
 *	float *mobility_factors;
 *	float *mm_values;
 *	struct Coord *moves;
 * } *InitialMove;
 */

InitialMove initialMoveConstruct(void) {
	InitialMove im = (InitialMove) malloc(sizeof(struct InitialMove_s));
	im->elements = 0;
	im->trees = NULL;
	im->moves = NULL;
	im->wc_values = NULL;
	im->mm_values = NULL;
	im->mobility_factors = NULL;
	return im;
}

void initialMoveDestruct(InitialMove im) {
	free(im->trees);
	free(im->moves);
	free(im->wc_values);
	free(im->mm_values);
	free(im->mobility_factors);
	free(im);
}

void initialMoveAdd(InitialMove im, Tree tree, struct Coord move) {
	im->trees = (Tree*) realloc(im->trees, (im->elements + 1) * sizeof(Tree));
	im->trees[im->elements] = tree;
	
	im->wc_values = (float*) realloc(im->wc_values, (im->elements + 1) * sizeof(float));
	im->mm_values = (float*) realloc(im->mm_values, (im->elements + 1) * sizeof(float));
	im->mobility_factors = (float*) realloc(im->mobility_factors, (im->elements + 1) * sizeof(float));
	
	im->moves = (struct Coord*) realloc(im->moves, (im->elements + 1) * sizeof(struct Coord));
	im->moves[im->elements] = move;
	
	im->elements++;
}

void initialMoveEvaluateWC(InitialMove im) {
	for (int i = 0; i < im->elements; i++) {
		im->wc_values[i] = im->trees[i]->data->value;
	}
}

void initialMoveEvaluateMM(InitialMove im) {
	for (int i = 0; i < im->elements; i++) {
		im->mm_values[i] = im->trees[i]->data->value;
	}
}

void initialMoveEvaluateMobility(InitialMove im) {
	Tree tree;
	unsigned int opponent_mobility, my_mobility = (unsigned int) INFINITY;
	float mobility_coefficient, mc = MOBILITY_COEFFICIENT;
	
	for (int i = 0; i < im->elements; i++) {
		tree = im->trees[i];
		if(!tree || !(tree->num_children)) return;
		
		// get own mobility
		opponent_mobility = tree->num_children;
		
		// Get worst case own mobility after opponent moves
		for(unsigned int j = 0; j < tree->num_children; j++) {
			if (tree->children[j]->num_children < my_mobility) {
				my_mobility = tree->children[j]->num_children;
			}
		}
		
		mobility_coefficient = (float) my_mobility / (float) opponent_mobility;
		mobility_coefficient = (mc + mobility_coefficient) / (1.2 * mc);
		
		im->mobility_factors[i] = mobility_coefficient;
	}
}

void initialMoveUpdate(InitialMove im, Tree root) {
	for (int i = 0; i < im->elements; i++) {
		if (treeHasChild(root, im->trees[i])) continue;
		
		/* Tree has been removed -> remove corrensponding move */
		// move remaining elements backwards
		for (int index = i + 1; index < im->elements; index++) {
			im->trees[index - 1] = im->trees[index];
			im->moves[index - 1] = im->moves[index];
			im->wc_values[index - 1] = im->wc_values[index];
			im->mm_values[index - 1] = im->mm_values[index];
			im->mobility_factors[index - 1] = im->mobility_factors[index];
		}
		i--; // otherwise next tree wont be evaluated...
		im->elements--;
		
		// Realloc all members of InitialMove_s
		im->trees = (Tree*) realloc(im->trees, im->elements * sizeof(Tree));
		im->moves = (struct Coord*) realloc(im->moves, im->elements * sizeof(struct Coord));
		im->wc_values = (float*) realloc(im->wc_values, im->elements * sizeof(float));
		im->mm_values = (float*) realloc(im->mm_values, im->elements * sizeof(float));
		im->mobility_factors = (float*) realloc(im->mobility_factors, im->elements * sizeof(float));
	}
}