Minimax Alpha-beta code for Java

Question

Not so long ago I learned how to implement the minimax algorithm with alpha beta pruning, and even created a perfect Tic Tac Toe player. How can I improve this?

public Best chooseMove(boolean side,int[]board,int alpha,int beta,int depth,int maxDepth){  
    Best myBest = new Best();
    Best reply;
    int num;

    if(Board.checkGameOver(board)||depth==maxDepth){
        Best fakeBest = new Best();
        fakeBest.setScore(returnPositionScore(board));
        return fakeBest;
    }

    if(side){
        myBest.setScore(alpha);
        num = numberOfEngine;
    }
    else{
        myBest.setScore(beta);
        num = numberOfOpponent;
    }
    ArrayList<Integer> availableMoves = new ArrayList<Integer>(searchAvailableMoves(board));

    for(Integer move:availableMoves){
        board[move.intValue()] = num;
        reply = chooseMove(!side,board,alpha,beta,depth+1,maxDepth);
        board[move.intValue()] = 0;
        if(side&&reply.getScore()>myBest.getScore()){
            myBest.setMove(move.intValue());
            myBest.setScore(reply.getScore());
            alpha = reply.getScore();

        }
        else if(!side&&reply.getScore()<myBest.getScore()){
            myBest.setMove(move.intValue());
            myBest.setScore(reply.getScore());
            beta = reply.getScore();

        }
        if(alpha>=beta){
            return myBest;
        }
    }

    return myBest;
}

Answer 1

As a starting point, address the issue you have: instead of returning an int (which is not sufficient for your needs), return an object that contains everything you WANT to get as a returnvalue.

In your case, that is:

1. an int (the return value of the alfabeta code)
2. a bestmove-object

So, define a return value class like this:

class MySpecialReturnvalueClass {
    int alfabetavalue;
    Best bestmove;
}

Of course you make the fields private, with getter-methods and 1 constructor with the 2 values, or setters, but that's a lower-level detail. The point is, if you NEED something to be returned, then just go and DO return it.

From that starting point, you change your code, then step back, look at the resulting code - and then you may see in which direction you could re-arrange. Maybe it turns out that class Best can contain the alfabeta value, thus the need for the new class vanishes, and you can return Best instead.

Answer 2

OK, here is a first cleanup...

public Best chooseMove(final boolean side, final int[] board, 
    int alpha, int beta, final int depth, final int maxDepth)
{
    final Best myBest = new Best();
    Best reply;
    final int num;

    if (Board.checkGameOver(board) || depth == maxDepth) {
        final Best fakeBest = new Best();
        fakeBest.setScore(returnPositionScore(board));
        return fakeBest;
    }

    if (side) {
        myBest.setScore(alpha);
        num = numberOfEngine;
    } else {
        myBest.setScore(beta);
        num = numberOfOpponent;
    }

    for (final int move: searchAvailableMoves(board)) {
        board[move] = num;
        reply = chooseMove(!side, board, alpha, beta, depth + 1, maxDepth);
        board[move] = 0;
        if (side && reply.getScore() > myBest.getScore()) {
            myBest.setMove(move);
            myBest.setScore(reply.getScore());
            alpha = reply.getScore();

        } else if (!side && reply.getScore() < myBest.getScore()) {
            myBest.setMove(move);
            myBest.setScore(reply.getScore());
            beta = reply.getScore();

        }
        if (alpha >= beta) {
            return myBest;
        }
    }

    return myBest;
}

Main differences:

• method parameters/variables which can are now final;
• remove unnecessary unboxing and array creation near searchAvailableMoves(board).

In order to do better than that, more code is needed ;)