/*
* 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));
        }
}