/*
 * Biloba
 * Copyright (C) 2004-2008 Guillaume Demougeot, Colin Leroy
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA
 */

/**
 * Biloba - Q1 2005
 * Game by Guillaume Demougeot <dmgt@wanadoo.fr>
 * Code by Colin Leroy <colin@colino.net>
 *
 * This file contains all the AI-related code.
 */

#include <SDL.h>
#include <SDL_thread.h>
#include <stdlib.h>
#include <time.h>

#include "utils.h"
#include "local_input.h"
#include "tile.h"
#include "net.h"
#include "computer.h"
#include "board.h"
#include "player.h"
#include "llist.h"
#include "logic.h"

#undef IA_DEBUG

static Pawn *selected_pawn = NULL;
static Tile *best_destination = NULL;
static Tile *best_destination_after_middle = NULL;

static int first = FALSE;

static Tile *computer_defend(Player *player, LList *allowed, int immediate_defense)
{
	/* get the best pawn to move so that it won't be eaten */
	LList *pawns;
	LList *cur;
	Tile *best = NULL;
	LList *max_eaten_pawns = NULL;
	int max_eaten = 0;
	int search_now = (immediate_defense > 0);
	int center_ok = can_move_on_center();

	if (allowed)
		pawns = llist_copy(allowed);
	else
		pawns = pawn_get_all(player->color);

search_again:	
	max_eaten_pawns = player_can_be_eaten(player, search_now, allowed);
	max_eaten = llist_length(max_eaten_pawns);
	llist_free(max_eaten_pawns);
#ifdef IA_DEBUG
	printf("DEFENCE: maximum possible to be eaten at %s move: %d\n",
			search_now?"next":"afternext", max_eaten);
#endif	
	assert(best_destination == NULL);

	for (cur = pawns; cur; cur = cur->next) {
		Pawn *pawn = (Pawn *)cur->data;
		Tile *origtile = pawn_get_tile(pawn);
		LList *positions = tile_get_accessible_surroundings(pawn_get_tile(pawn));
		LList *curpos = positions;

		for (; curpos; curpos = curpos->next) {
			Tile *desttile = (Tile *)curpos->data;
			LList *can_be_eaten = NULL;
			LList *allowed_for_this = NULL;

			if (desttile->pawn != NULL)
				continue; /* work around repaint hack */

			if (tile_is_near_center(origtile) &&
			    tile_is_near_center(desttile) &&
			    !center_ok)
				continue;

			allowed_for_this = llist_append(NULL, pawn);
			pawn_move_to(pawn, desttile);
			
			can_be_eaten = player_can_be_eaten(player, search_now, allowed);
			
			llist_free(allowed_for_this); 
			allowed_for_this = NULL;
			
			if (llist_length(can_be_eaten) < max_eaten) {
#ifdef IA_DEBUG
				printf("MIN!found %d to be eaten by moving %d,%d to %d,%d\n",
					llist_length(can_be_eaten),
					origtile->pos_x, origtile->pos_y,
					desttile->pos_x, desttile->pos_y);
#endif
				max_eaten = llist_length(can_be_eaten);
				best = origtile;
				best_destination = desttile;
			}
			llist_free(can_be_eaten);
			pawn_move_to(pawn, origtile);
		}
		llist_free(positions);
	}
	if (best == NULL && search_now == TRUE && immediate_defense > 1) {
		search_now = FALSE;
		goto search_again;
	}

	llist_free(pawns);

	return best;
}

static Tile *finish_move(Player *player, LList *allowed)
{
	Tile *orig = NULL;
	Tile *dest = NULL;
	LList *eater_dest = NULL;
	
	if (allowed) {
		Pawn *allowed_pawn = (Pawn *)allowed->data;
		eater_dest = allowed_pawn->just_ate_on;
	}

	assert(selected_pawn != NULL);
	
	orig = pawn_get_tile(selected_pawn);
	if (best_destination) {
		dest = best_destination;
	} else if (best_destination_after_middle) {
		if (orig->pos_x == 4 && orig->pos_y == 4) {
			dest = best_destination_after_middle;
		} 
		best_destination_after_middle = NULL;
	}

	selected_pawn = NULL;
	best_destination = NULL;

	if (first) {
		first = FALSE;
		return tile_get(4,4);	
	}

	if (orig && dest && !eater_dest)
		return dest;
	else {
		/* have to figure out dest, idiotic for now */
		LList *destinations = eater_dest ? eater_dest : tile_get_accessible_surroundings(orig);
		LList *cur = destinations;
		float r = (float)rand()/RAND_MAX;
		int num = r * llist_length(destinations);
		int i = 0;
		
		/* if replacement and best found position is acceptable, then great */
		if (dest && eater_dest && llist_find(eater_dest, dest))
			return dest;

		for (i = 0; i < num; i++) 
			cur = cur->next;
		
		dest = (Tile *)cur->data;
		if (eater_dest == NULL)
			llist_free(destinations);

		/* we should check we're not committing suicide */
		return dest;
	}
}

static Tile *prepare_move(Player *player, LList *allowed)
{
	/* get the best pawn to move so that I'll be able to eat later */
	LList *pawns, *cur;
	Pawn *best = NULL;
	int max_eatables_soon = 0;
	int pawn_count;
	int search_now = TRUE;

	if (allowed)
		pawns = llist_copy(allowed);
	else
		pawns = pawn_get_all(player->color);

	pawn_count = llist_length(pawns);

	if (pawn_count == 1) {
		Pawn *pawn = (Pawn *)pawns->data;
		if (pawn_get_tile(pawn)->type == TILE_CENTER) {
			/* move again */
			assert(selected_pawn == NULL);
			selected_pawn = pawn;
		} 
	}

	if (selected_pawn != NULL) {
		llist_free(pawns);
		return finish_move(player, allowed);
	}
	if (first) {
		llist_free(pawns);
		selected_pawn = tile_get(4,3)->pawn;
		return tile_get(4,3);
	}

search_again:
#ifdef IA_DEBUG
	printf("ATTACK: choosing for %s turn\n", search_now?"current":"next");
#endif
	for (cur = pawns; cur; cur = cur->next) {
		Pawn *pawn = (Pawn *)cur->data;
		Tile *origtile = pawn_get_tile(pawn);
		LList *positions = tile_get_accessible_surroundings(pawn_get_tile(pawn));
		LList *curpos = positions;
		
		for (; curpos; curpos = curpos->next) {
			Tile *desttile = (Tile *)curpos->data;
			LList *eatables = NULL;
			LList *can_be_eaten = NULL;
			LList *allowed_for_this = NULL;
			int score = 0, can_be_eaten_before_move = 0;
			
			if (desttile->pawn != NULL)
				continue; /* work around repaint hack */

			if (desttile->pos_x == 4 && desttile->pos_y == 4) {
				/*middle tile*/
				LList *mid_surr = tile_get_accessible_surroundings(desttile);
				LList *cur_mid = mid_surr;
				for (; cur_mid; cur_mid = cur_mid->next) {
					if (!llist_find(positions, cur_mid->data))
						llist_append(positions, cur_mid->data);
				}
				llist_free(mid_surr);
				continue;
			}
			can_be_eaten = player_can_be_eaten(player, search_now, allowed_for_this);
			can_be_eaten_before_move = llist_length(can_be_eaten);
			llist_free(can_be_eaten);
			can_be_eaten = NULL;

			allowed_for_this = llist_append(NULL, pawn);
			
			pawn_move_to(pawn, desttile);

			eatables = player_can_eat_soon(player, search_now, allowed_for_this);
			
			can_be_eaten = player_can_be_eaten(player, search_now, allowed_for_this);
			
			llist_free(allowed_for_this); 
			allowed_for_this = NULL;
			
			if (!search_now && llist_length(can_be_eaten) > can_be_eaten_before_move) {
#ifdef IA_DEBUG
				printf("won't move to %d %d, would be suicide\n",
						desttile->pos_x, desttile->pos_y);
#endif				
				goto no_suicide;
			}
			
			score = llist_length(eatables) - llist_length(can_be_eaten);

			if ((search_now || llist_length(can_be_eaten) == 0) && llist_length(eatables) > max_eatables_soon) {
#ifdef IA_DEBUG
				printf("MAX!found %d eatables and %d to be eaten by moving %d,%d to %d,%d\n",
					llist_length(eatables), llist_length(can_be_eaten),
					origtile->pos_x, origtile->pos_y,
					desttile->pos_x, desttile->pos_y);
#endif
				max_eatables_soon = llist_length(eatables);
				best = pawn;
				if ((abs(origtile->pos_x - desttile->pos_x) == 2 ||
				    abs(origtile->pos_y - desttile->pos_y) == 2) &&
				    tile_is_near_center(origtile) && 
				    tile_is_near_center(desttile) &&
				    search_now) {
					best_destination_after_middle = desttile;
					best_destination = tile_get(4, 4);
				} else if ((abs(origtile->pos_x - desttile->pos_x) == 2 ||
				    abs(origtile->pos_y - desttile->pos_y) == 2) &&
				    tile_is_near_center(origtile) && 
				    tile_is_near_center(desttile) && 
				    !search_now) {
					best_destination_after_middle = desttile;
					best_destination = tile_get(4, 4);
				} else {
					best_destination = desttile;
				}
			}
no_suicide:
			llist_free(eatables);
			llist_free(can_be_eaten);
			pawn_move_to(pawn, origtile);
		}
		llist_free(positions);
	}
	if (best == NULL && search_now == TRUE) {
		Tile *best_defense = computer_defend(player, allowed, TRUE); /* now only */
		if (best_defense) {
			best = best_defense->pawn;
			goto no_random;
		}
		search_now = FALSE;
		goto search_again;
	}	
	
	if (best == NULL) {
		Tile *best_defense = NULL;
		int pawn_num = 0;
		int i = 0;
		int center_ok = can_move_on_center();
#ifdef IA_DEBUG
		printf("no best move found, trying to protect myself\n");
#endif

		best_defense = computer_defend(player, allowed, 2); /* both now and later */
		if (best_defense) {
			best = best_defense->pawn; 
			goto no_random;
		}
#ifdef IA_DEBUG
		printf("no best move found, randomly playing\n");
#endif
random_again:
		pawn_num = (rand()%pawn_count);

		cur = pawns;
		for (i = 0; i < pawn_num; i++) {
			cur = cur->next;
		}

		best = (Pawn *)cur->data;
		if (tile_is_near_center(pawn_get_tile(best)) &&
		    !center_ok)
			goto random_again;

	}
no_random:
	llist_free(pawns);
	
	selected_pawn = best;

	return pawn_get_tile(best);
}

Tile *computer_select_tile(Player *player, LList *allowed)
{
	Tile *res = NULL;

	if (delay_with_event_poll(1000) < 0)
		goto out;

	while (game_suspended()) {
		if (delay_with_event_poll(20) < 0)
			goto out;
	}
	if (game_ended())
		goto out;

	board_freeze();
	res = prepare_move(player, allowed);
	board_thaw();
	
out:
	while (game_suspended()) {
		delay_with_event_poll(20);
	}
	if (game_ended())
		goto no_push;

no_push:
	return res;
}