0

我知道以前有人问过这种问题，但我无法解决我的疑问。我有一个简单的黑白棋引擎（实际上它玩得很好），它使用下面的类来获得最好的移动：

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参数 to minimax，从而省去 for garbage，然后替换best为this.bestFound。bestFound如果 depth = 0，则仅设置的属性。

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

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

  • 与其将bestFound列表存储为实例变量，不如将其设为局部变量run并将其作为参数添加到minimax
  • 不要Board.makeMove修改棋盘，而是返回一个新的棋盘实例并应用移动。您可以通过克隆板并将移动代码应用于克隆而不是 mutating 来实现这一点this。然后，将克隆的棋盘传递给 minimax 的下一个调用。
于 2013-03-11T15:13:24.920 回答
0

的第二个参数minimax用于返回最佳移动。

该业务garbage用于保持每个回合的最佳移动分开。使用您提供的代码，这并不重要。但是如果你想产生从当前棋盘到游戏结束的一系列移动，你需要让它们成为单独的移动对象。

为每个回合使用单独的最佳移动对象允许您使用线程执行许多技巧。首先，您可能想要限制奥赛罗 AI 的思考时间。在每个级别分别跟踪最佳移动意味着您始终拥有迄今为止可用的最佳移动。这也意味着您可以缓存棋盘的最佳移动，并在未来的极小极大搜索中查找。

其次，您可能希望并行搜索最佳移动，当每个极小极大调用独立时，这很容易实现。

于 2013-03-11T15:24:41.997 回答