package player.gamer.statemachine.sadna;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * Choose next move in Connect Four game by building Min Max Tree with Alpha Beta Pruning and randomization
 */
public class MinMaxTreeActionChooser implements ActionChooser {

	public static final int TREE_DEFAULT_DEPTH = 5;
	
	private ScoreCalculator calculator;
	private Random rand = new Random();
	private int movesCount = 0;
	private boolean trainingMode = false;
	private int treeDepth = TREE_DEFAULT_DEPTH;
	private int[] indexs = new int[]{3,4,2,5,1,6,0,7};
	
	public MinMaxTreeActionChooser(ScoreCalculator calculator, boolean trainingMode, int treeDepth) {
		this.calculator = calculator;
		this.trainingMode = trainingMode;
		this.treeDepth = treeDepth;
	}
	
	public MinMaxTreeActionChooser(ScoreCalculator calculator, boolean trainingMode) {
		this.calculator = calculator;
		this.trainingMode = trainingMode;
	}

	/**
	 * @param gameBoard The game board 
	 * @return The best move to play, that is the best column to put the player coin in
	 */
	@Override
	public int getAction(Board gameBoard) {
		movesCount++;
		
		// if forced move exists (winning move or blocking move against the opponent) - play it 
		int forcedMoveCol = playForcedMove(gameBoard); 
		if (forcedMoveCol != -1) {
			return forcedMoveCol;
		}
		
		// epsilon greedy play (only for training mode)
		if (trainingMode && rand.nextInt(100) == 1) {
			int randMove = rand.nextInt(Board.WIDTH);
			while (gameBoard.getHeight(randMove) == Board.HEIGHT) {
				randMove = rand.nextInt(Board.WIDTH);
			}
			return randMove;
		}
		
		// else - build min max tree and play
		int action = calcTreeToDepth(gameBoard, treeDepth);
		return action;
	}
	
	/**
	 * @return force move column if force move exists, otherwise -1
	 */
	private int playForcedMove(Board board) {
		// check forced move for player (= win move)
		for (int i = 0; i < Board.WIDTH; i++) {
			if (board.getHeight(i) != Board.HEIGHT) {
				if (board.forcedMoveExists(i, Coin.PLAYER)) {
					board.setDidWin(true); // update win state
					return i;
				}
			}
		}
		
		// check forced move for opponent (= block opponent from winning)
		for (int i = 0; i < Board.WIDTH; i++) {
			if (board.getHeight(i) != Board.HEIGHT) {
				if (board.forcedMoveExists(i, Coin.OPPONENT)) {
					return i;
				}
			}
		}
		
		return -1; // force move doesn't exists
	}
	
	/**
	 * Build min max tree to the given depth.
	 * Randomization - we have (1/moves count+2) probability to not play the best action, but one of the best three actions. In this case,
	 * the probability to play a move is determined by its score.
	 * @return The best move to play
	 */
	private int calcTreeToDepth(Board board, int depth) {
		int bestIndex = -1;
		double beta = Double.POSITIVE_INFINITY;
		double alpha = Double.NEGATIVE_INFINITY;
		
		List<TreeResult> allResults = new ArrayList<TreeResult>(); // save all results, used for the random play
		
		// try to play on every column
		for (int i = 0; i < Board.WIDTH; i++) {
			int column = indexs[i];			
			if (board.getHeight(column) != Board.HEIGHT) { // can play on this column
				board.setCoin(column, Coin.PLAYER);
				double sonScore = calcTreeToDepth(board, Coin.OPPONENT, depth-1, alpha, beta);
				allResults.add(new TreeResult(sonScore, column));
				board.removeCoin(column);
				if (sonScore > alpha) { // save best result
					alpha = sonScore;
					bestIndex = column;
				}
			}
		}
		
		// every move leads to loss - return random move 
		if (bestIndex == -1) {
			for (int i = 0 ; i < Board.WIDTH ; i++) {
				if (board.getHeight(i) != Board.HEIGHT){
					return i;
				}
			}
		}
		
		
		// randomize - play one of the best three actions, the probability to play a move is determined by its score
		if (alpha < Double.POSITIVE_INFINITY && rand.nextInt(movesCount + 2) == 0) { // (1/moves count+2) probability to play random
			Collections.sort(allResults);
			double sumScors = 0;
			for (int i = 0; i < allResults.size() && i < 3; i++) {
				
				if (allResults.get(i).bestScore < 0) { // if one of the scores is negative - do not random
					return bestIndex;
				}
				
				sumScors += allResults.get(i).bestScore;
			}
			double point = rand.nextDouble() * sumScors;
			
			if (point <= allResults.get(0).bestScore) {
				return allResults.get(0).nodeIndex;
			} else if (point <= allResults.get(1).bestScore + allResults.get(0).bestScore) {
				return allResults.get(1).nodeIndex;
			} else {
				return allResults.get(2).nodeIndex;
			}
		}

		return bestIndex;
	}

	/**
	 * Build min max tree to the given depth with alpha-beta Pruning.
	 * @return The best score of the tree
	 */
	private double calcTreeToDepth(Board board, Coin currentCoin, int depth, double alpha, double beta) {
		
		if (depth == 0) {
			return calculator.calculateScore(board);
		}

		boolean movePlayed = false;
		
		if (currentCoin == Coin.PLAYER) { // Return max result 
			
			for (int i = 0; i < Board.WIDTH; i++) {
				int column = indexs[i];
				if (board.getHeight(column) != Board.HEIGHT) {
					movePlayed = true;

					// win move - return infinity
					if (board.forcedMoveExists(column, Coin.PLAYER)) {
						return Double.POSITIVE_INFINITY;
					}
					
					board.setCoin(column, Coin.PLAYER);
					alpha = Math.max(alpha, calcTreeToDepth(board, Coin.OPPONENT, depth-1, alpha, beta));
					board.removeCoin(column);
					if (beta <= alpha) { // Alpha pruning
						break;
					}
				}
			}

			// no moves available
			if (!movePlayed) {
				return calculator.calculateScore(board);
			}
			
			return alpha;
		} else { // Min result
			for (int i = 0; i < Board.WIDTH; i++) {
				int column = indexs[i];
				if (board.getHeight(column) != Board.HEIGHT) {
					movePlayed = true;

					// losing move - return negative infinity
					if (board.forcedMoveExists(column, Coin.OPPONENT)) {
						return Double.NEGATIVE_INFINITY;
					}
					
					board.setCoin(column, Coin.OPPONENT);
					beta = Math.min(beta, calcTreeToDepth(board, Coin.PLAYER, depth-1, alpha, beta));
					board.removeCoin(column);
					if (beta <= alpha) { // beta pruning
						break;
					}
				}
			}
			
			// no moves available
			if (!movePlayed) {
				return calculator.calculateScore(board);
			}
			
			return beta;
		}
	}
	
	private class TreeResult implements Comparable<TreeResult> {

		public TreeResult(double alpha, int bestIndex) {
			bestScore = alpha;
			nodeIndex = bestIndex; 
		}
		public double bestScore;
		public int nodeIndex;
		
		@Override
		public int compareTo(TreeResult o) { 
			return Double.compare(o.bestScore, bestScore); // sort from max to min
		}
	}
}
