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。如果是这样的话,文档就很清楚了:

此类的iteratorlistIterator方法返回的迭代器是快速失败的:如果列表在创建迭代器后的任何时候在结构上被修改,除了通过迭代器自己的removeadd方法之外的任何方式,迭代器将抛出一个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 回答