0

このような質問は以前にも聞いたことがあると思いますが、疑問を解決することができませんでした。私は単純なOthelloエンジンを持っています（実際には非常にうまく機能します）。これは、以下のクラスを使用して最良の動きを実現します。

import java.util.*;
import java.util.concurrent.*;

public class MinimaxOthello implements Runnable
{
  private CountDownLatch doneSignal;    
  private int maxDepth;
  private int calls;    
  private OthelloMove bestFound;
  private OthelloBoard board;
  private static float INFINITY = Float.MAX_VALUE/1000;    
  private boolean solve = false;
  private Comparator<OthelloMove> comparator = Collections.reverseOrder(new MoveComparator());

public MinimaxOthello (OthelloBoard board, int maxDepth, CountDownLatch doneSignal, boolean solve)
{
    this.board = board;        
    this.bestFound = new OthelloMove();
    bestFound.setPlayer(board.getCurrentPlayer());
    this.maxDepth = maxDepth; 
    this.doneSignal = doneSignal;                
    this.solve = solve;
}

public OthelloMove getBestFound()
{       
    return this.bestFound;
}
public void run()
{        
    float val = minimax(board, bestFound, -INFINITY, INFINITY, 0);
    System.out.println("calls: " + calls);
    System.out.println("eval: " + val);
    System.out.println();
    doneSignal.countDown();        
}

private float minimax(OthelloBoard board, OthelloMove best, float alpha, float beta, int depth)
{
    calls++;             
    OthelloMove garbage = new OthelloMove();             
    int currentPlayer = board.getCurrentPlayer();

    if (board.checkEnd())
    {                        
        int bd = board.countDiscs(OthelloBoard.BLACK);
        int wd = board.countDiscs(OthelloBoard.WHITE);

        if ((bd > wd) && currentPlayer == OthelloBoard.BLACK)
        {                
            return INFINITY/10;
        }
        else if ((bd < wd) && currentPlayer == OthelloBoard.BLACK)
        {                
            return -INFINITY/10;
        }
        else if ((bd > wd) && currentPlayer == OthelloBoard.WHITE)
        {                
            return -INFINITY/10;
        }
        else if ((bd < wd) && currentPlayer == OthelloBoard.WHITE)
        {                
            return INFINITY/10;
        }
        else 
        {                
            return 0.0f;
        }
    }
    if (!solve)
    {
        if (depth == maxDepth)
            return OthelloHeuristics.eval(currentPlayer, board);
    }

    ArrayList<OthelloMove> moves = board.getAllMoves(currentPlayer);
    if (moves.size() > 1)
    {
        OthelloHeuristics.scoreMoves(moves);        
        Collections.sort(moves, comparator);
    }

    for (OthelloMove mv : moves)
    {                                    
        board.makeMove(mv);            
        float score = - minimax(board, garbage, -beta,  -alpha, depth + 1);           
        board.undoMove(mv);             

        if(score > alpha)
        {  
            alpha = score;                
            best.setFlipSquares(mv.getFlipSquares());
            best.setIdx(mv.getIdx());        
            best.setPlayer(mv.getPlayer());                              
        }

        if (alpha >= beta)
            break;                

    }            
    return alpha;
 }  
}

私はbestFoundインスタンス変数を持っていますが、疑問は、なぜ呼び出す必要があるのか​​ということです

OthelloMove garbage = new OthelloMove();

そしてそれを渡しますか？コードは機能しますが、私には非常に奇妙に思えます！

最高の動きやプリンシパルバリエーションを得るための「より良い」方法はありますか？私は実際には再帰の専門家ではありません。これをデバッグして視覚化するのは非常に困難です。ありがとう！

** PS：https://github.com/fernandotenorio/でクローンを作成できます

4

2 に答える 2

1

bestのパラメータminimaxを削除して、の必要性をなくし、garbageからに置き換えることbestができるようですthis.bestFound。bestFound深さ=0の場合にのみの属性を設定します。

this.bestFound最初は空のリストを作成することで、主要なバリエーションを取得できます。ループの前にmoves、新しい動きを作成します。このif (score > alpha)部分では、現在と同じように属性を設定します。ループの直後に移動をリストにプッシュします。その場合、主なバリエーションはリストの逆になります。

重要な場合は、クラスのマルチスレッド性を向上させるために行うことができるいくつかの変更を次に示します。

  • リストをインスタンス変数として保存する代わりに、bestFoundリストをローカル変数にしrunて、次のパラメーターとして追加します。minimax
  • ボードBoard.makeMoveを変更せずに、移動が適用されたボードの新しいインスタンスを返します。を変更する代わりに、ボードのクローンを作成し、移動コードをクローンに適用することで、これを実装できますthis。次に、複製されたボードを次のミニマックスの呼び出しに渡します。
于 2013-03-11T15:13:24.920 に答える
0

の2番目の引数はminimax、最良の動きを返すために使用されます。

とのビジネスgarbageは、各ターンの最良の動きを別々に保つために使用されます。提供したコードでは、これは重要ではありません。ただし、現在のボードからゲームの終了までの一連の移動を生成する場合は、それらを個別の移動オブジェクトにする必要があります。

ターンごとに個別のベストムーブオブジェクトを使用すると、スレッディングでいくつかのトリックを実行できます。まず、OthelloAIの思考時間を制限することをお勧めします。各レベルで個別に最良の動きを追跡することは、これまでのところ最良の動きを常に利用できることを意味します。また、ボードに最適な動きをキャッシュして、将来のミニマックス検索でそれを調べることができることも意味します。

第二に、あなたは並行して最良の動きを探したいかもしれません、そしてこれは各ミニマックス呼び出しが独立しているときに実装するのは簡単です。

于 2013-03-11T15:24:41.997 に答える