Hi, i try to understand minimax algorthm with make game piece with 9x9 board

1 1 1

0 0 0

2 2 2

the goal of the game to move the number 1 to the other side (2) and otherwise. number 2 is user and number 1 . first is user, so i move piece from (2,0) to (1,0) so the board became

1 1 1

2 0 0

0 2 2

and next is computer turn but it become

2 2 0

2 0 0

1 2 2

anyone know why it become like that ?

public List<Point> getAvailableStates() {
    availablePoints = new ArrayList<>();
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
                if (board[i][j] == Piece.X) {
                    for(int a = 0; a < 3; a++){
                        for(int b = 0; b < 3; b++){
                            if(board[a][b] == Piece.E){
                                availablePoints.add(new Point(i, j, a, b));
                            }
                        }
                    }
                }

        }
    }
    return availablePoints;
}

Point computersMove; 

public int minimax(int depth, int turn) {  
    if (hasXWon()) return +1; 
    if (hasOWon()) return -1;

    List<Point> pointsAvailable = getAvailableStates();
    if (pointsAvailable.isEmpty()) return 0; 

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

    for (int i = 0; i < pointsAvailable.size(); ++i) {  
        Point point = pointsAvailable.get(i);   
        if (turn == Piece.X) { 
            placeAMove(point, Piece.X); 
            int currentScore = minimax(depth + 1, Piece.O);
            max = Math.max(currentScore, max);

            if(depth == 0)
                System.out.println("Score for position "+point.toString()+" = "+currentScore);
            if(currentScore >= 0){ 
                if(depth == 0) 
                    computersMove = point;} 
            if(currentScore == 1){
                board[point.toRow][point.toCol] = turn;
                board[point.fromRow][point.fromCol] = board[point.toRow][point.toCol];
                board[point.toRow][point.toCol] = Piece.E; 
                break;
            } 
            if(i == pointsAvailable.size()-1 && max < 0){
                if(depth == 0)
                    computersMove = point;
            }
        } else if (turn == Piece.O) {
            placeAMove(point, Piece.O); 
            int currentScore = minimax(depth + 1, Piece.X);
            min = Math.min(currentScore, min);
            if(min == -1){ 
                board[point.toRow][point.toCol] = turn;
                board[point.fromRow][point.fromCol] = board[point.toRow][point.toCol];
                board[point.toRow][point.toCol] = Piece.E; 
                break;
            }
        }
        board[point.toRow][point.toCol] = turn;
        board[point.fromRow][point.fromCol] = board[point.toRow][point.toCol];
        board[point.toRow][point.toCol] = Piece.E;
    } 
    return turn == Piece.X?max:min;
} 

My guess is that you share the board between all calculations, ie while you iterate through all options, you don't start from the same board ever time, you continue to use the result of the previous iteration.
At least I don't see a "board = <copy board> + <make change>" at first sight.

In recursive searches like minimax, the normal approach is to either make a new board for every node (relatively easy), or you revert the changes before you jump back to the previous level (less memory needed, but more difficult).


EDIT: To debug, print the board at the start of each iteration, so you can check it's doing the right thing.
Also, limit recursion depth to 1 and then to 2, that way the amount of output is limited, and you can manually trace it's doing what it should be doing.

Your undo logic is suspect in a couple of ways:

* Why don't you have a function to undo moves, just like you have a function to make them?

* Why don't you undo the move immediately after the recursive call to minimax?

Other pieces of advice:

* Learn how to use a debugger!

* Use the NegaMax variant so you don't have duplicated code for the min and the max part. Duplicated code is very hard to maintain. As you edit your code, there is a high probability that you'll introduce some asymmetry.

* Separate the searching of the root to a different function, or your code will end up full of `if (depth == 0)' blocks. You already have 3 and you haven't even implemented iterative deepening, aspiration windows, time control... You are also using a global variable because you don't have a place to return the move, which should tell you that you are doing it wrong.