(The entire project lives here.)
Comparing game tree search AI algorithms in Java
I have a program that benchmarks three game tree search algorithms:
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.
lang-java