Minimax algorithm not respecting randomisation

Question

I'm developing a minimax alogorithm for use in a modified checkers game. In my evaluation function every score is multiplied by 10 and then a random number between 1 and 10 is added/subtracted from it (max or min node depending). However, when running the program it always executes the same sequence of moves. I've checked the evaluation function and it definitely returns randomised values for nodes that would be of equal value so I can only assume the problem lies in the minimax function itself, any ideas? The other functions, generateMoves and simulateMove also work correctly.

private int minimax(State state, int depth, int min, int max) {
    ArrayList<Move> moves = generateMoves(state.board, state.colour);
    char opponent = (state.colour == DraughtBoard.WHITE) ? DraughtBoard.BLACK : DraughtBoard.WHITE;

    if (moves.size() == 1)
        nextMove = moves.get(0);

    int bestScore;
    Move bestMove = new Move();
    int score = 0;

    if (depth == 0 || moves.size() == 0) {
        return evaluateBoard(state);
    }

    if (colour == DraughtBoard.WHITE) {
        bestScore = min;
        for (Move move : moves) {
            char[][] temp = state.board.clone();
            boolean scored = simulateMove(move, temp);

            State nextState = new State(temp, opponent, state.whiteScore, state.blackScore);
            if (scored) state.whiteScore++;

            score = minimax(state, depth-1, bestScore, max);

            if (score > bestScore) {
                bestScore = score;
                bestMove = move;
            }
            if (bestScore > max) return max;
        }
        nextMove = bestMove;
        return bestScore;
    } else {
        bestScore = max;
        for (Move move : moves) {
            char[][] temp = state.board.clone();
            boolean scored = simulateMove(move, temp);

            State nextState = new State(temp, opponent, state.whiteScore, state.blackScore);
            if (scored) state.blackScore++;

            score = minimax(state, depth-1, min, bestScore);

            if (score < bestScore) {
                bestScore = score;
                bestMove = move;
            }
            if (bestScore < min) return min;
        }
        nextMove = bestMove;
        return bestScore;
    }
}

score 0 · Answer 1 · edited May 23 '17 at 12:30

0

char[][] temp = state.board.clone(); will only do a swallow copy (except you wrote your own clone() method)

Which means temp has the same references as board therefor you will change board while calling siumlateMove.

This may causes your problem. deep copy of a 2d array

edited May 23 '17 at 12:30

Community

1
1

answered Dec 06 '16 at 20:25

Nordiii

446
1
3
10

That was a problem, thanks. However, it still follows the same sequence of moves. Changing this made sure it actually evaluated each move properly though. – dan Dec 06 '16 at 20:38
@user3893820 `if (bestScore > max) return max;` and `if (score < bestScore)` brothers me... when you'r multiply the score by 10 I would guess that they may always exceed the boundarys and because of this always min / max would be returned.... but thats only a guess – Nordiii Dec 06 '16 at 22:59
The randomisation adjustment is part of the evaluation function and so is done before any comparisons are made to max or bestScore, so max and bestScore will have the same adjustments to them when they are set. Just as a test I took out the randomisation and the same issue persisted – dan Dec 06 '16 at 23:02
@user3893820 is it possible that your first call of minimax returns before setting the nextMove? because then it would always go down till `if (moves.size() == 1) nextMove = moves.get(0);` which then would be always the same(maybe).... And why are you increasing the state.score while evaluating? – Nordiii Dec 06 '16 at 23:23
Thanks again for helping, what would you suggest in terms of returning from minimax? Also yeah it should have been nextState.score increasing, but unfortunately that didn't solve the problem – dan Dec 06 '16 at 23:51
Thats a rough question, the fastest way probably be to add a flag as parameter `boolean firstTime` and check `if (!firstTime && bestScore > max) return max;` you could set it to false in the next recursive call which than would return min max again but skips it in the first call.... Maybe not the nicest way but for testing purpose fitting enough – Nordiii Dec 07 '16 at 00:03

Minimax algorithm not respecting randomisation

1 Answers1