/**
 * @author Bengi Mizrahi
 *
 * To change this generated comment edit the template variable "typecomment":
 * Window>Preferences>Java>Templates.
 * To enable and disable the creation of type comments go to
 * Window>Preferences>Java>Code Generation.
 */
public class AI extends Player {
	
	public class State {
		Board board;
		State next;
		State child;
		boolean leaf;
		int movei;
		int movej;
	}
	
	public class Stack {
		int c;
		State [] buffer;
		
		public Stack (int length) {
			c = 0;
			buffer = new State [length];
		}
		
		public void push (State s) {
			buffer [c] = s;
			c++;
		}
		
		public State pop () {
			if (c == 0) return null;
			
			c--;
			State s = buffer [c];
			buffer [c] = null;
			return s;
		}
		
		public boolean isEmpty () {
			return c == 0;
		}
			
	}
	
	int side;
	static final int DEPTH = 2;
	
	public AI (int side) {
		this.side = side;
	}
		
	public void play () {
		State s = createTree (DEPTH, board.myClone(), Board.BLACK);
		movei = movej = -1;
		System.out.println (alpha_beta (s, -10000000, 100000000, Board.BLACK, DEPTH));
		System.out.println ("" + movei + " " + movej);
		board.performMove (movei, movej);
	}
	
	public State createTree (int depth, Board b, int player) {
		// the root state
		State s = new State ();
		s.leaf = false;
		s.board = b;
		
		if (depth == 0) {
			s.child = null;
			s.next = null;
			s.leaf = true;
		} else {
			s.child = new State ();
			State current = s.child;
			
			for (int i = 0; i < 8; i++) {
				for (int j = 0; j < 8; j++) {
					if (b.islegalMove (i, j, player)) {
						Board temp = b.myClone ();
						temp.performMove (i, j);
						current.movei = i;
						current.movej = j;
						current.next = createTree (depth - 1, temp, Board.opponent (player));
						current = current.next;
					}
				}
			}
		}
		return s;
	}

	int movei = -1, movej = -1;
	
	public int alpha_beta (State n, int alpha, int beta, int player, int depth) {
		if (n.leaf) {
			return n.board.evaluate (player);
		} else if (player == opponent ()) {
			State it = n.child;
			while (it.next != null && alpha < beta) {
				it = it.next;
				int result = alpha_beta (it, alpha, beta, player, depth - 1);
				if (result < beta) {
					beta = result;
				}
			}
			return beta;
		} else {
			State it = n.child;
			while (it.next != null && alpha < beta) {
				it = it.next;
				int result = alpha_beta (it, alpha, beta, opponent (), depth - 1);
				if (result > alpha) {
					alpha = result;
					if (depth == DEPTH) {
						movei = it.movei;
						movej = it.movej;
					}
				}
			}
			return alpha;
		}
	}
	
	public int opponent () {
		return board.opponent (side);
	}
	
	public static void main (String [] args) {
		AI ai = new AI (Board.BLACK);
		Board b = new Board (Board.BLACK, ai, new Human (Board.WHITE));
		ai.setBoard (b);
		ai.play ();
	}
}