Tag: tree

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 
 * 
 * Alpha-beta pruning algorithm for zero-sum two-player games.
 * 
 * @param  the game state type.
 * @param 
 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
        , 
         P extends Enum
>
           extends AbstractGameEngine {

    /**
     * Constructs this minimax game engine.
     * @param evaluatorFunction the evaluator function.
     * @param depth the search depth.
     */
    public SortingAlphaBetaPruningGameEngine(EvaluatorFunction 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 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 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;
        }
    }
}

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  the board state type.
 * @param 
 the player color type.
 */
public abstract class AbstractGameEngine<
    S extends AbstractState,
    P extends Enum

> {

    /**
     * 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 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 evaluatorFunction,
                      int depth,
                      int parallelDepth) {
        setEvaluatorFunction(evaluatorFunction);
        setDepth(depth);
        setParallelDepth(parallelDepth);
    }

    public EvaluatorFunction getEvaluatorFunction() {
        return evaluatorFunction;
    }

    public int getDepth() {
        return depth;
    }

    public int getParallelDepth() {
        return parallelDepth;
    }

    public void setEvaluatorFunction(EvaluatorFunction 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;
    }
}

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  the actual state type.
 */
public abstract class AbstractState,
                                    P extends Enum
> {

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

    /**
     * Returns the next ply.
     * 
     * @return the collection of next states.
     */
    public abstract List 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;
    }
}

package net.coderodde.zerosum.ai;

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

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