2
\$\begingroup\$

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;
}
\$\endgroup\$

2 Answers 2

3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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 ;)

\$\endgroup\$
9
  • \$\begingroup\$ thank you for the tips. yeah i know i did some unnecessary unboxing,before that i did it like you did and than i changed my mind.. but i guess that it doesn't make bad performance is it? anyway..in fact i was actually looking to get some very different code than mine because i know that there are shorter and more "Elegant" ways to write this function. so i found a little snippest of code on the net,and now i am trying to work with that instead. it is much less OOP but in this case i don't mind. but can you please look at this code and tell me how can i get the actual move out of it?? \$\endgroup\$ Jun 7, 2013 at 0:13
  • \$\begingroup\$ What is really needed here though is the data structures, and preferrably documented. As the saying goes, "show me your data, I'll show you the code" ;) \$\endgroup\$
    – fge
    Jun 7, 2013 at 0:23
  • \$\begingroup\$ In any event, this kind of construct --> searchAvailableMoves(EngineTask.newBoard) is fishy... There is a design problem somewhere in the library used. \$\endgroup\$
    – fge
    Jun 7, 2013 at 0:36
  • \$\begingroup\$ can you explain to me why it is a bad form? the searchAvailableMoves() gets a int[] (some board position) and generate all the legal moves from that board. than it return an arrayList with all the legal moves. the Engine.newBoard is a public static board (not the actual board which is the board class,but a subtitude..i simply don't want to change the original board) \$\endgroup\$ Jun 7, 2013 at 0:44
  • 1
    \$\begingroup\$ Well, especially in long methods, it helps you spot immediately which variables will never be modified (for instance, I know from the get go that the method reuses alpha and beta internally by just spotting the signature). As instance variables, they are also a precondition to make immutable objects. \$\endgroup\$
    – fge
    Jun 7, 2013 at 0:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.