4
\$\begingroup\$

This is my iterative deepening alpha beta minimax algorithm for a two player game called Mancala, see rules

The game and corresponding classes (GameState etc) are provided by another source. I provide my class which optimizes a GameState.

All criticism is appreciated.

package ai;

import java.lang.System.Logger;
import java.util.List;
import java.util.stream.Collectors;

import kalaha.GameState;

public class IterativeDeepeningOptimiser implements GameOptimiser {

    Logger logger = System.getLogger(IterativeDeepeningOptimiser.class.getName());

    private static final double MAX_CUTOFF = 101_000.0;
    private static final double MIN_CUTOFF = -101_000.0;
    private boolean searchCutoff = false;
    private int maxTime;

    private final GameState currentState;

    public IterativeDeepeningOptimiser(int maxTime, final GameState currentState) {
        this.maxTime = maxTime;
        this.currentState = currentState;
    }

    public int optimize() {
        List<Integer> validMoves = this.getPossibleMoves(currentState);
        int moves = validMoves.size();
        double maxScore = -Double.MAX_VALUE;
        int bestMove = -1;

        long timeForEach = maxTime / moves;

        for (var move : validMoves) {
            GameState clone = new GameState(currentState);
            if (clone.makeMove(move)) {
                double score = iterativeDeepSearch(clone, timeForEach);
                if (score > maxScore) {
                    maxScore = score;
                    bestMove = move;
                }
                // WE WIN.
                if (maxScore >= MAX_CUTOFF) {
                    return move;
                }
            }
        }

        return bestMove;
    }

    public double iterativeDeepSearch(final GameState gameClone, long timeForEachMove) {
        long sTime = System.currentTimeMillis();
        long endTime = sTime + timeForEachMove;

        long depth = 1;
        double score = 0;

        this.searchCutoff = false;
        boolean running = true;

        while (running) {
            GameState clone = new GameState(gameClone);
            long cTime = System.currentTimeMillis();

            if (cTime >= endTime) {
                running = false;
                break;
            }

            double searchResults = this.alphaBetaPruning(clone, depth, Integer.MIN_VALUE, Integer.MAX_VALUE, cTime,
                    endTime - cTime);

            if (searchResults >= MAX_CUTOFF) {
                return searchResults;
            }

            if (!this.searchCutoff) {
                score = searchResults;
            }

            depth++;
        }

        return score;
    }

    private double alphaBetaPruning(GameState gameClone, long depth, double alpha, double beta, long startTime,
            long timeLimit) {

        boolean isMaximizing = gameClone.getNextPlayer() == 2;
        double score = GameEvaluator.evaluate(gameClone);

        List<Integer> moveList = getPossibleMoves(gameClone);
        if (moveList.isEmpty()) {
            return score;
        }

        long currentTime = System.currentTimeMillis();
        long elapsedTime = (currentTime - startTime);

        if (elapsedTime >= timeLimit) {
            this.searchCutoff = true;
        }

        boolean over = this.gameOver(gameClone);
        if (over || depth <= 0 || score >= MAX_CUTOFF || score <= MIN_CUTOFF) {
            return score;
        }

        if (isMaximizing) {
            double currentAlpha = -1 * Double.MAX_VALUE;
            for (var move : moveList) {
                if (gameClone.moveIsPossible(move)) {
                    GameState child = new GameState(gameClone);
                    child.makeMove(move);
                    currentAlpha = Math.max(currentAlpha,
                            alphaBetaPruning(child, depth - 1, alpha, beta, startTime, timeLimit));
                    alpha = Math.max(alpha, currentAlpha);
                    if (alpha >= beta) {
                        return alpha;
                    }
                }
            }
            return currentAlpha;
        }

        double currentBeta = Double.MAX_VALUE;
        for (var move : moveList) {
            if (gameClone.moveIsPossible(move)) {
                GameState child = new GameState(gameClone);
                child.makeMove(move);
                currentBeta = Math.min(currentBeta,
                        alphaBetaPruning(child, depth - 1, alpha, beta, startTime, timeLimit));
                beta = Math.min(beta, currentBeta);
                if (beta <= alpha) {
                    return beta;
                }
            }
        }
        return currentBeta;

    }

    private List<Integer> getPossibleMoves(GameState gameClone) {
        return List.of(1, 2, 3, 4, 5, 6).stream().filter(e -> gameClone.moveIsPossible(e)).collect(Collectors.toList());
    }

    /**
     * True if the game is over.
     * 
     * @param clone
     * @return
     */
    private boolean gameOver(GameState clone) {
        return clone.getWinner() != -1;
    }
}

The evaluation function:

package ai;

import java.util.stream.IntStream;

import kalaha.GameState;

public class GameEvaluator {

    private static double[] HEURISTIC_WEIGHTS = new double[] { 30d, 7d, 100d, 100_000d, 1.3d };

    private GameEvaluator() {

    }

    /**
     * Heuristic function for the board. This heuristic cares about 1: Difference in
     * scores, 2: Difference of ambos in pits, 3: Possible captues. 4: Possible
     * steals. 5: If this player won.
     * 
     * @param board  current state of the game
     * @param player for what player
     * @return heuristic
     */
    public static double evaluate(GameState board) {

        int player = board.getNextPlayer();
        int otherPlayer = player == 2 ? 2 : 1;

        int difference = scoreDifference(board, player);

        double amboDiff = euclideanDifferenceAmbos(board);

        int possibleCaptures = possibleCaptures(board, player);

        int steals = possibleSteals(board, player, otherPlayer);

        int actualWinner = gameWinner(board, player);

        double[] values = new double[] { difference, possibleCaptures, steals, actualWinner, amboDiff };

        /*
         * if (board.getNextPlayer() == 2) { return board.getScore(2) -
         * board.getScore(1); } else { return board.getScore(1) - board.getScore(2); }
         */

        return weightedSum(values);
    }

    /**
     * Calculate weighted sum of constant weights and values provided.
     * 
     * @param values heuristic values
     * @return weighted sum
     */
    private static double weightedSum(double[] values) {
        double out = 0;
        for (int i = 0; i < HEURISTIC_WEIGHTS.length; i++) {
            out += HEURISTIC_WEIGHTS[i] * values[i];
        }
        return out;
    }

    /**
     * Difference in scores.
     * 
     * @param board  current game state
     * @param player current player
     * @return score difference
     */
    private static int scoreDifference(GameState board, int player) {
        int scoreL = board.getScore(2);
        int scoreR = board.getScore(1);
        return (player == 2 ? scoreL - scoreR : scoreR - scoreL);
    }

    /**
     * Returns whether or not the current player won.
     * 
     * @param board  current game state
     * @param player current player
     * @return 1 if current player won, 0 if draw or still ongoing, -1 if other
     *         player.
     */
    private static int gameWinner(GameState board, int player) {
        int winner = board.getWinner();

        if (winner == -1 || winner == 0)
            return 0;
        if (winner == 1 || winner == 2)
            return winner == player ? 1 : -1;

        return 0;
    }

    /**
     * Possible steals for a player, how many moves result in the last ambo landing
     * in an empty pit?
     * 
     * @param board      current game state
     * @param player     current player
     * @param nextPlayer next player
     * @return the amount of possible steals
     */
    private static int possibleSteals(GameState board, int player, int nextPlayer) {
        int steals = 0;
        for (int i = 1; i < 7; i++) {
            int ambos = board.getSeeds(i, player);

            int whereWeGot = 7 - i - ambos + 1;

            if (board.getSeeds(whereWeGot, player) == 0) {
                steals += board.getSeeds(whereWeGot, nextPlayer);
            }
        }
        return steals;
    }

    /**
     * Calculate the amount of possible captures you can do in this turn - i.e if
     * making a move gives you a score in your house.
     * 
     * @param board  current game state.
     * @param player current player.
     * @return amount of possible captures
     */
    private static int possibleCaptures(GameState board, int player) {
        int possibleCaptures = 0;
        for (int i = 1; i < 7; i++) {
            int ambosForPit = board.getSeeds(i, player);

            if (7 - i - ambosForPit >= 0)
                possibleCaptures++;
        }
        return possibleCaptures;
    }

    /**
     * Calculate the euclidean distance between the ambos in the pits.
     * 
     * @param board current state of game
     * @return euclidean distance
     */
    private static double euclideanDifferenceAmbos(GameState board) {
        double ambosInRPits = IntStream.range(1, 7).mapToDouble(e -> board.getSeeds(e, 1)).sum();
        double ambosInLPits = IntStream.range(1, 7).mapToDouble(e -> board.getSeeds(e, 2)).sum();

        double amboDiff = Math.sqrt(ambosInLPits * ambosInLPits + ambosInRPits * ambosInRPits);
        return amboDiff;
    }

}

Apart from a code review, I would love some comments on the choice of evaluation functions, weights, corresponding weights and cutoffs, and whether or not this actually makes sense.

Thank you!

\$\endgroup\$
2
+50
\$\begingroup\$

I'm not really familiar with game AI development other than I roughly know what minimax is, so this review is mostly based on general and Java aspects. I'll start with GameEvaluator.

GameEvaluator

It's generally a bad decision to make a class purely static, especially when it represents business logic. A class instance makes testing and swapping out the logic during development or at runtime easier.


The use of the d prefix for double literals is unusual, since it's the default. Just using .0 to distinguish them from integers is more common.

The use of underscore as thousands separator is nice. It's a Java feature too few know of.


I'm not a big fan of storing the weights (and later the values) directly in arrays. I understand it makes the summation at the end easier and probably faster than using something else, but it doesn't help the readability, because the meaning of the individual weights get lost.

Maybe "hide" the arrays in a "Weighter" class something like this:

class Weighter {
    private final double[] weights;

    public Weighter(double differenceWeight, double possibleCapturesWeight, double stealsWeight, double actualWinnerWeight, double amboDiffWeight) {
        weights = new double[] {differenceWeight, possibleCapturesWeight, stealsWeight, actualWinnerWeight, amboDiffWeight};
    }

    public double weightedSum(double difference, double possibleCaptures, double steals, double actualWinner, double amboDiff) {
        double[] values = new double[] { difference, possibleCaptures, steals, actualWinner, amboDiff };

        double out = 0;
        for (int i = 0; i < weights.length; i++) {
            out += weights[i] * values[i];
        }
        return out;
    }
}

Similarly representing the players representing the players as integers 1 and 2 isn't very Java-like. A representation as an enum would fit better and catch errors such as board.getScore(0) at compile time.


There are several things in the evaluation class that it should not need know, but should be provided by the game state (or an object representing the board independently from the game state):

  • How to calculate the opposing player.
  • How many pocket/holes there are on each players side (notice the hard coded 7 everywhere).
  • How to calculate the opposite pocket/hole.

I didn't understand some things:

  • The meaning of the word "ambo".
  • The difference between the return values 0and -1 of board.getWinner().
  • The meaning of the variable name whereWeGot.

Some documentation or alternative variable names may help here.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Hi, and thank you! I implemented your change (to a certain extent, I asked my professor if we were allowed to change anything in the GameState class and we were not.) Readability of the magic 7 is explained, weights have been refactored. I made some other changes, such as making GameEvaluator be injected into GameOptimiser, and most importantly, extending this algorithm with added multithreading functionality. Gained a ~6x performance boost and made the algorithm reach depths of avg 22 instead of avg 15. I too would have used an enum for players, but the gamestate api did not allow for it. \$\endgroup\$ – Edwin Carlsson Sep 24 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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