如何正确调用minimax方法（使用alpha-beta修剪）

Question

这是我的极小极大方法，它实现了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实际上输了。那么为什么这两种调用newximax499的方式会返回不同的结果呢？

这是它在GUI上的外观：

注意：运行程序所需的所有方法都可以在本文中找到。

Answer 1

在玩弄了一堆想法后，我终于找到了答案，所以不妨把它贴出来。这里讨论的方法newminimax499试图实现记忆和alpha-beta修剪。出于某种原因，这两个实用程序似乎不兼容（或者至少我对这两个实用程序的实现使它们不兼容）。删除与记忆相关的部分后，该方法成为纯alpha-beta修剪minimax算法，运行良好，如下所示：

public int[] newminimax499(int alpha, int beta){
    int bestPos=-1;
    int currentScore;
    if(isGameOver2()!='N'){
        int[] answer = {score(), bestPos};                                    
        return answer;
    }
    else{
        for(int x:getAvailableMoves()){
            if(turn=='O'){  //O is maximizer
                setO(x);
                //System.out.println(stateID++);
                currentScore = newminimax499(alpha, beta)[0];
                if(currentScore>alpha){
                    alpha=currentScore;
                    bestPos=x;
                }
            }
            else {  //X is minimizer
                setX(x);
                //System.out.println(stateID++);
                currentScore = newminimax499(alpha, beta)[0];
                if(currentScore<beta){
                    beta=currentScore;
                    bestPos=x;
                }
            }
            revert(x);
            if(alpha>=beta)
                break;
        }
        if(turn=='O'){ 
            int[] answer = {alpha, bestPos};                                    
            return answer;
        }
        else {
            int[] answer = {beta, bestPos};                                    
            return answer;
        }
    }
}

这种方法现在不仅可以工作（无论您在主方法中如何调用），而且它也比具有记忆的极小值快得多。该方法仅在7秒内计算4x4游戏中的第二步。而实现记忆的极小值在大约23秒内计算出来。

Answer 2

你在这里遇到的问题就像在国际象棋中使用换位表和阿尔法贝塔一样。我必须反驳你，因为它们不兼容！

正如我之前多次建议的那样，在尝试实现某些东西之前，请阅读相应的象棋编程wiki文章！

为了使memo和AB协同工作，您必须为memo表中的每个职位保存一个标志，以区分alpha cut节点、beta cut节点和precise节点。

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