9

我正在用 Java 为游戏编写一个极小极大算法，并且为了提高速度，在我递归地处理决策树时改变游戏状态。但是，这涉及修改我正在迭代的移动列表。

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
}

该board.move()方法会改变ArrayList legalMoves，但takeBack(1)会将其恢复到原始状态。这会导致任何问题吗？

4

2 回答 2

5

一句话，是的。

您没有指定board.legalMoves. 你说它是数组，但它不可能，因为你正在调用isEmpty()它。因此我怀疑你的意思是ArrayList。如果是这样的话，文档就很清楚了：

此类的iterator和listIterator方法返回的迭代器是快速失败的：如果列表在创建迭代器后的任何时候在结构上被修改，除了通过迭代器自己的remove或add方法之外的任何方式，迭代器将抛出一个ConcurrentModificationException. 因此，面对并发修改，迭代器快速而干净地失败，而不是在未来不确定的时间冒任意的、非确定性的行为。

我看到了两种解决方法：

1)避免结构修改。换句话说，可以更改元素的值，但不能添加/删除元素。

2）迭代ArrayList使用索引：

for (int i = 0; i < board.legalMoves.size(); i++) {
    Tuple move = board.get(i);
    ...
}
于 2012-11-20T08:21:33.103 回答
0

是的，你可以，但它很危险。我建议将 minmax 算法移到一个新类中，并将要分析的数据传递给构造函数。

现在，您可以在构造函数中复制一次数据，然后方法可以对副本进行操作。该算法现在可以按照它希望的任何方式修改数据，它不会影响游戏的其他部分或其他线程。此外，如果您有任何问题，它们必须来自一个类中的代码。

总体目标是为代码的每个修改部分提供一份数据副本，以减少可能导致麻烦的依赖关系。

于 2012-11-20T08:52:53.570 回答