import java.util.ArrayList;
/**
 * The class MMab contains the logic for Alpha Beta pruning Algorithm. To get a minimax move for a given board
 * position call getMaxMove()function.
 * @author sanshack
 *
 */
public class MMab {
	public static String maxChild;
	public static long numEstimation=0;
	public static long maxEstimate =0;
	
	/**
	 * This function would return a Mini Max move with alpha beta pruning.
	 * @param initialPosition
	 * @param totaldepth
	 * @param mode
	 * @return move
	 */
	public String getMaxMove(String initialPosition,int totaldepth,int mode) {
		int a=-10001;
		int b=10001;
		maxEstimate=MaxMin(initialPosition,0,totaldepth,a,b,mode);
		if(maxChild==null)maxChild=initialPosition;
		System.out.println("Board Position: "+maxChild);
		System.out.println("Positions Evaluated by static estimation:"+numEstimation);
		System.out.println("MINIMAX estimate="+maxEstimate);
		ArrayList<String> childList1 = new ArrayList<String>();
		childList1 = GenerateMoves(maxChild,totaldepth,'B',1);
		int numBlackMoves =childList1.size();
		int value = StaticEstimator.midEndGameEstimator(maxChild, numBlackMoves);
		if(value <= -10000 && mode==1){
			System.out.println("Player 2 wins");
		}  else if(value >= 10000 && mode==1) {
			System.out.println("Player 1  wins");
		}
		return maxChild;
	}
	
	/**
	 * 
	 * Recursive Max Min function
	 * @param x
	 * @param depth
	 * @param totaldepth
	 * @param mode
	 * @return Max value
	 */
	public int MaxMin(String x,int depth,int totaldepth,int a,int b,int mode) {
		int numWhite = Utility.countChar(x, 'W');
		int numBlack = Utility.countChar(x, 'B');
		ArrayList<String> childList1 = new ArrayList<String>();
		childList1 = GenerateMoves(x,depth,'B',mode);
		int numBlackMoves =childList1.size();
		ArrayList<String> childList2 = new ArrayList<String>();
		childList2 = GenerateMoves(x,depth,'B',mode);
		int numWhiteMoves =childList2.size();
		if(depth==totaldepth || ((mode==1)&&((numWhite<=2) || (numBlack<=2) ||(numWhiteMoves==0)))) {
			numEstimation++;
			//System.out.println("numblackmoves1 start");
			//System.out.println("depth="+depth);
			
			//System.out.println("numbBalcke="+numBlackMoves);
			if(mode==1) {
				return StaticEstimator.midEndGameEstimator(x,numBlackMoves);
			} else {
				return StaticEstimator.defaultEstimator(x);	
			}
				
			
		}
		else {
			int v =-100000;			
			ArrayList<String> childList = GenerateMoves(x,depth,'W',mode);
			java.util.Iterator<String> iter = childList.iterator();
			while(iter.hasNext()) {
				String childString = iter.next();
				int var = MinMax(childString,depth+1,totaldepth,a,b,mode);
				if(var > v) {
					if(depth==0) {
						maxChild = childString;
						//System.out.println(maxChild+"        "+depth);
						maxEstimate = var;
					}					
					v = var;
					
				}
				if(v>=b) {
					return v;
				} else {
					if(v>a) a=v;
				}
				
			}
			return v;
		}
	}
	
	public int max(int x ,int y) {
		if(x > y) return x;
		return y;
	}
	
	/**
	 * Recursive MinMax function
	 * @param x
	 * @param depth
	 * @param totaldepth
	 * @param mode
	 * @return Min value
	 */
	public int MinMax(String x,int depth,int totaldepth,int a,int b,int mode) {
		int numWhite = Utility.countChar(x, 'W');
		int numBlack = Utility.countChar(x, 'B');
		ArrayList<String> childList1 = new ArrayList<String>();
		childList1 = GenerateMoves(x,depth,'B',mode);
		int numBlackMoves =childList1.size();
		ArrayList<String> childList2 = new ArrayList<String>();
		childList2 = GenerateMoves(x,depth,'B',mode);
		int numWhiteMoves =childList2.size();
		if(depth==totaldepth || ((mode==1)&&((numWhite<=2) || (numBlack<=2) ||(numBlackMoves==0)))) {
			numEstimation++;
			//System.out.println("numblackmoves start");
			
			if(mode==1) {
				return StaticEstimator.midEndGameEstimator(x,numBlackMoves);
			} else {
				return StaticEstimator.defaultEstimator(x);	
			}
		}
		else {
			int v =1000000;
			ArrayList<String> childList = GenerateMoves(x,depth,'B',mode);
			java.util.Iterator<String> iter = childList.iterator();
			while(iter.hasNext()) {
				String childString = iter.next();				
				int var = MaxMin(childString,depth+1,totaldepth,a,b,mode);
				if(var < v) {
					v = var;
				}
				if(v<=a) {
					return v;
				} else {
					if(v < b)b=v;
				}
			}
			return v;
		}
	}
	
	/**
	 * Generate a moves in a list. 
	 * @param x
	 * @param depth - depth to traverse the tree
	 * @param color - generate moves of which color
	 * @param mode - 0 for opening 1 for midend game
	 * @return List of moves
	 */
	public ArrayList<String> GenerateMoves(String x,int depth,char color,int mode) {
		ArrayList<String> list;
		if(mode==0) {
			list = GenerateMovesOpening(x,depth,color);
		}else {
			list = GenerateMovesMidEndGame(x,depth,color);
		}
		
		return list;
	}
	
	/**
	 * Generate a moves in a list for mid end game. 
	 * @param x
	 * @param depth - depth to traverse the tree
	 * @param color - generate moves of which color
	 * @param mode - 0 for opening 1 for midend game
	 * @return List of moves
	 */
	public ArrayList<String> GenerateMovesMidEndGame (String x,int depth,char color) {
		//System.out.println("i am here");
		int numWhite=Utility.countChar(x, 'W');
		int numBlack=Utility.countChar(x, 'B');
		ArrayList<String> list=null;
		if((numWhite == 3 && color =='W')||(numBlack==3 && color=='B')) {
			list= GenerateHopping(x,depth,color);
		} else {
			list= GenerateMove(x,depth,color);
		} 
		if(list == null) {System.out.println("null for list");}
		return list;
	}
	
	public ArrayList<String> GenerateMovesOpening(String x,int depth,char color) {
		ArrayList<String> list = GenerateAdd(x,depth,color);
		return list;
	}
	
	/**
	 * Generate a moves in a list for opening. 
	 * @param x
	 * @param depth - depth to traverse the tree
	 * @param color - generate moves of which color
	 * @param mode - 0 for opening 1 for midend game
	 * @return List of moves
	 */
	public ArrayList<String> GenerateMove(String x,int depth,char color) {
		ArrayList<String> list= new ArrayList<String>();
		
		for(int i=0;i<Constants.BOARD_LENGTH;i++) {
			char temp = x.charAt(i);
			if(temp == color) {						
				int[] n = getNeighbors(i);
				for(int k=0;k<4;k++) {
					int j=n[k];
					if(j!=-1) {
						if(x.charAt(j)=='x')  {
							char[] charArray = new char[23];
							charArray = x.toCharArray();
							charArray[i]='x';
							charArray[j]=color;
							String tempString  = String.valueOf(charArray);
							if(closeMill(j,tempString,color)) {
								generateRemove(tempString,list,color);
							} else {
								//System.out.println("Generate mov:adding "+tempString);
								list.add(tempString);
							}
						}
					}
					
				}			
			
			}
		}
		return list;
	}
	
	/**
	 * Generate a moves in a list for end game. 
	 * @param x
	 * @param depth - depth to traverse the tree
	 * @param color - generate moves of which color
	 * @param mode - 0 for opening 1 for midend game
	 * @return List of moves
	 */
	public ArrayList<String> GenerateHopping(String x,int depth,char color) {
		ArrayList<String> list= new ArrayList<String>();
		for(int j=0;j<Constants.BOARD_LENGTH;j++) {
			if(x.charAt(j)==color) {
				for(int i=0;i<Constants.BOARD_LENGTH;i++) {
					char temp = x.charAt(i);
					if(temp == 'x') {		
						char[] charArray = new char[23];
						charArray = x.toCharArray();
						charArray[j]='x';
						charArray[i]=color;
						String tempString  = String.valueOf(charArray);
						if(closeMill(i,tempString,color)) {
							generateRemove(tempString,list,color);
						} else {
							//System.out.println("Generate hop:adding "+tempString);
							list.add(tempString);
						}
					
					}
				}
			}
			
		}		
		return list;
	}
	
	/**
	 * Generate a moves in a list by adding pieces of specified color at vacant spaces . 
	 * @param x
	 * @param depth - depth to traverse the tree
	 * @param color - generate moves of which color
	 * @return List of moves
	 */
	
	public ArrayList<String> GenerateAdd(String x,int depth,char color) {
		//System.out.println("i am here in add");
		ArrayList<String> list= new ArrayList<String>();
		
		for(int i=0;i<Constants.BOARD_LENGTH;i++) {
			char temp = x.charAt(i);
			if(temp == 'x') {		
				char[] charArray = new char[23];
				charArray = x.toCharArray();
				charArray[i]=color;
				String tempString  = String.valueOf(charArray);
				if(closeMill(i,tempString,color)) {
					generateRemove(tempString,list,color);
				} else {
					//System.out.println("Generate add:adding: "+tempString);
					list.add(tempString);
				}
			
			}
		}
		return list;
	}
	
	/**
	 * Generate list of moves possible by removing the desired piece
	 * @param b
	 * @param list
	 * @param color