Comparing game tree search AI algorithms in Java

Question

(The entire project lives here.)

I have a program that benchmarks three game tree search algorithms:

1. Minimax,
2. Alpha-beta pruning,
3. Alpha-beta pruning with move ordering.

So here is my code:

net.coderodde.zerosum.ai.impl.MinimaxGameEngine

package net.coderodde.zerosum.ai.impl;

import net.coderodde.zerosum.ai.EvaluatorFunction;
import net.coderodde.zerosum.ai.AbstractGameEngine;
import net.coderodde.zerosum.ai.AbstractState;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Minimax">Minimax</a> algorithm for 
 * zero-sum two-player games.
 * 
 * @param <S> the game state type.
 * @param <P> the player color type.
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 */
public final class MinimaxGameEngine<S extends AbstractState<S, P>,
                                     P extends Enum<P>> 
        extends AbstractGameEngine<S, P> {

    /**
     * Constructs this minimax game engine.
     * @param evaluatorFunction the evaluator function.
     * @param depth the search depth.
     */
    public MinimaxGameEngine(EvaluatorFunction<S> evaluatorFunction,
                             int depth) {
        super(evaluatorFunction, depth, Integer.MAX_VALUE);
    }

    /**
     * {@inheritDoc }
     */
    @Override
    public S makePly(S state, 
                     P minimizingPlayer,
                     P maximizingPlayer,
                     P initialPlayer) {
        state.setDepth(depth);

        // Do the game tree search:
        return makePlyImplTopmost(state,
                                  minimizingPlayer,
                                  maximizingPlayer,
                                  initialPlayer);
    }

    private S makePlyImplTopmost(S state, 
                                 P minimizingPlayer,
                                 P maximizingPlayer,
                                 P currentPlayer) {
        S bestState = null;

        if (currentPlayer == maximizingPlayer) {
            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S childState : state.children()) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                    bestState = childState;
                }
            }
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S childState : state.children()) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                    bestState = childState;
                }
            }
        }

        return bestState;
    }

    /**
     * Performs a single step down the game tree branch.
     * 
     * @param state            the starting state.
     * @param depth            the maximum depth of the game tree.
     * @param minimizingPlayer the minimizing player.
     * @param maximizingPlayer the maximizing player.
     * @param currentPlayer    the current player.
     * 
     * @return the value of the best ply.
     */
    private double makePlyImpl(S state,
                               int depth,
                               P minimizingPlayer,
                               P maximizingPlayer,
                               P currentPlayer) {
        if (state.getDepth() == 0 
                || state.checkVictory() != null
                || state.isTerminal()) {
            return evaluatorFunction.evaluate(state);
        }

        if (currentPlayer == maximizingPlayer) {
            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S child : state.children()) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                }
            }

            return tentativeValue;
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S child : state.children()) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                } 
            }

            return tentativeValue;
        }
    }
}

net.coderodde.zerosum.ai.impl.AlphaBetaPruningGameEngine

package net.coderodde.zerosum.ai.impl;

import net.coderodde.zerosum.ai.EvaluatorFunction;
import net.coderodde.zerosum.ai.AbstractGameEngine;
import net.coderodde.zerosum.ai.AbstractState;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">
 * Alpha-beta pruning</a> algorithm for zero-sum two-player games.
 * 
 * @param <S> the game state type.
 * @param <P> the player color type.
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 * @version 1.61 (Sep 12, 2019)
 * @since 1.6 (May 26, 2019)
 */
public final class AlphaBetaPruningGameEngine<S extends AbstractState<S, P>, 
                                              P extends Enum<P>> 
extends AbstractGameEngine<S, P> {

    /**
     * Constructs this minimax game engine.
     * @param evaluatorFunction the evaluator function.
     * @param depth the search depth.
     */
    public AlphaBetaPruningGameEngine(EvaluatorFunction<S> evaluatorFunction,
                                      int depth) {
        super(evaluatorFunction, depth, Integer.MAX_VALUE);
    }

    /**
     * {@inheritDoc}
     */
    public S makePly(S state,
                     P minimizingPlayer,
                     P maximizingPlayer,
                     P initialPlayer) {
        state.setDepth(depth);

        // Do the game tree search with Alpha-beta pruning:
        return makePlyImplTopmost(state,
                                  depth,
                                  -Double.NEGATIVE_INFINITY,
                                   Double.POSITIVE_INFINITY,
                                  minimizingPlayer,
                                  maximizingPlayer,
                                  initialPlayer);
    }

    /**
     * Pefrorms the topmost search of a game tree.
     * 
     * @param state            the state to start the search from.
     * @param depth            the depth of the tree to search.
     * @param alpha            the alpha cut-off value.
     * @param beta             the beta cut-off value.
     * @param minimizingPlayer the minimizing player color.
     * @param maximizingPlayer the maximizing player color.
     * @param currentPlayer    the current player color.
     * @return 
     */
    private S makePlyImplTopmost(S state,
                                 int depth,
                                 double alpha,
                                 double beta,
                                 P minimizingPlayer,
                                 P maximizingPlayer,
                                 P currentPlayer) {
        S bestState = null;

        if (currentPlayer == maximizingPlayer) {
            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S childState : state.children()) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                    bestState = childState;
                }

                alpha = Math.max(alpha, tentativeValue);

                if (alpha >= beta) {
                    return bestState;
                }
            }
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S childState : state.children()) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                    bestState = childState;
                }

                beta = Math.min(beta, tentativeValue);

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

        return bestState;
    }

    /**
     * Performs a single step down the game tree.
     * 
     * @param state            the starting state.
     * @param depth            the maximum depth of the game tree.
     * @param alpha            the alpha cut-off.
     * @param beta             the beta cut-off.
     * @param minimizingPlayer the minimizing player.
     * @param maximizingPlayer the maximizing player.
     * @param currentPlayer    the current player.
     * 
     * @return the value of the best ply.
     */
    private double makePlyImpl(S state,
                               int depth,
                               double alpha,
                               double beta,
                               P minimizingPlayer,
                               P maximizingPlayer,
                               P currentPlayer) {
        if (state.getDepth() == 0 
                || state.checkVictory() != null
                || state.isTerminal()) {
            return evaluatorFunction.evaluate(state);
        }

        if (currentPlayer == maximizingPlayer) {
            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S child : state.children()) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           alpha, 
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                }

                alpha = Math.max(alpha, tentativeValue);

                if (alpha >= beta) {
                    break;
                }
            }

            return tentativeValue;
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S child : state.children()) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                }

                beta = Math.min(beta, tentativeValue);

                if (alpha >= beta) {
                    break;
                }
            }

            return tentativeValue;
        }
    }
}

net.coderodde.zerosum.ai.impl.SortingAlphaBetaPruningGameEngine

package net.coderodde.zerosum.ai.impl;

import java.util.List;
import net.coderodde.zerosum.ai.EvaluatorFunction;
import net.coderodde.zerosum.ai.AbstractGameEngine;
import net.coderodde.zerosum.ai.AbstractState;
import net.coderodde.zerosum.ai.demo.DemoPlayerColor;

/**
 * This class implements the 
 * <a href="https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning">
 * Alpha-beta pruning</a> algorithm for zero-sum two-player games.
 * 
 * @param <S> the game state type.
 * @param <P> the player color type.
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 * @version 1.61 (Sep 12, 2019)
 * @since 1.6 (May 26, 2019)
 */
public final class SortingAlphaBetaPruningGameEngine
        <S extends AbstractState<S, P>, 
         P extends Enum<P>>
           extends AbstractGameEngine<S, P> {

    /**
     * Constructs this minimax game engine.
     * @param evaluatorFunction the evaluator function.
     * @param depth the search depth.
     */
    public SortingAlphaBetaPruningGameEngine(EvaluatorFunction<S> evaluatorFunction,
                                      int depth) {
        super(evaluatorFunction, depth, Integer.MAX_VALUE);
    }

    /**
     * {@inheritDoc}
     */
    public S makePly(S state,
                     P minimizingPlayer,
                     P maximizingPlayer,
                     P initialPlayer) {
        state.setDepth(depth);

        // Do the game tree search with Alpha-beta pruning:
        return makePlyImplTopmost(state,
                                  depth,
                                  -Double.NEGATIVE_INFINITY,
                                   Double.POSITIVE_INFINITY,
                                  minimizingPlayer,
                                  maximizingPlayer,
                                  initialPlayer);
    }

    /**
     * Pefrorms the topmost search of a game tree.
     * 
     * @param state            the state to start the search from.
     * @param depth            the depth of the tree to search.
     * @param alpha            the alpha cut-off value.
     * @param beta             the beta cut-off value.
     * @param minimizingPlayer the minimizing player color.
     * @param maximizingPlayer the maximizing player color.
     * @param currentPlayer    the current player color.
     * @return 
     */
    private S makePlyImplTopmost(S state,
                                 int depth,
                                 double alpha,
                                 double beta,
                                 P minimizingPlayer,
                                 P maximizingPlayer,
                                 P currentPlayer) {
        S bestState = null;
        List<S> children = state.children();

        if (currentPlayer == maximizingPlayer) {
            children.sort((a, b) -> {
                double valueOfA = super.evaluatorFunction.evaluate(a);
                double valueOfB = super.evaluatorFunction.evaluate(b);
                return Double.compare(valueOfA, valueOfB);
            });

            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S childState : children) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                    bestState = childState;
                }

                alpha = Math.max(alpha, tentativeValue);

                if (alpha >= beta) {
                    return bestState;
                }
            }
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            children.sort((a, b) -> {
                double valueOfA = super.evaluatorFunction.evaluate(a);
                double valueOfB = super.evaluatorFunction.evaluate(b);
                return Double.compare(valueOfB, valueOfA);
            });

            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S childState : children) {
                double value = makePlyImpl(childState,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                    bestState = childState;
                }

                beta = Math.min(beta, tentativeValue);

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

        return bestState;
    }

    /**
     * Performs a single step down the game tree.
     * 
     * @param state            the starting state.
     * @param depth            the maximum depth of the game tree.
     * @param alpha            the alpha cut-off.
     * @param beta             the beta cut-off.
     * @param minimizingPlayer the minimizing player.
     * @param maximizingPlayer the maximizing player.
     * @param currentPlayer    the current player.
     * 
     * @return the value of the best ply.
     */
    private double makePlyImpl(S state,
                               int depth,
                               double alpha,
                               double beta,
                               P minimizingPlayer,
                               P maximizingPlayer,
                               P currentPlayer) {
        if (state.getDepth() == 0 
                || state.checkVictory() != null
                || state.isTerminal()) {
            return evaluatorFunction.evaluate(state);
        }

        List<S> children = state.children();

        if (currentPlayer == maximizingPlayer) {
            children.sort((a, b) -> {
                double valueOfA = super.evaluatorFunction.evaluate(a);
                double valueOfB = super.evaluatorFunction.evaluate(b);
                return Double.compare(valueOfA, valueOfB);
            });

            double tentativeValue = Double.NEGATIVE_INFINITY;

            for (S child : children) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           alpha, 
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue < value) {
                    tentativeValue = value;
                }

                alpha = Math.max(alpha, tentativeValue);

                if (alpha >= beta) {
                    break;
                }
            }

            return tentativeValue;
        } else {
            // Here, 'initialPlayer == minimizingPlayer'.
            children.sort((a, b) -> {
                double valueOfA = super.evaluatorFunction.evaluate(a);
                double valueOfB = super.evaluatorFunction.evaluate(b);
                return Double.compare(valueOfB, valueOfA);
            });

            double tentativeValue = Double.POSITIVE_INFINITY;

            for (S child : children) {
                double value = makePlyImpl(child,
                                           depth - 1,
                                           alpha,
                                           beta,
                                           minimizingPlayer,
                                           maximizingPlayer,
                                           minimizingPlayer);

                if (tentativeValue > value) {
                    tentativeValue = value;
                }

                beta = Math.min(beta, tentativeValue);

                if (alpha >= beta) {
                    break;
                }
            }

            return tentativeValue;
        }
    }
}

net.coderodde.zerosum.ai.impl.AbstractGameEngine

package net.coderodde.zerosum.ai;

/**
 * This abstract class defines the API for game-playing AI algorithms such as 
 * Minimax, Alpha-beta pruning, and so on.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 * @param <S> the board state type.
 * @param <P> the player color type.
 */
public abstract class AbstractGameEngine<
    S extends AbstractState<S, P>,
    P extends Enum<P>
> {

    /**
     * The minimum depth of the game tree to traverse.
     */
    private static final int MINIMUM_DEPTH = 1;

    /**
     * The depth, after reaching which, the search spawns isolated tasks for a 
     * thread pool to process.
     */
    private static final int MINIMUM_PARALLEL_DEPTH = 1;

    /**
     * The state evaluator function.
     */
    protected EvaluatorFunction<S> evaluatorFunction;

    /**
     * The maximum depth of the game tree to construct.
     */
    protected int depth;

    /**
     * The depth after which to switch to parallel computation.
     */
    protected int parallelDepth;

    /**
     * Constructs this game engine with given parameters. Note that if 
     * {@code parallelDepth > depth}, the entire computation will be run in this
     * thread without spawning 
     * @param evaluatorFunction
     * @param depth
     * @param parallelDepth 
     */
    public AbstractGameEngine(EvaluatorFunction<S> evaluatorFunction,
                      int depth,
                      int parallelDepth) {
        setEvaluatorFunction(evaluatorFunction);
        setDepth(depth);
        setParallelDepth(parallelDepth);
    }

    public EvaluatorFunction<S> getEvaluatorFunction() {
        return evaluatorFunction;
    }

    public int getDepth() {
        return depth;
    }

    public int getParallelDepth() {
        return parallelDepth;
    }

    public void setEvaluatorFunction(EvaluatorFunction<S> evaluatorFunction) {
        this.evaluatorFunction = evaluatorFunction;
    }

    public void setDepth(int depth) {
        this.depth = checkDepth(depth);
    }

    public void setParallelDepth(int parallelDepth) {
        this.parallelDepth = checkParallelDepth(parallelDepth);
    }

    /**
     * Computes and makes a single move. 
     * @param state the source game state.
     * @param minimizingPlayer the player that seeks to minimize the score.
     * @param maximizingPlayer the player that seeks to maximize the score.
     * @param initialPlayer the initial player. Must be either 
     * {@code minimizingPlayer} or {@code maximizingPlayer}. The ply is computed
     * for this specific player.
     * @return the next game state.
     */
    public abstract S makePly(S state, 
                              P minimizingPlayer,
                              P maximizingPlayer,
                              P initialPlayer);

    /**
     * Validates the depth candidate.
     * @param depthCandidate the depth candidate to validate.
     * @return the depth candidate if valid.
     */
    private int checkDepth(int depthCandidate) {
        if (depthCandidate < MINIMUM_DEPTH) {
            throw new IllegalArgumentException(
                    "The requested depth (" + depthCandidate + ") is too " + 
                    "small. Must be at least " + MINIMUM_DEPTH + ".");
        }

        return depthCandidate;
    }

    /**
     * Validates the parallel depth candidate.
     * @param parallelDepthCandidate the parallel depth candidate to validate.
     * @return the parallel depth candidate.
     */
    private int checkParallelDepth(int parallelDepthCandidate) {
        if (parallelDepthCandidate < MINIMUM_PARALLEL_DEPTH) {
            throw new IllegalArgumentException(
                    "The requested parallel depth (" + parallelDepthCandidate +
                    ") is too small. Must be at least " +
                    MINIMUM_PARALLEL_DEPTH + ".");
        }

        return parallelDepthCandidate;
    }
}

net.coderodde.zerosum.ai.impl.AbstractState

package net.coderodde.zerosum.ai;

import java.util.List;

/**
 * This interface defines the API for search states.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 * @param <S> the actual state type.
 */
public abstract class AbstractState<S extends AbstractState<S, P>,
                                    P extends Enum<P>> {

    /**
     * The depth of this state.
     */
    private int depth;

    /**
     * Returns the next ply.
     * 
     * @return the collection of next states.
     */
    public abstract List<S> children();

    /**
     * Returns {@code true} if this state is a terminal state.
     * 
     * @return a boolean indicating whether this state is terminal.
     */
    public abstract boolean isTerminal();

    /**
     * Checks whether this state represents a victory of a player.
     * 
     * @return the winning player or {@code null} if there is no such.
     */
    public abstract P checkVictory();

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }
}

net.coderodde.zerosum.ai.impl.EvaluatorFunction

package net.coderodde.zerosum.ai;

/**
 * This interface defines the API for evaluation functions.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 26, 2019)
 * @param <S> the state type.
 */
public interface EvaluatorFunction<S> {

    /**
     * Evaluates the given state and returns the result.
     * @param state the state to evaluate.
     * @return the evaluation score.
     */
    public double evaluate(S state);
}

Critique request

I would like to hear comments about general code design, efficiency and readability/maintainability of my code. Yet, please tell me anything that comes to mind.

Answer 1

depth

From the snippets posted here I have a feeling that you didn't really know where to place the depth information. You're passing it as a parameter to the makePlyImpl method but then never use it. Instead you're checking state.getDepth() but that's only set before calling the method, and I don't see it updating the depth on all it's children.

As I understand it your code isn't really limiting search on depth then. Except if the initial depth is too low, in which case setDepth(...) throws an error that's never handled properly, and neither is it mentioned in the comments that this error could be thrown.

I personally would get rid of the depth as part of the State and keep it completely internally to the algorithms. Especially if some other algorithm might want to ignore depth altogether. Just use the one you already added in the internal method calls.

Same thing for the parallelDepth parameter. You're not even using it yet so why did you already provide it?

comment @params

Adding an @params in the comment block just to repeat what the name already says is meaningless. Unless you're required to do this by some outdated company policy I would leave those out of the comment block and instead use meaningful parameter names. Comments shouldn't say what things are, but why they're written like that.

For example:

/**
* Constructs this minimax game engine.

It's a constructor what else is it going to do?

* @param evaluatorFunction the evaluator function.

Ofcourse the evaluatorFunction is the evaluator function, that's why it's named evaluatorFunction in the first place

* @param depth the search depth.
*/

The only thing this comment adds is that depth is limiting the search depth. Instead of this comment I would have named the variable something like maxSearchDepth which would make this obvious without any comment.

why the special ...impTopmost methods?

The only difference between the two impl methods is that the topmost also stores a pointer to a state. Is it really such a problem to store both a double and a pointer for each call instead of only for the topmost?

Took me too long to realise the different return types required. It can be simplified if we consider my next point though.

P needed?

I was slightly confused when I saw the required parameters to make a play. All algorithms will go "max current player > min other player > max current player > ...". Since it will always start from max-ing do we really need to know the players here? I propose simplifying the initial method to

public S makePly(S state) {
    return calculateBestChildState(state);
}

Since the initial best state is always the max we can cut your ...topmost method in half and inline the remaining part here. With this change I also propose to split up the ...impl methods into a separate min and max method.

public S makePly(S state) {
    S bestState = null;
    double tentativeValue = Double.NEGATIVE_INFINITY;

    for (S childState : state.children()) {
        double value = playMin(childState,
                                   depth - 1);

        if (tentativeValue < value) {
            tentativeValue = value;
            bestState = childState;
        }
    }
    return bestState;
}

private double playMin(S state, int depth) {
     if (depth == 0 
            || state.checkVictory() != null
            || state.isTerminal()) {
        return evaluatorFunction.evaluate(state);
    }

    double tentativeValue = Double.POSITIVE_INFINITY;

    for (S child : state.children()) {
        double value = playMax(child,
                               depth - 1);

        if (tentativeValue < value) {
            tentativeValue = value;
        }
    }

    return tentativeValue;
}

private double playMax(S state, int depth) {
    ... //same as playMin but use > instead of <
}

state.checkVictory() != null

Copy pasting the implementation for playMin had me stunned on that line. When would checking a victory ever return null? Why not a boolean? Until I saw the the next line is checking for termination. Then what exactly is the point of this method? If we removed this check here, would the result ever change?

A more logical way for me would be that the termination check is sufficient in this step to see if the game is finished. After game end in some other place we can instead use the current player in that state as the winner... if only the state contained which player's turn it is in that state (hint hint)