2
\$\begingroup\$

I have a couple of projects:

  1. GameAI
  2. ConnectFour

GameAI implements a couple of algorithms: Minimax, Alpha-beta pruning and Alpha-beta pruning with state ordering.

The actual game tree search algorithms seems to be in order, yet when I play against the bot connected to such an algorithm, it acts rather dumb. My best guess is that the problem lies in the evalutation function. Here is my code:´

net.coderodde.zerosum.ai.impl.AlphaBetaPruningGameEngine

package net.coderodde.zerosum.ai.impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import net.coderodde.zerosum.ai.EvaluatorFunction;
import net.coderodde.zerosum.ai.GameEngine;
import net.coderodde.zerosum.ai.State;

/**
 * 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 AlphaBetaPruningGameEngine<S extends State<S>, P extends Enum<P>> 
        extends GameEngine<S, P> {

    /**
     * Stores the terminal node or a node at the depth zero with the best value
     * so far, which belongs to the maximizing player moves.
     */
    private S bestTerminalMaximizingState;

    /**
     * Stores the value of {@code bestTerminalMaximizingState}.
     */
    private double bestTerminalMaximizingStateValue;

    /**
     * Stores the terminal node or a node at the depth zero with the best value
     * so far, which belongs to the minimizing player moves.
     */
    private S bestTerminalMinimizingState;

    /**
     * Stores the value of {@code bestTerminalMinimizingState}.
     */
    private double bestTerminalMinimizingStateValue;

    /**
     * Indicates whether we are computing a next ply for the minimizing player 
     * or not. If not, we are computing a next ply for the maximizing player.
     */
    private boolean makingPlyForMinimizingPlayer;

    /**
     * Maps each visited state to its parent state.
     */
    private final Map<S, S> parents = new HashMap<>();

    /**
     * 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 }
     */
    @Override
    public S makePly(S state, 
                     P minimizingPlayer,
                     P maximizingPlayer,
                     P initialPlayer) {
        // Reset the best known values:
        bestTerminalMaximizingStateValue = Double.NEGATIVE_INFINITY;
        bestTerminalMinimizingStateValue = Double.POSITIVE_INFINITY;
        makingPlyForMinimizingPlayer = initialPlayer != minimizingPlayer;

        // Do the game tree search:
        makePlyImpl(state,
                    depth,
                    Double.NEGATIVE_INFINITY, // intial alpha
                    Double.POSITIVE_INFINITY, // intial beta
                    minimizingPlayer,
                    maximizingPlayer,
                    initialPlayer);

        // Find the next game state starting from 'state':
        S returnState =
                inferBestState(
                        initialPlayer == minimizingPlayer ? 
                                bestTerminalMinimizingState : 
                                bestTerminalMaximizingState);

        // Release the resources:
        parents.clear();
        bestTerminalMaximizingState = null;
        bestTerminalMinimizingState = null;
        // We are done with a single move:
        return returnState;
    }

    private S inferBestState(S bestTerminalState) {
        List<S> statePath = new ArrayList<>();
        S state = bestTerminalState;

        while (state != null) {
            statePath.add(state);
            state = parents.get(state);
        }

        if (statePath.size() == 1) {
            // The root node is terminal. Return null:
            return null;
        }

        // Return the second upmost state:
        Collections.<S>reverse(statePath);
        return statePath.get(1);
    }

    /**
     * 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,
                               double alpha,
                               double beta,
                               P minimizingPlayer,
                               P maximizingPlayer,
                               P currentPlayer) {
        if (depth == 0 || state.isTerminal()) {
            double value = evaluatorFunction.evaluate(state);

            if (!makingPlyForMinimizingPlayer) {
                if (bestTerminalMinimizingStateValue > value) {
                    bestTerminalMinimizingStateValue = value;
                    bestTerminalMinimizingState = state;
                }
            } else {
                if (bestTerminalMaximizingStateValue < value) {
                    bestTerminalMaximizingStateValue = value;
                    bestTerminalMaximizingState = state;
                }
            }

            return value;
        }

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

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

                parents.put(child, state);
                alpha = Math.max(alpha, value);

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

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

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

                parents.put(child, state);
                beta = Math.min(beta, value);

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

            return value;
        }
    }
}

net.coderodde.games.connect.four.impl.BruteForceConnectFourStateEvaluatorFunction

package net.coderodde.games.connect.four.impl;

import net.coderodde.games.connect.four.ConnectFourState;
import net.coderodde.games.connect.four.PlayerColor;
import net.coderodde.zerosum.ai.EvaluatorFunction;

/**
 * This class implements the default Connect Four state evaluator. The white 
 * player wants to maximize, the red player wants to minimize.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (May 24, 2019)
 */
public final class BruteForceConnectFourStateEvaluatorFunction
        implements EvaluatorFunction<ConnectFourState> {

    private static final double NEGATIVE_WIN_VALUE = -1e6;
    private static final double POSITIVE_WIN_VALUE = 1e6;
    private static final double BASE_VALUE = 1e1;

    /**
     * The weight matrix. Maps each position to its weight. We need this in 
     * order to 
     */
    private final double[][] weightMatrix;

    /**
     * The winning length.
     */
    private final int winningLength;

    /**
     * Constructs the default heuristic function for Connect Four game states.
     * 
     * @param width the game board width.
     * @param height the game board height.
     * @param maxWeight the maximum weight in the weight matrix.
     * @param winningPatternLength the winning pattern length.
     */
    public BruteForceConnectFourStateEvaluatorFunction(final int width,
                                             final int height,
                                             final double maxWeight,
                                             final int winningPatternLength) {
        this.weightMatrix = getWeightMatrix(width, height, maxWeight);
        this.winningLength = winningPatternLength;
    }

    /**
     * Evaluates the given input {@code state} and returns the estimate.
     * @param state the state to estimate.
     * @return the estimate.
     */
    @Override
    public double evaluate(ConnectFourState state) {
        // 'minimizingPatternCounts[i]' gives the number of patterns of 
        // length 'i':
        int[] minnimizingPatternCounts = new int[state.getWinningLength() + 1];
        int[] maximizingPatternCounts = new int[minnimizingPatternCounts.length];

        // Do not consider patterns of length one!
        for (int targetLength = 2; 
                targetLength <= winningLength; 
                targetLength++) {
            int count = findRedPatternCount(state, targetLength);

            if (count == 0) {
                // Once here, it is not possible to find patterns of larger 
                // length than targetLength:
                break;
            }

            minnimizingPatternCounts[targetLength] = count;
        }

        for (int targetLength = 2;
                targetLength <= state.getWinningLength();
                targetLength++) {
            int count = findWhitePatternCount(state, targetLength);

            if (count == 0) {
                // Once here, it is not possible to find patterns of larger
                // length than targetLength:
                break;
            }

            maximizingPatternCounts[targetLength] = count;
        }

        double score = computeBaseScore(minnimizingPatternCounts, 
                                        maximizingPatternCounts);

        return score + getWeights(weightMatrix, state);
    }

    /**
     * Finds the number of red patterns of length {@code targetLength}.
     * @param state the target state.
     * @param targetLength the length of the pattern to find.
     * @return the number of red patterns of length {@code targetLength}.
     */
    private static final int findRedPatternCount(ConnectFourState state,
                                                 int targetLength) {
        return findPatternCount(state, 
                                targetLength, 
                                PlayerColor.MINIMIZING_PLAYER);
    }

    /**
     * Finds the number of white patterns of length {@code targetLength}. 
     * @param state the target state.
     * @param targetLength the length of the pattern to find.
     * @return the number of white patterns of length {@code targetLength}.
     */
    private static final int findWhitePatternCount(ConnectFourState state,
                                                   int targetLength) {
        return findPatternCount(state,
                                targetLength, 
                                PlayerColor.MAXIMIZING_PLAYER);
    }

    /**
     * Implements the target pattern counting function for both the player 
     * colors.
     * @param state the state to search.
     * @param targetLength the length of the patterns to count.
     * @param playerColor the target player color.
     * @return the number of patterns of length {@code targetLength} and color
     * {@code playerColor}.
     */
    private static final int findPatternCount(ConnectFourState state,
                                              int targetLength,
                                              PlayerColor playerColor) {
        int count = 0;

        count += findHorizontalPatternCount(state, 
                                            targetLength, 
                                            playerColor);

        count += findVerticalPatternCount(state, 
                                          targetLength, 
                                          playerColor);

        count += findAscendingDiagonalPatternCount(state, 
                                                   targetLength,
                                                   playerColor);

        count += findDescendingDiagonalPatternCount(state, 
                                                    targetLength,
                                                    playerColor);
        return count;
    }

    /**
     * Scans the input state for diagonal <b>descending</b> patterns and 
     * returns the number of such patterns.
     * @param state the target state.
     * @param patternLength the target pattern length.
     * @param playerColor the target player color.
     * @return the number of patterns.
     */
    private static final int 
        findDescendingDiagonalPatternCount(ConnectFourState state,
                                           int patternLength,
                                           PlayerColor playerColor) {
        int patternCount = 0;

        for (int y = 0; y < state.getWinningLength() - 1; y++) {
            inner:
            for (int x = 0;
                    x <= state.getWidth() - state.getWinningLength(); 
                    x++) {
                for (int i = 0; i < patternLength; i++) {
                    if (state.readCell(x + i, y + i) != playerColor) {
                        continue inner;
                    }
                }

                patternCount++;
            }
        }

        return patternCount;
    }

    /**
     * Scans the input state for diagonal <b>ascending</b> patterns and returns
     * the number of such patterns.
     * @param state the target state.
     * @param patternLength the target pattern length.
     * @param playerColor the target player color.
     * @return the number of patterns.
     */
    private static final int 
        findAscendingDiagonalPatternCount(ConnectFourState state,
                                          int patternLength,
                                          PlayerColor playerColor) {
        int patternCount = 0;

        for (int y = state.getHeight() - 1;
                y > state.getHeight() - state.getWinningLength();
                y--) {

            inner:
            for (int x = 0; 
                    x <= state.getWidth() - state.getWinningLength();
                    x++) {
                for (int i = 0; i < patternLength; i++) {
                    if (state.readCell(x + i, y - i) != playerColor) {
                        continue inner;
                    }
                }

                patternCount++;
            }
        }

        return patternCount;
    } 

    /**
     * Scans the input state for diagonal <b>horizontal</b> patterns and returns
     * the number of such patterns.
     * @param state the target state.
     * @param patternLength the target pattern length.
     * @param playerColor the target player color.
     * @return the number of patterns.
     */
    private static final int findHorizontalPatternCount(
            ConnectFourState state,
            int patternLength,
            PlayerColor playerColor) {
        int patternCount = 0;

        for (int y = state.getHeight() - 1; y >= 0; y--) {

            inner:
            for (int x = 0; x <= state.getWidth() - patternLength; x++) {
                if (state.readCell(x, y) == null) {
                    continue inner;
                }

                for (int i = 0; i < patternLength; i++) {
                    if (state.readCell(x + i, y) != playerColor) {
                        continue inner;
                    }
                }

                patternCount++;
            }
        }

        return patternCount;
    }

    /**
     * Scans the input state for diagonal <b>vertical</b> patterns and returns
     * the number of such patterns.
     * @param state the target state.
     * @param patternLength the target pattern length.
     * @param playerColor the target player color.
     * @return the number of patterns.
     */
    private static final int findVerticalPatternCount(ConnectFourState state,
                                                      int patternLength,
                                                      PlayerColor playerColor) {
        int patternCount = 0;

        outer:
        for (int x = 0; x < state.getWidth(); x++) {
            inner:
            for (int y = state.getHeight() - 1;
                    y > state.getHeight() - state.getWinningLength(); 
                    y--) {
                if (state.readCell(x, y) == null) {
                    continue outer;
                }

                for (int i = 0; i < patternLength; i++) {
                    if (state.readCell(x, y - i) != playerColor) {
                        continue inner;
                    }
                }

                patternCount++;
            }
        }

        return patternCount;
    }

    /**
     * Gets the state weight. We use this in order to discourage the positions
     * that are close to borders/far away from the center of the game board.
     * @param weightMatrix the weighting matrix.
     * @param state the state to weight.
     * @return the state weight.
     */
    private static final double getWeights(final double[][] weightMatrix,
                                           final ConnectFourState state) {
        double score = 0.0;

        outer:
        for (int x = 0; x < state.getWidth(); x++) {
            for (int y = state.getHeight() - 1; y >= 0; y--) {
                PlayerColor playerColor = state.readCell(x, y);

                if (playerColor == null) {
                    continue outer;
                }

                if (playerColor == PlayerColor.MINIMIZING_PLAYER) {
                    score -= weightMatrix[y][x];
                } else {
                    score += weightMatrix[y][x];
                }
            }
        }

        return score;
    }

    /**
     * Computes the base scorer that relies on number of patterns. For example,
     * {@code redPatternCounts[i]} will denote the number of patterns of length 
     * [@code i}.
     * @param minimizingPatternCounts the pattern count map for red patterns.
     * @param maximizingPatternCounts the pattern count map for white patterns.
     * @return the base estimate.
     */
    private static final double computeBaseScore(
            int[] minimizingPatternCounts,
            int[] maximizingPatternCounts) {
        final int winningLength = minimizingPatternCounts.length - 1;

        double value = 0.0;

        if (minimizingPatternCounts[winningLength] != 0) {
            value = NEGATIVE_WIN_VALUE;
        }

        if (maximizingPatternCounts[winningLength] != 0) {
            value = POSITIVE_WIN_VALUE;
        }

        for (int length = 2; length < minimizingPatternCounts.length; length++) {
            int minimizingCount = minimizingPatternCounts[length];
            value -= minimizingCount * Math.pow(BASE_VALUE, length);

            int maximizingCount = maximizingPatternCounts[length];
            value += maximizingCount * Math.pow(BASE_VALUE, length);
        }

        return value;
    }

    /**
     * Computes the weight matrix. The closer the entry in the board is to the
     * center of the board, the closer the weight of that position will be to
     * {@code maxWeight}.
     * 
     * @param width the width of the matrix.
     * @param height the height of the matrix.
     * @param maxWeight the maximum weight. The minimum weight will be always
     * 1.0.
     * @return the weight matrix. 
     */
    private static final double[][] getWeightMatrix(final int width,
                                                    final int height,
                                                    final double maxWeight) {
        final double[][] weightMatrix = new double[height][width];

        for (int y = 0; y < weightMatrix.length; y++) {
            for (int x = 0; x < weightMatrix[0].length; x++) {
                int left = x;
                int right = weightMatrix[0].length - x - 1;
                int top = y;
                int bottom = weightMatrix.length - y - 1;
                int horizontalDifference = Math.abs(left - right);
                int verticalDifference = Math.abs(top - bottom);
                weightMatrix[y][x] =
                        1.0 + (maxWeight - 1.0) / 
                              (horizontalDifference + verticalDifference);
            }
        }

        return weightMatrix;
    }
}

Critique request

Any comments on my code?

\$\endgroup\$
  • \$\begingroup\$ Would you say the code works as intended? \$\endgroup\$ – yuri Jun 19 '19 at 8:33
  • \$\begingroup\$ Most likely not. The alpha-beta pruning seems to work, but the evaluation function favors suboptimal game states. \$\endgroup\$ – coderodde Jun 19 '19 at 8:37
3
\$\begingroup\$

I'm just going to do a detailed review of the more general class. With respect to Connect Four, have you read the paper by the person who solved it? They took a strategy-based approach, but there may be some tips for the evaluation function.


    /**
     * Maps each visited state to its parent state.
     */
    private final Map<S, S> parents = new HashMap<>();

Game trees aren't actually trees but digraphs. In the case of Connect Four there's an obvious parameter to show that they're layered digraphs. But a position at depth 4 might have various parents, and they might not be equally good choices. (Compare noughts and crosses / tic-tac-toe: it's a draw, but some moves give your opponent more chances to make mistakes).

I suspect that this is more an optimisation opportunity than a bug, but it would depend on the equality implementation of the state.


        // Do the game tree search:
        makePlyImpl(state,
                    depth,
                    Double.NEGATIVE_INFINITY, // intial alpha
                    Double.POSITIVE_INFINITY, // intial beta
                    minimizingPlayer,
                    maximizingPlayer,
                    initialPlayer);

Shouldn't depth be getDepth() in case a subclass overrides getDepth and setDepth?


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

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

                parents.put(child, state);
                alpha = Math.max(alpha, value);

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

            return value;

I don't see the value to having a variable for value rather than just reusing alpha. As I see it, makePlyImpl is called in two places: once with alpha = Double.NEGATIVE_INFINITY and the recursive call here. Eliminating value in favour of alpha would change the behaviour of the recursive calls slightly, equivalently to changing return value; to return Math.max(alpha, value);. But at the level up, this wouldn't cause alpha to increase where it wouldn't already have increased.

I also think it would be better to reduce duplication by merging both sides of the if. Reusing alpha and beta would reduce the differences between the two sides, giving:

        P otherPlayer = currentPlayer == maximizingPlayer
                            ? minimizingPlayer
                            : maximisingPlayer;

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

            parents.put(child, state); // See earlier comments

            if (currentPlayer == maximizingPlayer) {
                alpha = Math.max(alpha, value);
            } else {
                beta = Math.min(beta, value);
            }

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

        return currentPlayer == maximizingPlayer ? alpha : beta;
\$\endgroup\$
  • \$\begingroup\$ What do you think about correctness of my implementation of Alpha-beta pruning? \$\endgroup\$ – coderodde Jun 19 '19 at 8:47
  • \$\begingroup\$ I'd have to research alpha-beta. I'm more interested in the theoretical value of games than in AIs, so I've only ever implemented unpruned searches. \$\endgroup\$ – Peter Taylor Jun 19 '19 at 9:41

Not the answer you're looking for? Browse other questions tagged or ask your own question.