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ます。したがって、同時変更に直面した場合、イテレータは、将来の不確定な時間に任意の非決定論的な動作のリスクを冒すのではなく、迅速かつクリーンに失敗します。

私はこれを回避する2つの方法を見ます：

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アルゴリズムを新しいクラスに移動し、分析するデータをコンストラクターに渡すことをお勧めします。

これで、コンストラクターでデータを1回コピーでき、メソッドはそのコピーを操作できます。アルゴリズムは、データを任意の方法で変更できるようになりました。ゲームの他の部分や他のスレッドに影響を与えることはありません。また、問題がある場合は、1つのクラスのコードから取得する必要があります。

一般的な目標は、コードの各変更部分に、問題を引き起こす可能性のある依存関係をカットするために必要なデータのコピーを提供することです。

于 2012-11-20T08:52:53.570 に答える