#StackBounty: #java Mancala Iterative Deepening

Bounty: 50

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!


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.