Heuristic function ivalidating iterative deepening

For a Mancala game, I’m writing an iterative deepening algorithm. This is the code:

public int optimize(GameState currentBoard) {
    List<Integer> aiMove = this.getMoves(currentBoard.getNextPlayer());

    double maxScore = 1e-30;
    int bestMove = -1;

    int maxTime = 5000;
    int moves = aiMove.size();

    long timeForEach = maxTime / moves;

    for (var moveForPit : aiMove) {
        GameState gameClone = new GameState(currentBoard);

        gameClone.makeMove(moveForPit);

        double score = iterativeDeepSearch(gameClone, timeForEach);

        if (score >= MAX_CUTOFF) {
            return moveForPit;
        }

        if (score > maxScore) {
            maxScore = score;
            bestMove = moveForPit;
        }

    }

    return bestMove;
}

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

    int depth = 1;
    double score = 0;

    searchCutoff = false;

    while (true) {
        long cTime = System.currentTimeMillis();

        if (endTime - cTime < 0)
            break;

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

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

        if (!searchCutoff) {
            score = searchResults;
        }

        depth++;
    }

    return score;
}

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

    boolean isAi = gameClone.getNextPlayer() == 2;
    double score = gameClone.scoreHeuristic();

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

    boolean won = gameClone.gameEnded();

    searchCutoff = elapsedTime - timeLimit >= 0;

    if (won || searchCutoff || (depth == 0) || (score >= MAX_CUTOFF) || (score <= MIN_CUTOFF)) {
        return score;
    }

    if (isAi) {
        List<Integer> moveList = this.getMoves(Players.AI.id);
        double value = Double.MIN_VALUE;
        for (var m : moveList) {
            GameState childClone = new GameState(gameClone);
            if (childClone.makeMove(m)) {

                value = alphaBetaPruning(childClone, depth - 1, alpha, beta, startTime, timeLimit);
                alpha = Math.max(alpha, value);

                int comp = Double.compare(alpha, beta);
                if (comp >= 0) {
                    break;
                }
            }
        }

        return value;
    } else {
        List<Integer> moveList = this.getMoves(Players.HUMAN.id);
        double value = Double.MAX_VALUE;
        for (var m : moveList) {
            GameState childClone = new GameState(gameClone);
            if (childClone.makeMove(m)) {

                value = alphaBetaPruning(childClone, depth - 1, alpha, beta, startTime, timeLimit);
                beta = Math.min(beta, value);

                int comp = Double.compare(beta, alpha);
                if (comp >= 0) {
                    break;
                }
            }
        }

        return value;
    }
}

I also supply a heuristic function, given by board.scoreHeuristic(). This is essentially the players differnce in score divided by the total amount possible to win with. In this version of Mancala, this should be 72 (12 pits, 6 ambos in each pit). I understand that this is impossible, but almost, anyway.

My code occassionally runs into an infinite loop, and I believe that the issue is the heuristic, which some times returns 0. I cannot understand why this infinite loop happens.

Answer

Turns out, as many Java programmers know, that clone() is not the same as assigning arrays in a clone… For other programmers out there who are not aware (such as myself..):

This

GameState(GameState parent) {
    this.board = parent.board; // BAD!
}

Is supposed to be this:

GameState(GameState parent) {
    this.board = parent.board.clone(); // or Arraycopy...
}