java - 追踪Minimax的最佳举动

我知道以前曾问过这种问题，但我无法解决我的疑问。
我有一个简单的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/上克隆它

最佳答案

看起来您可以摆脱best的minimax参数，从而消除了对garbage的需要，然后将best替换为this.bestFound。如果depth = 0，则仅设置bestFound的属性。

您可以通过使this.bestFound最初为空列表来获得主要变体。在moves循环之前，创建一个新动作。在if (score > alpha)部分中，将其属性设置为与现在相同。循环后立即将移至列表。那么主要的变化将是列表的相反。

如果很重要，可以进行一些更改以提高您的类的多线程性：


不要将bestFound列表存储为实例变量，而应将其作为run中的局部变量，并将其作为参数添加到minimax
使Board.makeMove不修改板，而是返回应用了此举的板的新实例。您可以通过克隆电路板并将移动代码应用于克隆来实现，而不必突变this。然后，将克隆的板传递给minimax的下一个调用。

关于java - 追踪Minimax的最佳举动，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15341917/