/* Copyright 2018 Romain "Artefact2" Dal Maso <artefact2@gmail.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include <string.h>
#include <pthread.h>
#include <assert.h>
#include "gumble.h"

static int negamax(unsigned char depth, int alpha, int beta, cch_search_context_t* ctx, cch_movelist_t out_pv, unsigned char* out_pv_len) {
	cch_movelist_t ml;
	unsigned char start = 0, stop = cch_generate_moves(ctx->b, ml, CCH_LEGAL, 0, 64);

	if(!depth || !stop) {
		*out_pv_len = 0;
		return cch_evaluate_position(ctx->b, ml, stop);
	}

	const cch_transposition_entry_t* tt_entry = cch_hashtable_get(ctx->tt, ctx->b->hash);
	if(tt_entry) {
		if((tt_entry->best.padding & 63) >= depth) {
			switch(tt_entry->best.padding & 192) {
			case CCH_EVAL_EXACT:
				assert(cch_is_move_in_list(&(tt_entry->best), ml, stop)); /* Make sure move is legal, detect possible type 1 collisions */
				out_pv[0] = tt_entry->best;
				*out_pv_len = 1;
				return tt_entry->eval;

			case CCH_EVAL_LOWER_BOUND:
				//if(alpha < tt_entry->eval) alpha = tt_entry->eval;
				break;

			case CCH_EVAL_UPPER_BOUND:
				//if(beta > tt_entry->eval) beta = tt_entry->eval;
				break;

			default: assert(0);
			}
		} else if((tt_entry->best.padding & 192) == CCH_EVAL_EXACT) {
			/* Reuse best move as heuristic */
			ml[stop] = ml[0];
			ml[0] = tt_entry->best;
			++stop;
			start = 1;
		}
	}
	cch_transposition_entry_t te;
	assert(depth < 64);
	te.best.padding = CCH_EVAL_UPPER_BOUND | depth;

	/* Try capturing moves first; j is index of first non-capture in list */
	cch_move_t temp;
	for(unsigned char i = start, j = start; i < stop; ++i) {
		if(CCH_GET_SQUARE(ctx->b, ml[i].end)) {
			if(j < i) {
				temp = ml[i];
				ml[i] = ml[j];
				ml[j] = temp;
			}
			++j;
		}
	}

	cch_undo_move_state_t undo;
	int new_eval;
	cch_movelist_t pv;
	unsigned char pv_len;

	for(unsigned char i = 0; i < stop; ++i) {
		cch_play_legal_move(ctx->b, &(ml[i]), &undo);
		new_eval = -negamax(depth - 1, -beta, -alpha, ctx, pv, &pv_len);
		cch_undo_move(ctx->b, &(ml[i]), &undo);

		if(new_eval >= beta) {
			stop = i;
			alpha = beta; /* XXX: fail hard ??? */
			te.best.padding = CCH_EVAL_LOWER_BOUND | depth;
			break;
		}

		if(new_eval > alpha) {
			alpha = new_eval;
			out_pv[0] = ml[i];
			memcpy(&(out_pv[1]), pv, pv_len * sizeof(cch_move_t));
			*out_pv_len = pv_len + 1;
			te.best = ml[i];
			te.best.padding = CCH_EVAL_EXACT | depth;
		}
	}

	te.eval = alpha;
	ctx->nodes += stop;
	if((te.best.padding & 192) == CCH_EVAL_EXACT) {
		cch_hashtable_set(ctx->tt, ctx->b->hash, &te);
	}

	pthread_testcancel(); /* XXX for very obvious reasons */
	return alpha;
}

void cch_init_search_context(cch_search_context_t* ctx, cch_board_t* b, cch_hashtable_t* tt) {
	ctx->b = b;
	ctx->tt = tt;
	ctx->pv_len = 0;
}

/* XXX: i have no idea what i'm doing */
void cch_search_best_move(unsigned char depth, cch_search_context_t* ctx) {
	ctx->nodes = 0;
	ctx->start_depth = depth;
	ctx->eval = negamax(depth, -CCH_CHECKMATE_SCORE-1000, CCH_CHECKMATE_SCORE+1000, ctx, ctx->pv, &(ctx->pv_len));
}
