5
\$\begingroup\$

Is this code correct?

This code was adapted from this alphabeta pseudocode. AlphaBeta search is often mentioned but getting the code 100% correct is tricky.

IGame is an interface with two methods:
getScore() - evaluates the current game state from the viewpoint of the AI
generateMoves() - creates possible moves from the current game state.

class Search
{
    Move bestMove;

    Move findBestMove(int ply, IGame g)
    {
        bestMove = null;
        alpha_beta(ply, g, Integer.MINIMUM, Integer.MAXIMUM);
        return bestMove;
    }

    int alpha_beta(int depth, IGame g, int alpha, int beta)
    {
        if (depth == 0 || g.isGameFinished()) return g.getScore();

        Move[] gameMove = g.generateMoves();

        for (int i = 0; i < gameMove.length; i++)
        {
            g.execute(gameMove[i]);
            int score = -alpha_beta(depth - 1, -beta, -alpha);
            g.undo(gameMove[i]);

            if (alpha < score)
            {
                alpha = score;
                bestMove = gameMove[i];
            }
            if (beta <= alpha) return alpha;
        }
        return alpha;
    } 
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Even if the algorithm is know as "alphabeta", "minimax", etc, you should find better variable names that "alpha" and "beta". \$\endgroup\$ – Sulthan Mar 14 '13 at 15:56
  • 2
    \$\begingroup\$ By the way, what is the question? \$\endgroup\$ – Sulthan Mar 14 '13 at 15:57
  • \$\begingroup\$ @Sulthan, firstly, the question explicitly states the question: "is this correct." Secondly, this is Code Review. Every question is a code review, and we don't need to explicitly state a question. \$\endgroup\$ – Winston Ewert Mar 16 '13 at 5:40
  • \$\begingroup\$ @WinstonEwert firstly, the "is this correct" question was added some time after my comment. Secondly, per Code Review FAQ, only working code should be here. It seems to me that the OP doesn't even know if the code is working. \$\endgroup\$ – Sulthan Mar 16 '13 at 10:41
  • 2
    \$\begingroup\$ @Sulthan, actually the faq says: "To the best of my knowledge, does the code work?" As long as the poster is unaware of the flaws, asking for help in spotting them is on-topic. \$\endgroup\$ – Winston Ewert Mar 16 '13 at 19:56
5
\$\begingroup\$

My last AI course was too long time ago so just some generic notes and some modifications for easier testing.

  1. Fields should be private. (Item 13 of Effective Java 2nd Edition: Minimize the accessibility of classes and members)

  2. IGame could be Game.

    I don’t want my users knowing that I’m handing them an interface. I just want them to know that it’s a ShapeFactory.

    Source: Clean Code by Robert C. Martin, Interfaces and Implementations, p24

  3. Class names should be nouns, instead of verbs, like Search:

    Class and Interface Type Names

    Names of class types should be descriptive nouns or noun phrases, not overly long, in mixed case with the first letter of each word capitalized.

    Source: The Java Language Specification, Java SE 7 Edition, 6.1 Declarations

  4. What is ply? I guess maxDepth would be a more descriptive name.

  5. Short variable names (like g) are not too readable. I suppose you have autocomplete, so using longer names does not mean more typing but it would help readers and maintainers a lot since they don't have to remember the purpose of each variable - the name would express the programmers intent. (Clean Code by Robert C. Martin, Avoid Mental Mapping, p25)

Make it testable

Good design is testable, and design that isn't testable is bad.

(Source Michael C. Feathers: Working Effectively with Legacy Code)

I made some changes in the API (Game and Move classes to make it easier to test).

  1. I've added a Move parameter to the generateMoves() method to make it stateless. It results easier mocking since the output only depends only on the input parameter.

  2. I'm using move.isLeaf() instead of g.isGameFinished() (for the same reason). It could be game.isFinishingMove(Move move) too but the former was simpler.

  3. I've created a new method for the Move class:

    public String getName() { ... }
    

    It will helper when we'll verificate the test results.

  4. I've also changed the loop to a foreach. It also eliminated the duplicated gameMove[i] access.

So, the AlphaBetaSearcher class is the following now:

private Move bestMove;

public Move findBestMove(int maxDepth, Game game, Move root) {
    bestMove = null;
    alpha_beta(maxDepth, game, root, 
        Integer.MIN_VALUE, Integer.MAX_VALUE);
    return bestMove;
}

private int alpha_beta(final int depth, final Game game, 
        final Move move, int alpha, final int beta) {
    if (depth == 0 || move.isLeaf()) {
        return game.getScore();
    }

    final Move[] moves = game.generateMoves(move);
    for (final Move currentMove: moves) {
        game.execute(currentMove);
        final int score = 
            -alpha_beta(depth - 1, game, currentMove, -beta, -alpha);
        game.undo(currentMove);

        if (alpha < score) {
            alpha = score;
            bestMove = currentMove;
        }
        if (beta <= alpha) {
            return alpha;
        }
    }
    return alpha;
}

Test data

For the test below I've used the leftmost part of the sample tree from Wikipedia.

Test framework

I'm using Mockito and JUnit here. A mocking framework makes possible to test the Alpha-beta implementation without the actual Game and Move classes. In isolation you can make sure that the pruning works well before you integrate it into the game. If it isn't completely bug-free it's easier to debug and modify in isolation.

JUnit tests are self-checking, you don't have to check the output and decide if it's OK or not. The assert* assertion methods throws an exception when the tested class does not return the excepted value.

Test code

import static org.junit.Assert.assertEquals;
import static org.mockito.Mockito.mock;
import static org.mockito.Mockito.when;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.mockito.Mock;
import org.mockito.runners.MockitoJUnitRunner;

@RunWith(MockitoJUnitRunner.class)
public class AlphaBetaSearcherOrigTest {

    private final AlphaBetaSearcherOrig searcher = 
        new AlphaBetaSearcherOrig();

    // Mockito creates a dummy, programmable Game instance for us
    @Mock
    private Game game;

    @Test
    public void testSubTree() {
        // we are creating the move tree with names and scores
        final Move root = createMockedMove("root");
        final Move moveA = createMockedMove("A");
        final Move moveB = createMockedMove("B");
        final Move moveAA = createLeafMove("AA", 5);
        final Move moveAB = createLeafMove("AB", 6);
        final Move moveBA = createLeafMove("BA", 7);
        final Move moveBB = createLeafMove("BB", 4);
        final Move moveBC = createLeafMove("BC", 5);

        // programming the dummy Game instance
        // calling generateMoves() with the root node will 
        // return moveA and moveB
        when(game.generateMoves(root)).
            thenReturn(newMoveArray(moveA, moveB));
        when(game.generateMoves(moveA)).
            thenReturn(newMoveArray(moveAA, moveAB));
        when(game.generateMoves(moveB)).
            thenReturn(newMoveArray(moveBA, moveBB, moveBC));

        final Move bestMove = searcher.findBestMove(5, game, root);
        // checking the name of the best move
        assertEquals("BA", bestMove.getName());
    }

    private Move createMockedMove(String name) {
        // creating a dummy/programmable Move instance 
        // whose getName() method will return name
        final Move mock = mock(Move.class);
        when(mock.getName()).thenReturn(name);
        return mock;
    }

    private Move createLeafMove(String name, int score) {
        final Move move = createMockedMove(name);
        when(move.isLeaf()).thenReturn(true);
        when(move.getScore()).thenReturn(score);
        return move;
    }

    private Move[] newMoveArray(Move... moves) {
        return moves;
    }
}

The algorithm currently return with BA. If I'm right it should be A but I'm really not sure.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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