Can I safely mutate an array I am iterating over, if it returns to its original state after each iteration?

Question

I am writing a minimax algorithm for a game in Java, and, for speed purposes, mutating the game state as I recursively work through the decision tree. However, this involves modifying the list of moves I am iterating over.

public int minimax(int currentDepth) {
    if (currentDepth == depth || board.legalMoves.isEmpty()) {
        int eval = board.eval();
        board.takeBack(1);
        return eval;
    }
    int x = Integer.MIN_VALUE;
    for (Tuple move : board.legalMoves) {
        board.move(move);
        x = max(x, -1*minimax(currentDepth+1));
        board.takeBack(1);
    }
    return x
}

The board.move() method mutates the ArrayList legalMoves, but takeBack(1) brings it back to its original state. Could this cause any problems?

Answer 1

In a word, yes.

You don't specify the type of board.legalMoves. You say that it's array, but it can't be, since you're calling isEmpty() on it. I therefore suspect that you mean ArrayList. If that's the case, the documentation is pretty clear:

The iterators returned by this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

I see two ways around this:

1) Avoid structural modifications. In other words, it's OK to change the values of the elements, but it's not OK to add/remove elements.

2) Iterate over the ArrayList using indices:

for (int i = 0; i < board.legalMoves.size(); i++) {
    Tuple move = board.get(i);
    ...
}