/*
	This file is part of ct.

	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 3 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 ct. If not, see <https://www.gnu.org/licenses/>.
*/

#include "negamax.h"

// ===================================================================
// Variables
// ===================================================================

const float infty = 3.0;
char negamax_ptn[9];
uint8_t negamax_search_depth = 3;
static uint64_t negamax_best_action;

// ===================================================================
// Helper declarations
// ===================================================================

static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
										 float alpha, float beta,
										 const float colour, const uint64_t hash);

// ===================================================================
// Exported functions
// ===================================================================

void negamax_init(const uint8_t new_board_size) {
	board_size = new_board_size;
	action_list_init(new_board_size);
	zobrist_init();
	tt_init();
}

void negamax_free(void) {
	zobrist_free();
}

float negamax_generate(void) {
	// We need to start with something outside of [-∞,∞] because those
	// values are wins
	const float safe_infty = infty + 1;
	float result = -infty;

	negamax_best_action = -1;

	tt_init();
	for (int d = 1; d <= negamax_search_depth; d++) {
		result = negamax(d, d, -safe_infty, safe_infty,
										 (ply & 1) ? +1.0 : -1.0, zobrist_compute());
	}
	tt_free();

	return result;
}

// ===================================================================
// α-β negamax with iterative deepening, using the cnn1986 evaluation
// function and transposition tables using Zobrist hasing and a
// chaining hash table
// ===================================================================

static enum TT_FLAG flag;
static enum WIN_TYPE w;

static float negamax(const uint8_t cur_depth, const uint8_t init_depth,
										 float alpha, float beta,
										 const float colour, const uint64_t hash) {

	tt_entry_t *entry = tt_seek(hash);

	// CAUTION: ≥ breaks search stability (vs =) on shallow depths
	if (entry != NULL && entry->depth >= cur_depth) {
		if (entry->flag == TT_EXACT) {
			return entry->value;
		} else if (entry->flag == TT_LOWERBOUND && entry->value > alpha) {
			alpha = entry->value;
		} else if (entry->flag == TT_UPPERBOUND && entry->value < beta) {
			beta = entry->value;
		}
		if (alpha >= beta) return entry->value;
	}

	action_list_t *list;
	if ((list = action_list_generate()) == NULL)
		return alpha; // should never happen!

	if (entry != NULL) {
		action_move_to_front(entry->action, list);
	}

	if (init_depth > 1 && cur_depth == init_depth) {
		action_move_to_front(negamax_best_action, list);
	}

	// TODO: what to do if this is never written to?
	action_t best_action = list->head->action;
	float best_value = -infty;

	for (action_node_t *node=list->head; node!=NULL; node=node->next) {
		negamax_display_progress(cur_depth, init_depth, list->length);

		action_take(node->action);

		// Compute the value of the node
		float node_value;
		if (ply >= 2*board_size - 2 && (w = check_win()) < 0xFF) {
			node_value = -colour*infty;
			// Check win if far enough into the game
			if (w == WIN_ROAD_BLACK || w == WIN_FLAT_BLACK) {
				node_value = colour*infty;
			} else if (w == WIN_DRAW) {
				node_value = 0;
			}
		} else if (cur_depth > 1) {
			// If nobody won, or too early and not leaf, recurse
			node_value = -negamax(cur_depth - 1, init_depth,
														-beta, -alpha,
														-colour, zobrist_compute());
		} else {
			node_value = colour * cnn1986_evaluate_black_win();
		}
		action_undo(node->action);

		if (node_value > best_value) {
			best_value = node_value;
			best_action = node->action;
			if (cur_depth == init_depth) {
				action_to_ptn(node->action, negamax_ptn);
				negamax_best_action = best_action;
			}
		}

		if (best_value > alpha) alpha = best_value;
		if (alpha >= beta) break;
	}

	action_list_free(list);

	flag = TT_EXACT;
	if (best_value >= beta) flag = TT_LOWERBOUND;
	else if (best_value <= alpha) flag = TT_UPPERBOUND;

	if (entry == NULL) {
		tt_insert(hash, flag, cur_depth, best_value, best_action);
	} else {
		entry->flag = flag;
		entry->value = best_value;
		entry->depth = cur_depth;
		entry->action = best_action;
	}

	return best_value;
}