java - 如何正确调用 minimax 方法(使用 alpha beta 剪枝)

Question

这是我的 minimax 方法，它实现了 alpha beta 修剪和内存:

public int[] newminimax499(int a, int b){
    int bestPos=-1;
    int alpha= a;
    int beta= b;
    int currentScore;
    //boardShow();
    String stateString = "";                                                
    for (int i=0; i<state.length; i++) 
        stateString += state[i];                        
    int[] oldAnswer = oldAnswers.get(stateString);                          
    if (oldAnswer != null) 
        return oldAnswer;
    if(isGameOver2()!='N'){
        int[] answer = {score(), bestPos};                                    
        oldAnswers.put (stateString, answer);                                   
        return answer;
    }
    else{
        for(int x:getAvailableMoves()){
            if(turn=='O'){  //O is maximizer
                setO(x);
                //System.out.println(stateID++);
                currentScore = newminimax499(alpha, beta)[0];
                //revert(x);
                if(currentScore>alpha){
                    alpha=currentScore;
                    bestPos=x;
                }
                /*if(alpha>=beta){
                    break;
                }*/
            }
            else {  //X is minimizer
                setX(x);
                //System.out.println(stateID++);
                currentScore = newminimax499(alpha, beta)[0];
                //revert(x);
                if(currentScore<beta){
                    beta=currentScore;
                    bestPos=x;
                }
                /*if(alpha>=beta)
                    break;*/
            }
            revert(x);
            if(alpha>=beta)
                break;
        }
    }
    if(turn=='O'){ 
        int[] answer = {alpha, bestPos};                                    
        oldAnswers.put (stateString, answer);                                   
        return answer;
    }
    else {
        int[] answer = {beta, bestPos};                                    
        oldAnswers.put (stateString, answer);                                   
        return answer;
    }
}

作为测试游戏，在我的主要方法中，我在某处放置了一个 X(X 是玩家)，然后调用 newminimax499 来查看我应该放置 O(计算机)的位置:

 public static void main(String[] args) {
    State3 s=new State3(3);
    int [] result=new int[2];
    s.setX(4);
    result=s.newminimax499(Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.println("Score: "+result[0]+" Position: "+ result[1]);
    System.out.println("Run time: " + (endTime-startTime));
    s.boardShow();
}

该方法返回计算机应该播放的位置是 O(在这种情况下是 6)，所以我按照指示放置 O，自己播放 X，调用 newminimax499 并再次运行代码以查看 O 想要播放的位置等等。

public static void main(String[] args) {
    State3 s=new State3(3);
    int [] result=new int[2];
    s.setX(4);
    s.setO(6);//Position returned from previous code run
    s.setX(2);
    s.setO(8);//Position returned from previous code run
    s.setX(3);
    result=s.newminimax499(Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.println("Score: "+result[0]+" Position: "+ result[1]);
    System.out.println("Run time: " + (endTime-startTime));
    s.boardShow();
}

在这次特定的运行之后我得到了结果

Score: 10 Position: 7

哪个好。但是，在我的 GUI 中，这不是调用 newminimax 的方式。在那里，每次放置新的 X 或 O 时，电路板都不会重置。如果我像前面的例子那样把它放在一个 main 方法中，它将看起来像这样(请记住，它是完全相同的输入序列):

public static void main(String[] args) {
    State3 s=new State3(3);
    int [] result=new int[2];
    s.setX(4); //Player makes his move
    result=s.newminimax499(Integer.MIN_VALUE, Integer.MAX_VALUE);//Where should pc play?
    s.setO(result[1]);//PC makes his move
    s.setX(2);//Player makes his move
    result=s.newminimax499(Integer.MIN_VALUE, Integer.MAX_VALUE);//Where should PC make his move?
    s.setO(result[1]);//PC makes his move
    s.setX(3);//Player makes his move
    result=s.newminimax499(Integer.MIN_VALUE, Integer.MAX_VALUE);
    System.out.println("Score: "+result[0]+" Position: "+ result[1]);
    System.out.println("Run time: " + (endTime-startTime));
    s.boardShow();
}

现在，当以这种方式调用该方法时(这就是它在 GUI 中的调用方式)，它返回:

Score: 0 Position: 5

这意味着它没有采取获胜的行动，而是阻止了对手。以这种方式玩了几局游戏后，很明显 PC 确实输了。那么为什么这两种调用 newminimax499 的方式会返回不同的结果呢？

这是它在 GUI 上的样子:

注意:运行程序所需的所有方法都可以在这个 post 中找到.

Answer 1

您在这里遇到的问题与国际象棋中使用换位表和alpha beta 的问题相同。在他们不相容这一点上我不得不反驳你!

正如我之前多次建议的那样，请在尝试实现之前阅读相应的国际象棋编程 wiki 文章!

为了让备忘录和 AB 协同工作，您必须为备忘录表中的每个位置保存一个标志，以区分 alpha 切割节点、beta 切割节点和精确节点。

相信我，我从经验中知道他们一起工作；)