#include <array>
#include <memory>
#include "minimax.h"

using namespace std;

#define LARGE MINIMAX_LARGE


static int win_score[4] = {
	[WIN_NONE] = 0,
	[WIN_P0] = 1,
	[WIN_P1] = -1,
	[WIN_DRAW] = -1,
};

struct TransItem {
	Board B = Board::empty();
	int score = 0;
};

static unique_ptr<array<TransItem, 10000019>> transTable =
	make_unique<decltype(transTable)::element_type>();

static void transTableStore(uint64_t index, const Board &B, int score) {
	TransItem &entry = (*transTable)[index];
	// if (entry.B.isEmpty() || B.numFilled() < entry.B.numFilled()) {
		entry.B = B;
		entry.score = score;
	// }
}

static uint64_t transHits = 0, transTotal = 0;
static uint64_t transHitDepthSum = 0;

template <int player>
int minimax(const Board &B, int alpha, int beta, int depth) {
	uint64_t transIndex = B.hash() % transTable->size();
	transTotal++;
	if (!B.isEmpty() && (*transTable)[transIndex].B == B) {
		transHits++;
		transHitDepthSum += depth;
		return (*transTable)[transIndex].score;
	}

	win_t win = B.checkWin();
	if (win != WIN_NONE) {
		transTableStore(transIndex, B, win_score[win]);
		return win_score[win];
	}

	if (depth == 0) return win_score[WIN_NONE];

	if (depth >= 42) {
		printf("depth=%d alpha=%d beta=%d transHitrate=%lf (avg depth %lf)\n",
				depth, alpha, beta,
				(double)transHits / transTotal, (double)transHitDepthSum / transTotal);
	}

	int best = player == 0 ? -LARGE : LARGE;

	// Returns true if iteration should be stopped
	auto tryMove = [&](int i) {
		if (B.stkFull(i)) return false;

		Board C(B);
		C.drop(i, player);

		int sc = minimax<1 - player>(C, alpha, beta, depth - 1);

		if constexpr (player == 0) {
			best = max(sc, best);
			alpha = max(best, alpha);
		} else {
			best = min(sc, best);
			beta = min(best, beta);
		}

		return beta <= alpha;
	};

	for (int i = 0; i < 16; i++) {
		if (tryMove(i)) break;
	}

	transTableStore(transIndex, B, best);
	return best;
}

template int minimax<0>(const Board &B, int alpha, int beta, int depth);
template int minimax<1>(const Board &B, int alpha, int beta, int depth);