TicTacToe minimax algorithm. Could use some input

Question

I'm trying to write the minimax function so that the computer always wins or ties. So I've got my algorithm to the point where it is reactionary and ties the majority of the time (sometimes wins sometimes loses). Here is what I have so far.

public int minimax(char[][] state, int depth, boolean maximizingPlayer){
    BoardState node = new BoardState(state);

    if(depth == 0 || new BoardState(state).terminalState()){
        return score(node);
    }

    if(maximizingPlayer){
        int bestValue = Integer.MIN_VALUE;
        ArrayList<int[]> moves = node.moves();

        for(int[] move : moves){
            state[move[0]][move[1]] = mark;

            int value = minimax(state, depth - 1, false);

            if(value > bestValue){
                bestValue = value;
                bestX = move[0];
                bestY = move[1];
            }

            state[move[0]][move[1]] = '-';
        }

        return bestValue;
    }
    else{
        int bestValue = Integer.MAX_VALUE;
        ArrayList<int[]> moves = node.moves();

        for(int[] move : moves){
            state[move[0]][move[1]] = context.getOpposingMark();

            int value = minimax(state, depth - 1, true);

            if(value < bestValue){
                bestValue = value;
                bestX = move[0];
                bestY = move[1];
            }

            state[move[0]][move[1]] = '-';
        }

        return bestValue;
    }
}


private int score(BoardState node){
    if(node.winner(mark)){
        return 10;
    }
    else if(node.winner(context.getOpposingMark())){
        return -10;
    }
    else if(node.winningPosition(mark)){
        return 1;
    }
    else if(node.winningPosition(context.getOpposingMark())){
        return -1;
    }
    else{
        return 0;
    }
}

My function call looks like this.

minimax(state, 2, true);

The problem I'm having is that if the depth is increased, the computer is less likely to block the opponent from winning. However, since the depth is only two I do not believe the algorithm has enough insight to block forking moves (when the opposing player has a move where they can place a move in two locations to win the game). Does anyone have some advice or pointers as to how I can modify the algorithm? I can provide additional source code if necessary.

Answer 1

All your non-terminal positions have the same score of 0. Take a closer look at pre-terminal positions, that is, those where one move can lead to instant winning.

Try, for instance, to score +1 for each winning move you have in the position, and -1 or -2 for each winning move the opponent has in the position. This will make the algorithm more readily prune branches where opponent has many ways to win and you have few.

Counting immediate winning moves should be fairly cheap. Of course, this is basically a built-in step of descent, so your descent depth would be effectively one more. You can decrease the initial allowed depth.