18

Javaでチェッカーゲームのアルファベータプルーニングを使用してミニマックスを実装しようとしています。私のミニマックスアルゴリズムは完璧に機能します。私のコードは、アルファベータコードを使用して実行されます。残念ながら、標準のミニマックスアルゴリズムに対して1000ゲームをプレイすると、アルファベータアルゴリズムは常に50ゲーム程度遅れます。

アルファベータ法は動きの質を低下させるべきではないので、それらを達成するのにかかる時間だけで、何かが間違っている必要があります。ただし、ペンと紙を取り出し、仮想の葉ノード値を描画し、アルゴリズムを使用して、正しい最良の動きを計算するかどうかを予測しました。論理エラーはないようです。このビデオのツリーを使用しました：Alpha-BetaPruningを使用してアルゴリズムをトレースしました。論理的にはすべて同じ選択を行う必要があるため、機能する実装である必要があります。

また、コードにprintステートメントを追加しました（混乱を減らすために削除されています）。値は正しく返され、表示され、プルーニングが行われます。私の最善の努力にもかかわらず、私は論理エラーがどこにあるかを見つけることができませんでした。これは、これを実装するための私の3番目の異なる試みであり、それらすべてに同じ問題がありました。

ここに完全なコードを投稿することはできません。長すぎるため、エラーに関連するメソッドを含めました。確かではありませんが、問題は非再帰的なmove（）メソッドにある可能性が高いと思いますが、論理的なエラーを見つけることができないので、もっとスラッシングして、おそらく何かを作っているでしょう韻や理由がなくても、良くなるよりも悪くなる。

forループの再帰呼び出しから複数の整数値を回復するためのトリックはありますか？それは私のミニマックスとネガマックスの両方の実装でうまく機能しますが、アルファベータ法はいくつかの奇妙な結果を生み出すようです。

@Override
public GameState move(GameState state) 
{
    int alpha = -INFINITY;
    int beta = INFINITY;
    int bestScore = -Integer.MAX_VALUE;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    GameState bestMove = null;
    for(GameTreeNode child: gameTreeRoot.getChildren())
    {
        if(bestMove == null)
        {
            bestMove = child.getState();
        }
        alpha = Math.max(alpha, miniMax(child, plyDepth - 1, alpha, beta));
        if(alpha > bestScore)
        {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) 
{
    if(depth <= 0 || terminalNode(currentNode.getState())) 
    {
        return getHeuristic(currentNode.getState());
    }
    if(currentNode.getState().getCurrentPlayer().equals(selfColor))
    {
        for(GameTreeNode child: currentNode.getChildren())
        {
            alpha = Math.max(alpha, miniMax(child, depth - 1, alpha, beta));

            if(alpha >= beta)
            {
                return beta;
            }
        }
        return alpha;
    }
    else
    {
        for(GameTreeNode child: currentNode.getChildren())
        {
            beta = Math.min(beta, miniMax(child, depth - 1, alpha, beta));

            if(alpha >= beta)
            {
                return alpha;
            }
        }
        return beta;
    }
}
//Checks to see if the node is terminal
private boolean terminalNode(GameState state)
{
if(state.getStatus().equals(win) || state.getStatus().equals(lose) || state.getStatus().equals(draw))
    {
        return true;
    }
    else
    {
        return false;
    }
}
4

5 に答える 5

2

2013 年 3 月 16 日、sage88 は次のように質問しました。

for ループの再帰呼び出しから複数の整数値を復元するトリックはありますか? 私のミニマックスとネガマックスの両方の実装で問題なく動作しますが、アルファ ベータ プルーニングは奇妙な結果を生むようです。

アルファ ベータ プルーニングでは、関心のある唯一の出力値はノードのスコアです。最小ノードのベータの最終値は、その親の最大ノードのアルファ値と見なされます。同様に、最大ノードのアルファの最終値は、その親の最小ノードのベータ値と見なされます。したがって：

あなたの質問への答えは、最も関連性の高いトリックであるため、アルゴリズム自体です。

とはいえ、実装には 2 つのエラーがあります。1) Adrian Blackburn が最初に指摘したように、最小ノードから誤ってアルファを返し、その逆を行っているため、精度が歪んでいます。2) 現在のノードの値で親のアルファまたはベータを時期尚早に検討することで、剪定の機会を放棄しています。このバージョンでは、戻り値が修正され、プルーニングが最大化されます。

private int miniMax(GameTreeNode currentNode, int depth, int alpha, int beta) {
    if (depth <= 0 || terminalNode(currentNode.getState())) {
        return getHeuristic(currentNode.getState());
    }
    if (currentNode.getState().getCurrentPlayer().equals(selfColor)) {
        int currentAlpha = -INFINITY;
        for (GameTreeNode child : currentNode.getChildren()) {
            currentAlpha = Math.max(currentAlpha, miniMax(child, depth - 1, alpha, beta));
            alpha = Math.max(alpha, currentAlpha);
            if (alpha >= beta) {
                return alpha;
            }
        }
        return currentAlpha;
    }
    int currentBeta = INFINITY;
    for (GameTreeNode child : currentNode.getChildren()) {
        currentBeta = Math.min(currentBeta, miniMax(child, depth - 1, alpha, beta));
        beta = Math.min(beta, currentBeta);
        if (beta <= alpha) {
            return beta;
        }
    }
    return currentBeta;
}

楽しくて興味深い質問に貢献してくれてありがとう:)

もっと楽しくするために、move()メソッドを明確にし、への冗長な呼び出しを削除しますMath.max()。

@Override
public GameState move(GameState state) {
    GameState bestMove = null;
    int bestScore = -INFINITY;
    GameTreeNode gameTreeRoot = new GameTreeNode(state);
    for (GameTreeNode child : gameTreeRoot.getChildren()) {
        int alpha = miniMax(child, plyDepth - 1, bestScore, INFINITY);
        if (alpha > bestScore || bestMove == null) {
            bestMove = child.getState();
            bestScore = alpha;
        }
    }
    return bestMove;
}

最後に (さらに楽しい)、単なる提案です。 の意図を明確にするためにメソッド名を変更し terminalNode()ますが、これを に移動しGameStateて、パラメーターなしで呼び出すことができるようにします。

private boolean isTerminal(GameState state) {
    //return Is.any(state.getStatus(), win, lose, draw);
    return state.getStatus().equals(win)
        || state.getStatus().equals(lose)
        || state.getStatus().equals(draw);
}
于 2014-12-12T00:34:47.180 に答える
1

あなたはすでに問題を解決しましたが、遭遇した問題はかなり一般的です。したがって、AI エージェントのアルゴリズムの一部を構築するときはいつでも、適切にテストする必要があります。したがって、ミニマックス アルゴリズムが正しければ、多くのランダム ツリーを生成して、結果が同じかどうかを確認できます。たとえば、Python では次のように実行できます。

class Node():
    def __init__(self, data, children):
        self.data = data
        self.children = children

def generateTree(depth, branching):
    total = branching**depth
    values = [randint(-100, 100) for _ in xrange(total)]
    level = [Node(values[i], []) for i in xrange(total)]

    for _ in xrange(depth):
        total /= branching
        level = [Node(None, level[i * branching: (i+1) * branching]) for i in xrange(total)]

    return level[0], values

これで、多数のランダム ツリーを含むツリーを生成し、結果を比較できます。

tree, values = generateTree(depth, branching)
print negamax(tree, depth, 1) == alpha_beta_negamax(tree, depth, float('-inf'), float('inf'), 1)

minimax と alpha-beta は最高の値を返すことを忘れないでください。実際のゲームで関心があるのは動きです。手番を返せるように変更するのは簡単ですが、手番を返す方法を決定するのは開発者次第です。これは、最良の解決策につながる多くの動きが存在する可能性があるためです (最初のもの、最後のもの、または最も一般的なものは、すべての動きを見つけてランダムなものを返すことです)。

あなたの場合、問題は戻り値のランダム性にあったため、テスト中にランダム性を修正することをお勧めします。

于 2015-10-16T02:19:53.573 に答える