import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.Random;
import java.util.BitSet;
import java.util.*;

/*
 * Created on September 20, 2007
 */

public class Hope3 extends ComputerPlayer {
	
	int maxDepth = 28;
	static final int LOSS = -10;
	static final int WIN = 10;
	static final int maxWidth = 70;
	static int storeDepth = 4;			// increasing this requires more memory but speeds search at higher levels
	static final int bookSize = 2;		// increasing this adds randomization in later moves
	int totalMoves, totalAB, plyMoves, prune;
	int depth;
	int moveNumber;
	int width = 1;
	long[] adj;
	static final long unit = 1;
	long column4, column3, column5, column35, center, initial, second, row35;	// only initial and second currently used
	
	class HaltException extends Exception {
		HaltException(String s) {
			super(s);
		}
	}
	
	
	class Node implements Comparable{
		private long move;
		private long destroy;
		private int score;
		private ArrayList movelist; 
		
		public Node() {
			this.move = 0;
			this.destroy = 0;
			this.score = 0;
			movelist = null;
		}
		
		public Node(long m, long d, int s) {
			move = m;
			destroy = d;
			score = s;
			movelist = null;
		}
		
		public Node(long m, long d, int s, ArrayList r) {
			move = m;
			destroy = d;
			score = s;
			movelist = r;
		}
		public int compareTo(Object o) {				// natural order is descending order
			Node ms = (Node)o;
			if (this.score == ms.score)
				return 0;
			else if (this.score > ms.score)
				return -1;
			else return 1;
		}
	}
	
	public static void printbd(long b) {
		for (int y = 0; y < 7; y++) {
			for (int x = 0; x < 7; x++) {
				if (b % (2) == 0)
					System.out.print("0 ");
				else
					System.out.print("1 ");
				b = b >>> 1;
			}
			System.out.println();
		}
		System.out.println();			
	}

	
	public Hope3(Game game, PlayerNumber p, String limit )
	{
		super("Hope3", game, p, limit);
		moveNumber = 0;
		adj = new long[49];
		for (int i = 0; i < 49; i++) {
			long x = 0;
			if ((i + 6) < 49 && (i + 6) % 7 != 6)
				x = x + (unit <<  (i + 6));
			if ((i + 7) < 49)
				x = x + (unit << (i + 7));
			if ((i + 8) < 49 && (i + 8) % 7 != 0)
				x = x + (unit << (i + 8));
			if ((i - 1) >= 0 && (i - 1) % 7 != 6)
				x = x + (unit << (i - 1));
			if ((i + 1) % 7 != 0)
				x = x + (unit << (i + 1));
			if ((i - 8) >= 0 && (i - 8) % 7 != 6)
				x = x + (unit << (i - 8));
			if ((i - 7) >= 0)
				x = x + (unit << (i - 7));
			if ((i - 6) > 0 && (i - 6) % 7 != 0)
				x = x + (unit << (i - 6));
			adj[i] = x;
		}
		column4 = 0;
		for (int i = 0; i < 49; i++)
			if (i % 7 == 3)
				column4 = column4 + (unit << i);
		column3 = 0;
		for (int i = 0; i < 49; i++)
			if (i % 7 == 2)
				column3 = column3 + (unit << i);
		column5 = 0;
		for (int i = 0; i < 49; i++)
			if (i % 7 == 4)
				column5 = column5 + (unit << i);
		row35 = 0;
		for (int i = 0; i < 49; i++)
			if (i / 7 == 2 || i / 7 == 4)
				row35 = row35 + (unit << i);;
		initial = 0;
		for (int i = 0; i < 49; i++)
			if (i != 3 && i != 45)
				initial = initial + (unit << i);
		second = 0;
		for (int i = 0; i < 49; i++)
			if (i != 3 && i != 45 && i != 10)
				second = second + (unit << i);
		long column35 = column3 | column5;
/*		for (int i = 0; i < 49; i++) {
			long b = adj[i];
			printbd(b);
		}
		printbd(column4);
		printbd(column3);
		printbd(column5);
		printbd(column35);
		printbd(row35);
		printbd(initial);
		System.out.println(initial);
*/	}
	
	public Move findbest(Game g) throws GameException {
		plyMoves=0;
		prune=0;
		moveNumber++;
		System.out.println("Move number " + moveNumber);
		Move move;
		MoveIterator iter = g.getMoves();
		move = iter.next();
		move = iterativeDeepening((Isola)g);
		System.out.println();
		return move;
	}
	
	public Move iterativeDeepening(Isola g) throws GameException {
		
		Move mov = null;
		Node ms;
		Node root;
		int alpha, beta;
		Random rd;
		long xboard, board;										// x-prefixes indicate original data for this move
		long xmovePiece, xotherPiece, movePiece, otherPiece;
		int xmovePieceLoc, xotherPieceLoc, movePieceLoc, otherPieceLoc;
		int ply;
		long start = 0;
		
		
		((Isola)g).startEval();
		Collection c = g.board.members.values();
		Iterator iter = c.iterator();
		xboard = 0;
		while (iter.hasNext()){							//convert Isola format to long bitboards
			BoardCell cell = (BoardCell)iter.next();
			int i = cell.getX(), j = cell.getY();
			xboard = xboard + (unit << ((i - 1) + 7 * (j - 1)));
		}
		xmovePiece = 0;					//get piece BitBoards
		xotherPiece = 0;
		int x0 = ((PlayerPiece) g.players[0].getPlayerPiece()).getX(); 
		int y0 = ((PlayerPiece) g.players[0].getPlayerPiece()).getY(); 
		int x1 = ((PlayerPiece) g.players[1].getPlayerPiece()).getX(); 
		int y1 = ((PlayerPiece) g.players[1].getPlayerPiece()).getY(); 
		if(g.getCurrentPlayer().playerNumber.equals(PlayerNumber.ONE)){
			xmovePiece = unit << ((x0 - 1) + 7 * (y0 - 1));
			xotherPiece = unit << ((x1 - 1) + 7 * (y1 - 1));
		} 
		else {
			xmovePiece = unit << ((x1 - 1) + 7 * (y1 - 1)); 
			xotherPiece = unit << ((x0 - 1) + 7 * (y0 - 1));
		}
		xmovePieceLoc = Long.numberOfTrailingZeros(xmovePiece);
		xotherPieceLoc = Long.numberOfTrailingZeros(xotherPiece);
		root = new Node(0,0,0);								//initialize storage tree
		root.movelist = new ArrayList();
		totalMoves = 0;
		totalAB = 0;
		try {
			for (depth = 1; depth < maxDepth; depth++) {
				start = new Date().getTime();
				System.out.println();
				System.out.println("Hope3 Depth = " + depth);
				board = xboard;
				movePiece = xmovePiece;
				otherPiece = xotherPiece;
				movePieceLoc = xmovePieceLoc;
				otherPieceLoc = xotherPieceLoc;
				plyMoves = 0;
				prune = 0;
				alpha = LOSS;
				beta = WIN;
				ply = 0;

				root.score  = negamax(ply + 1, board, alpha, beta, root.movelist, movePiece, otherPiece);

				Collections.sort(root.movelist);
				ms = (Node) root.movelist.get(0);
				root.move = ms.move;
				root.destroy = ms.destroy;
				if (ms.score >= WIN) {
					// uncomment the following line for diagnostics
					goodMoveDiagnostics(root);
					
				}
				// uncomment following line for debugging
				diagnostics(root, start, depth);

				totalMoves = plyMoves + totalMoves;
				totalAB = prune + totalAB;
				if (halt){
					throw new HaltException("Halting at 1");
				}
			}
		}catch(HaltException e) {
			System.out.println(e);
			if (width != 0) width--;		  //discard branch that was in process
			
			summary(root);
			
			if (moveNumber < bookSize)
				return opening(xboard, root.movelist, xmovePieceLoc, xotherPieceLoc);
				
			// uncomment the next line for diagnostics
			//beforeDiagnostics(root);
			
			ArrayList bestmoves = new ArrayList();
			bestmoves.add((Node)root.movelist.get(0));
			for (int i = 1; i < width - 1; i++){
				bestmoves.add((Node)root.movelist.get(i));
			}
			Collections.sort(bestmoves);
			
			// uncomment the next line for diagnostics
			// afterDiagnostics(bestmoves);
			
			ms = (Node) bestmoves.get(0);
			PlayerPiece p = new PlayerPiece();
			p.move(Long.numberOfTrailingZeros(ms.move) % 7 + 1, Long.numberOfTrailingZeros(ms.move) / 7 + 1);

			mov = new Move();
			mov.piece = p;
			mov.cell = new BoardCell(Long.numberOfTrailingZeros(ms.destroy) % 7 + 1, Long.numberOfTrailingZeros(ms.destroy) / 7 + 1);
			return mov;

		}
		Collections.sort(root.movelist);
		summary(root);
		if (moveNumber < bookSize)
			return opening(xboard, root.movelist, xmovePieceLoc, xotherPieceLoc);
				
		// uncomment following line for debugging
		//diagnostics(root, start, depth);

		ms = (Node) root.movelist.get(0);
		PlayerPiece p = new PlayerPiece();
		p.move(Long.numberOfTrailingZeros(ms.move) % 7 + 1, Long.numberOfTrailingZeros(ms.move) / 7 + 1);
		mov = new Move();
		mov.piece = p;
		mov.cell = new BoardCell(Long.numberOfTrailingZeros(ms.destroy) % 7 + 1, Long.numberOfTrailingZeros(ms.destroy) / 7 + 1);
		return mov;
	}
	
	public int negamax(int ply, long board, int alpha, int beta, ArrayList list, long movePiece, long otherPiece) throws HaltException {
		
		int val;
		Node ms;
		Move mov;
		ArrayList movelist;
		long moveAdj, otherAdj, moveBoard, otherBoard, destroyBoard;
		long unit = 1;
		int movePieceLoc, otherPieceLoc;
	
		movePieceLoc = Long.numberOfTrailingZeros(movePiece) % 64;
		otherPieceLoc = Long.numberOfTrailingZeros(otherPiece) % 64;
		moveAdj = adj[movePieceLoc];
		otherAdj = adj[otherPieceLoc];
		
		moveBoard = (board ^ otherPiece) & moveAdj;
		if(moveBoard == 0) 
			return LOSS;
		otherBoard = board & otherAdj;
		if(otherBoard == 0)
			return WIN;				//just committed suicide
		 
		// evaluation
		if(ply > depth){
			plyMoves++;
			if(otherBoard == movePiece)
				return WIN;
			return Long.bitCount(moveBoard) - Long.bitCount(otherBoard);
		}

		// if list != null we may already have a list of moves

		if (list != null) {
			movelist = list;

			// move generation 
			if (movelist.size()==0) { 
				long killers = board ^ (otherBoard | otherPiece);
				long k = Long.lowestOneBit(killers);
				for (long i = moveBoard; i > 0; i = i & (i - 1)) {
					for (long j = otherBoard; j > 0; j = j & (j - 1) ) {
						long iPiece = Long.lowestOneBit(i);
						long jloc = Long.lowestOneBit(j);
						if (iPiece != jloc)
							movelist.add(new Node(iPiece, jloc, 0));	
						else if (killers != 0)
							movelist.add(new Node(iPiece, k, 0));
					}
				}
			}

			// AB search on movelist
			int i = 0;
			while (i < movelist.size()){
				if(halt) {
					width = i;
					throw new HaltException("Halting at 3");
				}
				try {
					ms = (Node) movelist.get(i);
					long newboard = board ^ ms.destroy;
					
					//Search
					if (ms.movelist == null && ply < storeDepth)
						ms.movelist = new ArrayList();

					ms.score = -negamax(ply + 1, newboard, -beta, -alpha, ms.movelist, otherPiece, ms.move);
					
					//Insert new score in movelist
					movelist.set(i, ms);

					if(ms.score > alpha)
						alpha = ms.score;

					if(ms.score >= beta){
						prune++;
						Collections.sort(movelist);
						return beta;
					}
				}
				catch(Exception e){
					System.out.println(e.getMessage());
					System.out.println("Ply = " + ply);
				}
				i++;
			}
			Collections.sort(movelist);
			return alpha;
		}

		// incremental generation -- done after search exceeds storeDepth
		else {
			//movelist = new ArrayList();
			//moveBoard = (board ^ otherPiece) & moveAdj;
			//destroyBoard = board & otherAdj;
			long killers = board ^ (otherBoard | otherPiece);
			long k = Long.lowestOneBit(killers);
			try {
				for (long i = moveBoard; i > 0; i = i & (i - 1)) {
					for (long j = otherBoard; j > 0; j = j & (j - 1) ) {
						long iPiece = Long.lowestOneBit(i);
						long jloc = Long.lowestOneBit(j);

						if (iPiece != jloc) {
							long newboard = board ^ jloc;
							val = -negamax(ply + 1, newboard, -beta, -alpha, null, otherPiece, iPiece);
							if(val > alpha){
								alpha = val;
							}	
							if(val >= beta){
								prune++;
								return beta;
							}
						}
						else if (killers != 0) {
							long newboard = board ^ k;
							val = -negamax(ply + 1, newboard, -beta, -alpha, null, otherPiece, iPiece);
							if(val > alpha){
								alpha = val;
							}	
							if(val >= beta){
								prune++;
								return beta;
							}
						}
					}
				}
			} catch(Exception e){
				System.out.println(e.getMessage());
				System.out.println("Ply = " + ply);
			}
			return alpha;
		}			
	}


	public Move opening(long xboard, ArrayList movelist, int xmovePieceLoc, int xotherPieceLoc) {
		Random rd;
		Move mov, mov1, mov2;
		PlayerPiece p;
		Node ms;
			
		mov = new Move();
		if (xboard == initial) {
			rd = new Random();
			p = new PlayerPiece();
			int r = rd.nextInt(9);
			if (r < 3) {
				p.move(4, 6);
				mov.piece = p;
				mov.cell = new BoardCell(4, 2);
			}
			else if (r < 4) {
				p.move(4, 6);
				mov.piece = p;
				mov.cell = new BoardCell(3, 2);
			}
			else if (r < 5) {
				p.move(4, 6);
				mov.piece = p;
				mov.cell = new BoardCell(5, 2);
			}
			else if (r < 6) {
				p.move(3, 6);
				mov.piece = p;
				mov.cell = new BoardCell(5, 2);
			}
			else if (r < 7) {
				p.move(5, 6);
				mov.piece = p;
				mov.cell = new BoardCell(3, 2);
			}
			else if (r < 8) {
				p.move(4, 6);
				mov.piece = p;
				mov.cell = new BoardCell(7, 3);
			}
			else {
				p.move(4, 6);
				mov.piece = p;
				mov.cell = new BoardCell(4, 3);
			}
		}
		else if (xboard == second) {
			if (xotherPieceLoc == 39) {
				rd = new Random();
				p = new PlayerPiece();
				int r = rd.nextInt(4);
				if (r < 1) {
					p.move(3, 2);
					mov.piece = p;
					mov.cell = new BoardCell(4, 5);
				}
				else if (r < 2) {
					p.move(3, 2);
					mov.piece = p;
					mov.cell = new BoardCell(5, 5);
				}
				else if (r < 3) {
					p.move(3, 2);
					mov.piece = p;
					mov.cell = new BoardCell(6, 5);
				}
				else {
					p.move(3, 2);
					mov.piece = p;
					mov.cell = new BoardCell(6, 6);
				}			
			}
			else if (xotherPieceLoc == 37) {
				rd = new Random();
				p = new PlayerPiece();
				int r = rd.nextInt(4);
				if (r < 1) {
					p.move(5, 2);
					mov.piece = p;
					mov.cell = new BoardCell(4, 5);
				}
				else if (r < 2) {
					p.move(5, 2);
					mov.piece = p;
					mov.cell = new BoardCell(3, 5);
				}
				else if (r < 3) {
					p.move(5, 2);
					mov.piece = p;
					mov.cell = new BoardCell(2, 5);
				}
				else {
					p.move(5, 2);
					mov.piece = p;
					mov.cell = new BoardCell(2, 6);
				}
			}
			else {
				ms = (Node) movelist.get(0);
				p = new PlayerPiece();
				p.move(Long.numberOfTrailingZeros(ms.move) % 7 + 1, Long.numberOfTrailingZeros(ms.move) / 7 + 1);
				mov.piece = p;
				mov.cell = new BoardCell(Long.numberOfTrailingZeros(ms.destroy) % 7 + 1, Long.numberOfTrailingZeros(ms.destroy) / 7 + 1);
			}
		}
		else {
			ms = (Node) movelist.get(0);
			if (movelist.size() > 1) {
				rd = new Random();
				if (rd.nextInt() % 2 == 0)
					ms = (Node) movelist.get(0);
				else
					ms = (Node) movelist.get(1);
			}
			p = new PlayerPiece();
			p.move(Long.numberOfTrailingZeros(ms.move) % 7 + 1, Long.numberOfTrailingZeros(ms.move) / 7 + 1);
			mov.piece = p;
			mov.cell = new BoardCell(Long.numberOfTrailingZeros(ms.destroy) % 7 + 1, Long.numberOfTrailingZeros(ms.destroy) / 7 + 1);
		}
		System.out.println("Making book move...   (" + mov.piece.getX() + "," + mov.piece.getY() +" -- " + mov.cell.getX() + "," + mov.cell.getY() + ")   ");
		System.out.println();
		return mov;
	}
				
	
		
	public void diagnostics(Node root, long start, int depth) {
		Node ms;
		boolean minimalDiagnostics = true;
		
		System.out.println();
		System.out.println("MoveNumber " + moveNumber + " Depth " + depth + " finished");
		System.out.println("Width = " + root.movelist.size());
		System.out.println("Nodes evaluated: " + plyMoves);
		System.out.println("A-B cutoffs: " + prune);
		ms = (Node) root.movelist.get(0);
		if (minimalDiagnostics) {
			System.out.print("Score: " + ms.score + " -- " + " (" + (Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + ")  ");
			System.out.println();
		}
		else {
			for (int i = 0; i < root.movelist.size(); i++) {			 // print out ply 1
				ms = (Node) root.movelist.get(i);
			System.out.print("Score: " + ms.score + " -- " + " (" + (Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + ")  ");
				System.out.println();
			}
			System.out.println();
		}
		System.out.print("Principle variation: ");					 // print principle variation
		ms = root;
		while (ms.movelist != null && ms.movelist.size() != 0) {
			ms = (Node) ms.movelist.get(0);
			System.out.print("(" + ( Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + "):" + ms.score + "  ");
		}
		System.out.println();
		long stop = new Date().getTime();
		long elapsed = stop - start;
		System.out.println("Elapsed time: " + elapsed + " milliseconds");
		System.out.println();		
	}

	public void summary(Node root) {
		System.out.println("Final width searched: " + width);
		System.out.println("Total Nodes evaluated: " + totalMoves);
		System.out.println("Total A-B cutoffs: " + totalAB);
		Node ms = (Node) root.movelist.get(0);
		System.out.println("Score: " + ms.score + " -- " + " (" + (Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + ")  ");
	}
	
	public void beforeDiagnostics(Node root){
		System.out.println("Before: ");
		for (int i = 0; i < width - 1 && i < root.movelist.size(); i++) {
			Node ms = (Node) root.movelist.get(i);
			System.out.print("Score: " + ms.score + " -- " + " (" + (Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + ")  ");
			System.out.println();
		}
		System.out.println();	
	}
	
	public void afterDiagnostics(ArrayList bestmoves) {
		System.out.println("After: ");
		for (int i = 0; i < bestmoves.size(); i++) {
			Node ms = (Node) bestmoves.get(i);
			System.out.print("Score: " + ms.score + " -- " + " (" + (Long.numberOfTrailingZeros(ms.move) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.move) / 7 + 1) + " - " + (Long.numberOfTrailingZeros(ms.destroy) % 7 + 1) + "," + (Long.numberOfTrailingZeros(ms.destroy) / 7 + 1) + ")  ");
			System.out.println();
		}
	}
	
	public void goodMoveDiagnostics(Node root) {
		System.out.println("Found good move...");
	}
	
}