java - Alpha beta 修剪没有产生好的结果

Question

----------------

真题

----------------

好的，真正的问题不在于 alpha-beta 剪枝与 minimax 算法。问题在于，树中的 minimax 算法只会给出最佳解决方案，而 alpha-beta 会给出正确的值，但多个子节点具有最佳值，而其中一些子节点不应该具有该值。

我想最终的问题是，获得根节点的最佳(在平局的情况下可能是多个)子节点的最有效方法是什么。

算法产生了正确的值，但多个节点与该值相关联，即使某些移动显然是错误的。

例子:滴答作响

-|-|O
-|X|-
-|X|-

将生成以下值:(0,1) 和 (1,0) 我的启发式值为 -0.06

(0,1) 是正确的值，因为它会阻止我的 X，但 (0,1) 是错误的，因为下一步我可以将 X 放在 (0,1) 并获胜。

当我在没有

的情况下运行相同的算法时

if(beta<=alpha)
    break;

它只返回值为 -0.06 的 (0,1)

----------------

最初发布的问题，现在只是糖

----------------

我花了几天时间试图弄清楚为什么我的最小最大算法有效，但是当我向它添加 alpha beta 剪枝时，它不起作用。我知道他们应该给出相同的结果，我什至对此进行了快速测试。我的问题是，为什么我的实现没有产生相同的结果？

这是 tic tak toe 在 android 中的实现。有时我可以打败算法

if(beta<=alpha) break; 

没有被注释掉，但是被注释掉了就不可战胜了。

private static double minimax(Node<Integer,Integer> parent, int player, final int[][] board, double alpha, double beta, int depth) {
    List<Pair<Integer, Integer>> moves = getAvailableMoves(board);
    int bs = getBoardScore(board);
    if (moves.isEmpty() || Math.abs(bs) == board.length)//leaf node
        return bs+(player==X?-1:1)*depth/10.;
    double bestVal = player == X ? -Integer.MAX_VALUE : Integer.MAX_VALUE;
    for(Pair<Integer, Integer> s : moves){
        int[][] b = clone(board);
        b[s.getFirst()][s.getSecond()]=player;
        Node<Integer, Integer> n = new Node<>(bs,b.hashCode());
        parent.getChildren().add(n);
        n.setParent(parent);
        double score = minimax(n,player==O?X:O,b,alpha,beta, depth+1);
        n.getValues().put("score",score);
        n.getValues().put("pair",s);
        if(player == X) {
            bestVal = Math.max(bestVal, score);
            alpha = Math.max(alpha,bestVal);
        } else {
            bestVal = Math.min(bestVal, score);
            beta = Math.min(beta,bestVal);
        }
        /*
        If i comment these two lines out it works as expected
        if(beta<= alpha)
            break;
        */
    }
    return bestVal;
}

现在，由于搜索树较小，这对 tick tack toe 来说不是问题，但我随后为西洋跳棋开发了它，并注意到了同样的现象。

private double alphaBeta(BitCheckers checkers, int depth, int absDepth, double alpha, double beta){
    if(checkers.movesWithoutAnything >= 40)
        return 0;//tie game//needs testing
    if(depth == 0 || checkers.getVictoryState() != INVALID)
        return checkers.getVictoryState()==INVALID?checkers.getBoardScore()-checkers.getPlayer()*moves/100.:
                checkers.getPlayer() == checkers.getVictoryState() ? Double.MAX_VALUE*checkers.getPlayer():
                        -Double.MAX_VALUE*checkers.getPlayer();
    List<Pair<Pair<Integer, Integer>, Pair<Integer, Integer>>> moves;
    if(absDepth == maxDepth)
        moves = (List<Pair<Pair<Integer, Integer>, Pair<Integer, Integer>>>) node.getValues().get("moves");
    else
        moves = checkers.getAllPlayerMoves();
    if(moves.isEmpty()) //no moves left? then this player loses
        return checkers.getPlayer() * -Double.MAX_VALUE;
    double v = checkers.getPlayer() == WHITE ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
    for(Pair<Pair<Integer, Integer>, Pair<Integer, Integer>> i : moves){
        BitCheckers c = checkers.clone();
        c.movePiece(i.getFirst().getFirst(),i.getFirst().getSecond(),i.getSecond().getFirst(),i.getSecond().getSecond());
        int newDepth = c.getPlayer() == checkers.getPlayer() ? depth : depth - 1;
        if(checkers.getPlayer() == WHITE) {
            v = Math.max(v, alphaBeta(c, newDepth, absDepth - 1, alpha, beta));
            alpha = Math.max(alpha,v);
        }else {
            v = Math.min(v, alphaBeta(c, newDepth, absDepth - 1, alpha, beta));
            beta = Math.min(beta,v);
        }
        if(absDepth == maxDepth) {
            double finalScore = v;
            for(Node n : node.getChildren())
                if(n.getData().equals(i)){
                    n.setValue(finalScore);
                    break;
                }
        }
        /*
        If i comment these two lines out it works as expected
        if(beta<= alpha)
            break;
        */
    }
    return v;
}

我用 pvs 对其进行了测试，它给出了与 alpha-beta 剪枝相同的结果，即几乎不如极小极大。

public double pvs(BitCheckers checkers, int depth, int absDepth, double alpha, double beta){
    if(checkers.movesWithoutAnything >= 40)
        return 0;//tie game//needs testing
    if(depth == 0 || checkers.getVictoryState() != INVALID)
        return checkers.getVictoryState()==INVALID?checkers.getBoardScore()-checkers.getPlayer()*moves/100.:
                checkers.getPlayer() == checkers.getVictoryState() ? Double.MAX_VALUE*checkers.getPlayer():
                        -Double.MAX_VALUE*checkers.getPlayer();
    List<Pair<Pair<Integer, Integer>, Pair<Integer, Integer>>> moves;
    if(absDepth == maxDepth)
        moves = (List<Pair<Pair<Integer, Integer>, Pair<Integer, Integer>>>) node.getValues().get("moves");
    else
        moves = checkers.getAllPlayerMoves();
    if(moves.isEmpty()) //no moves left? then this player loses
        return checkers.getPlayer() * -Double.MAX_VALUE;
    int j = 0;
    double score;
    for(Pair<Pair<Integer, Integer>, Pair<Integer, Integer>> i : moves){
        BitCheckers c = checkers.clone();
        c.movePiece(i.getFirst().getFirst(),i.getFirst().getSecond(),i.getSecond().getFirst(),i.getSecond().getSecond());
        int newDepth = c.getPlayer() == checkers.getPlayer() ? depth : depth - 1;
        double sign = c.getPlayer() == checkers.getPlayer()? -1 : 1;
        if(j++==0)
            score = -pvs(c,newDepth,absDepth-1,sign*-beta,sign*-alpha);
        else {
            score = -pvs(c,newDepth, absDepth-1,sign*-(alpha+1),sign*-alpha);
            if(alpha<score || score<beta)
                score = -pvs(c,newDepth,absDepth-1,sign*-beta,sign*-score);
        }
        if(absDepth == maxDepth) {
            double finalScore = score;
            for(Node n : node.getChildren())
                if(n.getData().equals(i)){
                    n.setValue(finalScore);
                    break;
                }
        }
        alpha = Math.max(alpha,score);
        if(alpha>=beta)
            break;
    }
    return alpha;
}

没有 alpha beta 修剪的跳棋很好，但不是很好。我知道使用 alpha-beta 的工作版本可能真的很棒。请帮助修复我的 alpha-beta 修剪。

我知道它应该给出相同的结果，我的问题是为什么我的实现没有给出相同的结果？

为了确认它应该给出相同的结果，我做了一个快速测试类实现。

public class MinimaxAlphaBetaTest {
    public static void main(String[] args) {
        Node<Double,Double> parent = new Node<>(0.,0.);
        int depth = 10;
        createTree(parent,depth);
        Timer t = new Timer().start();
        double ab = alphabeta(parent,depth+1,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,true);
        t.stop();
        System.out.println("Alpha Beta: "+ab+", time: "+t.getTime());
        t = new Timer().start();
        double mm = minimax(parent,depth+1,true);
        t.stop();
        System.out.println("Minimax: "+mm+", time: "+t.getTime());
        t = new Timer().start();
        double pv = pvs(parent,depth+1,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,1);
        t.stop();
        System.out.println("PVS: "+pv+", time: "+t.getTime());
        if(ab != mm)
            System.out.println(ab+"!="+mm);
    }

    public static void createTree(Node n, int depth){
        if(depth == 0) {
            n.getChildren().add(new Node<>(0.,(double) randBetween(1, 100)));
            return;
        }
        for (int i = 0; i < randBetween(2,10); i++) {
            Node nn = new Node<>(0.,0.);
            n.getChildren().add(nn);
            createTree(nn,depth-1);
        }
    }

    public static Random r = new Random();
    public static int randBetween(int min, int max){
        return r.nextInt(max-min+1)+min;
    }

    public static double pvs(Node<Double,Double> node, int depth, double alpha, double beta, int color){
        if(depth == 0 || node.getChildren().isEmpty())
            return color*node.getValue();
        int i = 0;
        double score;
        for(Node<Double,Double> child : node.getChildren()){
            if(i++==0)
                score = -pvs(child,depth-1,-beta,-alpha,-color);
            else {
                score = -pvs(child,depth-1,-alpha-1,-alpha,-color);
                if(alpha<score || score<beta)
                    score = -pvs(child,depth-1,-beta,-score,-color);
            }
            alpha = Math.max(alpha,score);
            if(alpha>=beta)
                break;
        }
        return alpha;
    }

    public static double alphabeta(Node<Double,Double> node, int depth, double alpha, double beta, boolean maximizingPlayer){
        if(depth == 0 || node.getChildren().isEmpty())
            return node.getValue();
        double v = maximizingPlayer ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
        for(Node<Double,Double> child : node.getChildren()){
            if(maximizingPlayer) {
                v = Math.max(v, alphabeta(child, depth - 1, alpha, beta, false));
                alpha = Math.max(alpha, v);
            }else {
                v = Math.min(v,alphabeta(child,depth-1,alpha,beta,true));
                beta = Math.min(beta,v);
            }
            if(beta <= alpha)
                break;
        }
        return v;
    }

    public static double minimax(Node<Double,Double> node, int depth, boolean maximizingPlayer){
        if(depth == 0 || node.getChildren().isEmpty())
            return node.getValue();
        double v = maximizingPlayer ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
        for(Node<Double,Double> child : node.getChildren()){
            if(maximizingPlayer)
                v = Math.max(v,minimax(child,depth-1,false));
            else
                v = Math.min(v,minimax(child,depth-1,true));
        }
        return v;
    }
}

这确实给出了我预期的 alpha-beta 和 pvs 大致相同的速度(pvs 较慢，因为 child 是随机顺序)并产生与 minimax 相同的结果。这证明算法是正确的，但无论出于何种原因，我对它们的实现都是错误的。

Alpha Beta: 28.0, time: 25.863126 milli seconds
Minimax: 28.0, time: 512.6119160000001 milli seconds
PVS: 28.0, time: 93.357653 milli seconds

Source Code for Checkers implementation

Pseudocode for pvs

Pseudocode for alpha beta i'm following

Full Souce Code for the Tick Tack Toe Implementation

Answer 1

我认为您可能误解了 AB 剪枝。

AB 剪枝应该会给你带来与 MinMax 相同的结果，它只是一种不沿着某些分支向下移动的方法，因为你知道这样做会比你检查过的另一个移动更糟糕，当你有大树时，它会有所帮助。

此外，如果不使用启发式算法并中断搜索，MinMax 将始终是不可战胜的，因为您已经计算了到达每个终止状态的每条可能路径。所以我预计 AB 修剪和 MinMax 都是无与伦比的，所以我认为你的 AB 修剪有问题。如果您的 minmax 是不可战胜的，那么您使用 AB 剪枝的方法也应该是不可战胜的。