typedef char **Board;


struct Player {
	int startpos, endpos;
	bool contbycpu;
	int search_depth;
	int playingnumber;
};

struct SMove {
	SMove() { }
	SMove(int ox2, int oy2, int tx2, int ty2) {
		ox = ox2;
		oy = oy2;
		tx = tx2;
		ty = ty2;
	}
	
	int ox, oy, tx, ty;
};

struct SJumpCoord {
	SJumpCoord() { }
	SJumpCoord(int xx, int yy) {
		x = xx;
		y = yy;
	}
	int x, y;
};




void minimax(int c_player, Player *player, int num_players, Board start_board, int board_size, std::list<SJumpCoord> *movelist);

int AlphaBeta (Board pos, int current_player, int max_for, int num_players, int depth, int alpha, int beta, int board_size, Player *player, SMove &best_move, int gs);



// fills move_list with possible moves **REMOVED FOR CONVIENCE**
void Successors(Board pos, std::list<SMove> &move_list, int current_player, int board_size);

// evaluates the board (numerical value rating board) **REMOVED FOR CONVIENCE**
int Evaluate(Board pos, int current_player, int board_size, int num_players, Player *player, int gs);



// absolute value **REMOVED FOR CONVIENCE**
int abs(int x);

// value squared **REMOVED FOR CONVIENCE**
int sqred(int x);

// 0 for still running, 1-6 for corrosponding player wins **REMOVED FOR CONVIENCE**
int get_gamestate(Board board, Player player[6], int num_players, int board_size);




// frees memory set for output **REMOVED FOR CONVIENCE**
int clear_output(char **(&output), int n);

// stores player id's pieces in output **REMOVED FOR CONVIENCE**
void get_players_pieces(Board board, char **(&output), int id, int n);

// stores the position of the pieces end position in output **REMOVED FOR CONVIENCE**
int get_piece_pos(int board_size, int pos, char **(&output));







const int INF_INITY = 100000;
const int MAX_VAL = 90000;



/*
	Player player[6];	// info on players
	c_player;			// 1-6
	num_players;		// 1-6
	start_board;		// current 'board'
	board_size;			// size of 'board' (note board would be declared as board[board_size*4+1][board_size*4+1]
	movelist;			// output
*/

void minimax(int c_player, Player *player, int num_players, Board start_board, int board_size, std::list<SJumpCoord> *movelist) {
	SMove best_move; // storage for best move
	
	AlphaBeta(start_board, c_player, c_player, num_players, player[c_player-1].search_depth, -INF_INITY, INF_INITY, board_size, player, best_move, 0);
	
	movelist->clear(); // clear movelist
	
	movelist->push_back(SJumpCoord(best_move.ox, best_move.oy)); // add orign to movelist
	movelist->push_back(SJumpCoord(best_move.tx, best_move.ty)); // add target to movelist
}





int AlphaBeta (Board pos, int current_player, int max_for, int num_players, int depth, int alpha, int beta, int board_size, Player *player, SMove &best_move, int gs) {
	if (depth == 0 || gs != 0) { // if we reached the leaf:
		return Evaluate(pos, max_for, board_size, num_players, player, gs);
	}
	
	
	
	
	
	SMove next_move, new_move; // stores next move
	int best = -INF_INITY, value;
	std::list<SMove> succ; // storage for successor moves
	
	Successors(pos, succ, current_player, board_size);
	
	
	int next_player = current_player + 1;
	if(next_player > num_players)
		next_player = 1;
	
	
	while(!succ.empty() && best < beta) {
		new_move = succ.front();
		succ.pop_front();
		
		
		if(best > alpha)
			alpha = best;
		
		pos[new_move.tx][new_move.ty] = pos[new_move.ox][new_move.oy];
		pos[new_move.ox][new_move.oy] = 0;
		
		
		// peek next gs
		int gs = get_gamestate(pos, player, num_players, board_size);
		
		ab_depth++;
		if(gs != 0 || depth -1 == 0) {
			value = AlphaBeta (pos, next_player, max_for, num_players, depth-1, alpha, beta, board_size, player, next_move, gs);
		} else if(next_player == max_for || current_player == max_for) {
			value = -AlphaBeta (pos, next_player, max_for, num_players, depth-1, -beta, -alpha, board_size, player, next_move, gs);
		} else {
			value = AlphaBeta (pos, next_player, max_for, num_players, depth-1, alpha, beta, board_size, player, next_move, gs);
		}
		ab_depth--;
		
		
		pos[new_move.ox][new_move.oy] = pos[new_move.tx][new_move.ty];
		pos[new_move.tx][new_move.ty] = 0;
		
		
		if(value > best) {
			best = value;
			
			best_move.ox = new_move.ox;
			best_move.oy = new_move.oy;
			best_move.tx = new_move.tx;
			best_move.ty = new_move.ty;
		}
	}
	
	
	return best;
}


int Evaluate(Board pos, int current_player, int board_size, int num_players, Player *player, int gs) {
	char **current = NULL, **target = NULL;
	
	if(gs != 0) {
		if(gs == current_player) {
			return MAX_VAL;
		} else {
			return -MAX_VAL;
		}
	}
	
	int value = 0;
	
	for(int i = 0; i < num_players; i++) {
		get_players_pieces(pos, current, i, board_size);
		int np = get_piece_pos(board_size, player[i-1].endpos, target);
		
		for(int j = 0; j < np; j++) {
			if(current_player-1 == i) {
				value -= sqred(current[j][0] - target[j][0]) + sqred(current[j][1] - target[j][1]);
			} else {
				value += sqred(current[j][0] - target[j][0]) + sqred(current[j][1] - target[j][1]);
			}
		}
	}
	
	clear_output(current, board_size);
	clear_output(target, board_size);
	
	return value;
}