0

私はTic-Tac-Toeゲーム（3x3）でアルファベータプルーニングアルゴリズムに取り組んでいます。現在、3x3グリッドの任意のインスタンスについて、最良のケースを見つけることができました。

public Best chooseAlphaBetaMove(int whosMov, int alpha, int beta) {

    Best reply = new Best();  
    Best myBest = new Best();

    if ((scoreGrid()==COMPUTER_WIN) || (scoreGrid()==OPPONENT_WIN) || 
                                       (scoreGrid()==GAME_DRAW)) {
        int score = scoreGrid();
        return new Best(score,-3,-3,count);
    }

    if (whosMov==COMPUTER_MOVE) {
        myBest.score = alpha;
    } else {
        myBest.score = beta;
    }

    for (int i=0; i<3; i++) {
    for (int j=0; j<3; j++) {
        if (layOut[i][j]==0) {
            moveGrid(whosMov,i,j);
            reply = chooseAlphaBetaMove(-whosMov,alpha,beta); 
            unmoveGrid(i,j);

            if ((whosMov==COMPUTER_MOVE)&&(reply.score>myBest.score)) {
                myBest.score = reply.score;
                alpha = reply.score;
                myBest.row = i;
                myBest.column = j;
            }

            if  ((whosMov==OPPONENT_MOVE)&&(reply.score<myBest.score)) {
                myBest.score = reply.score;
                beta = reply.score;
                myBest.row = i;
                myBest.column = j;
            }
            if (beta <= alpha) return myBest;
        }
    }
    }

        return myBest;
}

最適な構造は次のとおりです。

public class Best {

    public int score;
    public int row;
    public int column;
    public int count
}

最初のグリッドと次に移動する人を考えると、この次のプレーヤーが進むための最高のスコアと最高の位置を知ることができます。しかし、私はこの最良の動きのためにパス全体を印刷する方法を理解することはできません。（注-検索パス全体は必要ありません。この最良の移動からリーフまでの単一の検索パスのみを印刷したいと思います）。何かご意見は？ありがとう！

4

3 に答える 3

2

chooseAlphaBetaMove各パスを再帰的にたどる場合、おそらくリスト/スタックへの参照を各呼び出しに渡すことによって、それを追跡する必要があります。現在の最適パスよりも適切なパスが見つかった場合は、現在のパスのコピーを取得し、それを「これまでの最適パス」として保存します。終了したら、最適なパスを印刷できます。

于 2012-10-13T19:57:39.827 に答える
1

検索から最良の動きを追跡する何らかの方法が必要です。私の提案は、最良の手のリストを保持するデータ構造を維持することです。AStackは、この状況に最も適したデータ構造のようです。再帰呼び出しごとに、最初の動きをスタックにプッシュします (これまでのところ、これが最良の動きであるため)。より良い動きが見つかったら、スタックをポップして新しいものをプッシュします。alpha-beta pruning アルゴリズムが終了したら、単純にスタックをポップして各動きを出力します。これにより、ゲームの終わりまでの一連の「最良の」動きが得られます。

于 2012-10-13T19:57:13.813 に答える
1

http://xkcd.com/832/は TTT ツリーを視覚化する効果的な方法です

于 2012-10-13T21:29:27.813 に答える