I'm trying to implement a MiniMax algorithm with alpha/beta pruning. Totally stuck and can't see where I'm wrong. The class MiniMax contains a State and an Action. The method getAction returns an Action (supposedly the best action to take). The Game object has two methods, isTerminal returns true if the state is an "end state", ie there are no more children to that state. getUtility returns the value associated with an end state.
I'm trying to decide wheter it is Max or Min turn by using the counter round. Currently the algorithm doesn't return the correct action, and at this stage I am just focussing on getting the expansion order right, getting the pruning bit to work.
My current code seems to evaulte the following tree correctly, using the expansin order A, C, G, F, B:
But when the tree looks as below, it expands Z, A, B, E, H, I, L (correct expansion is Z, A, B, E, H, I since H does not need further expansion as I understand it).
public class MiniMax<State,Action> {
int alpha = Integer.MIN_VALUE;
int beta = Integer.MAX_VALUE;
int foundMax = 0;
int round = -1;
Action action = null;
public Action getAction(Game<State, Action> game, State state)
{
round++;
List<Successor<State, Action>> successors = (List<Successor<State, Action>>) game.getSuccessors(state);
for (int i=0; i < successors.size(); i++)
{
if ( round % 2 == 0 )
{
if ( game.isTerminal(successors.get(i).state))
{
System.out.println("Max turn: Node: " + successors.get(i).state + ", utility: " + game.getUtility(successors.get(i).state) + ", alpha: " + alpha + ", beta: " + beta);
alpha = Integer.max(alpha, game.getUtility(successors.get(i).state));
if ( alpha <= beta )
{
break;
}
action = successors.get(i).action;
}
if ( !game.isTerminal( successors.get(i).state) )
{
action = getAction(game, successors.get(i).state);
}
}
else
{
if ( game.isTerminal(successors.get(i).state))
{
System.out.println("Min turn: Node: " + successors.get(i).state + ", utility: " + game.getUtility(successors.get(i).state) + ", alpha: " + alpha + ", beta: " + beta);
beta = Integer.min(beta, game.getUtility(successors.get(i).state));
if ( beta <= alpha )
{
break;
}
action = successors.get(i).action;
}
if ( !game.isTerminal( successors.get(i).state) )
{
action = getAction(game, successors.get(i).state);
}
}
}
return action;
}