//
// miniMax Algorithm for Nim Game with some modifications
// Thanks to http://today.java.net/pub/a/today/2004/05/18/nim1.html
//

class Node
{
   int empties; // Number of matches remaining
                 // after a move to this Board
                 // from the parent Board.
   char player;  // Game configuration from which
                 // player (X - player X, O -
                 // player O) makes a move.
   Node one;    // Link to one child Board -- a
                 // move is made to one Board
                 // when 1 match is taken. (This
                 // link is only null when the
                 // current Board is a leaf.)
   Node two;  // Link to two child Board --
                 // a move is made to this Board
                 // when 2 matches are taken.
                 // (This link may be null, even
                 // if the current Board is not a
                 // leaf.)
   Node three;   // Link to three child Board -- a
                 // move is made to this Board
                 // when three matches are taken.
                 // (This link may be null, even
                 // if the current Board is not a
                 // leaf.)

   char board[];
   
   // Helper method to switch players
    char switchPlayer(char player)
   {
	   if (player == 'X') return 'O';
	   else return 'X';
   }
   
   // Helper method to copy boards
    void copyBoard(char[] original, char[] copy)
   {
	   for (int i=0; i<original.length; i++)
	   {
		   copy[i]=original[i];
	   }
   }
   
   // Helper method to make moves case 3 puts 3 pieces on board, case 2 puts 2 pieces on board
    char[] makeMoves(char[] oldBoard, int moveType, int empties, char player)
   {
	   char[] result = new char[oldBoard.length];
	   copyBoard(oldBoard, result);
  	
	   switch(moveType)
	   {
	   case 3:
		   result[oldBoard.length-empties+2] = player;   
	   case 2: 
		   result[oldBoard.length-empties+1] = player;   
	   case 1:
		   result[oldBoard.length-empties] = player;   
	   }
	   
	   return result;
   }
   
    void displayBoard(char[] board, int empties)
   {
	   for (int i=empties; i<board.length; i++)
	   {
		System.out.print(" ");   
	   }
	   for (int i=0; i<board.length; i++)
	   {
		  if (board[i]=='\0') board[i]=' ';
		  System.out.print("| "+board[i]+" |");
	   }
	   System.out.println();
   }
   
    Node buildGameTree (char[] oldBoard, int empties, char player)
   {
	   Node n = new Node ();
	   n.empties = empties;
	   n.player = player;
	   n.board = oldBoard;
	   n.one=n.two=n.three=null;
	   
	   displayBoard(n.board, empties);
	   
	   // Base Case (we're done building game tree)
	   if (empties == 0) 
	   {
		   return n;
	   }
	   // Can put down one piece
	   if (empties >= 1)
	   { 	
		   char[] newBoard = makeMoves(oldBoard,1,empties,player);
		   n.one = buildGameTree (newBoard, empties-1, switchPlayer(player));
	   }
	   // Can put down two pieces
	   if (empties >= 2)
	   {
		   char[] newBoard = makeMoves(oldBoard,2,empties,player);
		   n.two = buildGameTree (newBoard, empties-2,switchPlayer(player));
	   }
	   // Can put down 3 pieces
	   if (empties >= 3)
	   {
		   char[] newBoard = makeMoves(oldBoard,3,empties,player);
		   n.three = buildGameTree (newBoard, empties-3,switchPlayer(player));
	   }

	   return n;
   }

   // Helper method to compute score.  Score is 1 if player X wins and -1 if player B wins
   // but this is reversed because of the way that the board is populated.. we're actually
   // at the end of the board for the previous player.
    int getScore(char player)
   {
	   if (player == 'X') return -1;
	   else return 1;
   }
   
    int computeMinimax (Node n)
 {
		int ans = 0;

		// We're at the end of the tree... return score for player
		if (n==null)
		{
			System.out.println("computeMinimax::Error! Null Node!");
			return 0;
		}
		else if (n.empties == 0)
		{
			return getScore(n.player);
		}
		// We need to continue exploring the tree for player "X"
		else if (n.player == 'X') {
			// What's the best score if we put down one piece?
			ans = Math.max(-1, computeMinimax(n.one));

			// What's the best score if we put down two pieces?
			if (n.two != null) {
				ans = Math.max(ans, computeMinimax(n.two));
			}

			// What's the best score if we put down three pieces?
			if (n.three != null) {
				ans = Math.max(ans, computeMinimax(n.three));
			}
		}
		
		// We need to continue exploring the tree for player "O"
		else if (n.player == 'O') {
			ans = Math.min(1, computeMinimax(n.one));

			if (n.two != null) {
				ans = Math.min(ans, computeMinimax(n.two));
			}

			if (n.three != null) {
				ans = Math.min(ans, computeMinimax(n.three));
			}
		}
	   
	   return ans;
   }
   
	public static void main(String[] args) {
		
		// Build a game tree to keep track of all possible
		// game configurations that could occur during
		// games of Nim with an initial pile of four
		// matches. The first move is made by player X.
		char[] board = {'X','X','O',' ',' ',' '};
				
		Node root = new Node();
		root = root.buildGameTree(board, 2, 'X');

		// Use the minimax algorithm to determine if
		// player A's optimal move is the child Board to
		// the one of the current root Board, the child
		// Board directly below the current root Board, or
		// the child Board to the three of the current root
		// Board.
		int v1 = root.computeMinimax(root.one);
		int v2 = root.computeMinimax(root.two);
		int v3 = root.computeMinimax(root.three);
		if (v1 >= v2 && v1 >= v3)
			System.out.println("Put one piece down.");
		else if (v2 >= v1 && v2 >= v3)
			System.out.println("Put two pieces down.");
		else if (v3 >= v1 && v3 >= v2)
			System.out.println("Put three pieces down.");
		else
			System.out.println("?");
	}
}