Java TicTacToe MiniMax Recursively AI

Question

I'm currently working on an Android App containing TicTacToe with an AI opponent. I've come real far, but for some reason not all moves the opponent calculates are leading him to victory or a tie. I've made a recursive MiniMax algorithm (no pruning yet), and I hope somebody is able to see what's wrong here, since I really couldn't find it. I've drawn many trees so far and I've done a lot of debugging in Eclipse ADE and every step seems to be right, but in the end, it's obviously not.

So here's my function:

public int[] MiniMax( int[][] gameboard, boolean isCPUTurn, int[] move, int depth ){
    if (gameboard[1][1]==EMPTY) { // Always take middle if possible
        int[] best = {2,1,1};
        return best;
    }

    // Recursion base-case
    int winner = checkWinner();
    if ( winner == 1 || winner == 2 || winner == 3 ){ // Game is over
        int[] returnSet = {-1,-1,-1}; // leeg

        // adjust scores for Minimax    Player<----Tie---->CPU
        //                                  0       1       2
        switch (winner){
        case 1:
            returnSet[0] = 0 ; // Player wins
            break;
        case 2:
            returnSet[0] = 2; // CPU wins
            break;
        case 3:
            returnSet[0] = 1; // TIE
            break;
        default:            // impossible..
            returnSet[0] = 1;
        }
        // The last move led to the end of the game, return this outcome and move
        returnSet[1] = move[0];
        returnSet[2] = move[1];
        return returnSet;
    }

    // A move is still possible, the game's not over yet
    else{
        int[] bestMove = null;          // contains the best move found for this turn
        for (int i=0; i<3; i++){        // check all child nodes/boards
            for (int j=0; j<3; j++){

                if( gameboard[i][j] == EMPTY )              // if the spot's not yet filled
                {   
                    if (isCPUTurn) gameboard[i][j] = TWO;   // this move is CPU's
                    else gameboard[i][j] = ONE;             // this move is Player's

                    int[] thismove = {i,j}; // {move Row, move Column}

                    // recursion
                    int[] result = MiniMax( gameboard, !isCPUTurn, thismove, depth+1);
                    // result = { winner result, move Row, move Column}
                    gameboard[i][j] = EMPTY; // delete last move after recursion

                    // check if child is best option
                    if (bestMove == null) // first child is always the best initially
                        bestMove = result;
                    else {
                        if (!isCPUTurn) // for CPU, higher is better
                        {   if (result[0]>bestMove[0])
                                bestMove = result;                              
                            //if (bestMove[0]==2) return bestMove; Pruning thingy
                        }
                        else if (isCPUTurn) // for Player, lower is better
                        {   if (result[0]<bestMove[0])
                                bestMove = result;
                            //if (bestMove[0]==0) return bestMove; Pruning thingy
                        }   
                    }

                }
            }
        }
        return bestMove; // returns the best move found after checking all possible childs
    }

}

As you can see, this function calls itself directly, using middle recursion. It also calls the checkWinner function, which has 4 possible outcomes: 0 if nobody has won yet and the board is not filled, 1 if player 1 (you) has won, 2 if player 2 (AI) has won and 3 if it's a tie (and thus the board is filled).

So yea, I hope somebody finds the solution :D Thanks in advance!

Answer 1

The problem is that you are always returning the move from the deepest level. In the lines where you check if you have improved , you should set bestMoveto contain the coordinates iand j, not the coordinates from the move one level deeper, namely result.