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


Fields should be private. (Item 13 of Effective Java 2nd Edition: Minimize the accessibility of classes and members)
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
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
What is ply? I guess maxDepth would be a more descriptive name.
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). 


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.
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.
I've created a new method for the Move class:

public String getName() { ... }


It will helper when we'll verificate the test results.
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 &lt; score) {
            alpha = score;
            bestMove = currentMove;
        }
        if (beta &lt;= 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.