import java.util.*;

      class Move {
int r;
int c;
Move(int r, int c) {
    this.r=r;
    this.c=c;
}


@Override public String toString() {
    return "Move [ "+(this.r+1)+" , "+(this.c+1)+" ]";
}
    }

     class ChildNodes {
Move move;
int value;
ChildNodes(Move move, int value) {
    this.move=move;
    this.value=value;
}

@Override public String toString() {
    return " value: "+this.value;
}
    }

    class Board {
int[][] board=new int[3][3];
char[][] mark=new char[3][3];
List<Move> availableMoves;
List<ChildNodes> childNodes;

List<Move> getAvailableMoves() {
    availableMoves=new ArrayList<>();
    for (int i=0; i<board.length; i++) {
        for (int j=0; j<board.length; j++) {
            if (board[i][j] == 0) {
                availableMoves.add(new Move(i, j));
            }
        }
    }
    return availableMoves;
}

void showBoard() {
    for (int i=0; i<board.length; i++) {

        for (int j=0; j<board.length; j++) {
            if (board[i][j] == 0) {
                mark[i][j] = '-';
            }

            if (board[i][j] == 1) {
                mark[i][j] = 'X';
            }

            if (board[i][j] == 2) {
                mark[i][j] = 'O';
            }
            System.out.print("\t["+mark[i][j]+"]\t"); 
        }

        System.out.println();
    }


}

void showHint() {
    System.out.println();
    for (int i=1; i<=3; i++) {
        for (int j=1; j<=3; j++) {
            System.out.print("\t["+i+""+j+"]\t");
        }
        System.out.println();
    }
}



boolean xHasWon() {
    for (int i=0; i<board.length; i++) {

        if ((board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] == 1) || (board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[2][i] == 1)) {
            return true;
        }

        if ( i == 0) {
            if ((board[i][i] == board[1][1] && board[1][1] == board[2][2] && board[2][2] == 1) || (board[i][2] == board[1][1] && board[1][1] == board[2][i] && board[i][2] == 1)) {
                return true;
            }
        }



    }

    return false;
}

boolean oHasWon() {
    for (int i=0; i<board.length; i++) {

        if ((board[i][0] == board[i][1] && board[i][1] == board[i][2] && board[i][0] == 2) || (board[0][i] == board[1][i] && board[1][i] == board[2][i] && board[2][i] == 2)) {
            return true;
        }

        if ( i == 0) {
            if ((board[i][i] == board[1][1] && board[1][1] == board[2][2] && board[2][2] == 2) || (board[i][2] == board[1][1] && board[1][1] == board[2][i] && board[i][2] == 2)) {
                return true;
            }
        }



    }

    return false;
}

boolean isGameOver() {

    return xHasWon() || oHasWon() || getAvailableMoves().isEmpty();
}

void placeMove(Move m, int player) {
    board[m.r][m.c]=player;
}

int minimax(int depth, boolean turn) {

    List<Move> legalStates=getAvailableMoves();

    if (xHasWon()) {
        return +1;
    }

    if (oHasWon()) {
        return -1;
    }

    if (legalStates.isEmpty() && !xHasWon() && !oHasWon()) {
        return 0;
    }

    int max=Integer.MIN_VALUE;
    int min=Integer.MAX_VALUE;

    if (turn) {
        for (int i=0; i<legalStates.size(); i++) {
            Move move=legalStates.get(i);
            placeMove(move, 1);
            int score=minimax(depth+1, false);
            max=Math.max(max, score);




            if (depth == 0 ) {
                childNodes.add(new ChildNodes(move, max));





            }

            placeMove(move, 0);












        }
    }
    else {
        for (int i=0; i<legalStates.size(); i++) {
            Move move=legalStates.get(i);
            placeMove(move, 2);
            int score=minimax(depth+1, true);
            min=Math.min(min, score);



            if (depth == 0) {

                childNodes.add(new ChildNodes(move, min));

            }
            placeMove(move, 0);



        }
    }

    return turn?max:min;
}

Move getBestMove() {
    int max=Integer.MIN_VALUE;
    int index=0;
    for (int i=0; i<childNodes.size(); i++) {
        if (max < childNodes.get(i).value) {
            max = childNodes.get(i).value;
            index = i;

        }
    }

    return childNodes.get(index).move;
}

void callMinimax(int depth, boolean turn) {
    childNodes=new ArrayList<>();
    minimax(depth, turn);
}

void newGame() {
    System.out.println("Welcome to J-Tac-Toe.\n ************************************************************ \n Author: Kingsley Victor \n Version: 1.0.0 \n ************************************************************ ");
    showBoard(); showHint();
    System.out.println("\n To place a mark, enter the corresponding row and column value\n \n");
    Scanner gameInput=new Scanner(System.in);
    System.out.println("Who plays first? Computer (1), User(2)");
    int choice=gameInput.nextInt();
    while (choice < 1 || choice > 2) {
        System.out.println("Invalid choice. Enter either 1 or 2 for computer or human to make first move respectively");
        choice=gameInput.nextInt();

    }

    if (choice == 1) {
        Random rand=new Random();
        Move m=new Move(rand.nextInt(3), rand.nextInt(3));
        placeMove(m, 1);
        showBoard();
        showHint();
    }

    while (!isGameOver()) {
        System.out.println("Make your move. \n \n");
        int r=gameInput.nextInt()-1;
        int c=gameInput.nextInt()-1;
        Move m=new Move(r, c);
        while(board[m.r][m.c] !=0) {
            System.out.println("Invalid move. Point is already occupied \n \n");
            r=gameInput.nextInt()-1;
            c=gameInput.nextInt()-1;
            m=new Move(r, c);
        }


        placeMove(m, 2);
        showBoard();

        callMinimax(0, true);
        if (isGameOver()) {
            System.out.println();
            showBoard();
            break;
        }

        try {
            System.out.println();
            System.out.println("Wait!  Computer is thinking!");
            System.out.println();
            Thread.sleep(2000);
        }
        catch(InterruptedException e) {

        }
        placeMove(getBestMove(), 1);
        showBoard(); 
        if (!isGameOver()) {
            showHint();
        }

    }

    if (xHasWon()) {
        System.out.println("Computer  wins the game");
    }

    if (oHasWon()) {
        System.out.println("Congratulations, you win the game");
    }

    if (getAvailableMoves().isEmpty() && !xHasWon() && !oHasWon()) {
        System.out.println("It's a tie!");
    }
}

    }

        public class TicTacToe {
public static void main(String[] args) {
    Board b=new Board();
    b.newGame();
}
    }