/*
 * Faculty of Applied Science and Engineering, University of Toronto
 * CSC181: Introduction to Computer Programming, Fall 2000
 *
 * File: rminimax.cpp
 * Contains: Implementation for MinimaxTPlayer, a computer player which
 * uses the minimax algorithm to play a game of Connect Four.
 * Author: Ray Ortigas (rayo@dgp.toronto.edu)
 */

#include "rminimax.h"

static int max(int a, int b) { return a >= b ? a : b; }
static int min(int a, int b) { return a < b ? a : b; }

int MinimaxTPlayer::suggestMove(const TBoard& b) {
	int result;
	TBoard* boardCopy = b.clone();
	result = minimaxDecision(*boardCopy, boardCopy->getRed() == this);
	delete boardCopy;
	return result;
}

int MinimaxTPlayer::minimaxDecision(TBoard& b, bool redToMove) {
	int bestMove = -1;
	int bestValue;
	
	if (redToMove) {
		bestValue = T_MIN_WINS;
		for (int c = 0; c < T_NUM_COLUMNS; c++) {
			if (b.isLegalMove(c)) {
				int value;
				b.dropPiece(b.getRed(), c);				
				value = minimaxValue(b, !redToMove, depth-1);
				if (value >= bestValue) {
					bestValue = value;
					bestMove = c;
				}
				b.removeTopPiece(c);
			}
		}
	}
	else {
		bestValue = T_MAX_WINS;
		for (int c = 0; c < T_NUM_COLUMNS; c++) {
			if (b.isLegalMove(c)) {
				int value;
				b.dropPiece(b.getBlack(), c);				
				value = minimaxValue(b, !redToMove, depth-1);
				if (value <= bestValue) {
					bestValue = value;
					bestMove = c;
				}
				b.removeTopPiece(c);
			}
		}
	}
	
	return bestMove;
}

int MinimaxTPlayer::minimaxValue(TBoard& b, bool maxToMove,
								 int currentDepth) {
	TPlayer* winner = b.getWinner();
	if (winner == b.getRed()) {
		return T_MAX_WINS;
	}
	else if (winner == b.getBlack()) {
		return T_MIN_WINS;
	}
	else if (currentDepth == 0) {
		return evaluate(b);
	}
	else if (maxToMove) {
		int bestValue = T_MIN_WINS;
		for (int c = 0; c < T_NUM_COLUMNS; c++) {
			if (b.isLegalMove(c)) {
				b.dropPiece(b.getRed(), c);
				bestValue = max(bestValue, 
					minimaxValue(b, !maxToMove, currentDepth-1));
				b.removeTopPiece(c);
			}
		}
		return bestValue;
	}
	else { // if (minToMove)
		int bestValue = T_MAX_WINS;
		for (int c = 0; c < T_NUM_COLUMNS; c++) {
			if (b.isLegalMove(c)) {
				b.dropPiece(b.getBlack(), c);
				bestValue = min(bestValue, 
					minimaxValue(b, !maxToMove, currentDepth-1));
				b.removeTopPiece(c);
			}
		}
		return bestValue;
	}
}

int MinimaxTPlayer::evaluate(const TBoard& b) {
	int maxLines = 0;
	int minLines = 0;
	TPosition winningLine[T_NUM_TO_CONNECT];
	int r;
	int c;
	int i;
	
	// SW-NE diagonals
	for (r = 0; r <= T_NUM_ROWS-T_NUM_TO_CONNECT; r++) {
		for (c = 0; c <= T_NUM_COLUMNS-T_NUM_TO_CONNECT; c++) {
			for (i = 0; i < T_NUM_TO_CONNECT; i++) {
				winningLine[i].r = r+i;
				winningLine[i].c = c+i;
			}
			int redCount = b.countRed(winningLine, T_NUM_TO_CONNECT);
			int blackCount = b.countBlack(winningLine, T_NUM_TO_CONNECT);

			if (redCount == T_NUM_TO_CONNECT)
				return T_MAX_WINS;
			else if (blackCount == T_NUM_TO_CONNECT)
				return T_MIN_WINS;
			else if (redCount > 0 && blackCount == 0)
				maxLines++;
			else if (blackCount > 0 && redCount == 0)
				minLines++;
		}
	}

	// NW-SE diagonals
	for (r = T_NUM_ROWS-1; r >= T_NUM_TO_CONNECT-1; r--) {
		for (c = 0; c <= T_NUM_COLUMNS-T_NUM_TO_CONNECT; c++) {
			for (i = 0; i < T_NUM_TO_CONNECT; i++) {
				winningLine[i].r = r-i;
				winningLine[i].c = c+i;
			}
			int redCount = b.countRed(winningLine, T_NUM_TO_CONNECT);
			int blackCount = b.countBlack(winningLine, T_NUM_TO_CONNECT);

			if (redCount == T_NUM_TO_CONNECT)
				return T_MAX_WINS;
			else if (blackCount == T_NUM_TO_CONNECT)
				return T_MIN_WINS;
			else if (redCount > 0 && blackCount == 0)
				maxLines++;
			else if (blackCount > 0 && redCount == 0)
				minLines++;
		}
	}
	
	// Rows
	for (r = 0; r < T_NUM_ROWS; r++) {
		for (c = 0; c <= T_NUM_COLUMNS-T_NUM_TO_CONNECT; c++) {
			for (i = 0; i < T_NUM_TO_CONNECT; i++) {
				winningLine[i].r = r;
				winningLine[i].c = c+i;
			}
			int redCount = b.countRed(winningLine, T_NUM_TO_CONNECT);
			int blackCount = b.countBlack(winningLine, T_NUM_TO_CONNECT);

			if (redCount == T_NUM_TO_CONNECT)
				return T_MAX_WINS;
			else if (blackCount == T_NUM_TO_CONNECT)
				return T_MIN_WINS;
			else if (redCount > 0 && blackCount == 0)
				maxLines++;
			else if (blackCount > 0 && redCount == 0)
				minLines++;
		}
	}
	
	// Columns
	for (r = 0; r <= T_NUM_ROWS-T_NUM_TO_CONNECT; r++) {
		for (c = 0; c < T_NUM_COLUMNS; c++) {
			for (i = 0; i < T_NUM_TO_CONNECT; i++) {
				winningLine[i].r = r+i;
				winningLine[i].c = c;
			}
			int redCount = b.countRed(winningLine, T_NUM_TO_CONNECT);
			int blackCount = b.countBlack(winningLine, T_NUM_TO_CONNECT);
		
			if (redCount == T_NUM_TO_CONNECT)
				return T_MAX_WINS;
			else if (blackCount == T_NUM_TO_CONNECT)
				return T_MIN_WINS;
			else if (redCount > 0 && blackCount == 0)
				maxLines++;
			else if (blackCount > 0 && redCount == 0)
				minLines++;
		}
	}

	return maxLines - minLines;
}