/*
    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"
#include "actions.h"

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

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

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

static float negamax(tak_state_p state, 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) {
  actions_init(new_board_size);
  zobrist_init(new_board_size);
  tt_init();

  if (new_board_size == 5) {
    evaluate = &nn1986_evaluate_black_win;
  } else {
    evaluate = &nn2690_evaluate_black_win;
  }
}

void negamax_free(void) { zobrist_free(); }

float negamax_generate(tak_state_p state) {
  // 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(state, d, d, -safe_infty, safe_infty,
                     (state->ply & 1) ? +1.0 : -1.0, zobrist_compute(state));
  }
  tt_free();

  action_to_ptn(negamax_best_action, negamax_ptn);

  return result;
}

// ===================================================================
// α-β negamax with iterative deepening, using the nn1986 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(tak_state_p state, 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_t *actions;
  uint32_t num_actions;
  if ((actions = actions_generate(state, &num_actions)) == NULL)
    return alpha; // should never happen!

  // How did we land up with impossible actions for this hash?
  if (entry != NULL && action_in_list(entry->action, actions, num_actions)) {
    action_move_to_front(entry->action, actions, num_actions);
  }

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

  action_t best_action = actions[0];
  float best_value = -infty;

  for (uint32_t idx = 0; idx<num_actions; idx++) {
    negamax_display_progress(cur_depth, init_depth, num_actions);

    action_take(state, actions[idx]);

    // Compute the value of the node
    float node_value;
    if (state->ply >= 2 * state->board_size - 2 &&
        (w = check_win(state)) < 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(state, cur_depth - 1, init_depth, -beta, -alpha,
                            -colour, zobrist_compute(state));
    } else {
      node_value = colour * evaluate(state);
    }
    action_undo(state, actions[idx]);

    if (node_value > best_value) {
      best_value = node_value;
      best_action = actions[idx];
    }

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

  actions_free(actions);
  if (cur_depth == init_depth)
    negamax_best_action = best_action;

  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;
}