java - 来自随机值的 Minimax 结果给出了意想不到的低结果

Question

我创建了 minimax、pvs 和 alpha-beta 算法，并使用随机树遍历比较了它们的结果。这棵树的每个父节点有 [2,10] 个子节点，总深度为 10。每个叶节点的随机值为 [0,10]。

当我运行树遍历 minimax 算法时，结果值通常是 2 或 3。这对我来说很奇怪，因为我猜它会给出 5 或 4 或 6，但它始终是 2 或 3。这是minimax 算法它应该给出最小值的最大值，这令人困惑为什么它似乎几乎给出了整棵树的最小值，仅供引用，我将算法作为最大化玩家开始。

这是结果:

Alpha Beta: 2.0, time: 10.606461 milli seconds
PVS: 2.0, time: 41.119652 milli seconds
Minimax: 2.0, time: 184.492937 milli seconds

这是源代码，不包括 Timer 类，因为它与我的问题无关。

import testing.utilities.data.Timer;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Random;

public class MinimaxAlphaBetaTest {
    public static void main(String[] args) {
        Node parent = new Node(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 pv = pvs(parent,depth+1,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,1);
        t.stop();
        System.out.println("PVS: "+pv+", time: "+t.getTime());
        t = new Timer().start();
        double mm = minimax(parent,depth+1,true);
        t.stop();
        System.out.println("Minimax: "+mm+", time: "+t.getTime());
    }

    public static void createTree(Node n, int depth){
        if(depth == 0) {
            n.getChildren().add(new Node((double) randBetween(0, 10)));
            return;
        }
        for (int i = 0; i < randBetween(2,10); i++) {
            Node nn = new Node(0.);
            n.getChildren().add(nn);
            createTree(nn,depth-1);
        }
    }
    private static Random r;    // pseudo-random number generator
    private static long seed;        // pseudo-random number generator seed

    // static initializer
    static {
        // this is how the seed was set in Java 1.4
        seed = System.currentTimeMillis();
        r = new Random(seed);
    }
    public static int randBetween(int min, int max){
        return r.nextInt(max-min+1)+min;
    }

    public static double pvs(Node 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 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 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 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 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 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;
    }

    static class Node{
        List<Node> children = new ArrayList<>();
        double value;

        public Node(double value) {
            this.value = value;
        }

        public List<Node> getChildren() {
            return children;
        }

        public double getValue() {
            return value;
        }

        public void setValue(double value) {
            this.value = value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Node node = (Node) o;
            return Double.compare(node.value, value) == 0;
        }

        @Override
        public int hashCode() {

            return Objects.hash(value);
        }
    }
}

---

编辑

感谢 Jiri Tousek 的评论，它现在变得有意义了，当以奇数深度运行时给出的数字通常高于 5，而偶数通常低于 5，例如 11，它会产生以下结果:

Alpha Beta: 7.0, time: 39.697701 milli seconds
PVS: 7.0, time: 216.849568 milli seconds
Minimax: 7.0, time: 998.207216 milli seconds

用奇数进一步运行它，看起来深度 3 结果来 self 所看到的 (5,6,7,8,9,10)，深度 5 结果来 self 所看到的(7,8,9), depth 7 结果是我见过的 7 或 8, depth 9 我见过的结果是 8, depth 11 我见过 7 和 8

而偶数产生 {2,4,(2,3,4,5,6)},{6,8,10,(2,3)}

因此，在运行算法并寻找结果时，轮到谁重要吗？

IE 如果轮到最大化器则向下奇数深度，如果轮到最小器则向下偶数深度，任何深度都会产生理想的移动？

Answer 1

由于您从最大值(在最顶部)开始并向下 10 个级别，因此您将在最深的级别选择最小值。

由于您选择的是 [2-10] 个数字中的最小值(不是平均值)，因此您不能期望它大约为 5 - 它通常会更低。事实上，[0-10] 范围内的 6 个数字中的最小值为 5 或更高的概率大致为 (1/2)^6 ~ 1.5%。

然后操作交替进行。我无法在那里计算出任何好的概率，但直觉上效果应该是中性的。

---

看看 min 和 max 交替一次后会发生什么可能会有所帮助。让我们为每个节点设置 6 个子节点(为简单起见)。如前所述，“最小”阶段的结果为 5 或更高的可能性大致为 (1/2)^6。对于“最大”阶段产生 5 或更高的数字，任何 child 达到 5 或更高就足够了。有 6 个 child ，所以机会大约是 1 - (1 - (1/2)^6)^6 ~ 9%。

这已经比最底部出现 5+ 数字的最初 50% 的几率低得多。然后，另一次迭代将导致 1 - (1 - (0.09)^6)^6 ~ 3e-6 5+ 数字的概率。