小贝子编程

alpha beta修剪不会产生良好的效果



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

实际问题

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

好吧，真正的问题不是Alpha-Beta修剪与最小算法。问题是，在树上中只能提供最佳解决方案时，minimax算法将提供正确的价值，但是多个孩子具有最佳价值，其中一些孩子不应该具有此价值。

我猜最终的问题是，词根节点的最有效方法是什么最有效的方法(在领带的情况下可能是多重的(。

该算法会产生正确的值，但是即使某些动作显然是错误的，多个节点都与该值联系在一起。

示例：ticktacktoe 

-|-|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 pruning时，它行不通。我了解他们应该给出相同的结果，甚至对此进行了快速测试。我的问题是，为什么我的实施不产生相同的结果？

这是在Android中实现的TIC Tak Toe。有时我可以在

时击败算法 
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 Tok Toe来说不是问题，但是我随后为Checkers开发了它，并注意到了同样的现象。

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对其进行了测试，并给出与α-beta修剪相同的结果，即不像minimax一样好。

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修剪。

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

要确认它应该给出相同的结果，我进行了快速测试类实现。

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;
    }
}

实际上，这确实给出了我期望的α-beta和PV的速度大致相同(PVS较慢，因为儿童是随机顺序的(，并且产生与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

Checkers实施的源代码

pvs

的伪代码

alpha beta的伪代码我正在关注

tick钉脚趾实现的完整Souce代码

我认为您可能会误解AB修剪。

ab修剪应该给您与Minmax相同的结果，这只是一种不跌落某些分支机构的方式，因为您知道这一举动会比您检查过的另一个举动要糟，这在您有巨大的树木时会有所帮助。p>另外，Minmax不使用启发式启发式并切断您的搜索始终是不败的，因为您已经计算了到达每个终止状态的所有可能路径。因此，我希望AB修剪和Minmax都无与伦比，所以我认为您的AB修剪有问题。如果您的Minmax不败，那么您的方法也应使用AB修剪。

相关内容

最新更新


热门标签：

javascript python java c# php android html jquery c++ css ios sql mysql arrays asp.net json python-3.x ruby-on-rails .net sql-server django objective-c excel regex ruby linux ajax iphone xml vba spring asp.net-mvc database wordpress string postgresql wpf windows xcode bash git oracle list vb.net multithreading eclipse algorithm macos powershell visual-studio image forms numpy scala function api selenium